Game Algorithm Expert | A* 알고리즘

길찾기 알고리즘 중 하나인 A* 알고리즘에 대해 알아보자. 단순히 2D 타일맵에만 적용할 수 있다고 생각했는데 원리를 알고보니 가중치로 연결된 그래프에 모두 적용할 수 있는 방법이었다. 복잡한 공간도 다각형으로 분할한다면 A* 알고리즘을 적용시켜서 길을 찾을 수 있다.

A* 알고리즘은 닫힌 목록과 열린 목록이 있고, 이 두 목록을 갱신하면서 길을 찾아간다. 현재 위치에서 갈 수 있는 위치에 대해 G, F, Parent를계산해서 열린 목록에 넣고, 열린 목록에서 최소 F값을 가지고있는 위치를 닫힌 목록에 넣은 후 반복한다.

 

G : 해당 위치로 이동하기 위해 필요한 비용 F : G + 해당 위치에서 목표지점까지의 예상거리 Parent : 해당 위치로 오기 직전 위치

 

닫힌 목록과 열린 목록을 업데이트하면서 가장 빠른길을 찾는다.

 

간단한 2D 길찾기 예제를 통해서 원리를 알아보자. 알고리즘을 적용하기 위해서는 이동방식, 맵의 형태 등에 대한 규칙을 정해두고 시작해야한다. 큰 원리는 똑같지만 이런 세부적인 규칙에 따라 실제 동작하는 코드가 달라지게되고 찾는 길도 달라지게 된다. 예를들어 타일맵에서 대각선으로 이동할 수 있다면 대각선 이동도 염두하고 길을 찾을것이고 결국 대각선 이동이 포함된 경로를 찾을 것이다.

예제에서는 아래 규칙을 사용해서 과정을 간소화했다.

 

• 맵은 정사각형 타일로 구성되어있고, 각 타일을 이동하는데 드는 비용은 1이다.

• XY축과 평행한 방향 즉, 상, 하, 좌, 우 4방향으로만 움직일 수 있다.

• 예상거리는 맨하탄 거리로 계산한다. (가로+세로 거리)

 

파란색 타일에서 초록색 타일로 갈 수 있는 경로를 찾는다. 검은 타일은 벽이기 떄문에 움직일 수 없다.

 

왼쪽 아래가 영점인 좌표계를 사용하며 파란 타일(1,1)에서 초록색 타일(5,3)로 이동하는 경로를 찾는다.

4방향으로 이동할 수 있기 때문에 4방향에 대한 G,H를 계산해서 열린 목록에 넣는다. 열린 목록에서 F값이 가장 작은 위치를 닫힌 목록에 넣고 반복한다.

 

위쪽 타일부터 시계방향으로 검사하며 열린목록을 만들어간다.

 

(1,2)타일이 가장 F값이 작기 때문에 이제 이 위치에서 4방향에 대해 검사해야하는데 아래 위치는 닫힌목록에 있는 위치이므로 검사하지 않는다.

 

(2,1)의 F도 6이지만 리스트에 먼저 추가된 경로부터 닫힌경로에 추가한다.

 

새로운 열린 목록에서 (2,1)의 F가 가장 작기 때문에 닫힌목록에 추가하고 검사하면 위쪽 위치는 열린목록에 이미 있는것을 알 수 있다. 이제 새로운 G와 비교하는데 새로운 G값과 같기 때문에 갱신하지 않는다.

 

(1,2)에서 계산했을 때랑 지금(2,1) 계산했을 때랑 F가 같기때문에 업데이트하지 않는다.

 

G 갱신
이 예제에서는 이렇게 G값을 업데이트하는 일이 없다. 이건 타일맵보다는 가중치그래프로 그렸을 때 더 쉽게 설명할 수 있기 때문에 아래에 가중치그래프를 예제로 알아보자.

 

반복하면서 닫힌목록에 추가하고 새로운 열린목록을 계산한다.

 

이렇게 계속 반복하다보면 어느새 열린목록에 목적지가 들어오게되는데, 아직 최단경로인지는 확실하지 않기 때문에 (경우에 따라 G가 업데이트될 수 있다.) 탐색을 멈추지말고 같은 방법으로 반복한다. 

 

반복하다보면 드디어 최종 목적지가 열린목록에 들어오게된다.

 

반복 중 닫힌 목록에 추가되는 경로가 목적지라면 탐색을 종료할 수 있는데, 만약 열린목록이 비어버린다면 해당 목적지까지의 경로가 없다는 뜻이므로 이것 또한 탐색 종료 조건이 될 수 있다.

 

닫힌 목록에 목적지가 들어왔을 때 그 경로부터 Parent를 따라가면 최단경로가 나온다.

 

G갱신

하늘색 점선 한칸은 H계산을 위한 거리로 한칸당 1로 계산한다.

이렇게 생긴 그래프가 있다고하자. A 노드에서 F번 노드로 갈 때 결과적으로 A-C-D-E-F 순서로 이동하는게 가장 적은 비용으로 이동할 수 있는데 G값 갱신을 통해 이 경로를 찾을 수 있다.

먼저 B, C 중 B의 F가 더 작기 때문에 B를 닫힌 목록에 넣고 진행한다.

 

현재 D의 Parent는 B이고 G도 5인것을 볼 수 있다.

 

그리고 그 다음 F값이 작은 C를 닫힌목록에 넣고 진행해보면 새롭게 계산한 D의 수치들이 더 작은것을 알 수 있다.

 

C를 거쳐서 D로 가는것이 더 저렴하기 때문에 D의 Parent를 C로 갱신한다.

같은 방식으로 E또한 Parent가 D로 업데이트되어 결국 가장 짧은 경로인 A-C-D-E-F를 찾을 수 있다.