2 차원 격자 기반 길 찾기 : 위치에 도달 할 수 있는지를 찾는 가장 저렴한 방법/알고리즘

Question

내 기본 길 찾기는 aStar 알고리즘을 구현하여 수행합니다. 사용 가능한 경로가있는 한 성능이 우수합니다.

그러나 없으면 사용 가능한 모든 노드가 경로가 없다는 결론에 도달 할 때까지 구문 분석됩니다.

필자가 생각해 낼 수있는 최악의 시나리오는 주변을 둘러싼 대상 위치에 비교적 가까운 장애물이 거의 없다는 것입니다.

전체 성능이 증가 할 수 있습니다 내가 지금까지 함께 온 몇 가지 아이디어 :

• 발견을하고이 경우 대상이 도달 할 수 있는지 알아에서만 실행됩니다 algorithmn 싼 길 찾기를 실행 aStar를 실행하여 실제 경로를 얻으십시오.

• 지정된 반경 내 targetnode 주변의 모든 비가역 노드를 모아서 모두 링크되어 있는지 확인하십시오. 그럴 경우 목표는 도달 할 수 없으며 도달 할 수 없습니다. 노드를 수집하는 aStars 방식은 본질적으로이를 수행하기 때문에 시작 노드에 해당하는 작업을 수행 할 필요는 없습니다.

그래서 좀 bulletpoints을 가지고 거기에 사람이있는 경우/아이디어를 내 목록에 추가하거나, 내가 이용할 수있는 저렴한 길 찾기 알고리즘의 방향으로 날 지점 수 있습니다 여기에 대한 부탁 해요 경로가 있는지 확인하십시오

Answer 1

첫 번째 아이디어는 세련되어야합니다!

당신의 휴리스틱 때문에 A *는 대상을 중심으로 대부분 시간을 보내고 따라서 "방문한"벽을 만듭니다.

그래서 내가 방문한 사각형의 "벽"을 계속 확인할 수 있다고 생각합니다. 대상을 포함하는 닫힌 연속 경로를 찾을 수는 있지만 소스가 아니라면 더 이상 검색 할 수 없습니다.

둘째 아이디어, 완료되지, 그러나 아마, "손실"시간을 줄일 수
사용 양방향 A *, 소스를 대상으로 실행하지만, 동시에 대상에 소스에 방법 찾는 것입니다.

https://qiao.github.io/PathFinding.js/visual/에서 어떻게 동작하는지 생각해보십시오.