A* 알고리즘 예제 - A* algolijeum yeje

Game AI에 대한 첫 번째 강의로 간단한 Pathfinding 알고리즘을 살펴보자.

Pathfinding이란 말 그대로 “길을 찾는 방법”이다. 게임 속에서 각각의 캐릭터 혹은 NPC는 주어진 World(Environment) 내에서 한 지점에서 다른 지점으로 이동해야하는 경우가 자주 발생한다.

이때 Pathfinding 알고리즘은 한 지점에서 다른 지점으로 이동하는 경로(Path)를 찾아주게 된다. 보통은, 두 지점에 사이의 최단 경로를 찾고자 한다. 가장 간단한 예로 아래와 같은 팩맨 게임의 경우를 생각해보자.

위와 같은, 팩맨 게임을 만들기 위해서 우리는 적(Enemy)이 플레이어(Player)-팩맨-를 인식하고 다양한 경로를 통해 플레이어에게 접근하는 AI를 구축해야만 한다. 즉, 우리는 Pathfinding 알고리즘을 이용해서 적이 플레이어에게 접근하는 다양한 경로들을 찾아내야만 한다.

다양한 Pathfinding 알고리즘이 존재하지만, 이번 시간에는 가장 간단한 형태의 알고리즘인 A* Algorithm에 대해 살펴보겠다. A* Algorithm은 대표적인 Pathfinding 알고리즘으로 대부분의 상용게임들 또한 A* Algorithm을 변형한 형태의 알고리즘들을 사용한다. 따라서 상용 게임에 적용되는 Pathfinding 알고리즘들도 기본 원리는 A* Algorithm과 크게 다르지 않다. A* Algorithm-에이 스타라고 발음한다.-에서 *는 이 알고리즘이 제대로 작동할 때 최적의 경로-최단 거리-를 찾아낸다는 것을 의미한다.

지금부터 구체적인 예제를 통해 A* Algorithm이 어떻게 최적의 경로(Path)-최단 거리-를 찾는지 살펴보자. 지금부터 제시되는 자료는 모두 Patrick Lester의 “A* Pathfinding for Beginners”라는 글에서 가져왔음을 미리 밝혀둔다.[1]

아래와 같은 Grid World에서 시작 지점-초록색 사각형- A에서 목표 지점-빨간색 사각형- B까지의 최단거리를 구하려고 하는 경우를 생각해보자. 이때, 두 지점 사이에는 벽(Wall)-파란색 사각형-이 가로막고 있고 이 벽을 투과할 수는 없는 경우라고 하자.

이제 시작지점 A부터 탐색(Search)을 시작한다. 탐색 과정은 아래의 세가지 프로세스로 구성 된다.

시작 지점 A를 “Open List”에 넣는다.
시작 지점 A로부터 도달할 수 있는 사각형들(Adjacent Squares)을 “Open List”에 넣는다. 그리고 이들의 부모 사각형(“Parent Square”)가 A라는 사실을 저장해 놓는다.
시작 지점 A를 “Open List”에서 제거하고, 시작 지점 A를 “Closed List”에 넣는다.

이 과정을 묘사한 그림은 아래와 같다. 여기서 “Closed List”에 포함된 사각형은 Cyan 색으로 지정되어 있고, “Open List”에 포함된 사각형들은 Green 색으로 지정되어 있다. 또한, “Open List”에 포함된 사각형들은 “Parent Square”에 대한 정보를 화살표 형태로 가지고 있다.

이제, “Open List”에 포함된 사각형들 중 하나를 다시 선택해서 위의 과정을 반복해나가야한다. 그렇다면, “Open List”에 포함된 인접한 사각형들 중 어떤 사각형을 선택해야 할까? 정답은 F값이 가장 작은 사각형이다.

A* Algorithm은 아래의 식을 이용해서 각각의 사각형에 대한 점수를 매긴다.

F = G + H

