A* Pathfinding Project 사용법 - 2. navmeshes 사용하기

1부에선 Grid Graph로 경로를 만들었다면, 이젠 Navmesh Graph로 만들어볼 것이다.

Navmesh Graph

참고로 무료 버전은 Graph를 만들때 사용자가 직접 Blender등 모델링 응용 프로그램을 사용해야하는 번거로움이 있다.

Unity 상에서 자동으로 Navmesh를 구성하려면 Pro 버전을 구입해야한다.

해당 포스트에선 Pro 버전을 가정한다.

 

 

1. 개요

Grid Graph는 그리드 패턴을 사용해 갈 수 있는 영역을 찾는다. 균일하고 구조화되어있기에 매우 직관적이다.

또한 계산 속도가 매우 빨라, 런타임 중 Graph를 업데이트하기 좋은 타워디펜스나 RTS 장르등에 사용할 수 있다.

하지만 맵의 크기가 커질수록, 한 그리드의 크기는 고정적으로 정해져있기 때문에,

Grid Graph를 구성할 때 메모리를 엄청 잡아먹을 것이다!

(※ 그리드 크기 1일 경우, 8x8의 경우 64개의 그리드를, 16x16의 경우 256개의 그리드가 필요)

 

또한 아래와 같이 여러 층이 존재할 경우, 일반적인 Grid Graph로는 이를 처리할 수 없다.

(※ Pro 버전은 이를 처리해주는 LayerGridGraph 지원)

LayerGrid

따라서 복잡한 구조를 가지며, 맵이 넓은 3D 게임에선 Grid Graph를 사용하는게 힘들것이다.

 

이를 해결하기 위해선, 고정된 크기로 나누는 것이 아니라 유동적으로 크기를 조절하여 나누는 것이 가능해야하며,

맵을 바둑판같은 모양으로 Grid를 찍어내어 계산하는 것이 아니라, 지형지물을 자세히 스캔하여 영역을 계산해야 한다.

이 방식으로 Graph를 만드는 것이 바로 Navmesh이다.

 

Navmesh는 길을 폴리곤(삼각형) 단위로 표시한다. 그런데 폴리곤들의 크기가 일정하지 않다.

장애물이 없는 넓은 평지를 나타낼 경우 큰 폴리곤으로 표현하며,

좁은 통로나 장애물이 있을 경우 작은 폴리곤으로 영역을 구체적으로 쪼갠다.

아래 Grid Graph와 비교하면 확연히 차이가 보인다.

 

<NavMesh>

NavMesh

<Grid>

Grid Graph

따라서 같은 노드를 사용하더라도, 나타낼 수 있는 맵의 크기는 NavMesh가 압도적으로 더 넓다.

그러나, Grid보단 계산 속도는 많이 느리기때문에, 지형 지물이 자꾸 변하는 게임은 어울리지 않는다.

차이점을 보기좋게 표로 비교하면 아래와 같다.

	Grid	Navmesh
단위	그리드	폴리곤(삼각형)
장점	실시간 업데이트 빠름 맵 스캔이 빠름	사용하는 노드 수 적어, 메모리 사용량 적음 또한 길 찾기 연산 빠름 큰 맵에 어울림 세밀한 지형도 표현 가능
단점	메모리 사용량 큼 큰 맵엔 어울리지 않음 다층 구조 맵 표현 어려움	Navmesh를 만드는데 시간이 좀 걸림 그래프 업데이트 속도 느림
응용	타워 디펜스, RTS	오픈 월드 3D 게임

 

 

2. Navmesh 자동 생성(Pro 버전만 해당)

0) AI 수정

앞서 추가한 AIPath를 Navmesh에 기반한 이동 스크립트인 RichAI로 바꾸자.(※ 물론 AIPath를 이용해도됨)

또한 Smooth를 위한 스크립트를 Funnel로 바꿔줘야 한다.

이들또한 Pro 버전에만 존재한다.

 

1) Adding Recast Graph

수동의 경우, 대충 Blender를 사용해 Navmesh를 만들고, Pathfinder의 "Navmesh Graph"에 집어넣어 만든다.

그러나 이 포스팅에서는 자동 생성에 대해서만 알아보려고 한다.

자동 생성은 Navmesh Graph가 아닌, "Recast Graph"를 클릭하면 된다.

Recast Graph의 구성은 아래와 같으며, 중요 파라미터만 살펴본다.

Recast Graph 구성

• Width(voxels), Height(Voxels) : 직접 수정은 불가능하지만, Cell size와 Size를 바꿔주어 수정 가능
• Cell Size : voxel의 크기, 이를 통해 Width, Height 조절하여 해상도 결정. 해상도가 높을수록 그래프가 더 구체적임.
• Use Tiles : Tiles 단위로 계산할 것인지 아닌지 여부. 이때 Use Tiles를 선택하게 되면, Tile Size/2의 길이를 가진 정사각형 청크가 나타남. 사용하는 이유는 병렬 스캔때문인듯함.(아래 그림 참고)
  • Tile Size가 클수록 초기 스캔 속도는 빠르지만, 지형이 변경될 시 계산 속도가 느림.
  • Tile Size가 작을수록 path의 quality는 높아지지만, 너무 작으면 AI가 구불구불하게 움직이게 됨
  • 일반적인 Tile Size는 64 ~ 256값
• Layer Mask : 갈 수 있는 영역을 탐색할 Layer

Tile Size : 16 설정

 

Navmesh 그래프는 항상 최적 경로를 보장해주지 않는데, 길 찾기가 폴리곤 중심에서 이뤄지기 때문이다.

 

 

2) 파라미터 조절

① Snap bounds to scene 클릭

먼저 Snap bounds to scene을 눌러 Graph의 Center와 Size, Rotation등을 알맞게 조정해야한다.

Snap bounds to scene

 

② Layer Mask 지정

AI와 Target까지 Navmesh에 포함돼있기 때문에, Scan해보면 그 주변부가 못가는 길로 구성돼있다.

Layer Mask 지정의 필요성

 

이를 없애기 위해, Target과 AI에 따로 Layer를 지정하여 Layer Mask에서 제외시켜줘야한다.

 

이제 Scan하면 제대로 제외된것을 확인할 수 있다.

Layer Mask 제외 후

 

 

③ 이외 파라미터 알아서 조정

이외는 테스트를 해보며 입맛에 맞게 조정해주면 된다.

 

3) 실행

이제 실행하면 navmesh 기반으로 경로가 계산되고 길 찾기를 진행함을 볼 수 있다!

실행 결과

 

 

 

 

 

 

참조

https://arongranberg.com/astar/docs/getstarted2.html