A* 경로 탐색 계산기

목표까지 남은 거리의 짐작값 h를 더해 꺼내는 순서를 정하는 것이 다릅니다. 다익스트라는 f = g만 보고 출발점에서 가까운 순서로 사방으로 고르게 퍼지지만, A*는 f = g + h로 목표 쪽을 먼저 봅니다. h = 0으로 두면 A*가 그대로 다익스트라가 되며, 이 계산기도 같은 코드를 h만 바꿔 두 번 돌립니다.

h가 실제 남은 거리를 절대 넘지 않는 것을 말하며, 이때만 A*가 최단 경로를 보장합니다. h를 부풀리면 탐색은 빨라지지만 «조금 돌아가지만 결국 짧은 길»을 먼저 버려 최단이 아닌 답이 나옵니다. 이 계산기에서 가중치 w를 1보다 크게 올리면 그 일이 실제로 일어나는 것을 볼 수 있습니다.

대각선 한 걸음의 실제 비용이 √2 = 1.414인데 맨해튼 거리는 2로 세어 과대평가하기 때문입니다. 실제 거리를 넘어서므로 허용 불가능해지고, 최단이 아닌 경로가 나올 수 있습니다. 8방향에서 딱 맞는 h는 옥타일 거리 (√2−1)·min(dx,dy) + max(dx,dy)이며, 대각선으로 갈 수 있는 만큼 가고 남은 만큼 직선으로 가는 거리입니다.

h에 w를 곱하면 찾은 경로의 비용이 최단의 w배를 넘지 않습니다. w = 2면 최악의 경우에도 두 배 안쪽이라는 뜻이며, 실제로는 훨씬 적게 벌어지는 대신 펼치는 칸이 크게 줄어듭니다. 실시간 게임처럼 «충분히 좋은 길을 빨리»가 필요한 곳에서 일부러 쓰는 기법입니다.

아닙니다. 휴리스틱은 장애물을 모르므로, 목표 쪽으로 곧장 가는 길이 벽에 막혀 있으면 벽 앞에서 넓게 펼칩니다. «가로막 + 문 하나» 버튼으로 만든 격자에서 이것을 볼 수 있습니다. 극단적으로는 다익스트라와 거의 같아지지만, 그렇더라도 최단 경로를 찾는 것은 변하지 않습니다.

이 계산기에서는 막았습니다. 벽 두 장이 직각으로 맞닿은 자리를 대각선으로 스쳐 지나가면 벽을 뚫은 것처럼 보이므로, 양옆 두 칸이 모두 비어 있을 때만 대각선 이동을 허용합니다. 게임에서 흔히 쓰는 규칙입니다.

달라지지 않습니다. f가 같은 칸이 여럿일 때 g가 큰 쪽을, 그것도 같으면 칸 번호가 작은 쪽을 먼저 꺼내도록 정해 두었습니다. 이 순서를 정하지 않으면 최단 경로는 같아도 펼치는 칸 수가 실행마다 흔들려, 이 계산기가 비교하려는 숫자를 믿을 수 없게 됩니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지며 만든 격자는 이 기기에만 남습니다.