HPA*

HPA*

속칭 거의 최적화된 A* 길찾기 라고 불리는 2006년도 길찾기 알고리즘이다.

좋음(초록)/나쁜(빨강) 영향이 끼침

레벨이 높으면 -

속도의 평균격차 ( 속도 평균이 일정한가 )

속도

초기화 속도

메모리

유동성

가장 작은 클러스터 길이가 길수록-

유동성 

속도

그리드를 추상적 그래프로 만들어 A* 길찾기를 하는식이다.

단계는 다음과 같다.

1. 시작 노드와 도착 노드를 구한다.

2. 시작 노드와 도착 노드를 가장 작은 레벨의 클러스터의 테투리에 연결한다.

3. A* 한다

 3-1. 현재 노드가 maxLevel에서 0 level까지 클러스터의 출입구를 검색해 있다면 출입구를 반환, 아니라면 그대로 시작.

 3-2. 현재 노드와 끝 노드가 같은 클러스터가 있다면 다음 레벨로.

 3-3. 0 level에도 같은 클러스터라면 출입구를 반환한다.

4. 얻은 추상화된 길을 실체화 한다, 필요한다면 smoothing 작업도 한다.

5. 끝

A*과 비교해서

장점

더 빠름

메모리 소모 절약

시도성( fail faster )

단점

pre-processing으로 인해 초기화 할때 상대적으로 매우 느림

유동성 - 맵이 달라질 때 빠르게 대처할 수 있는가 

(뭐 어디 한 점이 부서지면 그리 영향이 없지만

어디 대폭발 같이 맵에 큰 영향이 끼치는 일이 일어나면 버벅인다)

명칭에 맞게 매우 가끔식 덜 최적인 길을 줄 수 있음

자료

https://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf 

HPA* 논문 링크