길찾기 알고리즘 : 다익스트라(Dijkstra) 와 에이스타(A*)

다익스트라 알고리즘 (Dijkstra)

시작점에서 각 노드가지의 최소 비용을 계싼하는 알고리즘이다.

각 노드를 탐색하며, 해당 지점까지 온 비용(g)이 가장 작은 노드부터 탐색한다.

그러므로 목표까지 가까워 보이는 방향을 추정하지 않고, 그저 현재까지 누적된 비용이 가장 작은 노드만을 기준으로 탐색한다.

 

 

위 이미지는 다익스트라가 길을 찾는 방식이다.

가까운 곳에 목표가 있음에도 원형으로 퍼져나가며 경로를 찾는 비효율적인 모습을 보인다.

 

다익스트라를 코드로 구현하면 다음과 같다.

 

using System.Collections.Generic;
using UnityEngine;

class DijkstraNode
{
    public int Index;           // ABCD, 0123 번호
    public Vector2 Pos;         // 해당 노드의 좌표
    public float Distance;      // 시작점으로부터 현재 노드까지의 누적 거리
    public DijkstraNode Parent; // 경로 추적용 부모 노드

    public DijkstraNode(int index, Vector2 pos, float dis, DijkstraNode parent = null)
    {
        Index = index;
        Pos = pos;
        Distance = dis;
        Parent = parent;
    }
}

public class DijkstraExample : MonoBehaviour
{
    void Start()
    {
        int n = 4;              // 노드 개수
        int startIndex = 0;     // 시작 노드 인덱스 A
        int goalIndex = 3;      // 목표 노드 인덱스 D

        // 각각의 노드에 좌표 설정해주기
        Vector2[] positions = new Vector2[4]
        {
            new Vector2(0, 0),      // A
            new Vector2(1, 0),      // B
            new Vector2(0, 1),      // 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)

        // 각 노드까지의 최소 거리 저장 배열
        float[] distances = new float[4];
        for (int i = 0; i < n; i++)
        {
            distances[i] = float.MaxValue;
        }

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

        // 방문 여부 저장 배열
        bool[] visited = new bool[n];

        // 탐색 대기 리스트
        var openList = new List<DijkstraNode>();

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

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

            // 치소 거리 노드 선택
            var current = openList[0];

            // 선택한 애는 탐색 대상에서 제외
            openList.RemoveAt(0);

            // 방문한 노드면 스킵
            if (visited[current.Index]) continue;

            // 방문 처리
            visited[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("Dijkstra Path " + string.Join(" -> ", path));
                Debug.Log("Distance " + current.Distance);

                break;
            }

            foreach(var neighbor in graph[current.Index])
            {
                // 이미 방문한 노드 패스
                if (visited[neighbor.to]) continue;

                // 현재 노드까지의 거리 + 간선 비용
                float t = current.Distance + neighbor.cost;

                // 더 짧은 경로 발견시
                if (t < distances[neighbor.to])
                {
                    distances[neighbor.to] = t;
                    // 새로운 노드 추가
                    openList.Add(new DijkstraNode(neighbor.to, positions[neighbor.to], t, current));
                }
            }
        }
    }
}

 

실행해보면 A B C D, 6 의 결과가 제대로 출력되는 걸 볼 수 있다.

 

---

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

다익스트라를 기반으로 한 최적화 된 알고리즘이다.

재밌게도 A*라는 건 대놓고

• A : 알고리즘 계열을 뜻하는 내부 코드명
• * : 최적화를 의미하는 수학적 표기

를 합쳐, 최적화 알고리즘 이란 뜻이다.

 

위 첨부 이미지에서 봤듯이 다익스트라는 불필요하게 넓은 범위를 탐색하기에 낭비가 있다.

여기서 휴리스틱(Heuristic)을 추가해 알고리즘을 강화한다.

 

지금까지 온 비용(g) + 앞으로 남은 거리의 추정(h)을 합해 탐색하는 개념이다.

F(n) = G(n) + H(n)

• G : 시작점 - 현재까지 실제 비용
• H : 현재 - 목표까지의 추정 비용
• F : 총 탐색 우선도

 

즉 휴리스틱을 적절히 사용하면 A*는 다익스트라보다 훨씬 적은 탐색으로 같은 정답을 얻을 수 있다.

 

 

 

다익스트라 보다 불필요하게 탐색하는 범위가 압도적으로 적어진다.

 

