A* Pathfinding 최적화를 위한 Grid 맵 파티셔닝 구현

넓은 Grid 맵에서 A* 탐색 범위를 줄이기 위한 파티셔닝 전략을 설명합니다. 구역 경계와 출입 지점을 이용해 전체 경로와 세부 경로를 나누는 실용적인 구현 방법을 다룹니다.

✓ 복사 완료!
분야🧠 게임 AI
챕터길찾기 & 내비게이션 (A*/NavMesh)
난이도중급
상태● 검토 완료
대상 엔진
Unity
최종 업데이트
A* Pathfinding 최적화를 위한 Grid 맵 파티셔닝 구현

왜 Grid 파티셔닝이 필요한가

A*는 시작점에서 목표점까지의 최단 경로를 찾는 대표적인 알고리즘입니다. 휴리스틱이 잘 동작하면 무작정 넓게 탐색하지는 않지만 맵이 커지고 장애물이 복잡해질수록 열린 목록과 닫힌 목록에 쌓이는 노드 수가 빠르게 증가합니다.

특히 많은 유닛이 각자 경로를 요청하는 RTS, 시뮬레이션, 오픈 월드형 게임에서는 매 요청마다 전체 Grid를 대상으로 A*를 실행하기 어렵습니다. 이때 맵을 일정한 크기의 구역으로 나누고 필요한 구역만 상세하게 탐색하면 탐색 비용을 크게 줄일 수 있습니다.

전체 Grid를 여러 파티션으로 나누고 구역 경계의 출입 지점을 연결한 경로 탐색 구조

기본 아이디어

Grid를 예를 들어 16×16 셀 단위의 파티션으로 나눕니다. 각 파티션은 자신의 셀 정보와 인접 파티션으로 이동할 수 있는 출입 지점을 관리합니다.

경로 탐색은 다음 두 단계로 나뉩니다.

  1. 시작 파티션에서 목표 파티션까지 이동할 파티션 경로를 찾습니다.
  2. 선택된 파티션 내부에서만 세부 A*를 실행하고 결과를 하나의 경로로 이어 붙입니다.
flowchart TD
    A[시작 셀] --> B[시작 파티션 확인]
    B --> C[파티션 그래프에서 상위 경로 탐색]
    C --> D[구간별 로컬 Grid A* 실행]
    D --> E[세부 경로 연결 및 정리]
    E --> F[최종 이동 경로]

상위 탐색의 노드는 개별 셀이 아니라 파티션입니다. 따라서 256×256 Grid를 16×16 파티션으로 분할하면 상위 탐색은 최대 256개 파티션을 대상으로 진행합니다. 전체 셀 65,536개를 직접 다루는 것보다 훨씬 작은 문제로 바꿀 수 있습니다.

파티션 크기 정하기

파티션이 너무 크면 로컬 A*의 탐색 범위가 넓어집니다. 반대로 너무 작으면 파티션 그래프와 경계 연결 정보를 관리하는 비용이 커지고 경로가 지나치게 잘게 나뉩니다.

파티션 한 변의 셀 수를 PP, 전체 Grid 한 변의 셀 수를 NN이라고 하면 한 축의 파티션 수는 다음과 같습니다.

⌈NP⌉\left\lceil \frac{N}{P} \right\rceil

일반적으로 다음 기준으로 시작하면 조정하기 좋습니다.

  • 타일 기반 맵이라면 8×8 또는 16×16 셀부터 시험합니다.
  • 유닛의 이동 반경이 크거나 장애물이 드문 맵은 16×16 또는 32×32 셀이 적합할 수 있습니다.
  • 좁은 통로나 복잡한 실내 맵은 작은 파티션이 유리할 수 있습니다.
  • 실제 결정은 프로파일링 결과와 동시 경로 요청 수를 기준으로 합니다.

경계 출입 지점 만들기

인접한 두 파티션이 맞닿은 경계에서 양쪽 셀이 모두 통과 가능하면 파티션 간 이동이 가능합니다. 이때 통과 가능한 모든 경계 셀을 그래프 노드로 만들면 연결 수가 불필요하게 많아집니다.

