칸이 아니라 구역 사이를 먼저 잇는다
맵이 커지면 한 칸씩 훑는 길찾기는 넓이만큼 헤맵니다. 맵을 구역으로 나누고 구역 사이만 미리 이어 두는 계층형 길찾기(HPA*, Hierarchical Pathfinding A*)의 구조와, 전처리·경로 품질·구역 크기의 거래.
건너뛰어도 되는 칸은 건너뛴다
균일한 격자에서는 같은 비용의 길이 수십 개라서 탐색이 그만큼 넓어집니다. 그중 하나만 보게 만드는 점프 포인트 서치(JPS, Jump Point Search)의 규칙과, 이 방법이 통하지 않는 자리.
음수가 있거나 모든 쌍이 필요할 때
비용이 가장 적은 후보부터 확정하는 방식이 안 통하는 두 경우입니다. 음수 간선을 다루는 벨만-포드(Bellman-Ford)와 모든 쌍의 거리를 한 번에 구하는 플로이드-워셜(Floyd-Warshall), 그리고 셋 중 무엇을 고를지.
남은 거리를 짐작하면 덜 헤맨다
목표가 하나일 때 탐색을 그쪽으로 기울이는 A 스타(A*) 알고리즘입니다. 휴리스틱이 지켜야 하는 조건, 과대평가하면 무엇이 깨지는지, 격자에서 무엇을 쓰고 동점은 어떻게 처리하는지.
꺼내는 순서를 큐가 아니라 비용이 정한다
칸마다 이동 비용이 다른 맵에서 최단 경로를 찾는 다익스트라 알고리즘(Dijkstra's algorithm)입니다. 왜 한 번 확정한 것을 다시 안 봐도 되는지, 음수 간선에서 왜 무너지는지, 게임에서 가중치를 어디서 얻는지.