네비메시에 관해서....

네비메시는 AI에서도 상당히 밀접한 관계가 있다.

X지점에 있는 객체를 Y지점으로 옮긴다. 그런데 그냥 이동하는 것이 아니라 장애물이나 방해되는 요소를 제외하여 알아서 움직이거나 최소의 비용으로 최단거리를 움직인다고 하면 쉽지 않다. 그렇다고 모든 이동 요소들을 검사해서 가기에도 퍼포먼스가 너무 떨어진다. 그래서 내가 원하는 구간 또는 영역을 한정시켜 최소한의 작업으로 지능적으로 이동할 수 있는 방법이 필요하다. 근데 이거 보통 실시간 3D 게임에서도 잘 적용안되는데 주로 쓴다해도 마을 정도이다. 어차피 내가 이동 할 건 내가 선정하고 내 판단으로 움직여서 사냥할 때나 그럴땐 잘 안쓰지.. 주로 마을에서 퀘스트를 받고 똥개훈련 받는다치면 맵 켜서 NPC클릭 하면 자동으로 그 앞까지 가게 하는 정도? 아무튼 마을이라는 한정적인 구간에서는 그나마 쓰기가 낫다. 실시간 게임에서 주변 타일이나 환경과 상호작용은 잘 없기 때문에 사용은 드물다고 본다. 

마을에서 장애물이나 벽, 건물등이 있다고 하면 내가 갈 수 있는 길에만 바닥에 삼각형으로 이루어진 메시를 만들어 굳이 오브젝트에 충돌검사 여부를 주지 않고 삼각형 메시 안에서만 이루게하면 된다. 네비게이션 메시가 이 같은 개념이라고 봐도 된다. 물론 이 바닥을 깔게 되면 2D에서 길찾기 알고리즘을 썼던것들을 응용해서 3D에서도 사용할 수 있다. 에이스타나 다익스트라나 점점 서치나.. 

만약 객체가 벽에 충돌했는지를 감지할 때 실제 해당하는 기하 구조와의 충돌을 검사할 필요가 없다. 그냥 네비게이션 메시의 외곽선에 도달했는지만 검사하면 된다. 

네비게이션 메시가 제대로 작동하려면 몇 가지 조건들을 만족해야 한다. 

1. 네비게이션 메시는 무조건 삼각형들로만 구성되어야한다.

2. 전체 메시는 반드시 연속적이어야한다. 그러려면 모든 인접한 삼각형들은 두 개의 정점들과 하나의 변을 공유해야한다.

3. 서로 다른 두 삼각형이 동일한 평면에 겹쳐져서는 안된다. 다시 말하면, 어떤 삼각형 안의 한 점은 오직 그 삼각형에만 속해야 한다. 이렇게 하지 않으면 검색 알고리즘이 매우 복잡해진다.

객체의 이동 과정.

1. 객체의 이동 벡터를 현재 칸의 평면에 대해 투영한다. 3D 이동 벡터를 현재 칸의 평면 상의 2D 선분으로 표현하기로 한다. 이 선분은 제어점의 시작과 목표를 양 끝점으로 한다.

2. 이동 경로가 메시 칸의 2D 삼각형 변들과 교차하는지 점검한다. 이 결과에 따라 다음 세 가지 경우들 중 하나를 수행한다.

1) 이동 경로가 공유되지 않은 변(즉 인접한 삼각형과 연결되지 않은 변)에 교차한다면, 벽이나 어떤 장애물에 부딪혔다는 뜻이다. 그러면 이동 경로의 선분을 제한하거나 객체의 방향을 조정하는 등의 작업을 수행하고 다시 2D 삼각형 변들과 교차하는지 검사한다.

2) 이동 경로가 공유된 변과 교차한다면 인접한 칸으로 이동한 후 1단계로 돌아가서 세 칸의 평면에 대해 다시 벡터를 투영하고 교차를 점검하면 된다.

3) 나머지 경우는 이동이 현재 삼각형을  벗어나지 않는 것이다. 이 경우라면 선분의 끝(목표)에 해당하는 점을 다시 3D 좌표로 변환하고 그것을 이용해서 실 객체를 이동시키면 된다.

이렇게 3D좌표와 2D좌표를 오락가락하면서 변환하면 생각보다 복잡하고 실시간으로 하기엔 쉽지 않은 연산일거다. 그래서 y축을 버린다. y축은 투영이 매우 쉽다. 모든 칸의 법선들은 바닥과 어차피 수직이기 때문에 버린다. 굳이 평평하지 않아도 되고 그냥 각 칸의 법선이 주어진 축과 동일한 방향이 되는것만 정하는것 뿐이다.

y축을 버린 후 객체 이동 과정.

1. 제어점으로부터 목표 위치로 가는 이동 경로를 만들고, 주어진 공통 축 값(y)을 제거해서 2D 이동 벡터를 얻는다.

2. 아까와 동일한 방법으로 2D 이동 벡터와 삼각형 변들의 교차 여부를 판단하는 과정을 반복해서 제어점이 목표 위치까지 도달하도록( 또는 벽에서 멈추도록) 한다.

3. 새(x,,z) 제어점이 놓여진 칸의 평면 방정식을 이용해서(x,z)로부터 y 값을 구하고, 그것을 이용해서 실제 3D 좌표를 얻은 후 객체를 실제로 이동한다.