남은 거리를 짐작하면 덜 헤맨다

비용이 가장 적은 후보부터 확정하는 방식은 사방으로 고르게 퍼집니다. 목표가 어느 쪽에 있든 상관하지 않습니다. 맵 전체의 거리 지도를 만들 거라면 그게 맞지만, 알고 싶은 것이 한 지점까지의 길이라면 반대편으로 퍼진 계산은 전부 버려집니다.

사람은 그렇게 길을 찾지 않습니다. 목적지가 동쪽이면 동쪽부터 봅니다. 그 감각을 알고리즘에 넣은 것이 A 스타(A)* 입니다.

남은 거리를 더해서 꺼낸다

바꾸는 것은 꺼내는 기준 하나입니다.

다익스트라   f = g
A 스타       f = g + h

g 는 시작점에서 여기까지 실제로 든 비용이고, h 는 여기서 목표까지 얼마나 더 들 것 같은가라는 짐작입니다. 둘을 더한 값이 작은 것부터 꺼내면, 이미 싸게 온 것과 목표에 가까운 것이 같이 앞으로 옵니다.

같은 그래프, 같은 목표인데 A 스타는 네 정점만 확정하고 끝냅니다. 비용만 보는 쪽은 여덟 개를 전부 확정합니다. 답으로 나오는 경로와 비용은 둘이 같습니다. 다른 것은 가는 길이 아니라 들여다본 넓이입니다.

목표를 확정하는 순간 멈추는 것은 둘 다 같습니다. 그런데 비용만 보면 목표가 큐에서 앞으로 나오기까지 가까운 것들을 전부 확정하게 되고, 그중 상당수는 목표와 반대편입니다.

휴리스틱은 넘겨 짚으면 안 된다

h 는 짐작이라 아무 값이나 넣어도 돌아갑니다. 다만 답이 최단이라는 보장은 조건 하나에 걸려 있습니다.

h 는 실제 남은 비용보다 크면 안 됩니다. 이 조건을 허용성(admissibility)이라고 부릅니다.

과대평가하면 무슨 일이 생기는지는 한 줄로 설명됩니다. 실제로는 2면 되는데 h 가 9라고 말하면, 그 정점의 f 가 부풀어서 뒤로 밀립니다. 그 사이에 더 비싼 다른 길이 목표를 먼저 확정해 버리면, 알고리즘은 그걸 답으로 내놓고 멈춥니다. 최단이 아닌 길입니다.

반대로 과소평가는 안전합니다. h 를 0으로 두면 그냥 다익스트라가 되고, 답은 여전히 최단입니다. 탐색이 넓어질 뿐입니다. 그래서 확신이 없으면 낮춰 잡는 쪽이 맞습니다.

조건이 하나 더 있습니다. 일관성(consistency) 입니다. 이웃으로 한 칸 갈 때 h 가 그 간선 비용보다 더 많이 줄어들면 안 된다는 것입니다. 일관적이면 한 번 확정한 정점을 다시 볼 일이 없어서 구현이 단순해집니다. 아래에서 쓰는 격자용 휴리스틱들은 전부 일관적이라 이 걱정을 안 해도 됩니다.

격자에서는 무엇을 쓰나

h 는 “장애물이 하나도 없다고 치고 목표까지 가는 비용” 으로 잡으면 자연스럽게 과소평가가 됩니다. 움직일 수 있는 방향에 따라 식이 달라집니다.

단위를 맞추는 것이 실수하기 쉬운 자리입니다. 이동 비용이 칸당 10이면 h 도 칸 수가 아니라 칸 수 × 10 이어야 합니다. 칸 수를 그대로 쓰면 h 가 실제보다 열 배 작아서, 틀리지는 않지만 A 스타가 다익스트라처럼 넓게 퍼집니다.

늪처럼 비싼 칸이 섞여 있을 때는 어떨까요. h 를 가장 싼 칸 기준으로 잡으면 언제나 과소평가라 안전합니다. 평균 비용으로 잡으면 더 빠르지만 과대평가가 생겨서 최단이 깨질 수 있습니다.

h 를 얼마나 믿을 것인가

같은 코드에서 h 에 곱하는 가중치만 바꿔도 성격이 달라집니다.

모바일에서 유닛이 수십 마리씩 길을 찾는다면 w 를 1.2 정도로 두는 선택이 실제로 쓰입니다. 경로가 조금 길어지는 대신 탐색이 확 줄어듭니다. 최단이 아니어도 되는지는 게임이 정할 문제입니다.

동점이 많으면 지그재그가 나온다

격자에서는 f 가 같은 후보가 무더기로 생깁니다. 가로세로 비용이 같으면 계단처럼 도는 길과 곧게 가는 길의 f 가 똑같습니다. 그러면 알고리즘은 아무거나 고르고, 결과가 눈에 거슬리는 지그재그로 나옵니다. 탐색 범위도 쓸데없이 넓어집니다.

동점일 때 순서를 정해 주면 해결됩니다.

• h 가 작은 쪽을 먼저. 같은 f 면 목표에 더 가까운 쪽부터 봅니다. 한 줄로 끝나고 효과가 큽니다
• h 에 아주 작은 값을 곱하기. h × 1.001 처럼 미세하게 기울이면 직선 경로가 선호됩니다
• 시작점과 목표를 잇는 직선에서 멀어질수록 조금 손해 주기. 경로가 더 곧아집니다

셋 다 목적은 같습니다. 답을 바꾸지 않으면서 보기 좋은 쪽을 먼저 고르게 하는 것입니다.

게임에서 부딪히는 자리

• 목표가 여럿일 때. 가장 가까운 목표까지의 거리를 h 로 쓰면 됩니다. 여러 개 중 아무 데나 도착하면 되는 경우입니다
• 목표에 도달할 수 없을 때. 큐가 빌 때까지 맵 전체를 훑고 실패합니다. 섬처럼 끊긴 구역이 있으면 미리 덩어리를 표시해 두고 시작 전에 거르는 편이 낫습니다
• 여러 유닛이 같은 목표로 갈 때. 유닛마다 A 스타를 돌리면 같은 계산을 반복합니다. 목표가 하나면 거리 지도를 한 번 만들어 모두가 읽는 쪽이 낫습니다
• 경로가 자주 막힐 때. 전체를 다시 계산하지 말고 막힌 지점부터 다시 찾거나, 몇 프레임에 나눠 계산합니다

A 스타가 느려지는 것은 대개 알고리즘이 아니라 한 프레임에 몇 번 부르느냐 때문입니다. 호출 자체를 줄이는 방법을 먼저 봐야 합니다.

정리

A 스타는 다익스트라에 목표까지의 짐작을 더한 것입니다. 꺼내는 기준이 g 에서 g + h 로 바뀐 것이 전부입니다.

• 답은 같고 들여다보는 넓이가 줄어듭니다. 목표가 하나로 정해져 있을 때만 값을 합니다
• h 는 실제 남은 비용을 넘으면 안 됩니다. 넘겨 짚으면 더 싼 길을 뒤로 밀어내고 엉뚱한 답을 냅니다
• 격자에서는 네 방향이면 맨해튼, 여덟 방향이면 옥타일입니다. 비용 단위를 맞추는 것을 잊지 마세요
• h 에 1보다 큰 가중치를 곱하면 빨라지지만 최단이 아닐 수 있습니다. 게임이 그걸 허용하는지로 정합니다
• 동점이 많으면 경로가 지그재그로 나옵니다. h 가 작은 쪽을 먼저 보게 하면 대부분 해결됩니다