G = 시작 지점 A에서 해당 사각형까지 이동하기 위해 필요한 Movement Cost

H = 해당 사각형에서 목표 지점 B까지 이동하기 위해 필요하다고 추정된 Movement Cost

여기서 H는 Heuristic의 약자인데 Heuristic은 어림잡은 추정이란 뜻이다. 즉, 우리는 해당 사각형에서 목표 지점 B까지 이동하기 위해 필요한 실제 Movement Cost를 알 수 없지만 Heuristic을 이용해 이 값을 추정한다.

이제 “Open List”에 포함된 사각형들 중에서 F값이 가장 작은 사각형을 선택하는 과정을 반복해 나간다.

우리의 예제에서 G값은 가로/세로 이동은 10의 Movement Cost, 대각선 방향의 이동은 14의 Movement Cost를 가진다고 가정하자.(피타고라스 정리에 의해 대각선의 길이는 가로/세로 길이의

배 이므로)

이제 G를 구하는 법을 알았으니 H를 어떻게 구하는지 알아보자. 우리의 예제에서 H는 Manhattan Method라는 방법을 이용해서 계산한다.

Manhattan Method : 모든 장애물들(Obstacles)을 무시하고, 현재의 사각형에서 목표 지점 B까지 도달 할 수 있는 최소의 가로/세로 이동 횟수-대각선 이동은 고려하지 않는다.-를 계산하고 이에 10을 곱한다.

이 방법이 Manhattan Method라고 불리는 이유는 아마도 한 장소에서 다른 장소로 이동하는데 필요한 City block들을 세는 것과 유사하기 때문이다.-City Block은 대각선으로 이동할 수 없다.-

이제 G와 H를 구하는 법을 알았으니 “Open List”에 있는 각각의 사각형에 대한 F값을 계산할 수 있다. 우리의 예제에서 F값을 계산한 결과는 아래와 같다.

“Open List”의 각각의 사각형에 대해 F값은 왼쪽 위, G값은 왼쪽 아래, H값은 오른쪽 아래에 표시되어 있다. 이제 시작 지점 A로부터 인접한 사각형들의 F값을 구했으니 이를 이용해 탐색(Search)을 계속해 나가자.

4. F값이 가장 작은 인접한 사각형을 선택한다. 그리고 이 사각형을 “Open List”에서 삭제하고 “Closed List” 에 삽입한다.

5. 인접한 사각형들을 모두 체크한다. 만약 “Open List”에 이미 포함되어 있지 않다면 “Open List”에 포함시킨다.

