내비게이션 메시 참고서

개요

월드를 점을 연결한 방식으로 나타내는 것보다, 컨벡스(볼록) 폴리곤의 연결 그래프를 통해 AI 환경설정 공간을 좀 더 정확히 나타내어 보고자 합니다. 각 노드(폴리곤)에서는 그 볼록성(convexity)으로 인해, AI가 그 노드의 한 지점에서 다른 지점까지 갈 수 있다는 것을 압니다. 따라서 그래프를 통한 길찾기 작업은 노드에 연결된 그래프에 따른 길찾기로 단순화됩니다. 이것은 현재 언리얼이 채택하고 있는 웨이포인트 그래프에서 실행되는 길찾기 방법과 유사합니다. 두 시스템간의 차이점은, 기존 방법으로는 패쓰가 일단 생성되면 패쓰상의 지점 이외에는 다른 데이터를 갖지 못한다는 점입니다.

내비게이션 메시를 사용하면 목적지에 도달하기 위해 거쳐야 하는 일련의 폴리곤을 나타내는 패쓰가 있지만, 그 길을 따라 걸을 수 있는 공간이 어떻게 보이는지 정확히 알 수 있습니다. 웨이포인트 그래프로 생성된 패쓰를 따라 각 지점을 통과하는 것 대신에 AI 는 내비게이션 메시 노드간의 인터페이스와 관련된 모든 정보를 가지게 되었습니다. 사실상 이를 통해 정확하고 자유롭게 지름길을 선택할 수 있으며, 일반적으로 이동이 더욱 자연스러워 보이게 됩니다.

그림 A 는 이 예제를 나타냅니다.

(FIG A)

10 개 노드의 패쓰를 가지고도 웨이포인트 그래프의 패쓰 컨트롤 방식이 4 개 노드의 내비게이션 메시 패쓰 보다 떨어진다는 것에 주목해 보십시오.

장애물 메시

메시 그 자체뿐 아니라 월드에 장애물을 나타내는 메시도 생성합니다. 이것은 이동 메시의 가장자리를 따라 서 있는 "벽"이 됩니다. 이 메시의 목적은 AI 가 한 지점에서 다른 지점으로 직접 걸어갈 수 있는지 여부를 알 필요가 있는 경우, 정확성이 낮은 광선투사(raycast)를 허용하는 것입니다. 이를 통해 출발지와 목적지 사이에 많은 폴리곤이 있더라도 넓게 열린 영역에서 길찾기를 건너뛸 수 있습니다. 두 그래프로부터의 폴리곤을 포함하는 옥트리(octree)가 생성됩니다. 이 옥트리는 출발지(현재 내가 위치한) 폴리곤의 빠른 검색뿐만 아니라 목적지 폴리곤 검색(어떤 폴리곤이 나의 목표에 있는지)에도 사용됩니다.

생성 과정

대부분의 내비게이션 메시 구현이 겪는 가장 큰 단점 중 하나는 메시 생성이 아티스트의 몫이라는 것입니다. 메시 생성은 상당한 시간의 (패쓰노드를 배치하는 것보다 더 오랜 시간의) 작업을 요합니다. 이것을 고려해서 디자이너의 고된 작업 없이 자동으로 메시를 생성하는 시스템을 만들기로 했습니다.

이 과정은 세 단계로 이루어집니다.

1. 탐색 (Exploration)

디자이너가 배치한 각 위치에서 시작해서, 맵은 '플러드 필'(flood fill)됩니다. 즉 어떤 스텝 크기에 따라 맵의 각 부분을 광선투사로 검사를 마치고 나면, 메시에 추가되는 것입니다. 이 스텝의 마지막에는 결국 그리드를 닮은 고밀도 메시가 됩니다. 여기서 언리얼 선 검사의 AABB 속성에 의한 정사각형 작업을 하고 있습니다. (그림 C 는 메시 생성 첫 단계 이후의 메시를 나타내고 있습니다.)

이 접근법의 단점은 탐색에 사용되는 스텝 정도 단계가 어긋나 있는 오브젝트는 메시의 경계에서 아주 멀어져 버리게 되는 것입니다. 이런 상황을 경감시키기 위해, 탐색 도중 장애물을 만나면 스텝 크기를 N 번 하위분할하여 바라는 수준의 정확도를 냅니다.

