길찾기 - A* Algorithm

Unity 3D를 이용해서 특정 좌표까지의 길을 찾을 때는 NavMeshAgent라는 것을 사용하면 쉽게 길을 찾을 수 있다.

하지만 2D에서는?

 

그럴 때 사용하는 것이 A* Algorithm (A-Star) 이다.

Wikipedia의 내용을 발췌해보면...

 

A* (pronounced "A-star") is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency.[1] One major practical drawback is its  O(b^{d}) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases.

 

https://en.wikipedia.org/wiki/A*_search_algorithm 

A* search algorithm - Wikipedia

개념

A* 알고리즘은 주어진 출발 지점에서부터 목표 지점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘이다.

Dijkstra Algorithm과 비슷해보이지만 차이점은 각 꼭짓점 x에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위 값인 휴리스틱 추정값 h(x)을 매기는 방법을 이용한다.

대개 휴리스틱 추정값은 맨해튼 거리, 두 점사이의 거리로 계산한다.

1. h(x) = |x2 - x1| + |y2 - y1|
2. h(x) = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2))

휴리스틱 추정값이 이 알고리즘의 핵심으로 휴리스틱 값에 따라 성능이 좌지우지된다.

A* 알고리즘은 다음과 같은 경우에 최악의 성능을 낸다.

1. 정점은 많은데 간선은 적을경우 ( 모든 정점을 다 검사해야되기 때문)
2. 휴리스틱 추정값이 비정상적일 때

 

최적 경로를 탐색하기 위해, 평가 함수를 정의해야 한다. 정의 함수 f(x)는 다음과 같다.

f(x) = g(x) + h(x)
g(x) = 출발 지점에서 꼭짓점 x까지의 경로 가중치

일반적으로 A* Algorithm의 시간복잡도는 h(x), 휴리스틱 값에 의해 결정 됩니다.

1. Heuristic Function이 Admissible 할 경우, 최단 경로가 보장됨 => 대개 O(log n)
2. Admissible하지 않을 경우 => O(2^n)

휴리스틱 함수에 의해 시간 복잡도와 공간 복잡도가 극명하게 갈린다.

 

 

대각선으로의 이동이 불가능하다고 할 때 탐색은 다음과 같이 이루어진다.

 

동작 순서

1. 노드형 openList, closedList 리스트 생성
2. 현재노드를 시작노드로 지정함.
3. 현재노드가 도착지점이 아니라면 아래를 실행
4. openList에서 현재노드를 제거 후, closedList에 추가
5. 현재노드의 상하좌우 노드들을 탐색함
   
   1. 노드가 벽이 아니고, 그래프를 벗어나지 않은 값이고, 아직 조사하지 않은 값이고, 검색하는 노드의 g(x)가 현재의 g(x)보다 작으면 f(x)값을 계산 후 openList에 추가 및 parentNode를 현재 노드로 지정
   2. 현재 노드를 탐색한 노드로 바꿈
   3. 3번으로 돌아가서 재귀적으로 수행
6. 현재노드가 도착지점이라면 새로운 List를 생성해서 도착지점에서 부모노드를 역으로 따라가 경로를 탐색
7. List를 Reverse를 해주면 시작노드 ~ 도착지점에 대한 최소 비용 경로가 나오게 된다.

 

Unity를 통한 구현

결과 및 GameManager Inspector

코드

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

[System.Serializable]
public class Node
{
    public int x, y, g, h;
    // g : 시작으로부터 이동했던 거리
    // h : |가로| + |세로| 장애물 무시하여 목표까지의 거리
    public bool isWall;
    public Node parentNode;

    public int F
    {
        get
        {
            return g + h;
        }
    }

    public Node(bool isWall, int x, int y)
    {
        this.isWall = isWall;
        this.x = x;
        this.y = y;
    }
}

public class GameManager : MonoBehaviour
{
    public Vector2Int bottomLeft, topRight, startPos, targetPos;
    public List<Node> finalNodeList;
    public bool allowDiagonal, dontCrossCorner;

    private int sizeX, sizeY;
    private Node[,] nodeArray;
    private Node startNode, targetNode, curNode;
    private List<Node> openList, closedList;

