A*(Astar) 길찾기 알고리즘

들어가며

로그라이크의 근본은 누가 뭐래도 작은 타일들로 이루어진 복잡한 미로 속에서 몬스터와 싸워나가며 결국엔 던전을 클리어하고 보물을 얻는것이라 생각한다. 

그런데 던전에서 캐릭터와 몬스터들이 이동하는 것을 보니 한 가지 궁금한것이 생긴다. 복잡한 미로 속에서 캐릭터는 어떻게 유저가 이동하라는 곳으로 자연스럽게 이동하는 것일까? 몬스터는 어떻게 장애물들을 피해 플레이어를 공격해 올 수 있는 것일까?
이번 포스트 이런 물음에 답을 주기 위해 게임을 만드는데 필수 요소 중의 하나인 길 찾기(path finding) 알고리즘에 대해 살펴 보도록 하겠다.

다익스트라 vs A*

알고리즘을 조금이라도 공부해본 사람이라면 길 찾기 알고리즘이라고 하면 가장 먼저 다익스트라 알고리즘을 떠올릴 것이다. 다익스트라 알고리즘은 '한 노드에서 연결된 모든 노드로 가는 각각의 최단 경로를 구하는 알고리즘'이다. 모든 경로를 비교하여 가장 최적의 경로를 찾아 낼 수 있긴 하지만 게임에서 '탐색'해야 하는 던전의 경우, 수 많은 작은 타일들로 집합인데다 각 타일들 간의 이동 비용마저 비슷해 경로를 계산하기 위해서는 거의 모든 타일들을 검사해야만 한다.
게임에서는 요구하는 반응성을 기대하기에는 다익스트라는 너무 무겁다. 그래서 이런 문제를 해결하기 위해 다익스트라 알고리즘에 휴리스틱 가중치 개념을 추가하여 탐색해야 하는 노드의 갯수를 현저히 줄인 것이 오늘 살펴 볼 A* 길찾기 알고리즘이다.

※ 휴리스틱 : 사전적 의미로 '경험적인', '스스로 발견하게 하는' 정도로 해석 될 수 있지만, 필드 용어로 대충, 적당히, 이쯤?? 정도로 생각하면 된다.

두 알고리즘의 차이를 시각화 한 아래 이미지를 살펴 보자.

다익스트라 알고리즘(왼쪽) vs A* 알고리즘(오른쪽) 출처 : Wikipedia

왼쪽의 다익스트라는 검색의 범위가 점점 넒어지며 결국 거의 전체 노드들을 검사하는 반면에 오른쪽의 A*는 목표가 있는 방향의 노드들을 우선으로 검사하기 때문에 같은 목표 지점으로 향하는 경로를 찾더라도 훨씬 적은 수의 노드들을 검사하는 것을 볼 수 있다.
A* 알고리즘은 다익스트라 처럼 전체 노드에 대한 각각의 최단 경로를 구하는 것이 아닌, '출발 노드'와 '목표 노드'를 미리 지정하고, 두 노드 사이에서의 최단 경로를 구하는데 특화 되어 있다. 그리고 도착점 까지 탐색을 하는데 있어 '휴리스틱 예상 비용'이라는 개념을 도입하여 가장 최소 경로로 '추정'되는 경로로 탐색하므로써 다익스트라 보다 검사해야하는 노드 개수를 훨씬 줄일 수 있는 것이다.
이로 인해 가끔은 가장 최적의 경로가 아닌 결과를 도출할 때도 있지만 게임 캐릭터들이 이동하는 것을 표현하기에 전혀 부족함이 없다. 아니 오히려 자연스럽기도 하므로 오히려 좋다.
다음 섹션에서는 이런 A* 알고리즘이 어떻게 동작하며 구현은 어떻게 하는지 자세히 살펴 보도록 하자.

A* 개념

