[알고리즘] A* 알고리즘 (에이스타 알고리즘)

⭐ A* (에이스타) 알고리즘

에이스타 알고리즘은 길찾기 알고리즘의 한 종류로 다익스트라에서 파생된 알고리즘입니다.

다익스트라 알고리즘과 다르게 휴리스틱(Heuristic)을 조합해 목표치까지의 남은 거리를 예측합니다.

 

에이스타 알고리즘에서의 휴리스틱은 현재 노드에서 목표까지의 거리를 추정하는 값을 의미합니다.

또한 여러 방식을 통해 목표까지의 남은 추정값을 계산합니다.

 

비슷한 방식의 알고리즘 중에서 가장 자주 사용되는 알고리즘입니다.

유니티의 내장 기능인 AI Navigation 또한 에이스타 알고리즘을 기반으로 동작합니다.

 

● 출처: https://qiao.github.io/PathFinding.js/visual/

 

 

 

💡 에이스타 알고리즘의 개념

시작점에서 목표 지점까지의 최소 비용 경로를 찾아내기 위해

다익스트라 + 휴리스틱을 조합해 사용하는 최적의 길찾기 알고리즘입니다.

각 노드를 탐색할 때 비교하는 비용의 공식은 F(n) = G(n) + H(n)입니다.

 

F → 총 예상 비용

G → 시작점에서 현재 노드까지의 실제 비용

H → 현재 노드에서 목표 노드까지의 예상 비용

 

 

 

휴리스틱 (Heuristic)

---

● 맨해튼 거리: 상하좌우 이동만 가능할 때 현재 노드에서 목표 노드까지의 X거리와 Y거리를 더한 값

● 유클리드 거리: 현재 노드에서 목표 노드까지의 직선 거리 값

● 체비셰프 거리: 대각선 이동도 포함해서 계산한 거리 (상하좌우 이동값이 1이라면 대각선의 값은 (1.4 ≈ √2))

 

● 3D 에서는 주로 유클리드 거리 방식을, 2D에서는 맨해튼 또는 체비셰프 거리 방식을 사용합니다.

방식	장점	단점
맨해튼 거리	계산이 빠름	대각선 거리 계산 불가능
유클리드 거리	계산 값이 정밀함	느림
체비셰프 거리	계산이 빠르고, 정밀함	정확하지 않음

 

 

💡 A* 알고리즘이 최단 거리를 보장하기 위해 휴리스틱이 갖춰야할 조건

아래 두 가지 조건을 만족할 경우 최단 거리를 보장할 수 있습니다.

 

● 허용적(Admissible): 휴리스틱은 항상 실제 거리보다 작거나 같아야 합니다.

    ○ h(n) ≤ h*(n)

    ○ 여기서 h(n)은 휴리스틱, h*(n)은 시작 노드 → n → 목표 노드 까지의 실제 최소 비용

 

● 일관적(Consistent): 현재 노드에서의 휴리스틱이 다음 노드에서의 휴리스틱 + 현재 노드 → 다음 노드의 비용보다 크면 안됩니다.

    ○ 쉽게 말해 노드를 한 칸 이동할 때 마다 최소한 그 이동 비용 만큼은 줄어야합니다.

    ○ h(n) <= g(n, n') + h(n')

    ○ 여기서 h(n)은 현재 노드의 휴리스틱, h(n')은 다음 노드의 휴리스틱 g(n, n')은 현재 노드 → 다음 노드로 가는 비용

 

 

 

에이스타 알고리즘의 특징

---

💡 장점

 

● 다익스트라보다 훨씬 빠릅니다.

● 장애물등이 많이 존재하는 복잡한 맵에서도 잘 동작합니다.

● 휴리스틱이 적법하다면 최단 거리를 보장합니다.

 

 

💡 단점

● 맵의 크기가 커질 경우 상당한 연산이 필요합니다. → JPS 알고리즘으로 해결 가능

 

 

 

 

 

A* 알고리즘 코드

---

● 위와 같은 그래프에서 A → D 최단거리를 구하는 코드입니다.

● A의 휴리스틱은 3, B는 2, C는 1, D는 0으로 가정하였습니다.

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

