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

2004년 MMORPG 게임 서버 개발시에 정리 했던 내용이네요.
추억이 새록 새록~ 지금은 너무 당연하고 공개된 자료도 많지만, 그 때는 정보 하나 하나가 너무 소중하고 덕분에 삽질 많이 했었지요.

네비게이션 메쉬 + 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테스트를 하여 직선 경로를 구해 이를 이동 경로로 사용 합니다.