Agent-Specific Pathfinding

때로는 각 에이전트마다 경로 탐색을 맞춤화해야 할 필요가 있습니다.

예를 들어, 일부 에이전트가 물을 피하게 하거나, 일부 에이전트가 도로에서 걷는 것을 선호하게 할 수 있습니다. 일부 게임에서는 모든 에이전트에 대해 고유한 경로 탐색 규칙이 필요할 수도 있습니다.

이 페이지에서는 각 옵션의 장단점을 설명하며, 다양한 방법으로 이를 수행하는 방법을 안내합니다.

• Alternatives
• The ITraversalProvider interface
• Case Studies
  • Ships and peasants
  • Turn based games
  • Multiple agent sizes
  • Prefering road

 

Alternatives

다음 몇 가지 옵션이 있습니다:

• 태그 사용. 모든 노드는 0에서 31까지의 단일 태그를 할당받을 수 있습니다. 각 에이전트마다 특정 태그가 통행 가능해야 하는지, 또는 이를 통과하는 비용이 얼마나 될지 결정할 수 있습니다. 태그에 대해 더 알아보려면 여기를 참조하십시오: Working with tags . 이것은 경로 탐색을 맞춤화하는 매우 간단한 방법이지만, 할 수 있는 일에 제한이 있습니다.
  
  
• 여러 그래프 사용. 다른 에이전트가 극적으로 다른 네비게이션 메쉬를 필요로 하는 경우, 여러 그래프를 사용하는 것이 좋은 옵션이 될 수 있습니다. 그러나 많은 그래프를 관리하는 것은 번거롭고 메모리와 성능에 부담이 될 수 있으므로, 소수의 그래프만 필요할 때에만 합리적입니다. 이것은 매우 견고한 옵션이며, 메모리와 성능을 약간 희생하여 최대한의 유연성을 제공합니다. 여러 그래프에 대해 더 알아보려면 여기를 참조하십시오: Multiple agent types.
  
  
• 각 경로 탐색 요청에 대해 각 노드의 통행 가능성과 패널티를 개별적으로 완전히 제어하려면 ITraversalProvider인터페이스를 사용하십시오. 이 옵션은 매우 유연하지만 가장 복잡한 옵션으로, 코드를 작성해야 합니다. 자세한 내용은 아래를 참조하십시오.

 

ITraversalProvider 인터페이스

모든 경로는  traversalProvider를 할당받을 수 있으며, 이 인터페이스에는 재정의해야 하는 세 가지 메서드가 있습니다.

bool CanTraverse (Path path, GraphNode node);
bool CanTraverse (Path path, GraphNode from, GraphNode to);
uint GetTraversalCost (Path path, GraphNode node);

 

CanTraverse(path, node) 메서드는 유닛이 해당 노드를 통과할 수 있는지 여부에 따라 true 또는 false를 반환해야 합니다. CanTraverse(path, from, to) 메서드는 유닛이 from에서 to로의 연결을 통과할 수 있는 경우 true를 반환해야 합니다. 기본적으로 이 메서드는 CanTraverse(path, to)와 동일한 값을 반환하도록 전달됩니다. GetTraversalCost 메서드는 해당 노드를 통과하는 추가 비용을 반환해야 합니다. 기본적으로 태그나 패널티가 사용되지 않는 경우 통과 비용은 0입니다. 비용이 1000인 경우 대략 1 월드 유닛을 이동하는 비용에 해당합니다.

참고로, 기본 구현은 다음과 동일합니다.

public class MyCustomTraversalProvider : ITraversalProvider {
    public bool CanTraverse (Path path, GraphNode node) {
        // 노드가 통행 가능하고 'enabledTags' 비트마스크가 노드의 태그를 포함하는지 확인합니다.
        return node.Walkable && (path.enabledTags >> (int)node.Tag & 0x1) != 0;
        // 또는:
        // return DefaultITraversalProvider.CanTraverse(path, node);
    }

    public bool CanTraverse (Path path, GraphNode from, GraphNode to) {
        return CanTraverse(path, to);
    }
    public uint GetTraversalCost (Path path, GraphNode node) {
        // 통행 비용은 노드의 태그 패널티와 노드의 패널티의 합입니다.
        return path.GetTagPenalty((int)node.Tag) + node.Penalty;
        // 또는:
        // return DefaultITraversalProvider.GetTraversalCost(path, node);
    }

    // Unity 2021.3 및 이후 버전에서는 기본 구현(반환 값 true)을 사용할 수 있으므로 이 코드는 생략할 수 있습니다.
    public bool filterDiagonalGridConnections {
        get {
            return true;
        }
    }
}

사용자 정의 ITraversalProvider 를 구현하면 게임의 규칙에 맞게 패널티를 원하는 대로 변경할 수 있습니다. 성능상의 이유로 그리드 그래프는 통행 불가능한 노드에 대한 모든 연결을 제거하므로, 트래버설 프로바이더에서 "node.Walkable &&" 부분을 제거하더라도 그리드 그래프의 경로는 여전히 통행 불가능한 노드를 통과하지 않습니다. 다시 말해, 노드를 통행 불가능하게 만들 수는 있지만, 통행 불가능한 노드를 다시 통행 가능하게 만들 수는 없습니다.

