C# PriorityQueue로 A* 경로탐색과 게임 이벤트 스케줄러 구현하기

우선순위 큐가 필요한 순간

게임 로직을 짜다 보면 "가장 우선순위가 낮은(또는 높은) 항목을 빠르게 꺼내야 하는" 상황이 생각보다 자주 등장한다. 대표적인 두 가지 사례가 있다.

첫 번째는 A* 경로탐색의 open set이다. 매 iteration마다 f값(비용 추정치)이 가장 낮은 노드를 꺼내야 하는데, 수십~수백 개 노드를 다루는 맵에서 이 연산이 느리면 프레임 드롭으로 직결된다. 두 번째는 타임드 이벤트 스케줄러다. "3.5초 후 버프 해제", "AI가 2초 후 패트롤 재개", "1.2초 후 투사체 폭발" 같은 지연 이벤트를 타임스탬프 순서대로 처리해야 할 때 우선순위 큐가 핵심 자료구조로 쓰인다.

이 두 패턴을 과거에는 어떻게 해결했을까? SortedList<float, T>는 키가 priority를 겸해야 해서 같은 priority 값이 두 개면 키 충돌이 났고, 삽입이 O(n)이었다. List<T> + Sort()는 매번 전체를 다시 정렬하는 낭비가 있었다. 직접 구현한 BinaryHeap은 버그 온상이었다. .NET 6부터 표준 라이브러리에 들어온 System.Collections.Generic.PriorityQueue<TElement, TPriority>는 이 모든 문제를 min-heap 기반으로 깔끔하게 해결한다.

---

PriorityQueue의 설계 포인트

var pq = new PriorityQueue<string, float>();

pq.Enqueue("버프해제",  3.5f);   // (element, priority)
pq.Enqueue("패트롤재개", 2.0f);
pq.Enqueue("공격시작",  1.2f);

while (pq.TryDequeue(out string action, out float time))
{
    Debug.Log($"[{time:F1}s] {action}");
}
// 출력: 1.2s 공격시작 → 2.0s 패트롤재개 → 3.5s 버프해제

API의 핵심 특징은 element와 priority가 분리되어 있다는 점이다. 기존 SortedList에서는 float 키가 중복되는 순간 예외가 터졌지만, PriorityQueue는 동일한 priority 값을 가진 항목이 여러 개여도 허용한다. 같은 프레임에 이벤트가 여러 개 겹치는 게임 상황에서 이 특성은 매우 중요하다.

주요 메서드는 간단하다.

메서드	설명	복잡도
Enqueue(element, priority)	항목 삽입	O(log n)
TryDequeue(out element, out priority)	최소 priority 항목 추출	O(log n)
TryPeek(out element, out priority)	추출 없이 최솟값 확인	O(1)
EnqueueRange(items)	여러 항목 일괄 삽입	O(n)
Count	현재 항목 수	O(1)

---

예제 1: A* 경로탐색 Open Set

public sealed class AStarPathfinder
{
    private readonly PriorityQueue<Vector2Int, float> _open = new();
    private readonly Dictionary<Vector2Int, float> _gCost = new();
    private readonly Dictionary<Vector2Int, Vector2Int> _cameFrom = new();

    public List<Vector2Int>? FindPath(Vector2Int start, Vector2Int goal, IGrid grid)
    {
        _open.Clear();
        _gCost.Clear();
        _cameFrom.Clear();

        _gCost[start] = 0f;
        _open.Enqueue(start, Heuristic(start, goal));

        while (_open.TryDequeue(out Vector2Int current, out _))
        {
            if (current == goal)
                return ReconstructPath(goal);

            float currentG = _gCost[current];

            foreach (Vector2Int neighbor in grid.GetNeighbors(current))
            {
                float tentativeG = currentG + grid.MoveCost(current, neighbor);

                if (!_gCost.TryGetValue(neighbor, out float existingG) || tentativeG < existingG)
                {
                    _gCost[neighbor] = tentativeG;
                    _cameFrom[neighbor] = current;
                    float f = tentativeG + Heuristic(neighbor, goal);
                    // 중복 삽입 허용 — Dequeue 시 stale 항목은 gCost 불일치로 건너뜀
                    _open.Enqueue(neighbor, f);
                }
            }
        }
        return null;
    }