대신 연속된 통과 가능 구간을 하나의 출입 구간으로 묶고 대표 셀 하나 또는 구간의 중앙 셀을 출입 지점으로 사용합니다. 예를 들어 경계에 통과 가능한 셀이 10개 연속으로 있다면 10개를 모두 연결하지 않고 대표 지점 하나를 둘 수 있습니다.

다만 대표 셀만 쓰면 최단 경로의 품질이 조금 낮아질 수 있습니다. 정밀도가 중요하다면 출입 구간의 양 끝과 중앙처럼 여러 후보를 두거나 상위 경로가 정해진 뒤 실제 경계 구간 안에서 가장 비용이 낮은 연결을 선택합니다.

public readonly struct GridPos
{
    public int X { get; }
    public int Y { get; }

    public GridPos(int x, int y)
    {
        X = x;
        Y = y;
    }
}

public sealed class Partition
{
    public int Id { get; }
    public RectInt Bounds { get; }
    public List<Portal> Portals { get; } = new();

    public Partition(int id, RectInt bounds)
    {
        Id = id;
        Bounds = bounds;
    }
}

public sealed class Portal
{
    public int FromPartitionId { get; set; }
    public int ToPartitionId { get; set; }
    public GridPos FromCell { get; set; }
    public GridPos ToCell { get; set; }
}

이 코드는 Unity C# 9에서도 사용할 수 있도록 C# 10의 record struct와 Unity에서 지원하지 않는 init 접근자를 사용하지 않습니다. 실제 프로젝트에서는 Portal을 생성 시 초기화하는 생성자 기반 타입으로 바꾸거나, 불변성이 필요하면 생성자와 읽기 전용 프로퍼티를 사용하세요.

Portal은 파티션 경계를 넘는 이동을 나타냅니다. FromCell과 ToCell을 분리해 두면 양쪽 셀이 서로 다른 파티션에 속한다는 사실이 명확해지고 이동 가능 여부를 검증하기도 쉽습니다.

파티션 그래프 구성

각 파티션을 그래프의 노드로 보고 출입 지점이 하나 이상 존재하는 인접 파티션을 간선으로 연결합니다. 상위 A*에서 간선 비용은 단순히 파티션 중심 간 거리로 시작할 수 있지만 더 안정적인 결과를 원한다면 실제 출입 지점까지의 예상 이동 비용을 반영해야 합니다.

가장 단순한 상위 휴리스틱은 파티션 좌표의 맨해튼 거리입니다.

h(n)=∣xn−xg∣+∣yn−yg∣h(n) = |x_n - x_g| + |y_n - y_g|

4방향 이동과 동일한 단위 비용을 가정하면 이 휴리스틱은 실제 최소 비용을 과대평가하지 않으므로 A*의 최단 경로 성질을 유지합니다. 셀 비용이 다르면 최소 이동 비용을 곱해 하한으로 사용하고, 대각선 이동을 허용한다면 이동 규칙과 비용에 맞는 옥타일 거리 휴리스틱을 사용해야 합니다.

public IEnumerable<PartitionEdge> GetNeighbors(int partitionId)
{
    foreach (Portal portal in partitions[partitionId].Portals)
    {
        yield return new PartitionEdge(
            portal.ToPartitionId,
            portal,
            cost: 1f);
    }
}

public readonly struct PartitionEdge
{
    public int ToPartitionId { get; }
    public Portal Portal { get; }
    public float Cost { get; }

    public PartitionEdge(int toPartitionId, Portal portal, float cost)
    {
        ToPartitionId = toPartitionId;
        Portal = portal;
        Cost = cost;
    }
}

위 GetNeighbors 메서드 조각은 파티션 그래프를 보유한 탐색 클래스의 멤버로 배치합니다.

상위 그래프의 간선 비용을 모두 1로 두면 거쳐 가는 파티션 수가 적은 경로를 선택합니다. 구현 초기에는 충분히 유용하지만 긴 우회로나 좁은 통로가 많은 맵에서는 실제 비용과 차이가 날 수 있습니다. 이후에는 출입 지점 간 사전 계산 비용을 간선 비용에 반영하는 방식으로 개선할 수 있습니다.

세부 경로 연결하기