경고 멀티스레딩이 활성화된 경우, ITraversalProvider의 메서드는 별도의 스레드에서 호출됩니다. 이는 Unity API의 어느 부분도 사용할 수 없다는 것을 의미합니다(수학 같은 것은 예외). 또한, 코드가 스레드 안전(thread safe)하도록 해야 합니다.

ITraversalProvider를 구현한 후에는 앞서 설명한 것처럼 이를 경로에 할당할 수 있습니다.
Seeker 컴포넌트에 설정하여, 해당 Seeker가 계산하는 모든 경로가 해당 트래버설 프로바이더를 사용하도록 할 수 있습니다:

seeker.traversalProvider = new MyCustomTraversalProvider();

또는 경로에 직접 설정하여:

var path = ABPath.Construct(...);
path.traversalProvider = new MyCustomTraversalProvider();

 FollowerEntity 컴포넌트를 사용하는 경우, 경로 탐색 설정에서 트래버설 프로바이더를 설정할 수 있습니다:

followerEntity.pathfindingSettings.traversalProvider = new MyCustomTraversalProvider();

참조 ITraversalProvider를 사용하는 또 다른 예시는 여기에서 확인할 수 있습니다: CircuitBoardExample.cs

 

Case Studies

다음은 몇 가지 일반적인 시나리오와 이를 해결하는 방법에 대한 사례 연구입니다.

Ships and peasants

중세 시대의 농민들이 섬에서 농사를 짓고 화물선이 바다를 항해하는 게임을 가정해봅시다. 농민은 육지에서 걸을 수 있어야 하지만 물에서는 걸을 수 없어야 합니다. 반면 배는 물에서 항해할 수 있어야 하지만 육지에서는 이동할 수 없어야 합니다.

이 경우, 여러 개의 그래프를 사용하는 것을 추천합니다. 하나는 육지를 위한 그래프, 다른 하나는 물을 위한 그래프입니다. 그런 다음 Seeker 인스펙터에서 적절한 그래프를 선택하여 에이전트가 사용할 그래프를 선택할 수 있습니다.

그 이유는 배와 농민이 공통된 표면을 이동할 수 없기 때문에, 이들을 위한 별도의 그래프를 갖는 것이 합리적입니다. 이렇게 하면 각 에이전트 유형에 맞게 그래프를 조정하기도 더 쉬워집니다. 예를 들어, 배가 해안에 너무 가까이 이동하는 것을 원치 않겠지만, 농민은 장애물에서 수 미터 떨어진 곳을 문제없이 걸을 수 있어야 합니다.

그리드 그래프를 사용하는 경우, 태그를 사용하여 농민을 섬에, 배를 물에 제한하는 방식으로 이 문제를 해결할 수도 있습니다. 이것은 가능하지만 설정하는 데 약간 더 번거로울 수 있습니다.

Turn based games

턴제 게임에서는 유닛이 같은 타일에 서지 못하도록 방지하고 싶어합니다. 하지만 현재 유닛이 서 있는 타일에는 서 있을 수 있어야 합니다. 턴제 게임에서는 종종 다른 유닛에 대해 서로 다른 이동 비용이 있으며, 이러한 규칙은 매우 복잡할 수 있습니다.

이것은  ITraversalProvider 인터페이스를 사용하여 이 로직을 구현하는 명확한 사례입니다. 다행히도, 이 경우를 위해 이미 구현된 편리한 도우미들이 있습니다.  Utilities for turn-based games 를 살펴보세요.

Multiple agent sizes

일부 게임에서는 매우 다양한 크기의 에이전트를 가지고 있습니다. 이 경우는 매우 흔하여 별도의 페이지가 있습니다! 여기에서 확인해보세요:  Multiple agent types.

Prefering roads

일부 게임에서는 유닛이 도로에서 걷는 것을 선호하게 하고 싶지만, 필요할 경우 다른 표면에서도 걸을 수 있도록 하고 싶습니다. 이는 태그를 사용하여 도로를 표시하고 태그 기반 패널티를 사용하여 유닛이 다른 표면을 피하려고 하도록 함으로써 가능합니다.

태그 패널티는 음수일 수 없으므로, 음수 패널티를 사용하여 유닛이 도로를 선호하게 만들 수는 없습니다. 대신, 도로가 아닌 모든 노드에 양수 패널티를 적용합니다.

이 기술은 그리드 그래프에서 가장 잘 작동합니다. 그리드 그래프에서 패널티를 사용하는 것은 예측 가능하고 설정하기 쉬우며 세분성이 좋기 때문입니다. 네비메쉬/리캐스트 그래프에서 패널티를 사용하는 Pathfinding은 본질적으로 덜 정밀합니다. 왜냐하면 노드가 더 크기 때문입니다.