Unity - A*

이번 글에서는 A*를 정리해보았습니다.

 

이번에는 Chat GPT를 적극적으로 사용 하였습니다.

먼저 A*는 알고리즘 중에서 하나이며 출발 노드에서 도착 노드까지 최단거리를 구하는 알고리즘 입니다.

 

https://recall.tistory.com/40

A* 알고리즘(A star algorithm) grid map 개념 및 구현

여기에서 자세한걸 볼수 있습니다.

 

코드가 너무 길어서 따로 깃 주소를 두겠습니다.

https://github.com/Dove-Dove/AlgStudy

GitHub - Dove-Dove/AlgStudy

 

핵심 코드만 정리 해보겠습니다.

 

먼저 Node 부터 보겠습니다.

public Node(bool _walkable, Vector3 _worldPos, int _gridX, int _gridY)
{
    walkable = _walkable;
    worldPosition = _worldPos;
    gridX = _gridX;
    gridY = _gridY;
}

먼저 A* 경로 탐색에서 쓰이는 노드(Node)이며 통과 여부, 유니티 월드 좌표, 그리드 상의 좌표를 저장할수 있도록 만듭니다.

 

이제 Node가 완료가 되었다면 이제 그리드를 생성 하는쪽으로 가면

public int gridSizeX = 20;
public int gridSizeY = 20;
public float nodeRadius = 0.5f; 

public void CreateGrid()
{
    grid = new Node[gridSizeX, gridSizeY];
    Vector3 worldBottomLeft = transform.position - Vector3.right * (gridSizeX / 2f) * nodeDiameter - Vector3.forward * (gridSizeY / 2f) * nodeDiameter;

    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 * 0.9f, obstacleMask));
            grid[x, y] = new Node(walkable, worldPoint, x, y);
        }
    }
}

이제 내가 지정한 만큼 그리드를 생성합니다. 여기에서 만약에 생성 그리드 쪽에 벽이 있으면 walkable가 false가 됩니다.

 

이제 지정 한 만큼 노드가 생성 되었으면 이제 경로를 탐색 하는 쪽으로 가보겠습니다.

public List<Node> FindPath(Vector3 startWorld, Vector3 targetWorld)
{
    Node startNode = gridManager.NodeFromWorldPoint(startWorld);
    Node targetNode = gridManager.NodeFromWorldPoint(targetWorld);

    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)
        {
            List<Node> finalPath = RetracePath(startNode, targetNode);
            DrawPath(finalPath); 
            return finalPath;
        }

        foreach (Node neighbor in gridManager.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);
            }
        }
    }

    ClearPath(); // 경로 없으면 지우기
    return new List<Node>();
}

public System.Collections.Generic.List<Node> GetNeighbors(Node node)
{
    System.Collections.Generic.List<Node> neighbors = new System.Collections.Generic.List<Node>();

    for (int dx = -1; dx <= 1; dx++)
    {
        for (int dy = -1; dy <= 1; dy++)
        {
            if (dx == 0 && dy == 0) continue;

            int checkX = node.gridX + dx;
            int checkY = node.gridY + dy;

            if (checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)
            {
                neighbors.Add(grid[checkX, checkY]);
            }
        }
    }

    return neighbors;
}

 

너무 길기때문에 하나씩 나눠서 설명을 하겠습니다

 

Node startNode = gridManager.NodeFromWorldPoint(startWorld);
Node targetNode = gridManager.NodeFromWorldPoint(targetWorld);

먼저 시작노드와 목표 노드는 월드 좌표에서 그리드 좌표로 변환을 합니다.

 

List<Node> openSet = new List<Node>();
HashSet<Node> closedSet = new HashSet<Node>();
openSet.Add(startNode);

오픈 셋과 클로즈 셋을 초기화 합니다.

오픈셋은 검사할 후보 노드 목록이고 클로즈 셋은 검사가 완료된 노드 집합 입니다.

 

while (openSet.Count > 0)

while문을 이용하여 후보 노드를 계속 검색을 합니다.

 

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];
}

여기에서 fCost를 계산 합니다. fCost는 시작점에서 현재비용 , 현재위치 에서 목표까지 예상 비용을 더한값입니다

fCost가 낮은 값을 찾고 만약에 fCost가 같다면 목표 추정 거리가 더 작은 쪽으로 갑니다.

 

foreach (Node neighbor in gridManager.GetNeighbors(currentNode))

 foreach를 이용하여 현재 노드에서 8방향을 탐색합니다.

 

//GetNeighbors 함수
for (int dx = -1; dx <= 1; dx++)
{
    for (int dy = -1; dy <= 1; dy++)
    {
        if (dx == 0 && dy == 0) continue;

        int checkX = node.gridX + dx;
        int checkY = node.gridY + dy;

        if (checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)
        {
            neighbors.Add(grid[checkX, checkY]);
        }
    }
}

여기에서 주변 8칸을 검사하고 그리드 범위 안에있는 노드만 neighbors에 추가합니다.

 

만약에 벽이 있거나 closedSet 있는경우

if (!neighbor.walkable || closedSet.Contains(neighbor))
    continue;

 

 if문을 사용하여 무시합니다.

 

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);
}

 여기에서는 경로비용을 계산 후 업데이트를 합니다

gCost는 현재 노드를 거쳤을 때 더 싸면 갱신, hCost는 항상 목표까지의 예상 거리로 계산,

 

parent는 경로를 역추적하기 위해 저장을 합니다.

이렇게 작성을 하고 움직이는 것을 넣는다면

원하는 지점까지 움직입니다.

 

여기에서 3D같은 경우에는 AI가 기본 지원하기 때문에 턴제나 전략 게임 등 기본 규칙이 특수한 경우가 아닌 이상 
기본 지원하는 AI를 사용하는것이 좋습니다.