Large worlds

대규모 세계에서의 경로 찾기 처리 방법.
대규모 세계는 경로 찾기에 부담을 줄 수 있으며, 특히 설정 방법을 잘못 선택하면 문제가 발생할 수 있습니다. 이 튜토리얼에서는 대규모 세계와 관련된 가장 일반적인 절충점과 이를 처리하기 위한 솔루션에 대해 알아봅니다.

Constraints

먼저 게임이 충족해야 할 요구 사항을 살펴보는 것이 중요합니다. 다양한 솔루션이 다양한 게임에 적합합니다. 다음 제약

사항 목록을 살펴보고 게임에 적용되는 내용을 확인하세요:

• 한 명 이상의 캐릭터가 있습니까?
• 전체 세계에 걸쳐 많은 에이전트가 동시에 경로 찾기가 필요합니까?
• 모든 경로 찾기가 단일 지점/캐릭터를 중심으로 이루어집니까?
• 게임 실행 중에 그래프를 업데이트해야 합니까?
• 세계가 빌드 시에 모두 알려져 있습니까, 아니면 절차적으로 생성됩니까?
• 게임에 패널티나 태그가 필요합니까?

Graph type

대규모 세계의 경우 기본 선택은 GridGraph 와  RecastGraph 사이에서 이루어집니다. Recast 그래프는 일반적으로 대규모 세계에 더 적합한데, 이는 적은 노드로도 세계를 정밀하게 표현할 수 있기 때문입니다. Grid 그래프는 적절한 크기의 세계까지 확장할 수 있지만, 대규모 그리드 그래프는 많은 노드로 인해 메모리와 성능 오버헤드가 큽니다. 500x500 노드의 그리드 그래프는 이미 큰 편이며, 1000x1000 노드를 초과하지 않는 것이 좋습니다. 그러나 전 세계에서 동시에 경로 찾기가 필요하지 않은 경우(예: 모든 것이 단일 플레이어 캐릭터를 중심으로 이동하는 경우) 이동하는 그리드 또는 Recast 그래프를 사용할 수 있습니다.

Solutions

다음은 일반적인 설정 몇 가지와 그 장단점입니다.

A single recast graph

단일 대형 Recast 그래프는 기본적으로 훌륭한 선택이 될 수 있습니다. Recast 그래프는 대형 빈 영역과 작은 세부 사항을 모두 잘 표현할 수 있습니다. 타일링이 활성화되어 있는지 확인하세요. 이는 대형 그래프 생성 및 업데이트를 훨씬 빠르게 만듭니다.

장점:

• 설정이 간단합니다.
• 작은 세부 사항과 큰 세부 사항 모두 잘 표현합니다.
• 비교적 낮은 메모리 사용량을 가집니다.
• 적은 노드 수로 인해 경로 찾기가 빠릅니다.
• 전체 맵이 메모리에 동시에 존재하므로 여러 캐릭터가 세계의 다른 부분을 동시에 탐색할 수 있습니다.
• Navmesh cutting 을 사용하면 빠르게 그래프를 업데이트할 수 있습니다.
  
  

단점:

• 전체 그래프 업데이트는 그리드 그래프보다 느립니다(Navmesh 절단은 더 빠름).
• Recast 그래프는 태그와 패널티를 잘 표현하지 못합니다.
• 큰 기복이 있는 빈 영역, 예를 들어 나무나 장애물이 없는 언덕은 Recast 그래프로 잘 표현하기 어렵습니다. 타일링을 활성화하면 큰 노드를 분할하는 데 도움이 됩니다.
• 매우 큰 Recast 그래프를 스캔하는 데 시간이 많이 걸릴 수 있습니다. 이는 절차적 세계에는 이상적이지 않을 수 있습니다.
• 시간이 지나면서 부분별로 생성할 수 있어야 합니다.
  
  

참고: Recast graph in a 3D game

A single large grid graph

단일 대형 그리드 그래프는 그리드 그래프가 잘 확장되지 않는 한계를 넘지 않는다면 매우 잘 작동할 수 있습니다. 그리드 그래프는 최대 500x500 노드까지 적절히 확장되며, 정말 필요하다면 1000x1000 노드까지 확장할 수 있습니다. 그 이상은 권장되지 않습니다.

 

장점:

• 설정이 간단합니다.
• 그리드 그래프는 패널티와 태그와 잘 작동합니다.
• 그래프 업데이트가 빠릅니다.
• 그래프 스캔이 비교적 빠릅니다(1000x1000 그래프를 스캔하는 데는 시간이 걸릴 수 있음).
• 전체 맵이 메모리에 동시에 존재하므로 여러 캐릭터가 세계의 다른 부분을 동시에 탐색할 수 있습니다.
  
  

단점:

• 메모리 사용량이 Recast 그래프보다 높습니다.
• 긴 거리의 경로 찾기가 Recast 그래프보다 훨씬 느려질 수 있습니다.
• 매우 큰 세계로 확장되지 않습니다.
  
  

참고: 예제 장면 "Example2"에서 그리드 그래프 예시를 찾을 수 있습니다.

A small moving graph

경로 찾기가 단일 지점 또는 캐릭터(예: 플레이어)를 중심으로 이루어지는 경우, 이동 그리드 또는 Recast 그래프를 사용할 수 있습니다.

이동 그리드/Recast 그래프는 ProceduralGraphMover 스크립트를 활용하는 그래프입니다. 작은 그리드 그래프(예: 100x100) 또는 Recast 그래프가 항상 캐릭터를 중심으로 합니다. 캐릭터가 이동함에 따라 ProceduralGraphMover 는 그래프를 이동시키고 시야에 들어오는 새로운 부분을 스캔하며, 오래된 부분은 버립니다.

여러 개의 작은 그래프가 필요하다면 이를 확장할 수도 있습니다. 각 작은 그래프는 다른 지점 또는 캐릭터를 중심으로 합니다. 그러나 2-4개의 그래프를 초과하면 모든 그래프를 이동하고 업데이트하는 오버헤드가 커질 수 있습니다.

 

Recast 그래프도 사용할 수 있습니다. 이 경우  ProceduralGraphMover는 타일 단위로 작동합니다.

 

장점:

• 패널티와 태그에 잘 작동하는 그리드 그래프 또는 작은 세부 사항을 잘 캡처하는 Recast 그래프를 사용할 수 있습니다.
• 그래프 업데이트가 빠르며, 그래프가 적절히 작게 유지되는 한 스캔 속도가 빠릅니다.
• 이 설정을 사용하면 매우 크거나 심지어 무한히 큰 세계를 쉽게 지원할 수 있습니다.
• 메모리 사용량이 낮습니다.
  
  

단점:

• 경로 찾기는 지정된 캐릭터/지점 주변에서만 가능합니다.
• 긴 거리의 경로 찾기는 불가능하며, 이는 산맥과 같은 큰 장애물을 우회하는 경로를 찾기 어렵게 만들 수 있습니다.
• 캐릭터/지점이 이동할 때마다 그래프를 정기적으로 업데이트해야 하기 때문에 지속적인 오버헤드가 발생합니다.
• 설정이 다소 복잡합니다.
  
  

Infinite procedurally generated world  참조

Conclusion

이 튜토리얼에서는 대규모 세계에서 경로 찾기를 원할 때 고려해야 할 사항과 게임에서 사용할 수 있는 몇 가지 예제 설정에 대해 살펴보았습니다. 다양한 그래프 유형에 대한 자세한 정보는 그래프 유형(Graph Types)을 참조하십시오.