[💬] A* 응용 길찾기 알고리즘

[모노모노모노(monosw2000)]

Clearance-based Pathfinding and Hierarchical Annotated A* Search이라고 하는 겁니다.

http://harabor.net/data/papers/harabor-aigamedev09.pdf

레퍼런스는 여기구요. 당연히 영어입니다.

A* 알고리즘의 제한 사항이 몇가지 있죠. 그중에서 Clearance-based Pathfinding와 연관된 제한 사항은 '모든 객체는 그리드 1칸에 1개만 있다.'라는 것입니다.

그런데 게임에서 어떻게 한 위치에 하나만 있나요? 일개 보병은 1칸에 1명 있을 수 있다고 쳐도, 거대 탱크 같은건 여러칸에 걸쳐 있어야 좀 멋져보이지 않겠읍니까? 그런데 그렇게 하려면 갈 수 있는 노드를 검색하는데 크기에 맞춰서 여러번 검색을 해줘야 한단 말이죠. 예를 들어 2x2 크기를 가진 탱크가 (0,0)에서 (0,1)로 이동하려면 사실 (0,1)은 물론이고 (0,2), (1,1), (1,2)를 모두 검색해서 갈 수 있는 곳인지 체크해줘야 하는 문제가 있습니다.

그래서 나온게 저 Clearance-based Pathfinding입니다. 한글명을 뭐라고 해야할지 모르겠네요. 아무튼 줄여서 CP라고 할께요.

CP에서는 다양한 층위의 노드를 미리 만들어 둡니다. 그러니까 크기가 1x1용으로 맵을 해석해두면 2x2용으로 따로 해석해두는 방식이죠. 1x1짜리 유닛은 매 그리드마다 한번만 이동 가능한지 체크한다면, 2x2는 매 그리드마다 미리 2x2 크기의 유닛이 들어갈 수 있는지 체크해두는 방식입니다.

이런 방식이라면 유닛 크기에 따라서 다른 메모리만 불러와서 계산하면 되니까 매 위치마다 유닛이 갈 수 있는지 없는지 체크할 필요가 없어져서 속도가 빠르죠. 이게 CP의 기본 개념입니다.

여기에 더해서 RTS 게임에서는 ㅈㄴ 많은 유닛을 ㅈㄴ 빠르게 길찾기를 시켜줘야 하는 문제가 생깁니다. CP를 쓴다해도 결국 전체 그리드 숫자는 변함이 거의 없습니다. 1x1짜리 유닛에게 192x192 크기의 맵은 3x3 유닛에게는 190x190짜리 크기가 되는거라서요. 그런데 RTS에서 유닛의 반응 속도는 빨라야 하고, 당시 CPU 수준은 지금보다 훨씬 병맛이고.. 그렇게 개발자들은 고통 받다가 몇가지를 눈치챕니다.

대부분의 경우 길찾기가 수행되는 지형은 다 고정되어 있단 말이죠. 기지의 건물을 지어서 막기도 하지만 말이죠. 

그래서 맵을 일정 크기의 클러스터로 쪼개놓고, 각 클러스터마다 이동되는 경로를 미리 다 계산해둔 다음에 A 클러스터의 a 위치에서 B 클러스터의 b 위치로 가게끔 해주는 방식으로 찾는 겁니다.

그러면 대부분은 미리 계산된 경로만 뽑아다가 쓰고, a의 위치에서 A 청크의 탈출점까지의 경로와 B청크의 진입점에서 b까지의 경로만 체크해주면 나머지는 미리 계산된 경로에서 빼오면 되죠. 계산을 많이 생략할 수 있게 되는 겁니다.

이게 저 레퍼런스에서 말하는 Hierarchical Annotated A* Search 입니다.

[모노모노모노(monosw2000)]

쉽게 설명하느라 몇몇 지점에서는 다르게 설명이 되었지만, 그래도 걍 저정도 개념이라고 생각하고 자세한건 원문을 읽어보도록 하세요.

[모노모노모노(monosw2000)]

근데 후자는 로딩이 ㅈㄴ 느려지는 문제가 발생하기 쉽기 때문에 실시간으로 맵이 로딩되고 삭제되는 심리스 월드에서는 써먹기 ㅈ 같읍니다.

[123(122.38)]

먼 거리는 큰 그리드의 패스파인딩으로 해결하고 짧은 거리는 좁은 그리드의 패스파인딩으로 해결해서 연산을 줄이는 거네

[모노모노모노(monosw2000)]

저보다 요약 쉽게 해주시네요. ㅋㅋ

[123(122.38)]

ND가 심리스에요?

[모노모노모노(monosw2000)]

네. 맵 로딩은 죄다 백스레드로 처리했고요.