[Unity ER] A Star*, Funnel Algorithm

PathFind Algorithm (A-Star)*

- 출발점에서 목적지까지의 최적의 경로를 찾는 알고리즘

1. F(총 비용) = G(현재 비용) + H(예상 비용) 조건에 따른다.

 

문제점

- A Star를 구현한 후 Monster의 경로를 테스트했을 때 최적의 경로로 짜여지지 않았다.

- 네비 메시 데이터를 저장할 때 Vertex/Index로 저장해서 Center 값을 구해서 그대로 그 Center 위치 값을

 

현재 경로에 집어넣었던 것이 원인이었다.

- 그래서 다른 방법을 고민했을 때 Funnel Algorithm에 대해서 알게 되었다. 

- 많은 자료가 존재하지 않아 찾아보던 과정에서 dotsnav의 오픈 소스를 찾게 되었다.

https://github.com/dotsnav/dotsnav

GitHub - dotsnav/dotsnav: A fully dynamic planar navmesh for Unity supporting agents of any size

 

 

해결점 1 : 리팩토링

- Navigation 자체를 구현한 오픈 소스로 참고하기 좋았다고 생각한다.

- 구현 기술에서 쿼드 트리를 사용하고, 내가 짠 코드와 다르게 PathFind에 대한 상세한 오류를 반환한 점이 인상 깊었다.

- 기존 로직은 하나의 클래스에 모든 AI 구현 코드를 집어넣었다.

- 리팩토링 한 코드의 경우는 최대한 단일 책임 원칙을 지킬 수 있도록 구현했다.

 

해결점 2 : Funnel Algorithm

- Funnel 구현 코드를 분석한 결과 해당 코드를 구현하는 방식은 다음과 같다.

1. AI가 가는 경로의 폴리곤의 이웃 노드와 공유된 변을 구해야 한다. 공유된 변의 Left와 Right Edge를 구하기 위함이다.

2. apex를 기준으로 Left Edge와 Right Edge를 외적한다. 

     => 외적의 경우 (0 <= value)는 반시계 방향, 왼쪽, (0 > value)는 시계 방향 오른쪽을 나타낼 것이다.

3. 단순히 생각하면 apex을 기준으로 L와 R를 점점 공통된 값이 나올 수 있도록 조여올 것이다.

    => Left Edge는 시계 방향, Right Edge는 반시계 방향의 값이 나와야 조여올 수 있다.

    => 순차적으로 외적을 하게 되면 어느 순간 L,R Edge가 겹치는 걸 넣어서 선이 역으로 꼬이게 되는데

         그 Edge 지점이 AI가 앞으로 향할 경로다.

for (int i = 0; i < channel.Count; i++)
{
    Gate currentGate = channel[i];

    Vector3 currentLeft = currentGate.Left;
    Vector3 currentRight = currentGate.Right;

    // 1. 새로운 정점이 왼쪽 경계를 좁히는 경우
    if (Cross(new Vector2(portalLeft.X - apex.X, portalLeft.Z - apex.Z),
              new Vector2(currentLeft.X - apex.X, currentLeft.Z - apex.Z)) <= 0)
    {
        if (Cross(new Vector2(currentLeft.X - apex.X, currentLeft.Z - apex.Z),
                  new Vector2(portalRight.X - apex.X, portalRight.Z - apex.Z)) > 0)
        {
            output.AddToBack(new Node(portalRight, Node.NodeType.Point)); 
            apex = portalRight;
            portalLeft = apex;
            portalRight = apex;
            i = rightIndex; 
            continue;
        }

        portalLeft = currentLeft;
        leftIndex = i;
    }

    // 2. 새로운 정점이 오른쪽 경계를 좁히는 경우
    if (Cross(new Vector2(portalRight.X - apex.X, portalRight.Z - apex.Z),
              new Vector2(currentRight.X - apex.X, currentRight.Z - apex.Z)) >= 0)
    {
        if (Cross(new Vector2(currentRight.X - apex.X, currentRight.Z - apex.Z),
                  new Vector2(portalLeft.X - apex.X, portalLeft.Z - apex.Z)) < 0)
        {
            output.AddToBack(new Node(portalLeft, Node.NodeType.Point)); 
            apex = portalLeft;
            portalLeft = apex;
            portalRight = apex;
            i = leftIndex; 
            continue;
        }

        portalRight = currentRight;
        rightIndex = i;
    }
}

   public float Cross(Vector2 a, Vector2 b)
   {
       return a.X * b.Y - a.Y * b.X;
   }

 

최적화 1 : 분할 공간

- A Star를 구현할 당시 Start Point와 Target Point의 노드를 찾기 위해 처음에는 모든 노드를 순회하여 가장 가까운 노드를 가져오는 방식으로 구현했다.

