NavMesh (Navigation Mesh) 네비게이션 메쉬

네비게이션 메쉬 + A* (Navigation Mesh + AStar)

원문 링크 : http://yoysh.egloos.com/25000 

네비게이션 메쉬 + A* (Navigation Mesh + AStar)

: 3차원 지형을 2D처럼 간단하게 표현 하는 방식으로 Object가 이동 가능한 모든 지형을 Cell(삼각형)으로 표시 하여 A*와 같은 길찾기 알고리즘을 쉽게 적용 할 수 있게 해줍니다.

[Navigation Mesh]

1. NaviCell 만들기

Cell 이란? vetex 세 개로 구성되어 이루어진 하나의 삼각형입니다.

- 삼각형의 사이드 라인 세 개를 만듭니다.

- 평면 방정식을 위한 Plane을 생성합니다.

- Cell의 중점을 계산합니다.

- Cell의 세 사이드 라인의 중점을 계산합니다.(mid[0], mid[1], mid[2])

- Cell의 중점에서 사이드 라인의 중점까지의 거리를 계산해둡니다.

(ArrivalCost)

2. NaviMesh 만들기

Navigation Mesh 란? 지형의 모든 이동 가능한 삼각형의 집합

앞에서 만든 NaviCell의 바로 이웃한 셀들을 연결시켜줍니다.

Link[0], Link[1], Link[2]가 이웃한 NaviCell을 가리키며,

만약 이웃한 Cell이 없다면 NULL

[A*]

3. Actor 만들기

NaviMesh로 부터 자신의 좌표와 자신이 위치한 Cell을 미리 계산해둡니다.

여기서 Actor는 x, z만 알면 평면방정식으로 부터 y값을 구합니다.

(앞으로 x,z는 평면의 좌표이며 y는 높이 값입니다.)

4. Heap 만들기

heap은 End좌표로 부터 거꾸로 start까지의 셀 노드들의 리스트입니다.

end cell은 시작점, start cell이 목표점으로 생각합니다.

EndCell로 부터 인접한 셀들을 구합니다. 이 인접 셀들중 비용이 가장 싼 것을 계산 합니다. 계산식은 Heuristic + ArrivalCost 입니다.

여기서 Heristic은

deltax = (목표점.x - 현제셀중점.x)

deltay = (목표점.y - 현제셀중점.y)

deltaz = (목표점.z - 현제셀중점.z)

max(max(deltax, deltay), deltaz) 값입니다.

이웃 셀중 비용이 싼 셀이 현재 셀로 되며 같은 방식으로 다시 이웃 셀을 비교합니다.

이를 반복 하면 start 셀까지 셀이 이동됩니다.

5. Path 만들기

앞에서 만든 heap으로 부터 start로 부터 end까지의 mid좌표와 cell을 연속적으로 저장해둡니다.

6. 추가 작업

삼각형의 중점으로 Cell들을 이동해 다니게 되면 술취한(갈지자) Actor처럼 보이므로, 앞에서 구해진 Path로 부터 line테스트를 하여 직선 경로를 구해 이를 이동 경로로 사용합니다.

추가사항

출처 - http://www.gpgstudy.com/forum/viewtopic.php?t=2209

네비게이션 메쉬와 A*는 같은 내용의 알고리즘이 아닙니다.

A*는, 경로가 표현되는 공간의 구체적인 표현방식과는 관계없는 알고리즘입니다.
어떠한 형태의 공간이 주어지든(2D격자, 3D격자, 불규칙 메쉬, 6각형2D격자 등등 ..)
이웃(neighbor)에 대한 표현만 주어지면 그 공간에서 실시간으로 최적화된 길찾기를 할 수 있는 알고리즘이 A*입니다.

네비게이션 메쉬는 '불규칙한 메쉬'로 이루어진 3D월드에서 보다 부드러운 주행을 위해서
길찾기에 이용될 월드 표현방법을 단순화시켜 보자는 알고리즘입니다. 말하자면 길을 찾는
것이 최종적인 목적이 아니라, 복잡한 3D공간을 단순화시켜서 생각하기에 편하도록 만들어보자는 겁니다.
네비게이션 메쉬에서 실제로 길을 찾는 알고리즘은 뭐든 상관없습니다.

-----------------------------------------------------------------------

Hun's review

 네비게이션 메쉬 오픈소스
c++ : https://github.com/memononen/recastnavigation

c# : https://github.com/Robmaister/SharpNa

Navigation Mesh 는 맵 또는 씬마다 각각 계산되어야 합니다.