'Astar'에 해당되는 글 1건

  1. 2011.03.28 A* ( A star )알고리즘
Computing2011. 3. 28. 16:54



 




A*알고리즘을 적용한 마름모 맵에서 길찾기

목적지를 정하면 해당 블럭주위 8방향에 대하여 이동 가능한 블럭 여부를 검사한다. 그리고 이동 가능한 블럭인 경우 openList에 짧은 거리의 블럭을 담아서 개별적으로 주위의 8방향에 대하여 검사한다. 그리고 검사한 원소는 표시를 해둔다. 산에서 길을 잃을까봐 나무에 표시하듯이 검사한 블럭은 검사여부와 이전의 블럭위치를 설정/저장하고 각각 블럭은 목적지와의 거리를 갱신한다.

여기까지는 엄청나게 많은 원소가 발생한다. 여러 경우의 루트를 찾아서 전부 가지고 있게 되는 것이다.
이후 다시 한 번 검사하였다. 최종목적지에서 출발지까지 역순으로 루프가 실행하며 각각에 담긴 블럭의 거리(F=G+H)를 검사하여 값이 작은 순으로 원소를 추적한다. 결국 그 합이 가장 짧은 값의 원소를 나열하여 루트배열로 선언하고 그 원소를 따라가도록 하였다.

위처럼 만들었지만 정확하게 잘 만들었는지는 모르겠다.
A*를 개발 중에  인터넷에 떠돌아 다니는 몇 개의 소스를 접해 보았지만 버그나 로직의 미흡 등으로 매트릭스 구조 변경, 장애물이 많거나 다른 복합한 환경에서 길 찾는 확률이 50%~60%도 못 미치는 소스가 많이 있었다. 그래도 아이디어에 도움이 많이 되었다.

내가 개발한 코드는 현재까지는 100%의 확률로 길을 찾고있지만 좀 더 테스트해봐야 할 것 같다.
위의 링크된 파일은 순전히 8방향이고 현재 8방향과 4방향 혼합 그리고 AI를 보강한 버전을 개발 중에 있다~
나중에 전부 완성되고 그때까지도 길을 100%찾는다면 좀 더 자세히 다루어 보겠다...

지금은 4방향으로 개발한 코드로 3D 사천성이나 만들어 볼까 한다~
아래는 개념에 대한 설명이다.

http://www.aistudy.com/heuristic/A_star.htm



Posted by 버터백통