[Algorithm] A* 알고리즘 : 최단 경로 탐색

 

✍️ 인트로

A* 알고리즘은 그래프의 탐색 알고리즘으로

주로 게임에서 플레이어를 목표지점으로 이동시킬 때 사용하는 알고리즘이다.

 

대표적인 그래프 탐색 알고리즘들과 A*의 차이점은

BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘이며

다익스트라는 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단거리를 구하는 그리디 알고리즘이다.

반면 A* 알고리즘은 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만 구하려 하는 그리디 알고리즘이다.

 

[※ 정리 ※]

BFS : 가중치 없는 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 완전 탐색 

다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘

A* : 가중치 그래프, 시작 노드에서 목표 노드까지의 최단 경로만을 구하려 함, 그리디 알고리즘

 

🍊 A* 알고리즘의 개념

다익스트라, A* 모두 그리디 기반의 길 찾기 알고리즘인데
다익스트라는 모든 경로를 구하고
A*는 목적지까지의 경로만을 구하려 하는 이유가 무엇일까?

 

기본적으로 다익스트라 알고리즘은 시작 노드로부터 가장 최소의 비용으로 도달한 노드를 다음 탐색 노드로 선정한다. 

 

반면 A* 알고리즘은 다음 탐색 노드를 선정하는 방식이 다익스트라와 사뭇 다른데, 시작 노드부터 현재 노드까지의 비용을 g(n), 현재 노드에서 목표 노드까지의 예상 비용을 h(n)이라 할 때, 이 두 값을 더한 f(n) = g(n) + h(n)이 가장 최소가 되는 노드를 다음 탐색 노드로 선정한다. 일반적으로 가장 작은 f(n)을 찾기 위해 우선순위 큐가 사용된다.

현재 노드에서 목표 노드까지의 예상 비용을 구하는 함수 h(n)을 휴리스틱 함수라 하며 휴리스틱 함수를 설계하는 방법에 따라서 알고리즘의 성능이 결정된다. 가장 단순하며 대표적인 휴리스틱 함수로 맨해튼 거리 함수와 유클리디안 거리 함수가 있으며 본 포스팅에선 맨해튼 거리를 이용해서 길 찾기 코드를 작성할 예정이다.

 

간단하게 예제를 살펴보면 시작 노드(A)와 목표 노드(B)가 있을 때, A 주변 노드의 f(n)을 구하면 다음과 같다.

8개의 노드 중 f(n)이 가장 작은 ↖방향 노드를 다음 탐색 노드로 선정하고 ↖방향 주변 노드의 f(n)을 다시 구한다.

( h(n) = 유클리디안 거리 함수 )

 

이처럼 가장 작은 f(n)을 가진 노드를 찾아가고 다시 주변 노드의 f(n)을 계산하고 찾아가고 계산하는 과정을 반복하면 목표 노드인 B에 도착할 수 있다.

예제 영상

A* Pathfinding (E01: algorithm explanation)

 

여기까지 이해가 됐다면 자연스럽게 한 가지 사실을 알 수 있는데 h(n) = 0일 때 즉, f(n) = g(n) 일 때 A* 알고리즘은 다익스트라 알고리즘과 동일하게 동작한다는 것이다.

 

쉽게 이해하기 위해 다익스트라와 A*를 비교한 유튜브 영상을 한 번쯤 시청하시길 바랍니다.

다익스트라 vs A* 눈으로 이해하기

Motion Planning Algorithms - A* vs Dijkstra's

 

🖥️ A* 알고리즘, 코드

private void AStar()
{
    int[] dirY = new int[] { -1, 0, 1, 0,  -1, 1, 1, -1 };
    int[] dirX = new int[] { 0, -1, 0, 1, -1, -1, 1, 1 };
    int[] cost = new int[] { 10, 10, 10, 10, 14, 14, 14, 14};

    bool[,] closed = new bool[_board.Size, _board.Size];
    int[,] open = new int[_board.Size, _board.Size];
    PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();
    Pos[,] parent = new Pos[_board.Size, _board.Size];

    for (int y = 0; y < _board.Size; y++)
        for (int x = 0; x < _board.Size; x++)
            open[y, x] = Int32.MaxValue;

    //시작점 발견
    open[PosY, PosX] = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX));
    pq.Push(new PQNode() { F = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX)), G = 0, Y = PosY, X = PosX });
    parent[PosY, PosX] = new Pos(PosY, PosX);

    //제일 좋은 후보 찾기
    while (pq.Count() > 0)
    {
        PQNode node = pq.Pop();

        //이미 방문했으면 스킵
        if (closed[node.Y, node.X])
            continue;

        //f(n)이 가장 작은 노드 방문 완료
        closed[node.Y, node.X] = true;

        if (node.Y == _board.DestY && node.X == _board.DestX)
            break;

        for (int i = 0; i < dirY.Length; i++)
        {
            int nextY = node.Y + dirY[i];
            int nextX = node.X + dirX[i];

            //유효범위 체크
            if (nextX < 0 || nextX >= _board.Size || nextY < 0 || nextY >= _board.Size)
                continue;
            if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
                continue;
            if (closed[nextY, nextX])
                continue;

            int g = node.G + cost[i];
            int h = 10 * (Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX));

            if (open[nextY, nextX] < g + h)
                continue;

            open[nextY, nextX] = g + h;
            pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX });
            parent[nextY, nextX] = new Pos(node.Y, node.X);
        }
    }

    CalcPathFromParent(parent);
}

대각선으로 잘 찾아간다.

벽이 있어도 잘 찾아간다.

 

👋 마치며

시간이 된다면 코드를 깃에 업로드하고 링크 올리겠습니다.