A*(A Star) 알고리즘에 대해 알아보자.

정명에 대한 개발을 했었고, 사라진 수많은 세부 기획과 내부 구현이 있다. 지금 확정된 구현이야, 키보드 조작을 통한 캐릭터의 이동이지만. 처음에 생각했던 방식 중 하나는 마우스로 한 지점을 찍어서 캐릭터를 이동시키는 방식이었다. 보스전과 플레이 경험을 최대한 일치시키기 위해서 폐기된 안이지만… 아무튼, 내부적인 구현은 모두 다 해놓았었다.

서론이 길었다. 그러면 A* 알고리즘이 왜 필요한지 알아보자.

#A* 알고리즘이란?

마우스로 이동을 하는 게임은 특정 지점을 누른다. 그러면 캐릭터는 그 지점으로 이동한다. 중간에 장애물이 있다면, 그 부분을 피해서 움직인다. 즉, 캐릭터는 사용자에게 이 지점으로 가라. 라는 명령을 받으면 그곳으로 가는 길을 찾아야 한다.

여러가지 방법이 많이 생각날 것이다. DFS, BFS, 다익스트라와 같은.

DFS는 방향 잘못들면 영영 길을 못 찾을수도 있다. BFS는 모든 방향을 순차적으로 가다보니, 시간이 당연히 어어어어엄청 느리다. 다익스트라는 길을 찾을수야 있기야 하겠지만… 우리가 원하는 건 한 곳으로 가는데 필요한 Pathfinding이다. 다익스트라는 모든 정점으로의 길을 찾는거니까 좀 알맞지 않다. 다만 다익스트라의 원리는 어느정도 차용한다.

그래서 A*를 쓰는거다.

일단 사전적인 정의를 해보자면, A* 알고리즘은 주어진 출발 노드에서 ‘목표 노드’까지 가는 최단 경로를 찾아내는 알고리즘이다.

격자 지도를 써서 설명하겠다. S는 시작 지점, E는 도착 지점이다. 중간에 색칠되어 있는 부분은 이동이 불가능한 지점이다. 또한 A* 알고리즘에는

f(n), g(n), h(n)이라는 표시가 있는데 이는 각 지점마다의 비용을 뜻한다. 으레 길찾기 알고리즘이 그렇듯이 결과적으로 가장 비용이 적게 드는 node끼리 연결하는 게 최단 경로이다.

g(n) -> 출발 노드에서 현재 노드(n)까지 도달하기 위한 최단 비용 h(n) -> 현재 노드에서 목표 노드까지의 예상 이동 비용으로, 이를 휴리스틱(Heuristic) 거리 측정값이라고 한다. f(n) -> 현재 노드 n까지의 최단 비용인 g(n)과 목표 노드까지의 휴리스틱 비용 h(n)을 더한 비용이다.

즉 간단한 식은 f(n) = g(n) + h(n) 방식이 된다.

그러면 가중치에 대한 정의를 하자.

A*알고리즘에서 g(n)에서 쓰는 방식은 유클리디안 거리(Euclidean distance)이다. 가로, 세로 한 칸당 10만큼의 비용(시간)을 쓰고 대각선으로 이동하면 피타고라스 법칙에 의해서 sqrt(10^2 + 10^2) = 14에 근점하게 나오니 14로 명명한다.

그러면 만약 n까지 도달하는데, 대각선 이동 2번, 세로 이동 1번, 가로 이동 1번을 하면 14 * 2 + 10 + 10 = 48이다.

다음으로 h(n)을 보자. h(n)은 맨하탄 거리를 사용한다. 맨하단 거리 이동방식에는 ‘대각선’이동 방식이란 존재하지 않는다. 그냥 가로, 세로. 이렇게 단 두가지의 이동방식 밖에 없다.

그래서 대각선 이동 2번은 (가로 + 세로) 2번으로 퉁쳐진다. 따라서 위의 수식을 맨하단 거리로 친다면 20 * 2 + 10 + 10 = 60이다.

그림을 처음에 잘못 가져와서 어느정도 수정했다.

저 중앙

50

00 50

부분이 현재 노드이고, 그 주변 방향 노드를 탐색한 것이다. 직선 움직임은 10만큼의 추가 가중치를, 대각선은 14만의 추가 가중치를 추가한 것이다.

노트 가중치 계산 방식에 대해서 알아보았다. 이제 경로 탐색 방법에 대해 알아보자.

경로 탐색

먼저 생각해야 할 부분은 열린 목록(open list)와, 닫힌 목록(closed list)이다. 둘은 유망하냐, 유명하지 않냐에 대한 일종의 보관함이라고 생각하면 된다는 걸 기억해놓고 제대로 들어가보자.

(1) 출발하는 노드를 열린 목록(open list) 에 넣어준다.

(2) 출발 노드에 인접한 장애물을 무시하고 지나갈 수 있는 노드를 열린 목록(open list)에 넣어준다. 이 때 노드들은 출발 노드를 부모로 지정한다. 즉, 위에 그림에서 봤듯이 장애물을 제외하고 갈 수 있는 방향의 노드들을 열린 노드에 넣어주는거다. 이 때, f(n), g(n), h(n)을 모두 계산해서 각각의 노드에 넣어준다.

(3) 열린 목록(open list)에서 출발 노드를 없애고, 다시 탐색 할 필요가 없는 닫힌 목록(closed list)에 넣어준다.

(4) 선택한 노드(열린 목록에 있는 노드 중 하나)를 열린 목록(open list)에서 뺴고 닫힌 목록(closed list)에 넣어준다. 이는 선택된 사각형이 ‘부모 노드’가 될 준비가 된 것이다.

(5) 이제 인접한 노드를 확인한다. 닫힌 목록(closed list)거나 장애물에 있는 것이라면 그냥 패스하고, 열린 목록(open list)에 그 노드가 없다면 열린 목록(open list)에 추가한다. 그리고, 현재 노드를 새로 이번에 넣어주는 노드들의 ‘부모’로 만든다. 또, 2번에서 그랬던 것처럼 f(n), g(n), h(n)에 각각 넣어준다.

(6) 새로 넣어줄 노드가 열린 목록(open list)에 이미 존재하는 노드라면, g(n)이 기존과 비교해서 낮아지는지 비교한다. 비용이 더 낮게 나온다면 부모 노드를 현재 진행중인 노드로 바꿔주고, 그 노드의 f(n), g(n)을 다시 계산해준다.

(7) 위 과정이 끝나면 열린 목록(open list)에 있는 노드들 중에서 가장 f(n)이 작은 노드를 선택한다. 그리고 다시 경로 탐색을 하며 4 ~ 6을 계속 반복한다.

(8) 목표 노드가 열린 목록(open list)에 추가되면, 목표 노드에서부터 거꾸로 부모 노드를 따라 거슬러 올라간다.

그러면 길을 찾을 수 있다.

조금 요약해서 말하자면, 한 노드의 사방 노드를 검색한 다음, 거기서 계속 유클라디움 거리, 맨해튼 거리 방식을 통해 전부 검색한다.

그 이후, 그 중에서 가장 작은 값을 유망하다고 생각한 이후, 그걸 기준으로 반복한다… 라고 나는 생각이 된다.

그리 어렵지 않은 알고리즘이다. 구현이 어렵지… 하지만 이 A* 알고리즘도 경우에 따라 단점이 있을수도 있다. 그래서 상황에 따라 D*, JPS등 여러가지 알고리즘을 쓴다.

Algorithm 카테고리 내 다른 글 보러가기