저번 포스팅에서 A* 알고리즘에 대해서 알아보았다. 그렇다면, 현재 나의 프로젝트에서는 어떻게 적용했는지 이번 포스팅에서 알아보자.
🔍 노드와 walkable
A* 알고리즘을 사용하려면, 노드에 대해서 알아야 한다.
노드는 기본적으로 G, H, F 코스트와 walkable bool 값이 담겨있다고 생각하면 된다.
G, H, F 코스트는 경로를 계산할 때 사용하는데, 이 walkable은 무엇을 하는 변수인가?
이는 해당 노드가 이동 가능한 유무를 나타낸다.
저번 포스팅에서 이웃 노드를 검사하고 오픈 리스트에 노드를 넣는다고 했는데, 이동이 불가능한 노드는 여기서 걸러진다.
🛡️ 타워 디펜스 게임에서의 노드
그런데, 타워 디펜스 게임에서는 목표 노드가 타겟의 위치일 경우가 있다. 이때 walkable 불 변수를 사용하면, 해당 노드는 타워의 콜라이더 등에 의해서 이동 가능하지 않다고 판단될 수 있다.
이 경우, A* 알고리즘을 돌려도 우리는 경로를 획득할 수 없다. 이유는 바로 목표 노드가 이동 불가능 노드이기 때문에 오픈 리스트에 들어갈 수 없어 경로를 찾지 못하는 것이다.
그래서, 나는 아래와 같은 방식을 사용해 보았다.
🔥 목표의 주변 노드로 이동
목표 노드가 이동 불가능 노드라면, 그 이웃 노드를 파악해서 이동하면 된다.
계산 방식을 동일하다. G 코스트는 이동한 거리, H 코스트는 목표 노드까지의 예상 비용으로 계산하면 된다. 그 대신에, 목표 노드까지 도달했는 지를 검사할 때, 목표 노드와 정확히 맞는 지가 아닌 목표 주변 노드에 포함되어 있는 지를 검사하면 된다.
이렇게 하면 목표 노드가 이동 불가능 노드라 할지라도 이동을 할 수 있다.
🔥 목표 노드는 이동 가능하게 설정
애초에 목표 노드가 이동 불가능하지 않다면, 이러한 일이 발생하지 않는다.
따라서, 목표 노드가 설정이 되면 그 노드를 이동 가능하도록 설정해 주는 것이다.
그러나, 이 방식은 해당 알고리즘을 통해 그 경로를 따라 움직이는 오브젝트가 목표의 콜라이더에 의해서 목표에 도달할 수 없는 문제가 있기 때문에 이에 대한 예외 처리나 다음 상태로의 전환을 확실하게 해주어야 한다.
나는 현재 이 방식을 더 발전시킨 형태로 몬스터가 길을 찾고 있다.
이에 대한 포스팅은 다음 포스팅에서 다루겠다.
✨ 마무리
오늘은 A* 알고리즘은 직접 적용하기 위해서 문제가 될 만한 요소에 대해서 알아보았다. 진짜 한 1~2주 동안 이 알고리즘에 대한 연구를 진행하다 보니 여러 시행착오가 쌓였고 많은 공부가 된 것을 이 글을 쓰면서 느끼고 있다.
위에서 말했듯이 다음 포스팅에서는 사이즈에 따른 A*알고리즘의 길찾기 방식에 대해서 작성할 것이다.