A* 알고리즘은 다익스트라 알고리즘은 확장한 것으로, 현재 상태가 되기 까지의 비용을 g(n), 현재 상태에서 목표 상태가 되기 위해 예상되는 비용을 계산하는 휴리스틱 함수를 h(n) 라고 할 때, 둘을 더한 f(n)이 최소가 되는 지점을 우선적으로 탐색하는 방법이다.

f(n) = g(n) + h(n)

갑자기 수학 공식 같은게 나와서 당황스럽겠지만 어렵게 생각할 필요 없다. 별것 아닌 내용을 수식으로 적었을 뿐이다. 위 수식을 좀 더 이해하기 쉬운 글로 풀어 보도록 하자.

• g(n) : 현재 상태가 되기 위한 비용. 즉, '출발 노드'에서 '현재 노드'까지 도달하기 위한 이동 비용을 말한다.
• h(n) : 목표 상태가 되기 위한 비용. 즉, '현재 노드'에서 '목표 노드'까지 도달하기 위한 예측 비용. 이를 휴리스틱 값이라고하며거리 이 값에 따라 A* 알고리즘의 성능이 극명하게 갈린다. 보다 자세한 설명은 뒤에 추가 하도록 하겠다.
• f(n) : 위 두 비용의 합.

현재 노드의 인접 노드들 중 f(n)이 가장 작은 노드들을 우선 탐색하여 목표 노드 까지 도착 할 때 까지 반복한다.

A* 알고리즘

A*는 알고리즘은 아래와 같다.

1. 출발 노드와 목표 노드를 지정한다
2. 출발 노드를 열린 목록에 저장한다.
   ※ 열린 목록 : 최단 경로 후보 노드들을 저장한 목록
3. 열린 목록에서 f(n)이 가장 작은 노드를 선택하여 현재 노드로 지정한다.
4. 현재 노드의 인접 노드들을 탐색하여 열린 목록에 저장한다. 이 때,  열린 목록에 저장 되는 노드들은 현재 노드를 부모로 가지게 된다.
   아래의 경우는 열린 목록에 저장하지 않는다 :
   • 인접 노드가 블록 노드라면 열린 목록에 저장하지 않는다.
   • 인접 노드가 닫힌 목록에 존재하고 있다면 열린 목록에 저장하지 않는다.
   • 인접 노드가 이미 열린 목록에  존재한다면 현재 노드와 경로 비용 g(n)을 비교하여, 인접 노드 비용이 작은 경우 현재 노드의 부모를 인접 노드로 변경 한다. 열린 목록에 저장하지 않는다.
5. 검사가 끝난 현재 노드는 닫힌 목록에 저장한다.
   ※ 닫힌 목록 : 이미 검사가 끝난 처리 완료된 노드들 저장 목록
6. 목표 노드에 도달하거나, 열린 목록이 빌 때 까지 3번 부터 다시 시작한다.

개략적인 설명이 끝났으니 보다 심도 깊은 이해를 위해 아래 5x5 사이즈의 작은 던전 맵의 S지점 부터 E지점까지 어떻게 경로를 찾아 갈 수 있는지 앞서 배운 A* 알고리즘을 시뮬레이션 해보도록 하자.
아래 맵은 상하좌우 네 방향으로만 이동할 수 있으며 S는 출발점(start), E는 도착점(end), B는 장애물(block)를 의미한다.

먼저 시작점 S를 열린 목록에 저장한다. 이 때 S의 비용을 계산하면 다음과 같다.

• g(n) : 아직 어디로도 이동하지 않은 시작 노드이므로 g(n)의 비용은 0이다.
• h(n) : S로 부터 E까지의 예측 비용은 간단하게 가로 세로 이동 비용을 더했다. 가로로 4칸 세로로 2칸을 이동하므로 h(n)은 6이 된다.
• f(n) : 위 두 비용의 합은 6이다.

이제 열린 목록에서 f(n)이 가장 작은 노드를 선택하여 현재 노드로 지정한다. 물론 현 시점에 열린 목록에는 S노드 밖에 없으로 S가 현재 노드가 된다.

