[알고리즘]A*(a스타) 알고리즘

A* 알고리즘이란

A* 알고리즘은 주로 게임에서 플레이어를 목표 지점으로 이동 시킬때 사용하는 알고리즘이다.

클릭시 해당 객체가 클릭한 위치로 이동한다.

위의 데모는 클릭한 위치로 오크가 이동하는 것인데 데모에서는 A* 알고리즘이 사용되지는 않았습니다.

오크가 있는 위치에서 클릭한 위치까지 장애물이 없기 때문에 그냥 클릭한 위치를 바라보고 직진으로 이동하기만 하면 되거든요.

하지만 대부분의 게임에서는 장애물이 있고 장애물을 만나면 피해서 가야 되고 또한 목표물까지 최단거리로 찾아 가야 합니다.

이러한 최단거리 알고리즘은 BFS 와 다익스트라 알고리즘과 같은 그래프 알고리즘이 존재 합니다.

BFS는 길을 가는 경로에 가중치가 없는 경로를 찾아 갈 때 유용하지만 즉 A 도시에서 B와 C가 연결 되었는데 B와 C가 가는 경로의 비용이 모두 동일하다면 BFS로 찾는 것이 가능합니다.

하지만 A와 B를 가는 거리와 A에서 C를 가는 거리의 비용이 서로 다르다면 BFS로 찾기가 힘들어 집니다.

이때 사용하는 것이 다익스트라 알고리즘인데, 다익스트라 알고리즘은 출발점을 기준으로 모든 경로의 최단거리 비용을 추출할 때 사용합니다.

다익스트라 알고리즘은 현재까지 진행 경로 중에서 가장 작은 값을 뽑아 내는데 비해 이것을 약간 개선해서 예측값을 두고 예측값이 더 적은 것을 찾아 내는 것이 A*알고리즘입니다.

게임에서와 같이 출발점과 목표지점이 있는 경우 A*알고리즘을 사용하게 되는데 A*알고리즘은 다음과 같은 방법으로 목적지를 찾아 가게 됩니다.

 

단계별 동작 방법

위와 같이 빨간선으로 연결이 되어 있다고 가정하고

각각 연결된 거리가 다음과 같다고 생각해 봅니다.

	서울(1)	강릉(2)	충주(3)	대전(4)	군산(5)	대구(6)	포항(7)	광주(8)	부산(9)
서울(1)		20	10	15	20
강릉(2)	20		10				30
충주(3)	10	10		5			25
대전(4)	15		5		5	15
군산(5)	20			5				5
대구(6)				15			3		4
포항(7)		30	25			3			4
광주(8)					5				20
부산(9)						4	4	20

비용은 위와 같고 서울에서 출발하여 부산을 찾아가는 최단 거리를 구하려고 하면 다음과 같이 지나온 위치를 넣어 두는 Close List, 현재 위치에서 연결되는 경로를 저장하는 Open List 를 두며

Close List 와 Open List 는 각각 Node 번호,F Score,G Score,H Score, Parent 번호 의 정보를 가지게 된다.

이때 F Score = G Score + H Score 로 이루어 지며 F Score 가 가장 작은 순서로 먼저 방문 하게 되는데 마치 다익스트라 알고리즘과 유사하다.

G Score 는 다익스트라 알고리즘에서 출발위치에서 현재 위치까지의 비용을 구하게 되는데 이 점수와 같다.

H Score 는 휴리스틱 추정값이라고 하는데 이 것은 자신의 위치에서 목표 위치까지의 직선의 거리와 같이 예측값이다.

위의 예를 단계별로 수행해 보자.

Close List 에 (1,0,0,0,-1) (nodeno,f,g,h,ParentNode) 를 담아 놓으면서 1번에서 연결된 경로를 다음과 같이 Open List에 담는다.

위와 같이 강릉에서 부산까지 직선 거리 50,충주에서 부산까지 직선 40,대전에서 군산까지 직선 30, 군산에서 부산까지 직선 30이라고 가정하면 이 거리가 휴리스틱 추정값이 되어 다음과 같이 Open List에 담겨진다.

(2,70,20,50,1) - 강릉은 H:50,G:20,F:70 이 된다.

(3,30,10,40,1)

(4,45,15,30,1)

(5,50,20,30,1)

위의 Open List에서 F 점수가 가장 작은 3번 노드를 Close List에 담는다.

3번에서는 2,4,7 이 연결 되어 있는데 2번은 F점수가 70 점이므로 이미 들어가 있는 점수와 같기 때문에 건너 뛰고 4번 역시 F점수가 45점이므로 이미 들어가 있는 점수가 같기 때문에 건너뛴다. 이때 만약 들어가 있는 점수보다 현재 점수가 더 유리하다고 하면 현재 점수로 갱신을 해 주게 된다. 마지막 7번은  다음과 같이 open List에 들어간다.

(7,39,35,4,3)

이렇게 추가하면 Open List 에는 

(2,70,20,50,1) 

(4,45,15,30,1)

(5,50,20,30,1)

(7,39,35,4,3)

이 들어가 있고 여기서 가장 작은 7번 노드를 뽑아서 Close List에 추가하면 목적지에 도착 했으므로 종료 된다.

따라서 Close List 에는 

(1,0,0,0,-1)(3,30,10,40,1)(7,39,35,4,3) 이 들어가 있으며 방문 순서는 거꾸로 7 -> 3 -> 1 과 같이 찾아가 주면 된다.

다익스트라 알고리즘과 유사한 A*알고리즘은 게임에서 적군이 플레이어를 찾아서 쫒아 올 때 장애물을 만나면 장애물을 피하면서 최단거리로 찾아 올 때 많이 사용하게 된다.