A* 알고리즘 경로 판단하기

김효중·2025년 4월 8일

개요

타워 디펜스 게임을 만들던중 3D이므로 NavMesh를 사용하여 적의 움직임을 구현할 수 있으나
타워를 설치할 때마다 적의 이동경로가 변경되게 할 필요가 있었다.
특히 타워를 설치할 때 타워 설치될 공간을 판단하여 경로를 모두 막는지 확인하고
경로를 모두 막고 있다면 설치가 안되게 할 필요가 있었다.

예) 언더 다크

그렇기에 NavMesh와는 별개로 경로를 탐색할 필요가 있었다.
이때 경로가 유효한지는 대각선 이동이 불가능하고 도착지점(기지)까지 이동이 가능한지 판단한다.

A* vs JPS

A와 JPS는 모두 길찾기 알고리즘이다.
A 알고리즘은 경로 기반 그래프를 탐색하며 최단 경로를 찾는다.
휴리스틱을 사용하여 예상 거리를 계산하고 탐색 속도를 개선한다.

JPS(Jump Point Search)는 A 알고리즘을 개선하여 고속화 시킨 알고리즘이다.
A는 모든 방향의 이웃 노드를 탐색하는데 JPS는 노드 탐색을 최소화 시켜
장애물과 같이 중요한 분기점만을 탐색하여 속도가 빠르다.
또한 직선을 빠르게 탐색할 수 있어 속도가 빠르다.

A와 JPS를 비교하였을 때는 JPS가 더 빠르지만
해당 프로젝트는 대각선 이동이 불가능하므로 A 알고리즘을 사용한다.

A* 알고리즘 코드

경로 자체를 반환하는 것이 아니라 "길이 존재하는가?" 여부만 빠르게 확인하고자 하여 만들었다.

사전조건
정수 배열 tileMap[x, y]은 2D 타일 맵을 나타낸다.
타일의 값이 2이면 벽 또는 통과 불가한 타일로 간주한다.
대각선 이동은 허용하지 않고, 네 방향(상/하/좌/우)만 이동 가능하다.
start와 end는 각각 시작 지점과 목표 지점이다.

public static int Heuristic(Vector2Int a, Vector2Int b)
    {
        return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
    }
// 경로가 존재하는지 검사, a*
    public bool FindPathAStar(Vector2Int start, Vector2Int end)
    {
        int width = tileMap.GetLength(0);
        int height = tileMap.GetLength(1);

        HashSet<Vector2Int> closeSet = new HashSet<Vector2Int>();
        PriorityQueue<Vector2Int> openSet = new PriorityQueue<Vector2Int>();
        // 출발점
        openSet.Enqueue(start, 0);

        Dictionary<Vector2Int, int> gScore = new Dictionary<Vector2Int, int>
        {
            [start] = 0
        };

        Vector2Int[] directions = new Vector2Int[]
        {
            Vector2Int.up, Vector2Int.down, Vector2Int.left, Vector2Int.right
        };

        while (openSet.Count > 0)
        {
            Vector2Int current = openSet.Dequeue();
            if (current == end)
            {
                // 도착 지점 도착
                return true;
            }

            closeSet.Add(current);

            foreach (var dir in directions)
            {
                // 방향에 따른 탐색 지점
                Vector2Int neighbor = current + dir;

                // 범위 조건 확인
                if (neighbor.x < 0 || neighbor.x >= width || neighbor.y < 0 || neighbor.y >= height)
                {
                    continue;
                }
                // 벽인지 확인
                if (tileMap[neighbor.x, neighbor.y] == 2 || closeSet.Contains(neighbor))
                {
                    continue;
                }

                // 거리 비교하여 추가
                int tentativeG = gScore[current] + 1;

                if (!gScore.ContainsKey(neighbor) || tentativeG < gScore[neighbor])
                {
                    gScore[neighbor] = tentativeG;
                    int fScore = tentativeG + Heuristic(neighbor, end);
                    openSet.Enqueue(neighbor, fScore);
                }
            }
        }
        return false; // 경로 없음
    }