A* 알고리즘

 

A*를 이용하여 길을 찾아 보자

게임에서 사용되되는 알고리즘 중 기초적인 알고리즘 중 하나인 A*를 알아보도록 하겠습니다.

 

A* 작동하는 법

[ 참고 ] 

이번 포스팅에서는 A*를 구현하는 방식에 대해서 알려드립니다.

전체적인 소스코드는 따로 주어지지 않습니다. 직접 스크립트를 작성해보며 실력을 기르시기 바랍니다.

---

A* 알고리즘 이란

그래서 A*가 어떤 알고리즘 이냐면 현재의 위치에서 목적지 까지의 최단 경로를 구하는 알고리즘 입니다.

A*에서는 크게 3가지로 구성 되어 있다고 보시면 됩니다.

  1. 현재 노드까지 오는데 필요했던 비용 ( g Cost )

  2. 현재 노드에서 목적지 까지 가는데 필요한 비용 ( h Cost )

  3. 현재 노드에까지 온 비용과 목적지 까지 비용을 합친 비용 ( f Cost )

위에 있는 3가지의 비용을 알아보기 위해서는  A* 알고리즘에서 제일 중요한 역할을 하는 함수 중 하나인 휴리스틱( Heuristic )을 이용해 보도록 하겠습니다.

 

휴리스틱이란?

휴리스틱이란 어려운것이 아닙니다. 간단하게 설명을 해보자면 현재 위치에서 목적지까지 가는데 걸리는 비용을 예측하는 함수라고 생각하시면 됩니다.

함수와 함께 휴리스틱의 값을 구하는 방법을 알아 보도록 하겠습니다.

const int MOVE_STRAIGHT_COST = 10;
const int MOVE_DIAGONAL_COST = 14;

public int Heuristics(Vector2Int _currPosition, Vector2Int _endPosition)
{
    int xDistance = Mathf.Abs(_currPosition.x - endPosition.x);
    int yDistnace = Mathf.Abs(_currPosition.y - _endPosition.y);
    int reming = Mathf.Abs(xDistance - yDistnace);
    return MOVE_DIAGONAL_COST * Mathf.Min(xDistance, yDistnace) + MOVE_STRAIGHT_COST * reming;
}

직선 거리의 값은 10, 대각선의 거리의 값은 14입니다. 이유는 피타고라스 법칙 때문에 대각선은 √2 이기 때문에 14가 되게 됩니다.

 

이값과 거리를 통하여 최단거리의 비용을 예측해보도록 하겠습니다.

  1. x, y 중 가장 짧은 값은 대각선으로 이동하는 거리가 됩니다.

  2. x. y 의 값을 뺀 후 나온값의 절대값은 직선으로 이동해야하는 거리가 되게 됩니다.

직접 계산해 보시면 알 수 있습니다.

 

그래서 A*는 어떻게 만드는 건가요?

기본적인 내용은 알아보았으니 A*를 직접 구해보도록 합시다.

A*는 전체적으로 아래의 일을 반복합니다.

  1. 현재 지점에서 갈 수 있는 모든 노드들의 휴리스틱 값을 구한 후 리스트에 넣어줍니다.

  2. 리스트에 들어간 값중 fCost가 가장 작은 노드를 꺼내 해당 노드에서 갈 수 있는 모든 노드를 리스트에 넣습니다.

 

아래의 코드는 위에 2가지를 반복하는 코드입니다.

while (nextPaths.Count > 0)
{
    PathNode currentNode = GetLowestFCostNode(nextPaths);
    currentNode.obj.GetComponent<Image>().color = Color.green;

    if (currentNode == endNode)
    {
        lastNode = currentNode;
        FindPath(lastNode);
        yield break;
    }

    AddClosePath(currentNode.position);
    nextPaths.Remove(currentNode);

    neighbours = GetNeighbourList(currentNode);

    for (int i = 0; i < neighbours.Count; i++)
    {
        neighbour = neighbours[i];
        if (GetClosePath(neighbour.position) == true) continue;
        int nextGCost = currentNode.gCost + Heuristics(currentNode.position, neighbour.position);
        if (nextGCost < neighbour.gCost)
        {

            neighbour.prevNode = currentNode;
            neighbour.gCost = nextGCost;
            neighbour.hCost = Heuristics(neighbour.position, endPosition);

            if (nextPaths.Contains(neighbour) == false)
            {
                nextPaths.Add(neighbour);
            }
        }
    }
}

---

A*의 단점

많은 사람들이 사용하는 A*에도 단점이 존재합니다. 그건은 바로 넓은 맵을 탐사할 경우 시간이 오래 걸린다는 것입니다.

그 이유는 각각의 노드의 휴리스틱의 값을 구해야 하고, 그 값을 큐나 리스트에 넣은 뒤 다시 fCost가 제일 작은 값을 꺼내 탐색을 해야하기 때문입니다.

 

이러한 단점을 보안한 알고리즘인 JPS 알고리즘은 다음 포스팅을 통해 글을 작성하도록 하겠습니다.

간단하게 JPS에 대해 알려드리자면 갈 수 있는 모든 노드를 리스트에 넣는 것이 아닌 현재 노드에서 갈 수 있는

특정 포인트를 찾아 해당 포인트만 리스트에 넣는 알고리즘 입니다.

 

JPS 알고리즘 알아보러 가기

Jump Point Search 알고리즘 ( C# 소스코드 )