A* 속도를 높이는 지름길: 휴리스틱을 개선하는 랜드마크 기법

게임이나 지도 서비스에서 최단 경로를 찾을 때 가장 널리 쓰이는 알고리즘이 A다. 성능을 끌어올리려는 개발자 대부분은 우선순위 큐 구현이나 맵을 그래프로 표현하는 방식을 손본다. 그런데 정작 A의 탐색 방향을 결정하는 휴리스틱 함수 자체를 개선하는 접근은 상대적으로 덜 다뤄진다. 레드블롭게임즈(Red Blob Games)의 아미트 파텔이 정리한 이 자료는 바로 그 지점을 파고든다. 알고리즘 본체는 그대로 두고 휴리스틱만 바꿔서 탐색해야 할 노드 수를 크게 줄이는 방법이다.

휴리스틱은 바람과 같다

A의 휴리스틱은 목표 지점을 향해 탐색을 밀어주는 바람에 비유할 수 있다. 휴리스틱 추정값이 실제 거리에 가까울수록 탐색 방향이 정확해지고, A가 살펴봐야 하는 노드가 줄어든다. 문제는 흔히 쓰는 맨해튼·체비쇼프·유클리드 같은 거리 기반 휴리스틱이 벽의 존재를 모른다는 데 있다. 실제 최단 경로는 벽을 우회해 서쪽으로 돌아가야 하는데, 단순 거리 휴리스틱은 목표가 동쪽에 있다는 이유만으로 계속 동쪽으로 밀어붙인다. 방향이 어긋나는 만큼 A*는 헛수고를 하며 노드를 낭비한다.

이상적인 해법은 벽까지 감안해 절대 틀린 방향을 가리키지 않는 '완벽한 휴리스틱'이다. 이런 값은 실제로 계산할 수 있지만, 목표 지점이 바뀔 때마다 완전히 새로 만들어야 한다는 치명적 약점이 있다. 매번 A*를 돌릴 때마다 이를 다시 계산하는 것은 너무 느리고, 미리 모든 목표에 대해 저장해 두기엔 용량이 감당되지 않는다. 목표가 고정돼 있다면 플로우 필드 방식을 쓰면 되지만, 현실의 경로 탐색은 대개 목표가 매번 달라진다.

랜드마크와 삼각부등식

해결의 실마리는 '한 번 계산해서 여러 목표에 재사용하는' 발상이다. 우선 맵의 특정 지점 하나를 랜드마크(landmark, 논문에 따라 pivot이나 beacon으로도 불린다)로 정하고, 그 지점까지의 완벽한 거리를 미리 구해 둔다. 저자는 이를 파리의 에펠탑에 빗댄다. 친구가 '집에서 에펠탑 방향으로 걷다가 다니엘의 집에 도착하라'고 알려주는 상황이다. 목표는 랜드마크에 도달하는 것이 아니라, 랜드마크가 알려주는 방향을 따라가다 도중에 있는 실제 목표에 닿는 것이다.

이 아이디어를 수식으로 뒷받침하는 것이 삼각부등식이다. 삼각형의 두 변의 합은 나머지 한 변보다 짧을 수 없다는 원리를 방향 그래프에 적용하면, 임의의 노드 B에서 목표 X까지의 비용은 'B에서 랜드마크 L까지의 비용에서 X에서 L까지의 비용을 뺀 값' 이상이 된다. 모든 지점 간 거리를 미리 계산하는 것은 비현실적이지만, 특정 랜드마크까지의 거리만 저장해 두면 그 값으로 다른 목표까지의 거리 하한을 추정할 수 있다는 것이다. 학계에서는 이를 삼각부등식 기반 휴리스틱, 또는 이미 계산된 거리들의 차이를 이용한다는 의미에서 '차분 휴리스틱(differential heuristic)'이라 부른다.

랜드마크 배치가 관건