    private static float Heuristic(Vector2Int a, Vector2Int b)
        => MathF.Abs(a.x - b.x) + MathF.Abs(a.y - b.y);

    private List<Vector2Int> ReconstructPath(Vector2Int goal)
    {
        var path = new List<Vector2Int>();
        var node = goal;
        while (_cameFrom.TryGetValue(node, out var prev))
        {
            path.Add(node);
            node = prev;
        }
        path.Reverse();
        return path;
    }
}

주목할 부분은 "stale entry" 처리 방식이다. 표준 A는 open set에서 노드의 priority를 갱신(decrease-key)해야 하지만, PriorityQueue는 decrease-key를 지원하지 않는다. 대신 동일 노드를 새 f값으로 다시 Enqueue*하고, Dequeue 때 _gCost와 비교해 낡은 항목이면 그냥 건너뛰면 된다. heap에 중복 항목이 조금 쌓이지만 실측 성능에는 거의 영향이 없고, 코드가 훨씬 단순해진다.

---

예제 2: 타임드 게임 이벤트 스케줄러

public sealed class GameEventScheduler : MonoBehaviour
{
    private readonly PriorityQueue<Action, float> _queue = new();

    /// <summary>delay 초 뒤에 callback 실행</summary>
    public void Schedule(float delay, Action callback)
        => _queue.Enqueue(callback, Time.time + delay);

    /// <summary>절대 게임 시간 기준으로 등록</summary>
    public void ScheduleAt(float absoluteTime, Action callback)
        => _queue.Enqueue(callback, absoluteTime);

    private void Update()
    {
        // TryPeek으로 가장 이른 이벤트만 확인 — 아직 시간 안 됐으면 루프 종료
        while (_queue.TryPeek(out _, out float triggerTime) && Time.time >= triggerTime)
        {
            _queue.TryDequeue(out Action? action, out _);
            action?.Invoke();
        }
    }
}

// 사용 예시 (적 AI MonoBehaviour)
void OnBuffApplied()
{
    _scheduler.Schedule(5f,  RemoveBuff);
    _scheduler.Schedule(1f,  () => _vfx.Play());
    _scheduler.Schedule(0.5f, PlayBuffSound);
}

TryPeek으로 heap 최상단만 들여다보고(O(1)), 시간이 안 됐으면 즉시 루프를 탈출한다. 이벤트가 수백 개여도 매 Update에서 실제로 꺼낼 항목 수만큼만 O(log n) 연산이 발생한다. Coroutine + WaitForSeconds 조합은 MonoBehaviour당 코루틴 오브젝트가 쌓이지만, 이 패턴은 단일 스케줄러가 전체를 관리하므로 GC 압력도 낮다.

---

Unity 버전별 지원 현황

PriorityQueue<T, P>는 .NET 6에서 추가됐다. Unity에서 사용 가능한 시점을 정리하면 다음과 같다.

• Unity 2022.2 이상: 기본 지원. using System.Collections.Generic;만 있으면 된다.
• Unity 2021 이하: 미포함. dotnet/runtime 소스를 Assets/Plugins/에 복사하거나, 오픈소스 NuGet 패키지를 NuGetForUnity로 설치하면 된다.
• Unity 6 (6000.x): .NET 9 기반으로 PriorityQueue는 물론 FrozenDictionary, SearchValues<T> 같은 최신 컬렉션도 사용 가능하다.

---

결론

PriorityQueue<TElement, TPriority>는 min-heap을 직접 구현하거나 SortedList 우회책으로 버티던 번거로움을 표준 API 하나로 대체한다. element와 priority가 분리된 설계 덕분에 priority 중복에 강하고, TryPeek + TryDequeue 콤보로 매 Update 오버헤드를 최소화할 수 있다. A* open set, 타임드 이벤트 스케줄러 외에도 AI 행동 우선순위 큐, 데미지 스플래시 처리, 네트워크 패킷 재조합 등 게임 전반에 걸쳐 활용도가 높다. Unity 2022.2 이상을 쓴다면 외부 의존 없이 바로 꺼낼 수 있으니, 다음에 "정렬된 컨테이너"가 필요한 순간에 반사적으로 List.Sort()로 가기 전에 PriorityQueue를 먼저 떠올려 보자.