Unity A* Algorithm 유니티 에이스타 알고리즘

A* Algorithm이란?

은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프/트리 탐색 알고리즘 중 하나이다. 이 알고리즘은 각 꼭짓점

X에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값 " H(X) 을 매기는 방법을 쓴다. 이 알고리즘은 이 휴리스틱 추정값의 순서로 꼭짓점을 방문한다. 그러므로 A* 알고리즘을 너비 우선 탐색의 한 예로 분류할 수 있다. 이 알고리즘은 1968년 피터 하트, 닐스 닐슨, 버트램 라팰이 처음 기술하였다. 그 3명의 논문에서, 이 알고리즘은 A 알고리즘(algorithm A)이라고 불렸다. 적절한 휴리스틱을 가지고 이 알고리즘을 사용하면 최적(optimal)이 된다. 그러므로 A* 알고리즘이라고 불린다. (출처 - 위키백과)

 

 

 

 

 

A* 핵심개념

1. 휴리스틱 추정값 사용 

    - 휴리스틱 추정값  F = H + G 

    H = 새로운 노드까지의 거리

    G = 도착노드까지의 예상비용

    F  = 둘의 합 ( H + G )

    수평 수직은 10, 대각선은 14의 비용을 갖습니다. (피타고라스의 정리를 이용)

2. OpenList , ClosedList , PathList를 이용하여 노드관리

   OpenList - 검색대상들을 집어넣는 리스트 

        - ClosedList에있는 노드들과 , 장애물들은 제외한 노드들을 넣어서 검사합니다.

        - 도착노드까지 가장 비용이 저렴한 노드를 선택합니다.

   ClosedList - 검색을 마친노드들을 집어넣는 리스트

        - 더이상 검사를 하지않아도 되는 노드들을 여기에 집어넣습니다.

   PathList - 시작지점부터 목표지점까지 최단경로가 담린 리스트

        - 여기에 담긴 경로를 따라움직이면 최단경로가 되겠습니다.

 

                                  에이스타 알고리즘을 이용하여 유니티에서 직접 구현해보았습니다

 

- 시작점 인접한 타일들을 전부 '검사할 대상'에 넣는다(8방향)

- 도착 지점까지의 비용을 계산후 가장 비용이 낮은 노드를 선택한다

- 선택한 노드의 인접타일들을 다시검사해준다
- 검사할 때 지나왔던 경로중 바로 전에 노드를 부모로 설정해서 그 길을 기억해둔다.
- 존재하는 '검사 대상'에서 다시 휴리스틱값이 가장 낮은걸 골라서 이동 후 그 주변을 검사대상에 넣는 방식으로 진행.
- 반복하다가 도착점을 발견하였다면, 부모 노드의 부모노드를 타고 타고 가면서 컨테이너에 담으면 Astar 경로가 나옴.

 

A*알고리즘 단점

맵의 크기가 커질경우 OpenList , ClosedLIst에 엄청난 개수의 노드들이 들어갈수있기때문에 상당한 연산이 필요하다.

또한 시작위치에서 목표까지의 경로가 막혀있다면 A*는 시작위치에서 도달할수있는 모든위치를 탐색하므로 매우 비효율적이다.