https://qiao.github.io/PathFinding.js/visual/

길찾기 인공지능의 가장 대표적인 A* 알고리즘 데모입니다. 오른쪽 하단에 있는 'Start Search' 버튼을 누르면 녹색에서 빨간색으로 가는 길을 보여줍니다. 마우스로 시작과 끝을 옮기거나 장애물도 추가할 수 있습니다. 현재 대부분의 게임에서 캐릭터를 이동하는데 이 방법을 응용하여 사용하고 있습니다.

보통 탐색을 하는 가장 쉬운 방법은 깊이우선/너비우선 탐색입니다. 깊이우선은 현재 위치에서 계속 한쪽 방향으로 연결을 찾다가 끝에 도달하면 바로 이전 위치로 돌아와 다른 연결로 이동합니다. 반대로 너비우선은 현재 위치에서 가로 방향으로 우선 찾고 그 다음 한단계 더 들어가 반복적으로 검색을 계속합니다.

만약 여기서 남산타워까지 가는 길을 알고 싶을때 깊이우선/너비우선 탐색으로는 시간이 너무 오래 걸립니다. 무식하게 모든 경로를 검사하기 때문입니다. 남산타워가 북쪽에 보인다면 굳이 남쪽 방향으로 먼저 찾을 필요가 없습니다. 중간에 길이 막혀 돌아가더라도 우선은 목표를 향해 가는 것이 더 효과적입니다. 이렇게 거리정보를 사용하는 방식이 A* 알고리즘의 특징입니다.