소년해방전선

http://www.kimchulho.com/fun/astar/

자바스크립트로 구현해본 A*(A star-에이스타) 알고리즘 입니다.
시작점, 끝점, 장애물을 각각 설정해 놓고 길찾기 버튼을 누르면 가장 최단 거리를 찾아줍니다.
본 알고리즘의 거리계산에도 여러가지 방식이 있는데요.
모든 노선을 고려 하지 않고 최단 거리를 계산하기 때문에 결과적으로 가장 짧은 길이 아닐 수도 있습니다. 모든 노선을 고려하게 한다면 가장 짧은 길이가 되는 경로를 찾아낼 수 있지요.

지금, 계산 방법으로 시작점과 끝점의 가로길이와 세로길이를 단순히 더한 거리를 참조하는 방법이 있고, 대각선 거리(유클리드 거리라고 하는 것 같습니다만)를 참조하는 방법을 제공합니다.

제 예상에는 대각선 거리를 참조하는 것이 좀더 최단 거리에 가까운 경로를 찾아줄것이라 생각했는데요. 아직 완전하지 않는 건지 상황에 따라 다른건지, 어떤 경우에는 가로세로축 참조가 더 짧은 경로를 찾기도 하고 어떤 경우에는 대각선거리 참조가 더 짧은 경로를 찾기도 하네요. 대각선거리 참조가 좀더 연산을 많이 하는 것 같습니다.
지도의 크기도 영향을 줄 수 있는것 같은데, 아무래도 자바스크립트로 테이블을 이용하여 짜다 보니 지도가 커지면 버벅거릴 우려가 있어서 지도의 크기를 가로 30 세로 30으로 제한했습니다.

astar 알고리즘을 재귀적으로 호출하여 시작점부터 끝점까지 찾아갑니다.
만일 길이 막혀 있다면 길이 막혀 있다고 출력을 하는데, 그전까지는 연결되어 있는 길은 모두 찾아가게 됩니다.

빨간색은 시작점
파란색은 끝점
검은색은 장애물
노란색은 이미 참조한 경로
연두색은 추후 참조할 경로
하늘색은 최종 경로를 표시해 줍니다.


길이 표시된 이미지 정보(지도)를 받아들여 내비게이션처럼 구현해보려고 했는데, 가로 100 세로 100 정도만 되어도 연산시간이 너무 오래걸리더군요. 전에 구현했던 다익스트라 알고리즘과 비교해 보자면 A*알고리즘은 격자형 지도에 사용하기가 좋고, 다익스트라는 규격화 되지 않은 노드로 이루어진 경우에 사용하기가 좋을 것 같습니다.

물론, 본질이 비슷해서 A*를 링크드리스트로 구현하거나 다익스트라를 격자형 노드로 구현하는 거랑 별 차이는 없겠네요.

심심할때 해보면 재미있을 겁니다.
A*에 대해서는 인터넷에서 찾아봐도 번역된 자료도 있고, 알고리즘은 이해하는데는 별 어려움이 없을 것 같네요.

2009년 12월 17일에 추가 사항입니다.

소스 파일 올립니다.

php를 조금 쓰기 때문에 php가 설치된 곳에서 동작합니다.

사용하시는 웹 서버(호스팅 등등)가 있다면 올리시면 됩니다.

하지만, 프로그램의 구현은 자바스크립트에 의해 이루어 집니다.

php로 짠 부분은 보시면 아시겠지만, 반복문으로 칸을 만드는 수준입니다.

index.zip