6. 만약 인접한 사각형이 이미 “Open List”에 포함되어 있다면 새로 추가된 경로가 기존의 경로보다 나은지를 체크 한다. 만약, 새로운 경로가 더 낫다면 (새로 선택된 사각형을 “Parent Square”로 지정했을때 G값이 더 작다면-G값이 더 작다면 F값도 당연히 더 작다.- 새로 선택된 사각형을 인접한 사각형의 “Parent Square”로 업데이트한다.

우리의 예제에서 위의 프로세스를 적용하면

F값이 가장 작은 오른쪽 사각형을 선택하고 이 사각형을 “Open List”에서 제거하고 이를 “Closed List”에 삽입한다. 이후 이 사각형의 인접한 사각형들을 체크한다. 오른쪽의 경우 벽에 막혀 있으므로 무시하고, 바로 왼쪽은 시작 지점으로 이미 “Closed List”에 들어가 있으므로 역시 무시한다. 이제 남은 네개의 사각형은 이미 “Open List” 에 포함되어 있다. 이 사각형들에 대해서 새로 선택한 사각형을 포함한 경로를 이용해서 더욱 작은 F값을 가질 수 있는지를 체크한다.
우리가 선택한 사각형의 위의 사각형의 경우 현재의 G값은 14이다. 만약 우리가 선택한 경로를 이용한다면 G값은 20이다.(시작지점으로부터 우리가 선택한 오른쪽 사각형으로 이동하는데 10, 우리가 선택한 사각형에서 다시 위의 사각형으로 이동하는데 10이 소요된다.) 따라서, 이미 있던 경로가 새로운 경로보다 더 나으므로-F값이 더 작으므로- 경로를 업데이트하지 않는다. 같은 방법으로 나머지 세개의 사각형도 체크하면 모두 기존 경로가 더 낫다는 사실을 알 수 있다. 따라서, 모두 경로를 업데이트 하지 않는다.
이제 새로운 사각형의 인접한 사격형들을 모두 체크했으므로 다시 이동할 사각형을 선택할 수 있다. 이제 가장 작은 F값은 갖는 사각형을 찾자. 현재 사각형에서 위와 아래 모두 F값이 54이다. 이런 경우, 둘 중 아무거나 선택해도 상관 없다. 우리는 아래를 선택하자.

이제 다시 이 사각형으로부터 인접한 사각형들을 체크하고 업데이트한다. (이 경우, 오른쪽 아래는 벽의 코너를 뚫고 갈 수 없으므로 이동할 수 없다.)

이런 프로세스를 목표 지점 B가 “Closed List”에 포함될때까지 반복한다. 그 결과는 아래 그림과 같다.

이제 이를 이용해 최적의 경로-최단 경로-를 어떻게 찾자. 최단 경로를 찾는 방법은 간단하다. 목표 지점 B-빨간 사각형-에서 시작해서 각각의 부모 사각형으로 뒷방향(Backward)으로 이동해간다. 만약 시작 지점 A에 도착하면 멈춘다.

위에서 설명한 과정을 우리의 예제에 적용하면 아래와 같다.

이제 지금까지 살펴본 A* 알고리즘을 단계별로 요약하면 아래와 같다.

A* Algorithm 요약

1. 시작 지점 A를 “Open List”에 삽입한다.

2. 아래의 과정을 반복한다.

a) “Open List”에 포함된 사각형들 중에서 F값이 가장 작은 사각형을 선택하고 현재 사각형(Current Square)으로 지정한다.

b) 이 사각형을 “Closed List”에 삽입한다.

c) 현재 사각형으로부터 인접한 8개의 사각형에 대해서

• 만약 인접한 사각형이 “Closed List”에 포함되어 있거나 벽등에 막혀 있어서 이동할 수 없다면 무시한다. 그렇지 않다면 아래의 과정을 따른다.

• 만약 인접한 사각형이 “Open List”에 포함되어 있지 않다면 이를 “Open List”에 삽입한다. 그리고 현재 사각형을 부모 사각형으로 지정하고 F, G, H값을 계산한다.

• 만약 인접한 사각형이 이미 “Open List”에 포함되어 있다면 현재 사각형을 이용한 경로가 기존의 경로보다 더 나은지를 판단한다.(G값을 기준으로 G값이 더 작은 경로가 더 나은 경로이다.) 만약 현재 사각형을 이용한 경로가 더 낫다면 현재 사각형을 부모로 지정하고 F, G 값을 새로 업데이트한다.

d) 아래의 조건 일때 알고리즘을 종료한다.

• 목표 지점 B가 “Closed List”에 포함되거나

• 목표 지점 B를 찾는데 실패하고 “Open List”가 비어 있을 때(Empty) 이런 경우, 시작지점부터 목표 지점까지의 경로(Path)가 존재하지 않는다.

3. 경로를 저장한다. 목표 지점으로부터 뒷방향으로(Backward)으로 부모 사각형을 따라서 시작 지점에 다다를 때까지 계속 이동한다. 이 경로가 최단 경로이다.

References

[1] A* Pathfinding for Beginners By Patrick Lester (Updated July 18, 2005)

http://homepages.abdn.ac.uk/f.guerin/pages/teaching/CS1013/practicals/aStarTutorial.htm