(그림 D 는 하위 분할로 인해 득을 보는 테스트 맵 부분을 나타냅니다.)

2. 메시 단순화

가장 까다로운 (그리고 가장 많은 시간을 소모하는) 것는, 메모리에 맞으면서 길찾기를 실행시킬 수 있을 정도로 메시를 단순화시키는 것입니다. 현재의 단순화 방법은 주로 슬라브(slab) 병합 접근법 이후 소위 슬라브를 최소량의 볼록 모양으로 볼록 분해하는 것입니다. 전체 프로세스는 다음과 같은 형태를 띕니다:

1. 정사각 병합하여 폴리 수를 줄이고 다음 단계를 가속
2. 모든 폴리를 경사만 다른 별도의 오목 슬라브로 병합
3. 오목 슬라브를 볼록 모양으로 분해

정사각 병합

정사각 병합은 단순히 시작 노드를 집은 다음, 모든 방향으로 확장해 가며 그 시작 정사각형의 최적 (영역이 가장 큰) 환경설정을 찾는 것입니다. 이 프로세스는 빠르며 노드 수를 큰 인수만큼 줄여주어, 나머지 프로세스를 가속시킵니다. 정사각 병합이 완료된 이후의 테스트 맵 스크린샷은 이와 같습니다:

UNavigationMeshBase::MergeSquares() 을 참고하십시오.

오목 슬라브 병합

이 단계는 (결과가 볼록이든 아니든) 가능한 한 많은 인접 폴리를 병합시킵니다. 경사가 너무 다르거나, 병합했을 때 결과 모양이 원래 폴리와 너무 달라지는 폴리는 병합되지 않습니다.

이 단계가 수행된 이후의 메시 모습은 이렇습니다:

주: 이 단계는 원래 확장 프로세스의 그리드 속성에 의해 유발되는 계단형 모양을 부드럽게 하는 에지 단순화를 통합시킵니다. 그려 보이기 위해 에지 단순화를 켠 모습은 이와 같습니다:

UNavigationMeshBase::MergePolysConcave() 를 참고하십시오.

슬라브 분해

메시를 비슷한 경사와 높이의 슬라브로 단순화시킨 후에는 사용가능한 모양으로 분해해 줘야 합니다. 이 작업은 볼록 분해 프로세스에서 수행되는데, 그 프로세스는 오목 슬라브를 나타내기 위한 모양의 최적 환경설정을 찾기 위해 A* 접근법을 사용합니다. UNavigationMeshBase::DecomposePolyToConvexPrimitives() 을 참고하십시오.

3. 메시 마무리

메시가 단순화된 이후 마지막 단계는 노드 사이에 패쓰-가능 에지를 세우고, 장애물 메시를 생성하는 것입니다. 이 단계 도중 사용되지 않은 버텍스를 쳐내고 직렬화를 위해 데이터를 다듬기도 합니다.

(그림 I 는 모든 단계가 완료된 후의 메시를 나타냅니다. 장애물 메시를 그리는 세로 표면에 주목해 보십시오.)

패쓰노드보다 내비게이션 메시가 나은 점:

노드 밀도 감소

메시를 사용하여 넓은 영역을 1 개의 폴리곤으로 표현할 수 있기 때문에 전반적인 그래프 밀도가 낮아지게 됩니다. 이것은 다음과 같은 여러 가지 이유로 인한 장점을 가집니다.

1. 저장되는 노드의 감소에 따라 메모리 공간이 감소합니다.
2. 검색되는 그래프의 밀도가 감소되므로 길찾기 시간이 감소합니다.
3. 더 적은 수의 노드는 교차 레벨 패쓰 정보를 수정하는 시간이 감소함을 의미합니다.

(그림 B 는 MP_Gridlock 에서 이것의 현재의 코드베이스를 사용한 노드 밀도의 예입니다.)

보다 적합한 데이터 구조

현재 패쓰 데이터는 레벨의 UReachSpecs 와 ANavigationPoints 를 통해 저장됩니다. 이것은 부모 클래스(특히 AActor)의 부하와 데이터의 분산된 특성으로 인해 두 메모리 공간의 비대화를 유발합니다. 메시의 사용으로 데이터가 하나의 큰 버퍼에 저장되며, 그 자체로 압축 및 기타 최적화가 쉬워지게 됩니다. 데이터를 최적하기 위한 노력을 별로 들이지 않았는 데도 MP_Gridlock 의 패쓰노드에 비해 이미 20% 향상된 것을 확인했습니다.

