도달 할 수없는 목적지에 가장 가까운 위치를 찾기 위해 AStar 조정 대상에 도달 할 수없는 경우 계산 된

Java로 AStar를 구현했으며 선택한 대상에 도달 할 수있는 장애물이있는 지역에서는 정상적으로 작동합니다.

그러나 대상에 도달 할 수없는 경우 계산 된 “경로”는 (가까운 위치에) 가장 가까운 위치가 아니라 임의의 경로입니다.

도달 할 수없는 목적지까지 가장 가까운 곳으로가는 길을 찾기 위해 AStar를 조정할 수있는 방법이 있습니까?



답변

가장 낮은 노드 EstimatedDistanceToEnd(즉, 가장 낮은 h(x)노드)를 추적하고, 끝 노드에 역 추적 할 수없는 경우 해당 노드에서 역 추적합니다.


답변

이것은 실제로 A * 질문이 아닙니다. A *는 지점 A에서 지점 B까지의 경로를 찾는 것입니다. 확장 할 수는 있지만 결과가 쉽게 지저분 해지고 예측할 수 없습니다. 대신 필요한 것은 가장 가까운 도달 가능한 목적지를 선택하는 알고리즘입니다.

이를 수행하는 한 가지 방법이 있습니다. A *가 유효한 경로 (경로 일치 입력 노드의 시작 / 종료 노드)를 리턴하면 경로를 리턴하십시오. 그렇지 않으면…

  • 초기 노드에서 검색 시작
  • 연결된 모든 노드를 순회합니다 (무한한 재귀를 피하기 위해 방문한 노드에 플래그를 지정해야 함).
  • 가장 가까운 노드를 찾기 위해 목적지까지의 거리를 비교