A* Search Path 알고리즘 (A star 경로 탐색 알고리즘)

A*(A-star) 경로 탐색 알고리즘은 최적의 경로를 찾기 위한 휴리스틱 기반의 알고리즘으로 게임이나 로봇, 내비게이션 시스템 등에서 목적지까지의 최단 경로를 효율적으로 찾는 데 자주 사용함

 

A-star 알고리즘은 아래의 공식을 기반으로 작동

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

n: 현재 노드

g(n): 시작점에서 현재 노드까지의 실제 비용

h(n): 현재 노드에서 목표까지의 추정 비용(휴리스틱)

f(n): 총 예상 비용

 

간단하게 표현

 

하나의 셀을 위와 같이 간단히 표현

직선으로 이동시엔 10 cost, 대각선으로 이동시엔 14cost라 할때(cost는 꼭 10, 14일 필요는 없음 대각선이동 cost를 직선보다 더 많이 주기만 하면 됨)

 

이동별 cost 시각화

이동별 cost를 시각화 하면 위의 그림과 같다. 직선으로 이동시엔 10cost, 대각선으로 이동시엔 14cost

 

 

간단한 예로 위와 같이 3x3 grid system이 있고 start 포인트에서 end포인트로 최적의 경로를 이동한다 할때 각 셀별 g,f,h의 값은 위의 그림과 같다

f가 44인 1행 1열의 값을 계산한 그림을 보면 start지점까지의 cost는 10 + 10으로 20이므로 g(n)은 20을 end 지점까지의 cost는 직선 한번 대각선 한번으로 10 + 14를 하여 h(n)은 24가 된다. 그러므로 총 f(n) 20 + 24로 44가 된다

 

작동 방식

- 시작 노드를 Open list에 추가

- open list에서 f(n) 값이 가장 낮은 노드를 꺼냄

- 해당 노드가 목표라면 경로를 리턴하고 종료

- 그렇지 않으면 이웃 노드들을 확인하여 g(n)을 계산하고 더 좋은 경로면 그 정보를 저장

- 현재 노드는 closed list에 넣고 다시 반복

 

open List란 현재 탐색 중인 노드들을 저장하는 리스트이고 Closed List는 이미 탐색이 완료된 노드들을 저장하는 리스트 입니다.

OpenList

- 탐색을 시작할 때, 시작 노드만 포함하여 이후 탐색 과정에서 새롭게 발견된 노드들을 추가하는 리스트

- 가장 유망한 노드를 선택해 탐색

- 선택된 노드는 열린 목록에서 제거되고 닫힌 목록에 추가

 

ClosedList

- 이미 탐색이 완료되어 더이상 탐색하지 않아도 되는 노드들을 저장

- 중복 탐색을 방지하여 탐색효율을 높임

 

코드

1. PathNode.cs 각 노드별 g,h,f cost와 위치 값등을 관리하는 클래스 생성

public class PathNode
{
    private Grid<PathNode> grid;
    public int x;
    public int y;

    public int gCost;
    public int hCost;
    public int fCost;

    public PathNode cameFromNode;


    public PathNode(Grid<PathNode> grid, int x, int y)
    {
        this.grid = grid;
        this.x = x;
        this.y = y;
    }

    public void CalculateFCost()
    {
        fCost = gCost + hCost;
    }

    public override string ToString()
    {
        return x + "," + y;
    }
}

 

2. PathFinding.cs]

PathNode startNode = grid.GetGridObject(startX, startY);
PathNode endNode = grid.GetGridObject(endX, endY);

start 지점과 end 지점의 x,y 값을 받아 startNode와 endNode를 가져온다

 

openList = new List<PathNode> { startNode };
closedList = new List<PathNode> { };

openList와 closedList를 생성한다 openList에는 제일 처음 startNode를 넣는다

 

startNode.gCost = 0;
startNode.hCost = CalculateDistanceCost(startNode, endNode);
startNode.CalculateFCost();

startNode의 값들을 넣어준다. start이기 때문에 gCost는 0이고 endNode와의 거리를 계산해 hCost값을 넣어준뒤 fCost를 계산한다

 

