A* Algorithm 구현

C++ 로 A* 알고리즘을 구현하는데 성공했다. 다익스트라 알고리즘도 직전에 구현했는데 곧 포스팅 하도록 하겠다.

A* 알고리즘이란?

길찾기 알고리즘의 일종으로 Openlist, Closedlist, Parent 와 F=G+H 라는 식을 통해 최적의 경로를 찾는다.

Openlist 는 경로를 탐색하면서 고려대상으로 포함이 되는 노드들을 말한다. Closedlist는 Openlist 중에 목적지까지의 가장 짧은 거리를 가진 노드들이다. Parent는 현재 노드의 바로 직전 노드, 이걸 통해서 경로를 이어줄 수 있다.

F, G, H는 보통 프로그래머가 어떤 식으로 계산하느냐에 따라 달라질 수 있다. 일반적으로 G는 시작노드에서 특정노드까지의 이동거리, H는 특정노드에서 목적노드까지의 이동거리, F는 G+H 이다.

---

A* 알고리즘을 간략히 설명하자면,

1. 맵을 생성한다.

2. start 와 dest 를 설정하고 block 이 필요하다면 지어준다.

3. start 를 Openlist 에 push_back 한다.

4. Openlist 가 0이 되거나 가장 비용이 작은 노드가 dest가 될때까지 다음을 반복한다.

   1) Openlist 에서 가장 비용이 F 같이 작은 노드를 검색 (최초에는 start)

   2) 현재 노드를 Closedlist 에 push_back 하고 Openlist에서 erase (이제 이 노드는 체크안함)

   3) Closedlist의 상하좌우 4방향을 탐색하고 Openlist에 추가(벽이나 타일 밖처럼 갈 수 없는 곳이면 제외)

   4) Closedlist에 있다면 제외 ( 이미 2에서 체크했으니까)

의 방식으로 경로를 탐색하게 된다. 하지만 경우에 따라 최적이 아닌 길을 찾을 수도 있음.

아래에 직접 구현한 영상을 첨부한다. 코드는 올리고 싶은데 너무 길어서 안 올린다.

 

참고 자료 :

http://lhh3520.tistory.com/343

[알고리즘] A* (A Star) 길찾기 알고리즘

http://egloos.zum.com/cozycoz/v/9748811

초보자를 위한 A* 알고리즘 (기초개념 설명 및 소스)

https://blog.naver.com/denoil/221014139704

A* 알고리즘, Astar 알고리즘