아래 코드는 다익스트라를 기반으로 해서 A*를 구현한 코드다.

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

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)
    {
        Index = index;
        this.pos = pos;
        G = g;
        H = h;
        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
{
    // 두 좌표 사이의 거리를 휴리스틱으로 사용
    static float Heuristic(Vector2 a, Vector2 b) => Vector2.Distance(a, b);

    void Start()
    {
        int n = 4;                  // 노드 4개 쓸거임
        int startIndex = 0;         // 시작 위치는 0번 노드 A
        int goalIndex = 3;          // 종료 위치는 3번 노드 D

        // 각각의 노드에 좌표 설정해주기
        Vector2[] positions = new Vector2[4]
        {
            new Vector2(0, 0),      // A
            new Vector2(1, 0),      // B
            new Vector2(0, 1),      // 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[] gScore = new float[4];
        for (int i = 0; i < n; i++)
        {
            gScore[i] = float.MaxValue;
        }

        // 시작 위치
        gScore[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;
                }

                path.Reverse();

                Debug.Log("Astar 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 < gScore[neighbor.to])
                {
                    gScore[neighbor.to] = t;

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

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

 

 

---

 

다익스트라와 A* 차이

정렬 기준

다익스트라

openList.Sort((a, b) => a.Distance.CompareTo(b.Distance));

• 오직 현재까지 온 비용(G)만 비교
• 가장 싼 G값을 가진 노드를 우선 탐색
• 목표 방향과 무관한 원형 탐색 발생

A*

openList.Sort((a, b) => a.F.CompareTo(b.F));

• F = G + H
• 단순히 싼 노드가 아니라 "싼 + 목표에 가까워 보이는" 노드를 선택
• 때문에 목표 방향으로 탐색이 집중되어 낭비를 줄여 성능이 향상

 

노드 구조

다익스트라

public float Distance; // g(n)

A*

public float G;			// 실제 누적 비용
public float H;			// 목표까지 예상 비용(휴리스틱)
public float F => G + H		// 탐색 우선도

 

휴리스틱 계산 여부

다익스트라

없음

A*

float h = Heuristic(positions[neighbor.to], positions[goalIndex]);

 

H는 현재 위치에서 목표까지 남은 거리의 추정값이다.

이 값이 정확할수록 A*는 적은 탐색으로 동일한 결과를 얻게 된다.

 

 

정리

	다익스트라	A*
탐색 기준	g(n)	g(n) + h(n)
목표 방향 고려	X	O
휴리스틱 사용	X	O
탐색 영역	넓게 퍼짐	목표 방향으로 좁아짐
처리 속도	상대적으로 느림	빠름

 

 

---

추가 개선 사항

위 코드는 다익스트라와 에이스트라의 구현 개념을 이해하기 위해 다루었던 코드다.

• 때문에 openList를 List<T>로 구현돼있는데, 현재 방식에는 다음과 같은 문제점이 남아있다.
• 매 프레임 Sort() 수행 - O(n log n)
• 같은 노드가 중복해서 리스트에 들어갈 수 있음
• 리스트에서 기존 노드를 찾아 갱신하는 비용이 큼

즉 이 리스트 기반 구조는 실제 게임 맵처럼 노드 수가 많아지고 복잡한 상황에서는 매우 비효율 적이다.

 

그래서 실제로 A*를 구현할 때는 우선순위 큐(PriorityQueue)를 사용한다고 한다.

 

기존 코드를 다음 단계를 통해 개선할 수 있다.

 

선언부 수정

// 기존 코드
var openList = new List<AStarNode>();

// 수정
var openQueue = new PriorityQueue<AStarNode, float>();

 

시작 노드 추가 부분 수정

// 기존 코드
openList.Add(new AStarNode(
    startIndex,
    positions[startIndex],
    0,
    Heuristic(positions[startIndex], positions[goalIndex])
));

// 수정
var startNode = new AStarNode(
    startIndex,
    positions[startIndex],
    0,
    Heuristic(positions[startIndex], positions[goalIndex])
);

openQueue.Enqueue(startNode, startNode.F);

 

정렬 부분 수정

//기존 코드
openList.Sort((a,b) => a.CompareTo(b)); // 정렬
var current = openList[0];              // 최소 F값 pop
openList.RemoveAt(0);                   // 제거

// 수정
var current = openQueue.Dequeue();		// Dequeue로 간단

 

새 후보 노드 추가부 수정

// 기존 코드
openList.Add(new AStarNode(neighbor.to, positions[neighbor.to], t, h, current));

// 수정
var node = new AStarNode(neighbor.to, positions[neighbor.to], t, h, current);
openQueue.Enqueue(node, node.F);

 

 

이렇게 우선순위 큐를 이용하는 방식으로 개선할 수 있다.