현재 길 찾기 연구를하고 있으며 시뮬레이션은 다음과 같습니다. 시작점과 끝 점이 표시된 3D 장면이 있으며 길 찾기를 돕기 위해 탐색 메시, 웨이 포인트 및 다각형을 만들 수 있습니다.
나는 A * 알고리즘과 그 변형 중 일부를 시도했으며 완벽하게 작동합니다. 그러나 이제는 ‘동적’경로 찾기에 더 관심이 있습니다. 예를 들어 A 지점에서 B 지점으로 경로를 찾는 동안 새로운 장애물이 갑자기 나타나면 알고리즘에서 즉시 경로를 다시 계획하고 검색을 다시 시작할 수 없도록하고 싶습니다.
나는 D * 알고리즘에 대해 약간의 독서를했고 이것이 내가 필요한 것에 적합하거나 이것이 과잉 인 것처럼 보일지 궁금해했다.
그래서 내 질문은 기본적으로 : 실시간 동적 경로 찾기에 가장 적합한 알고리즘은 무엇입니까? 또는 대신 어떤 기술 조합을 사용할 수 있습니까?
답변
D *는 매우 관련이 있습니다. 구현을 권장하지 않습니다. 똑똑한 / 경험이 많은 사람들이 자금을 지원하고 개발 한 프로젝트 일지라도 D *는 올바른 고통을주기 때문에 D * 라이트가 사용됩니다.
Left 4 Dead의 길 찾기에 대한 토론이 포함 된이 프레젠테이션에 관심이있을 수 있습니다.
http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf
한 가지 방법은 대략적인 레벨 A * 검색을 사용하여 에이전트의 일반 경로를 얻은 다음 에이전트의 로컬 환경에 대한 세부 레벨 A * 검색을 수행하는 것입니다. 이렇게하면 지형이 변경되면 코스 세부 사항 A * 검색을 빠르게 다시 계산 한 다음 환경의 작은 세그먼트에 대한 세부 사항 A * 검색을 빠르게 다시 계산할 수 있습니다. 이것은 완벽하지 않습니다. 장애물이 여러 코스 상세 그래프 노드를 차단할 수없는 한 대부분의 게임에 적합합니다. 에이전트가 100 개 미만인 경우이 방법을 권장합니다.
수백 또는 수천 명의 에이전트를 지원하려는 경우 연속 군중과 같은 것을 구현할 수 있습니다. 이 연구를 참조하십시오 :
http://grail.cs.washington.edu/projects/crowd-flows/
동적 환경에서 수천 명의 행위자를 지원할 수있는 순수한 CPU 기반 방법에 대해 설명합니다.
수만 또는 수십만 개의 에이전트를 지원하려는 경우 GPU 지원을 통해 연속 군중과 같은 것을 구현할 수 있습니다. 관련 연구는 여기를 참조하십시오 :
https://a248.e.akamai.net/f/674/9206/0/www2.ati.com/misc/siggraph_asia_08/GPUCrowdSimulation_SLIDES.pdf
여기에 행동에 연속 군중을 보여주는 비디오입니다 :
http://www.youtube.com/watch?v=lGOvYyJ6r1c
(. 자동차와 도시 주위에 산책하는 사람의 수백에 영향을 미치는 정지 신호와 같은 큰 동적 장애물을 볼 수 4시 10분으로 건너 뛰기)
답변
간단한 조향 동작을 살펴 보셨습니까?
http://www.red3d.com/cwr/steer/
로컬 장애물을 피하기 위해 A * 경로에서 방향을 바꾸고 나면 경로로 돌아갈 수 있습니다.
여러 동작을 결합하는 것도 매우 쉽습니다.
답변
귀하의 게시물이 스택 교환의 “게임 개발”부분에 있으므로 대부분의 게임 프로그래머가 귀하에게 대답 할 내용은 다음과 같습니다. 실시간 동적 경로 찾기가 아니라 실시간 동적 경로 *에 대한 것입니다 !
내비게이션 그래프의 가장자리가 완전히 방해되는 일부 가장자리의 경우 패스 파인더가 다른 경로를 다시 계산해야하지만 대부분의 경우 장애물을 중심으로 개체를 조정하고 위치 예측을 수행하고 올바른 방향으로 피할 수 있습니다. 대부분의 게임에서 시간이 지남에 따라 동적 에이전트의 위치를 예측하기에는 너무 무겁습니다. 특히 플레이어의 행동이나 에이전트 결정을 정확하게 예측할 수 없기 때문입니다.
따라서 내 조언은 Steering Behaviors (http://red3d.com/cwr/steer/)를 구현하여 시작하고 경로가 불가능한 경우를 처리 한 다음 그 위에 레이어를 추가하여 가장자리가 아닌 경우를 처리하는 것입니다. 이전의 두 가지 솔루션으로 처리되지 않습니다.
도움이 되었기를 바랍니다