- 쿼드 트리를 사용하는 것이 좋다고 생각했지만, 맵이 크지 않았기에 문제가 되지 않을 것이라고 생각했다.

 private void BuildSpatialGrid()
 {
     foreach (var node in _triangleNodes)
     {
         int gridX = (int)(node.Center.X / GRID_SIZE);
         int gridZ = (int)(node.Center.Z / GRID_SIZE);
         var key = (gridX, gridZ);

         if (!_spatialGrid.ContainsKey(key))
             _spatialGrid[key] = new List<Node>();

         _spatialGrid[key].Add(node);
     }
 }

- 초반 세팅에 노드를 분할해서 Dictionary에 저장했다.

   
   public Node FindNearestNode(Vector3 position)
   {
       int gridX = (int)(position.X / GRID_SIZE);
       int gridZ = (int)(position.Z / GRID_SIZE);

       float minDistance = float.MaxValue;
       Node nearestNode = null;

       // 주변 9개 그리드만 검색
       for (int dx = -1; dx <= 1; dx++)
       {
           for (int dz = -1; dz <= 1; dz++)
           {
               var key = (gridX + dx, gridZ + dz);

               if (!_spatialGrid.TryGetValue(key, out List<Node> nodes))
                   continue;

               foreach (var node in nodes)
               {
                   float dx2 = node.Center.X - position.X;
                   float dy2 = node.Center.Y - position.Y;
                   float dz2 = node.Center.Z - position.Z;
                   float distanceSq = dx2 * dx2 + dy2 * dy2 + dz2 * dz2;

                   if (distanceSq < minDistance * minDistance)
                   {
                       minDistance = (float)Math.Sqrt(distanceSq);
                       nearestNode = node;
                   }
               }
           }
       }
       if (minDistance * minDistance > MAX_SEARCH_DIST_SQ)
           return null;

       return nearestNode;
   }

- O(n)이 걸리던 노드 찾기로 계속 플레이 반응 속도가 느렸지만, 그리드로 분할함으로써 반응이 확연히 빨라지는 것을 느낄 수 있었다.

최적화 2 : 역추적 : 계산 비용 줄이기

- 원래 역추적을 수행했을 때 Node 안에 저장된 Parent (이전 노드를 저장한 Node 변수)을 통해서 Reverse 해서 경로를 탐색시킨 후 Funnel 알고리즘을 위한 공유된 변을 찾는 과정은 Funnel에서 그 정점마다 계속해서 변환하는 과정을 거쳤다.

- dotsnav를 분석했을 때 Funnel 알고리즘에 넘기기 전의 정보가 연결된 변의 정보를 저장하여 이러한 구조체를 넘기는 것을 확인할 수 있었다.

  struct Gate
  {
      public Vector3 Left;
      public Vector3 Right;
      public bool IsGoalGate;
  }

 

- Funnel 알고리즘을 사용하는 와중에 연결된 변을 확인하는 부분이 이보다 확실하게 역할을 분할해서 데이터 구조화를 더 간소화 시킬 수 있는 부분이라 생각했고, 한 번에 처리하는 것 계산 처리 과정에서 검색 시간이 효율적으로 줄 수 있을 거라 생각해 변경했다.

 List<Gate> RetracePath(Node startNode, Node endNode)
 {
     List<Node> nodePath = new List<Node>();
     Node currentNode = endNode;

     while (currentNode != null)
     {
         nodePath.Add(currentNode);
         currentNode = currentNode.Parent;
     }
     nodePath.Reverse();

     List<Gate> gateChannel = new List<Gate>();

     for (int i = 0; i < nodePath.Count - 1; i++)
     {
         Node nodeA = nodePath[i];
         Node nodeB = nodePath[i + 1];

         Gate gate;
         if (GetSharedEdge(nodeA, nodeB, out gate) == PathState.PathFound)
             gateChannel.Add(gate);
     }
     return gateChannel;
 }

 // 두 삼각형 간의 공유된 변 찾기.
 private PathState GetSharedEdge(Node nodeA, Node nodeB, out Gate gate)
 {
     gate = new Gate();

     int triAStart = nodeA.Index * 3;
     int triBStart = nodeB.Index * 3;

     int common1 = -1;
     int common2 = -1;
     int foundCount = 0;

     for (int i = 0; i < 3 && foundCount < 2; i++)
     {
         int vA = _navMeshData.triangles[triAStart + i];

         for (int j = 0; j < 3; j++)
         {
             int vB = _navMeshData.triangles[triBStart + j];

             if (vA == vB)
             {
                 if (foundCount == 0)
                     common1 = vA;
                 else if (foundCount == 1)
                     common2 = vA;

                 foundCount++;
                 break;
             }
         }
     }

     if (foundCount == 2)
     {
         Vector3 v1 = _navMeshData.vertices[common1];
         Vector3 v2 = _navMeshData.vertices[common2];

         gate.Left = v1;
         gate.Right = v2;
         return PathState.PathFound;
     }

     return PathState.EdgeInvalid;
 }

 

결과물

1. 플레이어에게 AI 적용

 

2. 몬스터에게 AI 적용