상위 탐색 결과가 시작 파티션 → A → B → 목표 파티션이라면 세부 탐색은 다음처럼 구간별로 실행합니다.

  1. 시작 셀에서 첫 출입 지점까지 탐색합니다.
  2. 각 파티션에서 들어온 출입 지점에서 다음 출입 지점까지 탐색합니다.
  3. 마지막 출입 지점에서 목표 셀까지 탐색합니다.

로컬 A*는 현재 파티션의 범위만 통과하도록 제한합니다. 단, 출입 지점을 향해 경계를 넘는 마지막 한 칸은 허용해야 합니다.

List<GridPos> BuildPath(GridPos start, GridPos goal)
{
    int startPartition = GetPartitionId(start);
    int goalPartition = GetPartitionId(goal);

    if (startPartition == goalPartition)
        return FindLocalPath(start, goal, startPartition);

    List<Portal> portals = FindPartitionPath(startPartition, goalPartition);
    var result = new List<GridPos>();
    GridPos current = start;

    foreach (Portal portal in portals)
    {
        AppendWithoutDuplicate(result,
            FindLocalPath(current, portal.FromCell, portal.FromPartitionId));
        current = portal.ToCell;
        result.Add(current);
    }

    AppendWithoutDuplicate(result,
        FindLocalPath(current, goal, goalPartition));

    return SimplifyPath(result);
}

BuildPath도 GetPartitionId, FindPartitionPath, FindLocalPath 등을 제공하는 경로 탐색 클래스의 메서드 조각입니다. 각 구간의 로컬 경로가 없을 때는 실패를 결과에 명시하고 상위 경로를 다시 탐색해야 합니다.

AppendWithoutDuplicate는 이전 구간의 마지막 셀과 다음 구간의 첫 셀이 겹칠 때 중복을 제거합니다. SimplifyPath에서는 같은 방향으로 연속된 셀을 정리하거나 장애물 충돌 검사를 통과하는 범위에서 시야 기반 경로 단축을 적용할 수 있습니다.

정확도와 성능의 균형

단순한 파티션 단위 탐색은 빠르지만 항상 전역 최단 경로를 보장하지는 않습니다. 상위 그래프가 선택하지 않은 출입 지점을 지나야 더 짧아지는 경우가 있기 때문입니다. 또한 인접 파티션 간 출입 지점이 있어도 한 파티션 안에서 진입 지점과 다음 출구가 서로 연결되지 않을 수 있으므로, 포털 쌍 사이의 로컬 도달 가능성과 비용을 계산해 상위 그래프에 반영해야 잘못된 경로 연결을 피할 수 있습니다.

품질을 높이는 대표적인 방법은 다음과 같습니다.

  • 파티션 경계의 통과 구간마다 복수의 출입 지점을 둡니다.
  • 같은 파티션 안의 출입 지점 쌍 사이 비용을 미리 계산해 캐시합니다.
  • 상위 그래프의 노드를 파티션 자체가 아니라 출입 지점으로 구성합니다.
  • 정적 장애물만 있는 맵에서는 사전 계산 결과를 재사용합니다.
  • 동적 장애물은 로컬 탐색 단계에서만 반영하고 상위 그래프는 큰 지형 변화가 있을 때만 갱신합니다.

출입 지점 쌍 사이의 로컬 경로 비용을 저장하면 상위 탐색의 비용 추정이 정확해집니다. 대신 파티션마다 출입 지점이 많을수록 사전 계산량과 메모리 사용량도 늘어납니다. 따라서 한 파티션의 출입 지점 수를 제한하고 자주 쓰이는 파티션부터 지연 계산하는 방식이 실용적입니다.

동적 장애물 처리

문, 이동식 상자, 다른 유닛처럼 상태가 자주 바뀌는 요소를 파티션 그래프 전체에 즉시 반영하면 갱신 비용이 커질 수 있습니다. 장애물의 영향 범위에 따라 처리 방식을 나누는 편이 좋습니다.

  • 셀 몇 개만 막는 유닛은 로컬 A*에서만 회피합니다.
  • 파티션 경계의 출입 구간을 완전히 막는 문은 해당 Portal을 비활성화합니다.
  • 넓은 지역의 지형이 바뀌면 영향을 받은 파티션의 출입 지점과 내부 캐시를 다시 만듭니다.

