그리드가 아닌 맵을 사용할 때 길 찾기에서 문제가되는 영역 (swamps, dead-ends)을 찾고 회피하기위한 기존 알고리즘이 있습니까? 이러한 영역을 피하거나 jump point recursion 등으로 이러한 영역을 의사가 피하는 그리드에는 충분히 사용할 수 있지만 쿼트 트리, 탐색 메쉬 또는 기타 비 균일 맵에 유용한 것을 아직 찾지 못했습니다.그리드가 아닌 맵에서 늪/데드 엔드 프 루닝
불감 대 검출 및 늪은 그리드와 관련이 없습니다. 그것들은 그리드 맵에서 평가됩니다.
이런 일은 아마도 존재할 것입니다. 수백 개의 경로 찾기 및 운동 계획서가 매년 발행되지만, 더 큰 질문을 던져야 할 필요가 있다고 생각합니다. 왜이 일을하고 싶습니까?
탐색 메시 또는 스파 스 그리드 표현으로가는 생각은 그래프의 노드 수를 줄임으로써 솔루션을 찾는 데 필요한 시간을 줄이는 것입니다. 검색 속도가 너무 느리다면 그래프의 노드와 가장자리 수를 줄이기 만하면됩니다. 심지어 시작하기 전에 수동으로 오프라인 검색에서 막 다른 부분을 제거하면 검색 할 때마다 오버 헤드가 줄어 듭니다.
당신이 당신의 그래프를 정리 한 후에도, 검색 을 느리게 여전히이며, 만약 당신은 당신이 최적의 비용이 할 때까지 인플레이션 요인을 감소 replan Weighted A*를 사용하는 것이 좋습니다 문제를 검색 할 대략적인 솔루션을 견딜 수 있습니다.
계획 알고리즘은 타협점이 있지만, 무엇을 선택하든 장단점에 대해 이해하고 있는지 확인하십시오.
마지막 제안 사항은 사용중인 플래너에서 A *와 같은 알고리즘을 올바르게 구현했는지 확인하십시오. 특히 우선 순위 대기열을 올바르게 구현했는지 확인하십시오. 특히 감소 키이 O (로그 n) 또는 better.
저는 작업중인 게임에 쿼드 트리를 사용하고 있습니다. 나는 그들을 길 찾기와 충돌 테스트에 사용한다. 막 다른 골목과 늪지를 피하기위한 알고리즘을 찾고 싶습니다. 온라인에서 플레이 할 때 만들어지는 맵에서 성능을 향상시킬 수 있기 때문입니다. 지도가 무작위로 생성되므로 수동으로 길 찾기를 최적화 할 수는 없습니다. 그러나 내가 할 수있는 것은 맵 생성을 최적으로 만든 다음 실행 중에 발견되는 문제 영역을 피함으로써 길 찾기를 빠르게하는 것입니다. – bendicott
다음 기사도 관심 대상이 될 수 있습니다. [Thomas Young, 가시성 최적화, Game Programming Gems II, 2001] 점프 포인트와 비슷한 가시성 그래프의 가지 치기 기술에 대해 자세히 설명합니다. 그러나 Nav Meshes에 적용 할 수 있다면 지금은 분명하지 않습니다. – Daniel