알고리즘 - A*에 대해 알아보자

오늘은 A*알고리즘에 대해 정리해 보고자 합니다.

 

A* 알고리즘

A*알고리즘은 대표적인 길 찾기 알고리즘으로서 

보통 A* 같은 알고리즘을 휴리스틱(heuristic) 하다고 설명하던데

간단히 정리하자면  "경험에 기반하여 문제를 해결하는 방식" 정도로 이해하시면 됩니다.

 

완벽하게 입증되진 않았지만

대신 실용적이고 어느 정도 빠르게 원하는 답에 접근할 수 있기에

이러한 방식을 사용하는 듯합니다.

 

공식으로 정리하자면 다음과 같습니다.

 

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

 

 

• g(n): 시작 노드에서 현재 노드까지의 실제 비용
• h(n): 현재 노드에서 목표 노드까지의 추정 비용(휴리스틱)
• f(n): 총 예상 비용

 

 

추정 비용에 원하는/해당하는 가중치를 줌으로써,

휴리스틱한 함수가 적절하다면 항상 최적의 경로를 찾는다는 게 핵심입니다. 

 

2D 게임 환경에서 많이 사용된다고 합니다.

 

진행 과정 

 

1) 시작 노드부터 탐색 시작

2) 현재 노드의 인접한 노드들을 열린 목록(open list)에 추가

3) f(n)이 가장 작은 노드를 선택하여 탐색

4) 탐색한 노드는 닫힌 목록(closed list)에 추가

5) 목표 노드에 도달할 때까지 이 과정을 반복

 

 

 

예시 

 

GPT를 통해 생성한 코드

using UnityEngine;
using System.Collections.Generic;

public class Node
{
    public bool walkable;
    public Vector3 worldPosition;
    public int gridX;
    public int gridY;
    
    public int gCost;
    public int hCost;
    public Node parent;
    
    public int fCost
    {
        get { return gCost + hCost; }
    }
    
    public Node(bool _walkable, Vector3 _worldPos, int _gridX, int _gridY)
    {
        walkable = _walkable;
        worldPosition = _worldPos;
        gridX = _gridX;
        gridY = _gridY;
    }
}

public class Grid : MonoBehaviour
{
    public LayerMask unwalkableMask;
    public Vector2 gridWorldSize;
    public float nodeRadius;
    Node[,] grid;
    
    float nodeDiameter;
    int gridSizeX, gridSizeY;
    
    void Start()
    {
        nodeDiameter = nodeRadius * 2;
        gridSizeX = Mathf.RoundToInt(gridWorldSize.x / nodeDiameter);
        gridSizeY = Mathf.RoundToInt(gridWorldSize.y / nodeDiameter);
        CreateGrid();
    }
    
    void CreateGrid()
    {
        grid = new Node[gridSizeX, gridSizeY];
        Vector3 worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x/2 - Vector3.forward * gridWorldSize.y/2;
        
        for (int x = 0; x < gridSizeX; x++)
        {
            for (int y = 0; y < gridSizeY; y++)
            {
                Vector3 worldPoint = worldBottomLeft + Vector3.right * (x * nodeDiameter + nodeRadius) + Vector3.forward * (y * nodeDiameter + nodeRadius);
                bool walkable = !(Physics.CheckSphere(worldPoint, nodeRadius, unwalkableMask));
                grid[x,y] = new Node(walkable, worldPoint, x, y);
            }
        }
    }
    
    public List<Node> GetNeighbors(Node node)
    {
        List<Node> neighbors = new List<Node>();
        
        for (int x = -1; x <= 1; x++)
        {
            for (int y = -1; y <= 1; y++)
            {
                if (x == 0 && y == 0)
                    continue;
                    
                int checkX = node.gridX + x;
                int checkY = node.gridY + y;
                
                if (checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)
                {
                    neighbors.Add(grid[checkX,checkY]);
                }
            }
        }
        
        return neighbors;
    }
}

public class Pathfinding : MonoBehaviour
{
    public Grid grid;
    
    public List<Node> FindPath(Vector3 startPos, Vector3 targetPos)
    {
        Node startNode = grid.NodeFromWorldPoint(startPos);
        Node targetNode = grid.NodeFromWorldPoint(targetPos);
        
        List<Node> openSet = new List<Node>();
        HashSet<Node> closedSet = new HashSet<Node>();
        openSet.Add(startNode);
        
        while (openSet.Count > 0)
        {
            Node currentNode = openSet[0];
            for (int i = 1; i < openSet.Count; i++)
            {
                if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost)
                {
                    currentNode = openSet[i];
                }
            }
            
            openSet.Remove(currentNode);
            closedSet.Add(currentNode);
            
            if (currentNode == targetNode)
            {
                return RetracePath(startNode, targetNode);
            }
            
            foreach (Node neighbor in grid.GetNeighbors(currentNode))
            {
                if (!neighbor.walkable || closedSet.Contains(neighbor))
                {
                    continue;
                }
                
                int newMovementCostToNeighbor = currentNode.gCost + GetDistance(currentNode, neighbor);
                if (newMovementCostToNeighbor < neighbor.gCost || !openSet.Contains(neighbor))
                {
                    neighbor.gCost = newMovementCostToNeighbor;
                    neighbor.hCost = GetDistance(neighbor, targetNode);
                    neighbor.parent = currentNode;
                    
                    if (!openSet.Contains(neighbor))
                        openSet.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;
    }
    
    int GetDistance(Node nodeA, Node nodeB)
    {
        int dstX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
        int dstY = Mathf.Abs(nodeA.gridY - nodeB.gridY);
        
        if (dstX > dstY)
            return 14 * dstY + 10 * (dstX - dstY);
        return 14 * dstX + 10 * (dstY - dstX);
    }
}

 

 

• Node 클래스:
  • 각 그리드 셀의 정보를 저장
  • walkable 여부, 위치, 비용(f, g, h) 등을 포함
• Grid 클래스:
  • 게임 월드를 그리드로 분할
  • 장애물 체크를 위한 Layer Mask 사용
  • 각 노드의 이웃 노드들을 찾는 기능
• Pathfinding 클래스:
  • A* 알고리즘의 핵심 로직 구현
  • 시작점에서 목표점까지의 경로 탐색
  • 대각선 이동도 고려한 거리 계산

 

 

마무리

 

오늘은 A* 알고리즘에 대해 간단하게 정리해 봤습니다.

평소 이름은 많이 들어봐서 알고 있었는데,

사용해 본 경험이 없어서 추후 간단한 미니 프로젝트를 만들어

A*를 사용해 보고 글로 작성해 보도록 하겠습니다.

 

다익스트라(Dijkstra) 알고리즘을 개선한 게 A*였다는 건 처음 알았네요.

다른 길 찾기 알고리즘들에 대해서도 따로 한번 정리해 보겠습니다.

 

참고한 자료

https://youtu.be/tqwsnUkUleA?si=ueBd4M0BuNf1AzHD