개요

게임의 인공 지능에서 빠질 수 없는 주제는 길 찾기(Path-finding)다.

현재 게임에서 가장 일반적으로 널리 사용하는 길 찾기 알고리즘은 A*다.

(스타크래프트의 유닛의 길 찾기 알고리즘은 A*라고 한다.)

A*는 해당 유닛의 시작점부터 종착점까지 추정치 비용(Heuristic cost)를 계산해서 길을 찾는다.

Dijkstra 알고리즘과 다른 점은 모든 경로에 대한 계산을 피한다는 점이다.

더 멀리 돌아간다고 생각하면 그 길로 가지 않으려 한다.

(물론 그 길 밖에 없으면 거기로 가겠지만…)

만약, 여러 유닛이 시작점은 다르지만 같은 종착점을 가려고 한다면?

유닛이 각각 A* 알고리즘으로 길 찾기를 할 것이다.

Flow field는 위와 같은 상황일 때 효율적이다.

Flow field는 Dijkstra 알고리즘의 변형 버전으로 필드의 비용(Cost)을 구하고,

방향(Direction) 필드로 바꿔 길을 찾을 수 있도록 한다.

맵 전체에 종착점까지의 모든 길이 있는 것이다.