FindAnchor 불필요

현재 패쓰검색이 시작할 때마다 AI 는 먼저 어느 패쓰노드에서 길찾기를 시작해야 하는지 결정할 필요가 있습니다. 이것은 범위 내 패쓰노드를 반환하는 옥트리 검사를 통해 이루어지고, 그런 다음 가장 가까이 도달 가능한 패쓰노드를 검색하기 위해 AI 에서 패쓰노드까지 광선투사를 수행합니다. 목적지가 이미 그래프에 없는 경우 패쓰 목적지에 대해서도 반드시 똑같이 수행해 줘야 합니다. 이것의 일부는 캐시 등을 통해 개선될 수 있(고 또 실제로 되)지만, 런타임 시 주기적으로 길찾기 AI가 무시할 수 없는 양의 광선투사를 해야 한다는 사실에는 변함이 없습니다. 내비게이션 메시를 사용하면 FindAnchor 가 해결해야 할 모호성이 존재하지 않습니다. AI 가 현재 있는 폴리곤을 간단하게 찾아내고 그것이 시작 위치가 됩니다. 목적지에 관해서도 마찬가지입니다.

길찾기 방식 개선

먼저 (그림 A 에서) 시연된 바와 같이, 웨이포인트 그래프에서의 움직임이 부자연스러운 경우가 있었습니다. AI 에 가장 가까운 패쓰노드는 바로 뒤에, 또는 진행 방향 정 반대에 있을 수 있습니다. 목적지에 대해서도 동일한 문제가 있습니다.

추가 광선투사 없음

내비게이션 메시 속에 생성한 데이터를 사용하여, 상당량의 AI 광선투사를 제거할 수 있습니다. 한 예제로 AI 가 처음 이동하려 할 때인데, AI가 목적지로 직접 갈 수 있어서 네트워크 상의 길찾기를 피할 수 있는지 알아보기 위해 초기 광선투사를 수행합니다. 이것은 두 가지 이유로 인해 더 이상 필요하지 않습니다. 첫째, 대부분의 직접 도달할 수 있는 지점인 경우 그 지점은 AI 와 동일한 폴리곤에 위치합니다. 따라서 단순히 시작점과 목적지의 폴리곤을 찾아내고 그것이 동일하다는 것을 탐지하면 되는 것입니다. 둘째, 장애물 메시에 의존하여 직접 도달 가능한지 결정하기 위해 로우-파이 선검사를 할 수 있습니다. 두 옵션 모두 광선투사 보다 비용이 훨씬 저렴합니다. Gears 코드베이스에서 AI 가 한 지점으로 직접 갈 수 있는지 물어 보는 경우가 여럿 있는데, 그런 경우에 광선투사가 더 이상 필요하지 않습니다.

또다른 최적화가 시도 가능한 부분은, (PHYS_Walking 를 통해 실행하는 것 보다) AI를 메시 자체에서 움직이게 하는 것입니다. 메시는 AI 가 걸을 수 있는 환경설정 공간을 적절히 표현해 놓은 것이기에, 메시에 투영시킨 다음 PHYS_Walking 에서와 같이 프레임마다 N 번의 광선투사를 하는 것이 아니라, 보이는 지오메트리에 있는 AI 를 1 번의 광선투사를 통해 수정시키게 됩니다. 이것은 특히 군중에 좋습니다. 일반적인 AI 가 필요로 하는 정확성이 그대로 필요하지 않기 때문에, 월드 지오메트리에 대해 충돌 검사를 수행하는 대신 군중을 내비게이션 메시로 스냅시켜 한 번에 더 많은 수의 군중을 처리할 수 있게 됩니다. 물론 일반적으로 화면에서 AI 의 수를 증가시킬 수 있을 것입니다.

엄밀히 더 나은 월드 표현

걸을 수 있는 공간의 지속적인 묘사는 AI 가 하는 많은 다른 유형의 공간 쿼리에 이득이됩니다. 다음은 그 예입니다.

