2002년에 발간된 AI Game Programming Wisdom이란 책은 한 번쯤 꼭 읽어 봐야 하는 책이다. 십수 년이 지난 책이지만 지금 이 순간에도 개발에 도움이 되는 이야기를 찾을 수 있다. Show 게임 AI에서 길찾기란 빼놓을 수 없는 부분이다. A*(이하 A star) 알고리즘의 책 내용을 기반으로 구현을 해보았다. 개인적으로 책에 나와있는 코드 스닛핏은 아무리봐도 완전히 이해하기가 어려웠다. 참고로, 유튜브나 웹에서 A star 알고리즘에 대한 정보를 많이 찾을 수 있다. 개인적으로는 아래 유튜브 영상이 차근차근 잘 설명을 잘 해주어 이해하는 데 큰 도움이 되었다. A* (A Star) Search Algorithm A star 알고리즘의 pseudo 코드는 다음과 같다.
g 값은 출발점부터 현재 노드 위치까지 거리이고, h는 현재 노드 위치부터 목표점 까지의 heuristic한 거리이다. 즉 일관성있는 거리 측정 기준만 있으면 h는 구현마다 다를 수 있다. f는 g+h값이다. 이를 바탕으로 구현해 보았다. 맵은 2d array에 1과 0으로 구성하고, 1은 다닐 수 있는 길, 0은 가로 막힌 길로 표시하였다. 그리고 S는 출발점, G는 목표점이다.
h는 Manhattan distance를 이용하여 과 사이이면 형식으로 계산하였다.
노드는 ASNode 클래스로 정의하였다. conn은 실제 패스에 연결되는 노드이고, row, col는 해당 노드의 맵 인덱스이다. 그리고 경로를 찾으며 업데이트 될 g, h, f 값이 있고, nodeName는 유니크한 노드 이름이다. Pseudo 코드에 충실하려고 했으나 역시 그대로 구현하기는 정말 어려운 것 같다. 중요한 포인트는 Open리스트에서 f의 최소값을 꺼내와서 모든 children (여기서는 4방향)을 찾아 g, h, f를 업데이트후 Close리스트에 넣는 과정이다. 이 과정은 FindPath()와 GetChildNodes()에서 찾아 볼 수 있다. 실행을 해보면 아래와 같이 프린트된다. 첫번째 맵은 찾아야 될 맵이고, 두번째 맵은 최단 거리를 별표(*)로 표시해 준 것이다. Optimal Path는 출발점부터 목표점까지의 맵 인덱스를 보여준다. 풀 소스는 아래와 같다. 몇번의 테스트 정도만 했기 때문에, 좀 더 다양한 상황이 발생한다면 오류가 있을 수도 있겠다. 최대한 알고리즘을 따르려고 노력을 했긴 했는데, 코드의 깨끗함은 점점 멀어져만 갔다. 하지만 A star 알고리즘이 어떻게 동작하는 지를 이해하는 데는 큰 도움이 되었다. ✨개요및 소개🔥개요리그오브레전드같은 탑다운게임에서는 플레이어가 마우스를 클릭한 곳으로 캐릭터가 이동합니다. 본 포스팅에서는 2차원배열내에서 출발점에서 도착점까지 최단경로로 이동하는 A*알고리즘을 구현하겠습니다. 이 글은 어디까지나 저의 개인적인 노트, 정리같은것이기 때문에 이론들을 깊게 설명하는것은 하지 않겠습니다. 🔥개발환경2021-08-08기준 Windows10 Home 사용했으며, 컴파일러는 GCC를 사용했습니다. 🔥참고GeeksforGeeks ✨A*알고리즘🔥정의
🔥소스코드
🔥소스코드 설명💎함수 - isDestination
💎함수 - isInRange
💎함수 - isUnBlocked
💎함수 - GethValue
💎함수 - tracePath
💎함수 - aStarSearch
💎함수 - PrintMap
💎함수 - fileload
🔥실행(0: 빈 공간, 1: 벽, 2: 출발지점, 3: 도착지점)
(밑에 사진 0과 1위치가
반전됬습니다. 참고바랍니다.)
와우~!!! 아주 정상적으로 잘됩니다!! 🔥다운로드✨마치며...이렇게 A*알고리즘 공부를 해봤습니다. 궁금한 부분있으면 댓글로 질문주세요. |