    public void PathFinding()
    {
        //NodeArray의 크기를 정해주고 isWall, x, y 대입
        this.sizeX = this.topRight.x - this.bottomLeft.x + 1;
        this.sizeY = this.topRight.y - this.bottomLeft.y + 1;
        this.nodeArray = new Node[this.sizeX, this.sizeY];

        for (int i = 0; i < this.sizeX; i++)
        {
            for (int j = 0; j < this.sizeY; j++)
            {
                bool isWall = false;
                foreach (Collider2D col in Physics2D.OverlapCircleAll(new Vector2(i + this.bottomLeft.x, j + this.bottomLeft.y), 0.4f))
                {
                    if (col.gameObject.layer == LayerMask.NameToLayer("Wall"))
                        isWall = true;
                }
                this.nodeArray[i, j] = new Node(isWall, i + bottomLeft.x, j + bottomLeft.y);
            }
        }

        //시작과 끝 노드, 열린리스트와 닫힌리스트, 마지막리스트 초기화
        this.startNode = this.nodeArray[this.startPos.x - this.bottomLeft.x, this.startPos.y - this.bottomLeft.y];
        this.targetNode = this.nodeArray[this.targetPos.x - this.bottomLeft.x, this.targetPos.y - this.bottomLeft.y];

        this.openList = new List<Node>() { this.startNode };
        this.closedList = new List<Node>();
        this.finalNodeList = new List<Node>();

        while (this.openList.Count > 0)
        {
            //열린리스트 중 가장 F가 작고 F가 같다면 H가 작은 걸 현재노드로 하고
            //열린리스트에서 닫힌리스트로 옮기기
            this.curNode = this.openList[0];
            for(int i = 1; i < this.openList.Count; i++)
            {
                if (this.openList[i].F <= this.curNode.F
                    && this.openList[i].h < this.curNode.h)
                    this.curNode = this.openList[i];
            }

            this.openList.Remove(this.curNode);
            this.closedList.Add(this.curNode);

            //마지막 처리
            if(this.curNode == this.targetNode)
            {
                Node targetCurNode = this.targetNode;
                while(targetCurNode != this.startNode)
                {
                    this.finalNodeList.Add(targetCurNode);
                    targetCurNode = targetCurNode.parentNode;
                }
                this.finalNodeList.Add(this.startNode);
                this.finalNodeList.Reverse();

                for(int i = 0; i < this.finalNodeList.Count; i++)
                {
                    Debug.LogFormat("{0}번째는 {1}, {2}", i, this.finalNodeList[i].x, this.finalNodeList[i].y);
                }
                return;
            }

            // ↗↖↙↘
            if (allowDiagonal)
            {
                AddOpenList(this.curNode.x + 1, this.curNode.y + 1);
                AddOpenList(this.curNode.x - 1, this.curNode.y + 1);
                AddOpenList(this.curNode.x - 1, this.curNode.y - 1);
                AddOpenList(this.curNode.x + 1, this.curNode.y - 1);
            }

            // ↑ → ↓ ←
            AddOpenList(this.curNode.x, this.curNode.y + 1);
            AddOpenList(this.curNode.x + 1, this.curNode.y);
            AddOpenList(this.curNode.x, this.curNode.y - 1);
            AddOpenList(this.curNode.x - 1, this.curNode.y);
        }
    }

    private void AddOpenList(int x, int y)
    {
        // 상하좌우 범위를 벗어나지 않고, 벽이 아니면서, 닫힌리스트에 없다면...
        if(x >= this.bottomLeft.x && x < this.topRight.x + 1 &&
            y >= this.bottomLeft.y && y < this.topRight.y + 1 &&
            !this.nodeArray[x-this.bottomLeft.x, y-this.bottomLeft.y].isWall &&
            !this.closedList.Contains(this.nodeArray[x-this.bottomLeft.x, y - this.bottomLeft.y]))
        {
            //대각선 허용시, 벽 사이로 통과 안됨
            if (this.allowDiagonal)
            {
                if (this.nodeArray[this.curNode.x - this.bottomLeft.x, y - this.bottomLeft.y].isWall &&
                    this.nodeArray[x - this.bottomLeft.x, this.curNode.y - this.bottomLeft.y].isWall)
                    return;
            }

            if (this.dontCrossCorner)
            {
                if (this.nodeArray[this.curNode.x - this.bottomLeft.x, y - this.bottomLeft.y].isWall ||
                    this.nodeArray[x - this.bottomLeft.x, this.curNode.y - this.bottomLeft.y].isWall)
                    return;
            }

            //이웃노드에 넣고, 직선은 10, 대각선은 14
            Node neighborNode = this.nodeArray[x - this.bottomLeft.x, y - this.bottomLeft.y];
            int moveCost = this.curNode.g + (this.curNode.x - x == 0 || this.curNode.y == 0 ? 10 : 14);

            // 이동비용이 이웃노드 G보다 작거나 또는 열린리스트에 이웃노드가 없으면, G, H, parentNode를 설정 후 열린리스트에 추가
            if(moveCost < neighborNode.g || !this.openList.Contains(neighborNode))
            {
                neighborNode.g = moveCost;
                neighborNode.h = (Mathf.Abs(neighborNode.x - this.targetNode.x) + Mathf.Abs(neighborNode.y - this.targetNode.y)) * 10;
                neighborNode.parentNode = this.curNode;

                this.openList.Add(neighborNode);
            }
        }
    }

    private void OnDrawGizmos()
    {
        Gizmos.color = Color.red;

        if (this.finalNodeList.Count != 0)
        {
            for(int i = 0; i < this.finalNodeList.Count - 1; i++)
            {
                Gizmos.DrawLine(new Vector2(this.finalNodeList[i].x, this.finalNodeList[i].y),
                    new Vector2(this.finalNodeList[i + 1].x, this.finalNodeList[i + 1].y));
            }
        }
    }
}

https://github.com/ljw4112/A_Star_Algorithm_Tutorial

GitHub - ljw4112/A_Star_Algorithm_Tutorial