A * 알고리즘

https://youtu.be/GksldGWvHrk

▲2019년 3월 25일 제작. A* (에이스타) 알고리즘
A 스타 구현 및 휴리스틱추정값을 바꾸어 변하는 루트에 대해서 알아보았습니다

 

일단 영상에서의 문제점부터 보자면, 인접한 타일을 검사대상에 넣을때, 대각선까지 검사하는 걸 막아두었습니다.
즉, 동서남북 4방향으로만 길을 체크합니다. 아이러니하게, 4방향만 검색하는것이 8방향으로 검색하는거보다
검사대상노트(Open Node)를 더 많이 연다는 사실을 발견했습니다.
연산량이 많아 프레임이 떨어지는 모습도 모이는터라, 개선이 필요해보입니다.

---

사실 길찾기 알고리즘은 처음부터 바로 에이스타 개념으로 뛰어들어갈 수 없습니다. 
또한 A스타 알고리즘이 매번 정답은 아니고, 노드별로 도달시간이 다른 Weighted Graph 에선 되려 부적합합니다.
선행 학습되어야 할 길찾기 개념들이 많이 있는데

- 오일러 회로
- 해밀턴 순환로
- 탐욕법 알고리즘
- A 알고리즘
- 다익스트라 알고리즘

 

등이 있습니다. 이번 포스팅은 A*이니, 위에 있는 다른 알고리즘들에 관심이 있으신분들이라면
하나씩 검색해서 보시는걸 추천해드립니다.

 

A스타 알고리즘은 탐욕법의 검색속도, 다익스트라의 최적경로 찾기의 특성을 섞은 알고리즘으로,
효율적인 사용을 위해선 아래 두가지 조건이 만족되어야 합니다. 첫째는 목적지의 위치를 정확히 알고있을때,
둘째는 모든 노드간의 도달속도가 일정할 때 입니다. 

 

제가 구현한 A* 알고리즘 개념을 순서대로 정리하면 이러합니다.
- 시작점 인접한 타일들을 전부 '검사할 대상'에 넣는다
- 모든 '검사할 대상'들과 도착점과의 거리를 잰다. (그 거리추정값을 '휴리스틱값' 이라고 한다)
- 휴리스틱값이 가장 낮은, 즉 도착점과 가까운 노드를 선택해서 그 노드의 인접한 타일들을 다시 '검사대상'에 넣는다.
- 검사할 때 본인이 시작점서 지나왔던 경로중 바로 앞에걸 부모로 설정해서 그 길을 기억해둔다.
- 존재하는 '검사 대상'에서 다시 휴리스틱값이 가장 낮은걸 골라서 이동 후 그 주변을 검사대상에 넣는 방식으로 진행.
- 반복하다가 도착점을 발견하였다면, 부모 노드의 부모노드를 타고 타고 가면서 컨테이너에 담으면 A스타 경로가 나옴.

 

▲ 휴리스틱 추정값을 바꾸는 코드. 
위에 방식은 피타고라스로 대각선 길이를 구하는 방법이고
아래 x,y 타일 갯수만 세는 방식은 맨허튼 추정값으로 구하는 방식입니다. 둘의 차이는 영상에서 나타납니다.

 

▲노드들의 휴리스틱을 기준으로 정렬시켜서 휴리스틱이 가장 낮은거로 하나씩 나아가는 방식.
일단 4방향만 체크하는 A* 알고리즘을 구현하였습니다.