로봇이 격자 모양이 아닌 평면에서 한 지점에서 다른 지점으로 이동해야한다고 생각해보십시오. 숲과 같은 것이 있으면 어떻게 최단 경로를 찾을 수 있습니까? 그리드가 A * 알고리즘을 사용할 수 있다는 것을 알고 있습니다. 그러나 내가 달성하려는 또 다른 예는 인간에게 가장 짧은 경로를 찾으려고하는 지형에 대한 뛰어난 지식을 가진 좀비입니다.
간단한 몇 가지 가정을하면이 값을 좀 더 다루기 쉬운 것으로 줄일 수 있습니다. 로봇 / 좀비는 포인트입니다.
이것은 당신이 맞는지 확인하는 것과 같은 것들을 피하는 것입니다. 로봇 / 좀비가 원이라면 장애물의 모든 가장자리를 원의 반경으로 물체 바깥쪽으로 이동하여 다른 모든 물체를 '더 뭉개지게'만들 수 있습니다. 로봇 / 좀비가 직사각형 인 경우 여전히 가장자리를 밀어 낼 수 있지만 큐브 치수를 사용하여 수행 할 수 있지만 직사각형이 회전해야하는 경우 작동하지 않습니다.
단일 지점에 대한 경로를 찾으려고하면 더 간단 해집니다. '뚱뚱한'다각형 장애물의 모든 정점을 그래프의 노드로 변환하고 직접 볼 수있는 다른 모든 노드에 연결합니다 (일부 장애물을 통과하지 않음). 3D를 사용하는 경우 가장자리를 고려해야하며 문제가 좀 더 지루해집니다.
그래프가 있으면 A * / Dijkstra / 문제에 대해 작동하는 모든 작업을 수행하십시오.
정말 정확한 결과를 원한다면 코너를 돌아 다니는 것이 호 세그먼트를 따라 움직이기 때문에 로봇 / 콤비가 원이라면 코너 주위를 조심해야합니다. 게임 / 시뮬레이션을 실행하는 경우 매우 얇은 장애물과 비교적 큰 원 / 로봇 / 좀비를 제외하고는 차이가 보이지 않을 가능성이 높습니다.
성능을 위해 설정이 정적 인 경우 그래프를 미리 계산할 수 있습니다. 또한 노드 수는 장애물의 정점 수에 따라 달라 지므로 경로 찾기를 위해 낮은 품질의 개체로 실행할 가치가있을 수 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다