현재 노드의 인접 노드들을 열린 목록에 저장한다. 현재 노드의 상하우 노드는 15, 11, 5번이 된다. 좌측 방향은 맵의 바깥쪽이므로 포함하지 않는다. 각 노드들은 현재노드로 부터 1씩 이동 했으므로 g(n)은 1이 되고, 예측 비용은 11번과 5번은 5, 목표 노드와 가장 멀리 있는 15번 노드는 7이된다. 인접 노드들의 비용을 계산하고 부모 노드로써 현재 노드를 가리키게 한 후(각 노드에 화살표를 주목 하자) 열린 목록(하늘색)에 저장한다.
열린 목록에서 가장 작은 값을 가진 노드는 11번과 5번이다. 둘 다 '현재 노드'가 될 수 있지만 이 예에서는 5번을 다음 '현재 노드'로 지정하도록 한다.

그럼 아래와 같이 15, 11, 6, 0번 노드가 열린 목록에 저장 된다. 

이전 '현재 노드'였던 S는 열린 목록에서 삭제하고 닫힌 목록(짙은 회색)에 저장한다. 위와 같은 과정을 거치면 현재 노드는 점점 E쪽으로 이동하며 결국 더 이상 이동 할 수 없는 다음과 같은 상태가 된다.

목표 노드로 부터 멀어지긴 하지만 열린 목록에는 15번 밖에 남지 않았으므로 이제 15번을 현재 노드로 지정하고 다시 위의 과정들을 반복하면 결국 다음과 같이 된다.

열린 노드에서 가장 작은 f(n)을 선택하여 목표 지점까지 이동하는 과정

가장 마지막 단계에서 결국 목표 노드에 도착하게 되면, 부모 노드(각 노드의 화살표가 가리키는 노드가 부모 노드다)를 거슬러 올라가 시작점 부터 목표 지점까지 이동할 수있는 경로(노란색)를 구할 수 있게 된다.

마치며

시뮬레이션을 위한 Unity 프로젝트를 다음 링크(https://github.com/ChoiIngon/blog/tree/master/190)에 업로드 해놓았다. 관심있는 분이라면 링크를 따라가 확인하실 수 있다.

위 링크의 유니티 프로젝트를 실행하면 Project 윈도우의 Assets/Scenes 아래 SampleScene을 실행한다. 그리고 Hierarchy 윈도우의 TileMap 오브젝트를 선택하면 TileMap 오브젝트의 Inspector에 A* 알고리즘을 시뮬레이션 할 수 있는 버튼들이 보일 것이다.
먼저 Generate Tile Map을 선택하면 width, height 크기의 타일 맵을 생성한다. 다음, 생성된 타일맵의 타일을 선택하고 'Set from', 'Set to' 버튼을 이용해 시작점과 도착점을 지정해주면 'Find Path' 버튼이 나타난다.

Find Path 버튼을 클릭해 경로를 찾은 후,  'Simulate Path Finding'을 이용해 어떤 계산식으로 경로가 도출 되었는지를 단계별로 시뮬레이션 할 수 있다.

이상 A* 알고리즘의 개념과 동작 방식에 대해 살펴 보았다. 이해가 되지 않는 부분이 있다면 블로그의 댓글로 남겨주면 성심성의것 답변드리도록 하겠다.
여기까지 지루함을 견디고 읽어 주신 모든 분들이 좋은 던전을 만들 수 있길 바라며..이만!!

부록 1. 같이 읽으면 좋은 글

로그라이크 던전을 구현하기 위해서는 길 찾기 알고리즘 뿐만 아니라 어두운 던전에서 시야를 계산할 수 있는 FoV(Field of View)를 위한 쉐도우 캐스팅(Shadow Casting), 절차적 던전 생성(Procedural dungeon generation) 등의 추가 알고리즘에 대해 공부할 필요가 있다. 해당 내용들은 이 블로그의 다른 포스트에서 다루고 있으므로 함께 살펴 보도록 하자.

FoV - 쉐도우 캐스팅(Shadow Casting)

랜덤 맵 만들기