길찾기 알고리즘 공부-1(Astar)

3d는 네비메쉬가 있는데 2d는 네비메쉬 적용을 하려면 다른 에셋을 사용하거나 직접 길 찾기 알고리즘을 적용해야 해서 구글로 여러 가지 공부중 astar와 jps 등등 여러 가지가 있어서 

 

astar 테스트할 겸 프로젝트 하나를 만들어 봤습니다.

 

사용 리소스 https://cupnooble.itch.io/sprout-lands-asset-pack

 

 

 

 

각각 플레이들에게는 3가지 옵션이 있는데

대각선 이동 못하는 None과

대각선 이동하는 Allow Diagonal

대각선 이동하는데 대각선 가는 방향에 경로 방해가 하나라도 있으면 못 가는 Allow Diagonal DontCross

 

현재 격자 이동이라 상관없는데 대부분 2d는 격자로 이동을 안 하기 때문에 격자 이동을 안 할 때는

저 타일 확인을 더 작게 쪼개서 하는지 잘 모르겠네요. 보통 ai에게 길 찾기 알고리즘을 사용하기 때문에

ai들이 이동할 때는 격자로 이동해도 부자연스럽지 않을 거 같기도 하고 좀 더 공부가 필요해 보이네요

 

또 문제점이 있는데 도착지역이 못 가는 지역이거나 벽이 있으면 모든 노드를 탐색하는데 코드 실행시간을 확인해보니 평소에는 0ms가 뜨는데 모든 노드를 탐색하면 코드 실행시간이 늘어납니다. 맵 크기가 커지면 그 이상으로 무거워질 거 같습니다.

 

임시로 도착지점이 지역이 못가는 지점이면 도착지역 근처로 재조정을 넣었는데

 

도착지역에 벽이있으면 도착지역 근처로 재조정

근데 이것도 만약 경로가 막힌거라면 어차피 모든 노드를 탐색하는 건 똑같아 보여요

astar는 최악의 경우 모든 노드를 확인해야 하는데 그걸 개선하기 위해서 jps가 나왔는데

Jump Point Search로 레이더처럼 방사 형태로 검색해서 충돌 정보를 기반으로 확인하는 알고리즘이라고 합니다

jps도 그리드 탐색 시간 부분을 개선하기 위해서 jps+와 jps(b)가 나왔다고 하고

 

우선 jps를 이용한 알고리즘을 한번 만들어서 확인해봐야겠네요

 

깃허브 주소 : https://github.com/wolstar415/Unity_Pathfinding-Algorithm