while (openList.Count > 0)
{
    PathNode currentNode = GetLowestFCostNode(openList);
    if (currentNode == endNode)
    {
        // Reached final node
        return CalculatePath(endNode);
    }

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

    foreach (PathNode neighbourNode in GetNeighbourList(currentNode))
    {
        if (closedList.Contains(neighbourNode)) { continue; }

        int tentaiveGCost = currentNode.gCost + CalculateDistanceCost(currentNode, neighbourNode);
        if (tentaiveGCost < neighbourNode.gCost)
        {
            neighbourNode.cameFromNode = currentNode;
            neighbourNode.gCost = tentaiveGCost;
            neighbourNode.hCost = CalculateDistanceCost(neighbourNode, endNode);
            neighbourNode.CalculateFCost();

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

openList에 있는 노드들 중 가장 낮은 fCost 값을 가지는 노드를 가져와 현재 노드(currentNode)에 할당 currentNode는 openList에서는 제거하고 closedList에 추가한다

 

그렇게 할당된 currentNode 주변 노드들의 gcost, hcost를 계산해 fCost값을 그 후 계산하고 이전 Node가 무엇인지를 할당한 후 openList에 추가한다 그리고 openList들 중 가장 낮은 값을 다시 currentNode에 할당 후 openList에서 해당값을 제거하고 closedList에 추가한다(while 문)

 

 

그렇게해서 추가된 closedList로 최적의 경로를 알 수 있게 된다

 

전체코드

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class PathFinding
{
    private const int MOVE_STRAIGHT_COST = 10;
    private const int MOVE_DIAGONAL_COST = 14;

    private Grid<PathNode> grid;
    private List<PathNode> openList;
    private List<PathNode> closedList;


    public PathFinding(int width, int height)
    {
        grid = new Grid<PathNode>(width, height, 10f, Vector3.zero, (Grid<PathNode> grid, int x, int y) => new PathNode(grid, x, y));
    }

    public Grid<PathNode> GetGrid()
    {
        return grid;
    }

    public List<PathNode> FindPath(int startX, int startY, int endX, int endY)
    {
        PathNode startNode = grid.GetGridObject(startX, startY);
        PathNode endNode = grid.GetGridObject(endX, endY);

        openList = new List<PathNode> { startNode };
        closedList = new List<PathNode> { };

        // Initialize
        for (int x = 0; x < grid.GetWidth(); x++)
        {
            for (int y = 0; y < grid.GetHeight(); y++)
            {
                PathNode pathNode = grid.GetGridObject(x, y);
                pathNode.gCost = int.MaxValue;
                pathNode.CalculateFCost();
                pathNode.cameFromNode = null;
            }
        }

        startNode.gCost = 0;
        startNode.hCost = CalculateDistanceCost(startNode, endNode);
        startNode.CalculateFCost();

        while (openList.Count > 0)
        {
            PathNode currentNode = GetLowestFCostNode(openList);
            if (currentNode == endNode)
            {
                // Reached final node
                return CalculatePath(endNode);
            }

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

            foreach (PathNode neighbourNode in GetNeighbourList(currentNode))
            {
                if (closedList.Contains(neighbourNode)) { continue; }

                int tentaiveGCost = currentNode.gCost + CalculateDistanceCost(currentNode, neighbourNode);
                if (tentaiveGCost < neighbourNode.gCost)
                {
                    neighbourNode.cameFromNode = currentNode;
                    neighbourNode.gCost = tentaiveGCost;
                    neighbourNode.hCost = CalculateDistanceCost(neighbourNode, endNode);
                    neighbourNode.CalculateFCost();

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

        // Out of nodes on the openList
        return null;
    }

    private int CalculateDistanceCost(PathNode a, PathNode b)
    {
        int xDistance = Mathf.Abs(a.x - b.x);
        int yDistance = Mathf.Abs(a.y - b.y);
        int remaining = Mathf.Abs(xDistance - yDistance);

        return MOVE_DIAGONAL_COST * Mathf.Min(xDistance, yDistance) + MOVE_STRAIGHT_COST * remaining;
    }

    private PathNode GetLowestFCostNode(List<PathNode> pathNodeList)
    {
        PathNode lowestFCostNode = pathNodeList[0];
        for (int i = 1; i < pathNodeList.Count; i++)
        {
            if (pathNodeList[i].fCost < lowestFCostNode.fCost) { lowestFCostNode = pathNodeList[i]; }
        }

        return lowestFCostNode;
    }

    private List<PathNode> CalculatePath(PathNode endNode)
    {
        List<PathNode> path = new List<PathNode>();
        path.Add(endNode);

        PathNode currentNode = endNode;
        while (currentNode.cameFromNode != null)
        {
            path.Add(currentNode.cameFromNode);
            currentNode = currentNode.cameFromNode;
        }
        path.Reverse();

        return path;
    }

    private List<PathNode> GetNeighbourList(PathNode currentNode)
    {
        List<PathNode> neighbourList = new List<PathNode>();

        if (currentNode.x - 1 >= 0)
        {
            neighbourList.Add(GetNode(currentNode.x - 1, currentNode.y));       // Left
            if (currentNode.y - 1 >= 0) { neighbourList.Add(GetNode(currentNode.x - 1, currentNode.y - 1)); }   // Left Down
            if (currentNode.y + 1 < grid.GetHeight()) { neighbourList.Add(GetNode(currentNode.x - 1, currentNode.y + 1)); }     // Left Up
        }
        if (currentNode.x + 1 < grid.GetWidth())
        {
            neighbourList.Add(GetNode(currentNode.x + 1, currentNode.y));       // Right
            if (currentNode.y - 1 >= 0) { neighbourList.Add(GetNode(currentNode.x + 1, currentNode.y - 1)); }   // Right Down
            if (currentNode.y + 1 < grid.GetHeight()) { neighbourList.Add(GetNode(currentNode.x + 1, currentNode.y + 1)); }     // Right Up
        }
        if (currentNode.y - 1 >= 0)
        {
            neighbourList.Add(GetNode(currentNode.x, currentNode.y - 1));   // Down
        }
        if (currentNode.y + 1 < grid.GetHeight())
        {
            neighbourList.Add(GetNode(currentNode.x, currentNode.y + 1));   // Up
        }

        return neighbourList;
    }

    private PathNode GetNode(int x, int y)
    {
        return grid.GetGridObject(x, y);
    }
}