[알고리즘] A* 알고리즘

개요

게임 개발에서 경로 탐색(Pathfinding)은 AI 캐릭터나 오브젝트가 특정 목적지까지 장애물을 피해 최적의 경로를 찾는 데 필수적인 기능이다. 특히 Grid 기반 맵을 사용하는 2D 혹은 3D 게임에서는 대표적인 휴리스틱 기반 탐색 알고리즘인 A* 알고리즘이 자주 사용된다.

---

A*

A* 알고리즘은 BFS의 완전 탐색성과, DFS의 목표 지향적 성격을 적절히 결합한 휴리스틱 기반 최단 경로 탐색 알고리즘이다. 이 알고리즘은 현재 노드에서 시작하여 목표 노드까지의 예상 비용을 기준으로 다음 탐색 노드를 선택한다.

평가 함수 (f(n))

A* 알고리즘은 각 노드에 대해 아래의 평가 함수를 사용하여 우선순위를 계산한다.

f(n) = g(n) + h(n)

• g(n): 시작 노드에서 현재 노드까지의 실제 이동 비용 (이동 거리)

• h(n): 현재 노드에서 목표 노드까지의 휴리스틱(Heuristic) 비용 (예상 이동 거리)

이 두 값을 더하여 가장 비용이 적은 노드를 우선적으로 탐색한다.

휴리스틱 함수 (h)

휴리스틱 함수는 실제 경로가 아닌 예상 경로 비용을 추정한다. 일반적으로 사용되는 휴리스틱 함수는 다음과 같다.

• 맨해튼 거리 (Manhattan Distance)
  4방향(상하좌우) 이동만 가능한 경우 사용.
  h(n) = |x1 - x2| + |y1 - y2|

• 유클리디안 거리 (Euclidean Distance)
  대각선 이동이 가능한 경우 사용.
  h(n) = sqrt((x1 - x2)^2 + (y1 - y2)^2)

• 체비셰프 거리 (Chebyshev Distance)
  8방향 이동이 가능한 경우 사용.
  h(n) = max(|x1 - x2|, |y1 - y2|)

---

알고리즘 작동 방식

1. 시작 노드를 Open 리스트에 추가한다.

2. Open 리스트에서 f(n) 값이 가장 작은 노드를 선택한다.

3. 해당 노드를 Closed 리스트로 이동시키고, 인접 노드들을 탐색한다.

4. 인접 노드가 이동 가능하고(장애물이 아니고), Closed 리스트에 없다면:

5. Open 리스트에 없으면 추가하고 g, h, f 값을 계산.

6. 이미 Open 리스트에 있다면, 현재 경로가 더 효율적인 경우 g 값을 갱신하고 부모 노드를 변경한다.

7. 목표 노드에 도달할 때까지 2~4 과정을 반복한다.

8. 목표 노드에 도달하면 부모 노드를 따라 경로를 재구성한다.

유니티에서의 구현

노드 클래스 (Node)

public class Node
{
    public Vector2Int GridPosition;
    public bool IsWalkable;
    public int GCost;
    public int HCost;
    public int FCost => GCost + HCost;
    public Node Parent;
}

그리드 매니저 (GridManager)

• 게임 맵을 일정한 크기의 그리드로 나눈다.
• 각 그리드 셀은 Node로 구성되며, 이동 가능 여부(IsWalkable)를 가진다.
• 맵의 정보를 기반으로 장애물을 설정한다.

A* 알고리즘 구현

public List<Node> FindPath(Vector2Int start, Vector2Int target)
{
    Node startNode = grid[start.x, start.y];
    Node targetNode = grid[target.x, target.y];

    List<Node> openList = new List<Node> { startNode };
    HashSet<Node> closedList = new HashSet<Node>();

    while (openList.Count > 0)
    {
        Node currentNode = openList.OrderBy(n => n.FCost).ThenBy(n => n.HCost).First();

        if (currentNode == targetNode)
            return RetracePath(startNode, targetNode);

        openList.Remove(currentNode);
        closedList.Add(currentNode);

        foreach (Node neighbor in GetNeighbors(currentNode))
        {
            if (!neighbor.IsWalkable || closedList.Contains(neighbor))
                continue;

            int newMovementCostToNeighbor = currentNode.GCost + GetDistance(currentNode, neighbor);
            if (newMovementCostToNeighbor < neighbor.GCost || !openList.Contains(neighbor))
            {
                neighbor.GCost = newMovementCostToNeighbor;
                neighbor.HCost = GetDistance(neighbor, targetNode);
                neighbor.Parent = currentNode;

                if (!openList.Contains(neighbor))
                    openList.Add(neighbor);
            }
        }
    }

    return null;
}

경로 재구성

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

    while (currentNode != startNode)
    {
        path.Add(currentNode);
        currentNode = currentNode.Parent;
    }

    path.Reverse();
    return path;
}

---

최적화

• Open 리스트를 List 대신 PriorityQueue나 Binary Heap으로 대체하여 성능 개선 가능

• 탐색 대상이 많아질 경우, 전체 그리드 생성 대신 필요 영역만 동적으로 생성

• 휴리스틱 계산이 너무 과도하거나 부정확하면 비효율적인 경로가 도출될 수 있음