최적경로 A* 알고리즘 (기본 개념 및 한계)

A* 알고리즘은 현재까지의 거리 g(n) + 제안된 이웃노드를 선택했을 때 이웃 노드에서 최종점 까지의 거리 h(n)를 합한 f(n)이 최소가 되는 이웃노드를 선택

 

하지만 이웃노드와 현재 노드 사이에 장애물이 있는지는 추가적으로 확인해야 함

 

제안된 점이 장애물 위에 있지는 않은지는 기본적으로 확인하지만, 라인-폴리곤 충돌 감지와 같은 알고리즘을 추가적으로 적용해야 함

 

A* 알고리즘이 간단하긴 한데, 당연히 휴리스틱한 방법이기 때문에 최적은 아닐 수 있음