public class AStarNode : IComparable<AStarNode>
{
    public int index;           //노드 인덱스, 구별값 ABCD 0123
    public Vector2 pos;         //노드 위치
    public float G;             //시작점에서 지금 위치까지의 실제 비용
    public float H;             //휴리스틱, 예측비용
    public float F => G + H;    //총 점수, 가중치
    public AStarNode parent;    //부모 노드, 경로 복원 용도

    public AStarNode(int index, Vector2 pos, float g, float h, AStarNode parent = null)
    {
        this.index = index;
        this.pos = pos;
        G = g;
        H = h;
        this.parent = parent;
    }

    //F값 기준 정렬을 위한 비교 함수
    public int CompareTo(AStarNode other)
    {
        //F값으로 우선 비교해보기
        int fCompare = F.CompareTo(other.F);
        if (fCompare != 0)
            return fCompare;

        //F값이 같을 경우 인덱스 기준 비교하기
        return index.CompareTo(other.index);
    }
}

public class AStarExample : MonoBehaviour
{
    //두 좌표 사이의 직선 거리를 휴리스틱으로 사용하기
    private static float Heuristic(Vector2 a, Vector2 b) => Vector2.Distance(a, b);

    private void Start()
    {
        int n = 4;              //노드 총 개수
        int startIndex = 0;     //시작 위치는 0번 노드, A
        int goalIndex = 3;      //목표 위치는 3번 노드, D

        //각각의 노드에 좌표 설정해주기
        Vector2[] positions = new Vector2[4]
        {
            new Vector2(1, 0),      //A
            new Vector2(0, 1),      //B
            new Vector2(0, 0),      //C
            new Vector2(1, 1)       //D
        };

        //그래프 구성, (목표 노드, 목표까지의 비용)
        List<(int to, float cost)>[] graph = new List<(int to, float cost)>[n];

        for (int i = 0; i < n; i++)
        {
            graph[i] = new List<(int to, float cost)>();
        }

        //비용 정보 추가
        graph[0].Add((1, 1));   //A → B (1)
        graph[0].Add((2, 4));   //A → C (4)
        graph[1].Add((2, 2));   //B → C (2)
        graph[1].Add((3, 6));   //B → D (6)
        graph[2].Add((3, 3));   //C → D (3)

        //G 점수 배열 초기화
        float[] gScores = new float[n];

        for(int i = 0; i < n; i++)
        {
            gScores[i] = float.MaxValue;
        }

        //시작 위치
        gScores[startIndex] = 0;

        //방문 여부
        bool[] closed = new bool[n];

        //오픈 리스트, 탐색 대상들
        var openList = new List<AStarNode>();

        //시작 지점 추가
        openList.Add(new AStarNode(startIndex, positions[startIndex], 0,
            Heuristic(positions[startIndex], positions[goalIndex])));

        //탐색 루프
        while(openList.Count > 0)
        {
            //F값 기준 정렬
            openList.Sort((a, b) => a.CompareTo(b));

            //가장 F가 낮은 노드 찾아오기
            var current = openList[0];

            //방문한 노드는 제거
            openList.RemoveAt(0);

            //이미 방문한 노드면 패스
            if (closed[current.index])
                continue;

            //방문처리
            closed[current.index] = true;

            //목표에 도달했으면 경로 복원
            if(current.index == goalIndex)
            {
                //경로 저장용 리스트
                var path = new List<int>();
                var temp = current;

                //부모 따라가면서 역추적
                while(temp != null)
                {
                    path.Add(temp.index);
                    temp = temp.parent;
                }

                //D - C - B - A

                //역순으로 들어갔으니까 뒤집기
                path.Reverse();

                //A - B - C - D

                Debug.Log("A* Path " + string.Join(" => ", path));
                Debug.Log("Distance " + current.G);

                break;
            }

            //완전 노드 탐색
            foreach(var neighbor in graph[current.index])
            {
                //이미 처리한 노드는 패스
                if (closed[neighbor.to])
                    continue;

                //현재의 G + 이동 비용 계산
                float t = current.G + neighbor.cost;

                //더 짧은 경로 발견시 갱신
                if(t < gScores[neighbor.to])
                {
                    gScores[neighbor.to] = t;

                    //H값 계산
                    float h = Heuristic(positions[neighbor.to], positions[goalIndex]);

                    //새로운 노드 추가
                    openList.Add(new AStarNode(neighbor.to, positions[neighbor.to], t, h, current));
                }
            }
        }
    }
}