A *의 알고리즘/의사 코드를 검색 한 후 코드화했습니다. 나는 h (n)에 맨해튼 거리를 사용했다. (F (N) = g (N) + N H()) 그리고이 결과,A 맨하탄 거리
길을 차단하는 벽이 없을 때 항상 발생하지만 때 내가 많이 넣어 벽이 가장 짧아 보인다. 이것이 가장 짧은 길입니까? 내 말은 왜 이것이 아래에있는 것과 같지 않은가?
이 또한 A * Manhattan이며 같은 크기 (19x19)입니다. 이것은 http://qiao.github.com/PathFinding.js/visual/
두 경로의 맨하탄 거리가 같습니다. 따라서 어느 경로가 선택되는지는 구현에 따라 다릅니다. 이 특정 부분이 선택된 이유를 알기 위해이 특정 A * 구현 코드를 살펴 봐야합니다.
힌트 : Von Neumann neighborhood만을 사용하는 소스에서 대상 셀까지의 모든 경로 (즉, 대각선으로 걷지 않음)와 "잘못된"방향으로 한 발 걸리지 않습니다 (즉, 예제에서 위로 걷거나 왼쪽으로 걷지 마십시오).) 같은 맨해튼 거리를 가지고 있습니다. 그래서 뉴욕에 계신다면, 맨해튼의 특정 장소에 도달하기 위해 어떤 교차로가 걸릴지는 중요하지 않습니다.
맨하탄 거리로 첫 번째 것은 가장 짧은 경로입니다. 단순히 수평 및 수직 단계 수를 계산합니다. 당신이 유클리드 거리에서 가장 짧은 경로와 비슷한 것을 원한다면 알고리즘을 변경하여 한 점에서 수평 또는 수직으로 움직일 선택이있을 때 수평 거리가 수직보다 큰 경우 수평을 선택합니다 하나는 그 반대입니다.
아, 그래. 감사! :) – Zik
완료 될 때까지 시작 지점에서 모든 지점 (맨해튼/A * 결과)까지 시선 (피타고라스/유클리드)을 시준해야합니다. 특정 지점에 선을 캐스팅 한 것이 장애물에 의해 차단/숨겨져 있다면 이전에 캐스팅 된 지점을 사용하고 차단 된 지점에서 다른 선을 캐스팅 한 다음 완료 될 때까지 앞으로 이동합니다. 차단 점은 세그먼트/선의 시작점의 시선으로 숨기는 경우입니다. 그래서 그건 같은 :
첫 번째 라인 : 시작 ---------> S + N (전 차단 점)
둘째/중동 라인/S : 차단 된 포인트 ------ ----> S + N (다른 차단 된 지점 이전)은 목표에 대한 시선을 설정할 때까지 다시 반복합니다 (새 선/세그먼트).
마지막 라인 : 차단 된 포인트 -------------> 목표
연결 모든 라인 당신은 훨씬 더 짧은 최단 경로를 가지고있다. 다시 실행할 수는 있지만 반대 방향으로 다른 정확도를 추가하면 시작할 때까지 목표 지점에서 시선이 시작됩니다.
음, 같은 거리, 33 큐브 ... 내가 잘못 계산하지 않으면. –
대각선으로 갈 수 없으므로 첫 번째 예제보다 짧아지지는 않을 것입니다. 두 번째 방법과 같이 거리가 같고 짧아 보이지만 길지는 않은 방법을 많이 얻을 수 있습니다. 당신은 항상 오른쪽으로 16 블록을, 아래쪽으로는 16 블록을 넘겨 주어야합니다. – Nobody
아, 그래서 다른 최단 경로가 있습니다. – Zik