[C++] A* 알고리즘의 구현

2002년에 발간된 AI Game Programming Wisdom이란 책은 한 번쯤 꼭 읽어 봐야 하는 책이다.  십수 년이 지난 책이지만 지금 이 순간에도 개발에 도움이 되는 이야기를 찾을 수 있다.  

게임 AI에서 길찾기란 빼놓을 수 없는 부분이다.  A*(이하 A star) 알고리즘의 책 내용을 기반으로 구현을 해보았다.  개인적으로 책에 나와있는 코드 스닛핏은 아무리봐도 완전히 이해하기가 어려웠다.    

참고로, 유튜브나 웹에서 A star 알고리즘에 대한 정보를 많이 찾을 수 있다.  개인적으로는 아래 유튜브 영상이 차근차근 잘 설명을 잘 해주어 이해하는 데 큰 도움이 되었다.

A star 알고리즘의 pseudo 코드는 다음과 같다. 

1. P = 시작점
2. P에 f, g, h 할당
3. Open 리스트에 P 넣기
4. B = Open 리스트에서 가장 낮은 f 값을 가진 노드
    a. B가 목표점이면, 경로 완성
    b. Open 리스트가 비었으면, 목표점까지 경로가 존재하지 않음
5. C = B에 연결된 노드
    a. C에 f, g, h 값 할당
    b. Open/Close 리스트에서 C가 있는지 체크
       1. 있으면, 더 낮은 f 값으로 경로 업데이트
       2. 없으면, C를 Open 리스트에 넣기
    c. 5번으로 돌아가서 B에 연결된 모든 노드를 대상으로 진행
6. 4번으로 돌아감

g 값은 출발점부터 현재 노드 위치까지 거리이고, h는 현재 노드 위치부터 목표점 까지의 heuristic한 거리이다. 즉 일관성있는 거리 측정 기준만 있으면 h는 구현마다 다를 수 있다. f는 g+h값이다.

이를 바탕으로 구현해 보았다. 맵은 2d array에 1과 0으로 구성하고, 1은 다닐 수 있는 길, 0은 가로 막힌 길로 표시하였다.  그리고 S는 출발점, G는 목표점이다.

char map[7][5] = {
       {'G', '0', '1', '1', '1' },
       {'1', '0', '1', '0', '1' },
       {'1', '1', '1', '0', '1' },
       {'1', '1', '0', 'S', '1' },
       {'1', '1', '1', '1', '1' },
       {'1', '1', '0', '1', '1' },
       {'1', '1', '1', '1', '1' }
};

h는  Manhattan distance를 이용하여 과  사이이면  형식으로 계산하였다. 

class ASNode {
public:
       ASNode *conn;
       int row, col; //index
       int g, h, f;
       char nodeName;
}

노드는 ASNode 클래스로 정의하였다.  conn은 실제 패스에 연결되는 노드이고, row, col는 해당 노드의 맵 인덱스이다.  그리고 경로를 찾으며 업데이트 될 g, h, f 값이 있고, nodeName는 유니크한 노드 이름이다.

Pseudo 코드에 충실하려고 했으나 역시 그대로 구현하기는 정말 어려운 것 같다.

중요한 포인트는 Open리스트에서 f의 최소값을 꺼내와서 모든 children (여기서는 4방향)을 찾아 g, h, f를 업데이트후 Close리스트에 넣는 과정이다.  이 과정은 FindPath()와 GetChildNodes()에서 찾아 볼 수 있다.

실행을 해보면 아래와 같이 프린트된다.

첫번째 맵은 찾아야 될 맵이고, 두번째 맵은 최단 거리를 별표(*)로 표시해 준 것이다. Optimal Path는 출발점부터 목표점까지의 맵 인덱스를 보여준다. 

풀 소스는 아래와 같다.  몇번의 테스트 정도만 했기 때문에, 좀 더 다양한 상황이 발생한다면 오류가 있을 수도 있겠다.  최대한 알고리즘을 따르려고 노력을 했긴 했는데, 코드의 깨끗함은 점점 멀어져만 갔다.  하지만 A star 알고리즘이 어떻게 동작하는 지를 이해하는 데는 큰 도움이 되었다. 

---