내일배움캠프 60일차 7/10 TIL + A* 알고리즘 길찾기

작업 내용

A* 알고리즘을 활용한 길찾기 시스템 제작

A* 길찾기 알고리즘은 시작지점에서 해당 지점까지 이동한 거리 g와 현재 지점에서 특수한 휴리스틱 함수에 의해 계산된 도착지점까지의 비용 h를 더해서 f라는 비용으로 비용을 비교해서 적은 비용의 자리를 우선 탐색하는 방법이다.
물론 한쪽으로만 가다보면 해당 방향의 비용이 점점 증가 할 수 있는데 그렇기에 주변 환경에 따라서 모든 방향으로 탐색하는 BFS같은 모습을 보일 수도 있다.
내가 구현한 알고리즘에서는 특별한 휴리스틱 함수는 없고 그냥 도착지점까지 직선 거리로 계산했다.
A* 길찾기 알고리즘은 GridGenerator 클래스에 제작하였고 다음과 같다.

public LinkedList<Vector2Int> AStarPathFinding(Vector2Int startPos, Vector2Int endPos)
{
    LinkedList<Vector2Int> path = new LinkedList<Vector2Int>();

    // 다음에 살펴볼 시작 위치를 넣는 openList, 지나온 위치를 넣는 closedList
    List<Node> openList = new List<Node>();
    HashSet<Node> closedList = new HashSet<Node>();

    Node startNode = new Node(startPos);
    Node endNode = new Node(endPos);

    openList.Add(startNode);

    while (openList.Count > 0)
    {
        // 최소 fCost 노드 찾기
        Node currentNode = openList[0];
        for (int i = 1; i < openList.Count; i++)
        {
            if (openList[i].fCost < currentNode.fCost || (openList[i].fCost == currentNode.fCost && openList[i].hCost < currentNode.hCost))
            {
                currentNode = openList[i];
            }
        }

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

        // 도착 지점에 도착
        if (currentNode.Equals(endNode))
        {
            return RetracePath(startNode, currentNode);
        }

        // 상하좌우, 대각선까지 8 방향에 대해 현재 위치에서 각 방향의 노드에 Cost를 구하고 openList에 추가
        foreach (Vector2Int direction in eightDirections)
        {
            Vector2Int neighborPos = currentNode.Position + direction;
            if (!grid.IsGridAvailable(neighborPos) || closedList.Contains(new Node(neighborPos)))
            {
                continue;
            }

            Node neighbor = new Node(neighborPos);
            int newCostToNeighbor = currentNode.gCost + GetDistance(currentNode.Position, neighborPos);

            if (newCostToNeighbor < neighbor.gCost || !openList.Contains(neighbor))
            {
                neighbor.gCost = newCostToNeighbor;
                neighbor.hCost = GetDistance(neighborPos, endPos);
                neighbor.parent = currentNode;

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

    return path;
}

이동 가능한 방향은 상하좌우, 대각선까지 8 방향이기에 단순히 다음 자리로 가면 g 값이 1이 증가하는 것이 아니라 대각선의 경우 14가 증가한다.
참고로 거리 계산은 계산 속도를 높이기 위해 float보다 연산이 빠른 int로 연산하게 하였다.

private int GetDistance(Vector2Int a, Vector2Int b)
{
    int distX = Mathf.Abs(a.x - b.x);
    int distY = Mathf.Abs(a.y - b.y);
    if (distX > distY)
        return 14 * distY + 10 * (distX - distY);
    return 14 * distX + 10 * (distY - distX);
}

한쪽 거리가 더 멀면 짧은 쪽은 대각선으로 이동한 것과 같기에 그 만큼 대각선으로 해주고 둘의 차이인 남은 거리 만큼은 긴 쪽으로 직선 이동한 것과 같기에 10을 곱해준다.
14는 45도 대각선 길이인 루트2의 값이다.
참고로 최종 값인 path는 어차피 모두 돌아볼 것이기에 추가와 제거가 빠른 LinkedList를 썼다.
여기에 쓰인 Node 클래스는 Cost와 Parent값들을 가지고있다.

private class Node
{
    public Vector2Int Position;
    public int gCost;
    public int hCost;
    public Node parent;

    public int fCost { get { return gCost + hCost; } }
  ...

이렇게 parent로 노드에 직접 붙여주니 백트래킹으로 최종 path를 찾을 때 매우 편리하다.

private LinkedList<Vector2Int> RetracePath(Node startNode, Node endNode)
{
    LinkedList<Vector2Int> path = new LinkedList<Vector2Int>();
    Node currentNode = endNode;

    while (currentNode != startNode)
    {
        path.AddFirst(currentNode.Position);
        currentNode = currentNode.parent;
    }

    return path;
}

마무리

이제 내일은 이 알고리즘을 적용해서 유닛들의 이동을 구현할 것인데, 한가지 의문점이 매 1 발자국마다 유닛의 위치를 갱신시켜서 충돌을 피하게 할지, 아니면 도착지점에만 둘지, 만약 도착지점에서만 유닛 위치를 그리드에서 갱신하면 이동이 중단 된 경우는 어떻게 처리할지 등이 문제다.
추가로 지금은 Update로 이동을 하는데, 이렇게 그리드의 한칸한칸을 움직이게 하면 한칸에서 다음 칸으로 가는데 중간에 멈출 일이 생기면 이 때 처리도 해주어야한다.
예외 처리를 할게 많아 조금 험난한 날이 될 것 같다.