• 팀 대형으로 남아있기 위한 위치를 결정하는 프로세스가 크게 향상됩니다. 바라는 대형 위치가 메시에 있어 걸어갈 수 있는지 아닌지를 쉽게 알아볼 수 있기 때문입니다. 이전 방법은 대형 위치에 가장 가까운 패쓰 노드를 찾는 것에 의존하는데, 이 작업은 비용이 비쌉니다. 게다가 위치에 가장 가까운 패쓰 노드가 꼭 가장 가까운 대형 위치도 아니고, 모양새도 좋지 않습니다.
• AI는 '맨틀-가능한' 위치를 나타내는 개별 패쓰노드로 갈 필요 없이도, 벽 상의 아무 지점을 넘어서도 맨틀 가능합니다.
• 정확한 영향 맵으로써 메시를 명백한 적응하는 것입니다. 수작업 웨이포인트-그래프에 걸쳐 전파하는 것은, 월드스페이스가 완전히 덮히지 않고 인간이 놓은 노드에 의존하기에 정확도가 그리 높지 않은 반면, 메시는 정확하고 완벽합니다.

이외에도 많은 예제가 있지만, 사용 가능한 데이터의 증가는 많은 부수적인 AI 행동에 이점이 있다고 말할 수 있습니다.

자동 생성

생성 프로세스가 자동이기 때문에, 디자이너가 레벨에 패쓰를 생성(하고 유지)하는 데 드는 부담이 줄어듭니다. 명백한 이점이라면 애초에 디자이너가 노드를 놓을 필요가 없다는 것으로, 그에 따라 (누군가 패쓰 네트워크를 변경하지 않고 지오메트리를 변경했다든가 해서) 패쓰가 '잘못될' 가능성이 감소되는 것입니다. 왜냐하면 자동 생성 프로세스는 항상 '정확하기' 때문입니다. 예를 들어 기어즈 제작 과정에서 비주얼 패스용으로 완전히 스크립팅된 레벨이 건네지는 경우가 많이 있었는데, 레벨의 패쓰 데이터의 큰 부분을 깨뜨리게 됩니다. 패쓰 자동 구성 기능을 통해 이러한 상황을 쉽게 벗어날 수 있습니다.

크기가 다양한 에이전트에 대해 본질적인 유연성

월드에 대한 더욱 정확한 표현으로 인한 또다른 장점은, 폭이 다양한 개체에 대해 특별히 고려하지 않아도 된다는 점입니다. 사용중인 모든 유형의 보행 생물에 폭 클래스를 수동으로 추가하기 보다, 메시가 제공하는 부가 데이터를 활용하면 됩니다. 폴리 사이의 에지 폭은 이미 계산되어 있으며, 로우-파이 장애물 메시에 대한 '규모' 선검사에 의해서도, 실행시간에 다양한 개체에 대한 도달가능성 정보를 정확히 유지할 수 있습니다.

동적 오브젝트의 "실제적인" 처리 가능성

중간에 끼어드는 동적 오브젝트를 웨이포인트 그래프로만 처리하는 것은 매우 어렵거나 심지어 불가능할 때가 있습니다. 예를 들어 리치스펙에 상자를 던지면, 장애물을 돌아갈 수 있는 방법을 알지 못합니다. 물론 광선투사를 하고 동적 앵커를 추가시켜 장애물을 피해 가도록 할 수는 있지만, a) 광선투사가 필요하고, b) 여러 상황에서 잘 작동하지도 않습니다. 내비게이션 메시를 사용하면, 장애물을 돌아가기 위해 필요한 모든 작업이 메시 안에서 이루어지며, 광선투사가 필요치 않습니다. 그 장애물의 경계 박스를 잡은 다음 그 내부 폴리를 경계 주변으로 분할하기만 하면 되는 것입니다. 그러면 선 검사 없이도 장애물을 돌아갈 수 있는 방법을 바로 알 수 있는, 완전히 패씽 가능한 메시가 되는 것입니다. 새로이 분할된 폴리곤은 그 폴리곤에 대한 하위-계층구조 역할을 합니다. 전체 메시를 조절할 필요 없이 영향받은 폴리곤 안에 메시를 만들어서, AI가 거기에 들어서면 그 하위-메시에서 장애물을 돌아가기 위한 길찾기를 수행하는 것입니다. 이에 대한 예제는 다음 페이지의 그림. J를 참고하시기 바랍니다.