2020. 1. 28. 22:58ㆍ유니티/자료
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*는 시작위치에서 도달할수있는 모든위치를 탐색하므로 매우 비효율적이다.
'유니티 > 자료' 카테고리의 다른 글
Unity C# 병합연산자 (0) | 2020.02.02 |
---|---|
Unity C# 클래스와 구조체의 차이점 (0) | 2020.02.02 |
Unity C# Call By Value , Call By Reference (0) | 2020.01.27 |
Unity C#제네릭(Generic), <T> (2) | 2020.01.27 |
Unity RayCast - 클릭시 정보받아오기 및 처리하기 (3) | 2020.01.27 |