08/12 AI Navigation - NavMesh 제작 및 사용하기

F(x) = G(x) + H(x)

F : 예상 최종 거리       - 이 칸을 거쳐 가면 총 얼마나 걸릴 것 같은가  
G : 지금까지 걸린 거리   - 시작점에서 이 칸까지 실제로 든 비용  
H : 남은 예상 거리       - 이 칸에서 목적지까지 대략 얼마나 남았는가 (휴리스틱)

// 경로를 탐색하는 함수
    public List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal)
    {
        // [준비]
        // openList: 앞으로 탐색할 후보 노드들
        // closedList: 이미 확정된 노드들(다시 안 봄)
        List<Node> openList = new List<Node>();
        List<Vector2Int> closedList = new List<Vector2Int>();

        // 같은 좌표의 Node를 매번 만들지 않도록 좌표를 통해 노드를 찾을 수 있도록 해준다.
        Dictionary<Vector2Int, Node> nodes = new Dictionary<Vector2Int, Node>();

        // [시작]
        // 시작 노드의 G = 0, H = 휴리스틱 계산
        Node startNode = new Node(start, true)
        {
            G = 0,
            H = GetDistance(start, goal)
        };
        // 시작 노드를 openList에 추가
        openList.Add(startNode);
        nodes[start] = startNode;

        // [반복] openList가 비어있지 않은 동안
        while (openList.Count > 0)
        {
            //   ① openList에서 F가 가장 낮은 노드를 고른다
            //        (F가 같으면 H가 낮은 쪽)
            Node current = openList[0];

            // F와 H를 비교해서 가장 낮은 것을 찾아준다.
            for (int i = 1; i < openList.Count; i++)
            {
                bool isBetterF = openList[i].F < current.F;
                bool isBetterH = openList[i].F == current.F && openList[i].H < current.H;

                if (isBetterF || isBetterH)
                {
                    current = openList[i];
                }
            }
            //   ② 그 노드를 openList에서 빼고 closedList에 넣는다  
            openList.Remove(current);
            closedList.Add(current.position);


            //   ③ 그 노드가 목적지면 → 경로를 역추적하고 종료
            if (current.position == goal)
            {
                return RetracePath(startNode, current);
            }

            //   ④ 그 노드의 이웃 칸들을 하나씩 확인한다
            foreach (Vector2Int dir in Directions)
            {
                Vector2Int neighborPos = current.position + dir;

                // 격자 밖이거나
                if (!IsInsideGrid(neighborPos))
                {
                    continue;
                }
                // 벽이면 건너뛴다
                if (!map[neighborPos.x, neighborPos.y])
                {
                    continue;
                }
                // 이미 closedList에 있으면 건너뛴다 == 이미 확정된 칸이면 건너뛴다.
                if (closedList.Contains(neighborPos))
                {
                    continue;
                }
                // 대각선이면 인접한 수직·수평이 모두 열려있는지 확인
                if (IsDiagonal(dir) && !CanMoveDiagonally(current.position, dir))
                {
                    continue;
                }
                // 새 G = 현재 노드의 G +이동 비용(직선 10 / 대각선 14)
                int moveCost = IsDiagonal(dir) ? DIAGONAL_COST : STRAIGHT_COST;
                int newG = current.G + moveCost;

                // 현재 위치에 만들어진 노드가 존재하지 않는 경우
                // openList에 중복으로 들어가게 되는 현상을 막기위해
                if (!nodes.TryGetValue(neighborPos, out Node neighborNode))
                {
                    // 새로 노드를 만들어 준다.
                    neighborNode = new Node(neighborPos, true);
                    nodes[neighborPos] = neighborNode;
                }

                bool isOpenListExist = openList.Contains(neighborNode);

                // 새 G가 기존에 기록된 G보다 작거나, openList에 없다면
                if (newG < neighborNode.G || !isOpenListExist)
                {
                    // G, H를 갱신하고  
                    neighborNode.G = newG;
                    neighborNode.H = GetDistance(neighborPos, goal);

                    // 부모(어디서 왔는지)를 현재 노드로 기록하고  
                    neighborNode.parent = current;

                    // openList에 없으면 openList 추가까지 진행.
                    if (!isOpenListExist)
                    {
                        openList.Add(neighborNode);
                    }
                }
            }
        }
        // [종료]
        // openList가 비었는데 목적지에 도달하지 못했다면 → 경로 없음
        return null;
    }