이미 만든 경로가 막혔을 때는 전체 경로를 즉시 다시 찾기보다 현재 위치가 속한 파티션부터 다음 출입 지점까지 먼저 재탐색하는 방법도 사용할 수 있습니다. 단, 다음 출입 지점 자체가 막혔다면 상위 파티션 경로도 다시 계산해야 합니다.

구현 시 확인할 점

좌표 변환을 한곳에 모으기

월드 좌표, Grid 좌표, 파티션 좌표를 여러 곳에서 직접 계산하면 경계에서 오류가 나기 쉽습니다. WorldToGrid, GetPartitionId, GetPartitionBounds 같은 함수를 한 모듈에 모으고 음수 좌표와 맵 외부 좌표의 규칙을 명확히 정합니다.

우선순위 큐를 사용하기

A*의 열린 목록을 매번 선형 탐색하면 파티셔닝 효과가 줄어듭니다. C#에서는 PriorityQueue<TElement, TPriority>를 사용하거나 Unity 버전에 맞는 이진 힙을 구현해 최소 비용 노드를 빠르게 꺼내는 것이 좋습니다.

프로파일링으로 효과 확인하기

최적화는 평균 탐색 시간만으로 판단하기 어렵습니다. 다음 값을 함께 기록하면 병목을 파악하기 좋습니다.

  • 경로 요청당 확장한 셀 수
  • 상위 탐색에서 방문한 파티션 수
  • 로컬 A* 호출 횟수와 호출당 탐색 셀 수
  • 출입 지점 및 캐시의 메모리 사용량
  • 경로 실패와 재탐색 발생 횟수

마무리

Grid 파티셔닝은 A* 자체를 바꾸기보다 탐색 문제의 크기를 나누는 방법입니다. 먼저 파티션 단위의 경로를 고른 뒤 필요한 구역에서만 세부 A*를 실행하면 넓은 맵과 다수의 경로 요청에서 탐색 비용을 관리하기 쉬워집니다.

처음에는 고정 크기 파티션, 대표 출입 지점, 단순한 파티션 간선 비용으로 구현한 뒤 프로파일링 결과를 바탕으로 출입 지점 복수화와 내부 비용 캐시를 추가하는 순서가 안전합니다. 이 구조는 이후 계층형 경로 탐색과 스트리밍 맵 구조로 확장하기에도 좋은 기반이 됩니다.

🔗 관련 가이드 (Related Guides)

🧠 게임 AI길찾기 & 내비게이션 (A*/NavMesh)
Click-to-Move 구현하기: NavMesh 기반 장애물 회피와 타겟 자동 접근 및 스킬 발동

마우스 클릭 위치를 월드 좌표로 변환하고 NavMesh로 장애물을 회피하면서 적을 클릭하면 사거리까지 자동으로 접근해 스킬을 발동하는 Click-to-Move 시스템의 구조와 구현 방법을 정리합니다.

🧠 게임 AI길찾기 & 내비게이션 (A*/NavMesh)
NavMesh 기반 몬스터 Pathfinding과 경로 최적화 기법

NavMesh 위에서 몬스터가 목표 지점까지 이동하는 과정을 이해하고 경로 탐색 비용과 군집 이동 문제를 줄이는 실용적인 최적화 방법을 정리합니다.

🧠 게임 AI길찾기 & 내비게이션 (A*/NavMesh)
Grid 기반 A* 길찾기 알고리즘 성능 최적화 기법

Grid 맵에서 A*가 느려지는 원인을 짚고 탐색 범위·자료구조·할당 비용·경로 후처리를 줄이는 실용적인 최적화 방법을 정리한다. 정확도를 유지해야 하는 지점과 상황별 선택 기준도 함께 다룬다.

🧠 게임 AI길찾기 & 내비게이션 (A*/NavMesh)
A* 길찾기 최적화: NavMesh와 Flow Field를 활용한 수십 마리 몬스터의 동시 경로 탐색

게임 내 수십~수백 마리의 몬스터가 동시에 플레이어를 추적할 때 발생하는 CPU 병목 현상을 해결하는 길찾기 최적화 기법을 살펴봅니다. Grid 기반 A*의 한계를 극복하고 NavMesh와 계층적 길찾기, Flow Field를 결합해 연산량을 획기적으로 줄이는 구조를 정리했습니다.

관련 토픽 탐색

#Unity#A*#Pathfinding#AI#C#