하나의 랜드마크는 목표가 그 랜드마크 '너머'에 있을 때만 유용하다. 따라서 모든 (출발, 목표) 조합을 개선하려면 여러 개의 랜드마크가 필요하다. 각 랜드마크가 주는 하한값 중 가장 큰 값을 max()로 취하면 된다. 실제 데모에서 하나의 랜드마크는 주요 복도는 잘 커버하지만 옆방까지는 닿지 못하며, 랜드마크를 늘려야 맵 전체가 개선 영역으로 채워진다. 다만 랜드마크가 최적 위치가 아니어도 일반 휴리스틱보다 나빠지지는 않으므로, 배치 실패의 위험 부담은 크지 않다.

랜드마크 개수와 위치 선정은 프로젝트마다 다르다. 맵을 미리 알고 있다면 맵 에디터에서 직접 배치하면 되고, 절차적으로 생성되는 맵이라면 무작위 경로들을 반복해 만들면서 많은 경로에 도움이 되는 지점을 골라내는 방식을 쓸 수 있다. 이 방법은 대체로 맵의 바깥쪽 모서리, 특히 좌상단 같은 외곽을 선택하는 경향을 보였는데, 랜드마크가 맵 가장자리에 있어야 한다는 직관과 맞아떨어진다. 두 번째 랜드마크는 첫 번째와 떨어진 곳, 세 번째는 앞의 둘과 모두 떨어진 곳처럼 각 랜드마크가 새로 더해주는 값을 기준으로 순차적으로 고른다.

구현과 실무적 의미

구현 부담이 작다는 점이 이 기법의 매력이다. A* 자체는 손대지 않는다. 먼저 랜드마크를 정한 뒤 cost[노드][랜드마크] 형태의 2차원 배열을 확보하고, 각 랜드마크마다 다익스트라를 한 번씩 돌려 값을 채운다. 이때 랜드마크는 출발점이 아니라 도착점이므로 방향 그래프에서는 간선을 모두 뒤집어야 하고, 무방향 그래프라면 그대로 쓸 수 있다. 가중치가 모두 1이라면 다익스트라 대신 너비 우선 탐색(BFS)으로 충분하다. 이 전처리는 백그라운드 스레드에서 돌려도 된다. 이후 휴리스틱 함수만 기존 거리 계산에 랜드마크 기반 하한을 반영하도록 살짝 고치면 끝난다.

저자는 이 기법을 드래곤 에이지, 미로, 그리고 코그마인드 같은 실제 게임 맵(무방향 그래프)에 적용해 효과를 확인했다. 거리 휴리스틱이 특히 취약한 미로에서는 단 네 개의 랜드마크만으로도 탐색 영역이 크게 줄었고, 넓은 개활지가 많은 맵에서도 잘 작동했다. 랜드마크는 목표보다 출발점에 가깝고 목표 '너머'에 있을 때 더 큰 효과를 냈다. 무작위 경로 분석으로 위치를 잘 고르면 더 적은 수의 랜드마크로 비슷한 성과를 얻을 수 있었다.

다만 한계도 분명하다. 랜드마크 데이터는 노드 하나당 숫자 하나씩을 저장해야 하므로 맵이 커지면 메모리 부담이 따르는데, 인접한 격자들의 값이 비슷하다는 점을 이용해 이미지 압축처럼 데이터를 압축하는 여지가 있다. 또 이 페이지가 다루는 방식은 랜드마크를 경로의 끝 너머에 두는 배치이며, 경로 중간중간에 랜드마크를 놓는 다른 계열의 알고리즘도 존재한다. 무엇보다 저자 스스로 2007년에 이 기법을 처음 접한 뒤 여러 해에 걸쳐 이해를 다졌지만 아직 실제 프로젝트에 써 본 적은 없다고 밝힌 만큼, 도입을 검토하는 실무자라면 자신의 맵 특성에 맞는 랜드마크 개수와 배치를 직접 실험해 보는 과정이 필요하다.