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* 논문 링크