내비게이션 시스템의 내부 작업

When you want to intelligently move characters in your game (or agents as they are called in AI circles), you have to solve two problems: how to reason about the level to find the destination, then how to move there. These two problems are tightly coupled, but quite different in nature. The problem of reasoning about the level is more global and static, in that it takes into account the whole scene. Moving to the destination is more local and dynamic, it only considers the direction to move and how to prevent collisions with other moving agents.

걸을 수 있는 영역

게임 씬에서의 걸을 수 있는 영역을 나타내기 위해 내비게이션 시스템은 자체적인 데이터가 필요합니다. 걸을 수 있는 영역은 씬에서 에이전트가 서거나 움직일 수 있는 장소를 정의합니다. Unity에서 에이전트는 실린더로 정의됩니다. 걸을 수 있는 영역은 씬의 지오메트리에서 에이전트가 설 수 있는 위치를 테스트하여 자동으로 빌드됩니다. 그런 다음, 이러한 위치가 씬 지오메트리의 맨 위에 위치한 표면에 연결됩니다. 이 표면을 내비게이션 메시(줄여서 내비메시라고 함)라고 합니다.

내비메시는 이 표면을 Convex 폴리곤으로 저장합니다. Convex 폴리곤은 폴리곤 안의 두 지점 사이에 아무런 장애물이 없기 때문에 이런한 목적으로 유용하게 사용됩니다. 폴리곤의 경계를 비롯하여 서로 이웃한 폴리곤에 대한 정보도 저장합니다. 이렇게 하면 걸을 수 있는 모든 영역을 추론할 수 있습니다.

경로 찾기

씬에서 두 위치 사이의 경로를 찾기 위해서는 먼저 시작 위치와 목적지 위치를 가장 가까운 폴리곤에 매핑해야 합니다. 그런 다음, 시작 위치에서 탐색을 시작하여 모든 이웃 폴리곤을 거쳐 목적지 폴리곤에 도달합니다. 이동 중에 방문한 모든 폴리곤의 경로를 추적하여 시작에서 목적지까지 연결해주는 폴리곤의 시퀀스를 찾을 수 있습니다. 이렇게 경로를 찾는 일반적인 알고리즘을 A*(“에이스타”라고 발음)라고 하며, Unity도 바로 이 방법을 사용합니다.

경로 따라가기

시작 폴리곤에서 목적지 폴리곤까지의 경로를 정의하는 폴리곤의 시퀀스를 통로라고 합니다. 에이전트는 통로를 따라 보이는 가장 가까운 코너를 향해 움직이는 방법으로 목적지에 도달합니다. 씬에서 에이전트가 하나만 움직이는 간단한 게임이라면 한 번에 통로 선상의 모든 코너를 찾은 뒤 코너를 연결하는 라인 세그먼트를 따라 캐릭터가 움직이도록 애니메이션화할 수 있습니다.

여러 에이전트가 동시에 움직인다면 에이전트끼리의 충돌을 피하기 위해 원래 경로에서 벗어나야 할 필요가 있습니다. 라인 세그먼트로 이루어진 경로를 사용하여 이러한 경로 이탈을 수정하는 것은 매우 어렵고 오류가 쉽게 발생합니다.

각 프레임에서 에이전트의 움직임이 매우 적기 때문에 우회할 필요가 있을 경우 폴리곤의 연결을 사용하여 통로를 수정할 수 있습니다. 이후 에이전트가 향할 가장 가까운 보이는 코너를 검색하면 됩니다.

장애물 회피

스티어링 로직은 통로 선상에 있는 다음 코너의 포지션을 파악하고, 이에 기반하여 목적지에 도달하기 위한 원하는 방향과 속도를 계산합니다. 원하는 속도를 사용하여 에이전트를 움직일 때 다른 에이전트와의 충돌이 발생할 수 있습니다.

장애물 회피는 원하는 방향으로 나아가되 다른 에이전트 및 내비게이션 메시의 가장자리와 충돌하지 않게 적절한 균형점을 찾아 새로운 속도를 선택합니다. Unity는 상호간 속도 장애물(RVO)을 사용하여 충돌을 예견하고 방지합니다.

에이전트 이동

스티어링과 장애물 회피가 적용된 이후에 최종 속도가 계산됩니다. Unity에서 에이전트는 간단한 동적 모델을 사용하여 시뮬레이션되며, 자연적이고 부드러운 움직임을 위해 가속도까지 고려됩니다.

이 단계에서 시뮬레이션된 에이전트의 속도를 애니메이션 시스템에 제공하여 루트 모션을 사용해 캐릭터를 이동하거나 내비게이션 시스템이 이동을 처리하도록 할 수 있습니다.

두 메서드 중 하나를 사용하여 에이전트가 이동되면 시뮬레이션된 에이전트 위치가 이동되며 내비메시에 적용됩니다. 이 간단한 마지막 단계는 확실한 내비게이션 과정에서 중요한 역할을 합니다.

글로벌 및 로컬

내비게이션과 관련하여 이해해두어야 할 가장 중요한 사항 중의 하나는 글로벌 내비게이션과 로컬 내비게이션의 차이입니다.

글로벌 내비게이션은 월드에서 통로를 찾는 데 사용됩니다. 월드에서 경로를 탐색하려면 상당한 프로세싱 능력과 메모리가 필요합니다.

경로를 정의하는 폴리곤의 리니어 리스트는 스티어링을 위한 유연한 데이터 구조이며, 에이전트의 포지션이 움직임에 따라 로컬하게 조정될 수 있습니다. 로컬 내비게이션은 다른 에이전트나 움직이는 오브젝트와 충돌 없이 어떻게 효율적으로 다음 코너를 향해 나아갈 수 있는지를 결정합니다.

장애물의 두 가지 사례

내비게이션에는 다른 에이전트보다 다른 타입의 장애물이 많이 응용됩니다. 슈팅 게임에서 일반적으로 볼 수 있는 상자나 통을 예로 들 수 있고, 차량도 이에 해당합니다. 이러한 장애물은 로컬 장애물 회피 또는 글로벌 경로 탐색을 통해 처리할 수 있습니다.

움직이는 장애물이라면 로컬 장애물 회피를 사용하는 것이 좋습니다. 이 경우 에이전트가 장애물을 예측하여 회피합니다. 정지해 있을 수 있고 모든 에이전트의 경로를 차단하는 장애물이라면 글로벌 내비게이션인 내비게이션 메시에 영향을 주어야 합니다.

내비메시를 변경하는 것을 카빙이라고 합니다. 이 프로세스는 장애물의 어떤 부분이 내비메시에 닿는지를 감지한 다음, 내비메시에서 해당 부분을 깎아내어 구멍을 만듭니다. 이를 계산할 때 매우 많은 비용이 소모되기 때문에 움직이는 장애물은 충돌 회피를 통해 처리하는 이유이기도 합니다.

로컬 충돌 회피는 종종 흩어진 장애물을 피하는 데 사용되기도 합니다. 알고리즘이 로컬이므로 바로 직면한 충돌만 회피할 수 있으며, 함정을 피하거나 장애물이 경로를 차단하는 경우를 처리할 수 없습니다. 이러한 경우는 카빙을 통해 해결할 수 있습니다.

Describing OffMesh Links

The connections between the NavMesh polygons are described using links inside the pathfinding system. Sometimes it is necessary to let the agent navigate across places which are not walkable, for example, jumping over a fence, or traversing through a closed door. These cases need to know the location of the action.

These actions can be annotated using OffMesh Links which tell the pathfinder that a route exists through the specified link. This link can be later accessed when following the path, and the special action can be executed.