A* 알고리즘(에이스타 알고리즘)을 통해서 길찾기 구현[이론]

A* 알고리즘이란?

길찾기 알고리즘에 여러 종류가 있다.

DFS,BFS를 통해서 길찾기를 할 수도 있고, 다익스트라 알고리즘을 통해서 가중치가 포함된 경로의 길찾기를 할 수 있을 것이다.

게임에서 보통 길찾기를 할 때에는 다익스트라 알고리즘의 변형인 A* 알고리즘을 사용한다.

A* 알고리즘은 휴리스틱 이론을 사용하는데, 이는 중간 지점에서부터 목적지까지의 가중치를 예상하는 기법을 말하며, 이 기법의 계산 방식에 따라서 수행시간의 차이가 매우 달라진다.

 

A* 알고리즘은 다익스트라와 다르게 출발지와 목적지의 입력을 받는다.

출발지부터 갈 수 있는 선택지를 모두 openlist에 넣고, 이 openlist에 들어간 노드들의 비용 순서대로 탐색을 진행하는데,

비용은

출발지로부터 현재 노드까지의 최단거리를 gcost, 목적지까지의 예상거리를 hcost

이 두가지를 합친 최종점수를 fcost라고 한다.

fcost가 낮은 노드일수록 방문의 우선순위가 높아진다.

 

openlist에 있는 노드들을, 우선순위 순으로 방문을 해주고 다시 방문할 수 있는 노드드를 fcost가 낮은 순서대로 리스트에 넣는다. 이 과정에서 이미 방문을 한 노드는 closedlist에 넣어서 방문을 했는지 구분을 해준다. 또한 방문 시 gcost를 계산해서 기존 값 보다 크다면, 해당 경로는 사용하지 않는다. 새로운 gcost가 작을 경우에는 어느 노드에서부터 이동을 했는지 parent node를 설정해준다.

 

목적지에 도착하면 탐색을 종료하고, 도착지로부터 출발지까지 어떠한 경로로 왔는데 parent node를 따라 가주고, 이를 역순으로 리스트에 넣으면 목적지까지의 최단 경로이다.

 

 

다익스트라 알고리즘은 현재 위치에서 최단거리(gcost)만을 고려하는 것이라는 점에서 A*알고리즘과 큰 차이가 있다.

 

---

게임에서 적용

게임에서 보통 가중치는, 이런 식으로 정의한다. (중력이나 외부 요소 없이 이동한다고 가정할 때)

캐릭터 기준에서 한 노드에서 상,하,좌,우 노드로 간다면 10, 대각선으로 이동한다면 14로 정의한다.

이는 세로 길이가 10,가로 길이가 10인 정사각형이 있다면 대각선의 길이는 √20 이고 이는 14.1~~~이 되는데, 연산 시 소수가 껴 있으면 계산이 오래걸리게 되므로 어림잡아 14로 계산한다.

 

---

예시

이런 형태의 그리드가 있다고 가정했을 때, 출발지로부터 갈 수 있는 노드는 {(2,1),(2,2),(1,2)}가 되고,

각각 노드의 gcost와 hcost는

 

(2,1) -> gcost=10 hcost=24  >fcost=34

(2,2)->  gcost=14 hcost=14  >fcost=28

(1,2)->  gcost=10 hcost =24 >fcost=34

가 되고, 리스트에는 {(2,2),(2,1),(1,2)}순서대로 저장이 된다.

 

다시 (2,2)로부터 탐색을 하게 되면, (2,2)로부터 갈 수 잇는 노드는  {(1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(3,3)} 이 되며, 이 중 (1,1)은 이미 탐색을 한 노드기 때문에 방문에서 제외한다.

 

이 상황에서 각각 노드의 gcost와 hcost는

(1,2) ->gcost는 기존의 10과, 새로 탐색되는 과정에서 24(1,1에서 2,2를 거쳐 1,2를 가는 경로)중 10이 더 작은 값이므로 업데이트 시키 않고 10 그대로 가져가고, fcost는 변하지 않는다. parent node도 바꾸지 않는다.

(1,3) ->gcost=14+14=28 hcost=20 fcost=48

(2,1)->gcost는 기존의 10과, 새로 탐색되는 과정에서 24(1,1에서 2,2를 거쳐 1,2를 가는 경로)중 10이 더 작은 값이므로 업데이트 시키 않고 10 그대로 가져가고, fcost는 변하지 않는다. parent node도 바꾸지 않는다.

(2,3)->gcost=14+10=24 hcost=10 fcost=34

(3,1)->gcost=14+14=28 hcost=20 fcost=48

(3,2)->gcost=14+10=24 hcost=10 fcost=34

(3,3)->gcost=14+14=28 hcost=0 fcost=28

 

이 되고, 다시 fcost가 가장 낮은 노드부터 방문하면 되는데 가장 낮은 노드는 (3,3)인데 이는 목적지이기 때문에 탐색을 종료한다.

 

또한 각각의 parent node를 따라가면 (3,3)->(2,2)->(1,1)순으로 갔음을 알 수 있고, 이를 역순으로 정렬하면 출발지로부터 목적지까지의 경로가 된다.

---

이상 A* 알고리즘에 대해서 알아봤으며, 다음 포스팅부터는 실제 게임에 적용을 해보겠다.