Grid 기반 A* 길찾기 알고리즘 성능 최적화 기법

A*는 왜 Grid에서 느려질까

A*는 시작 지점에서 목표 지점까지의 비용이 가장 낮을 것으로 예상되는 노드를 우선 탐색한다. 휴리스틱이 적절하면 다익스트라보다 훨씬 적은 노드를 방문하지만 큰 Grid·복잡한 장애물·동시 경로 요청이 겹치면 여전히 병목이 될 수 있다.

각 노드의 우선순위는 다음과 같이 계산한다.

f(n) = g(n) + h(n)

$g(n)$ : 시작 노드에서 현재 노드까지 실제로 누적한 이동 비용
$h(n)$ : 현재 노드에서 목표 노드까지의 추정 비용
$f(n)$ : 탐색 우선순위를 정하는 예상 총비용

성능 문제를 해결할 때는 단순히 알고리즘을 바꾸기보다 실제 비용이 어디서 생기는지 먼저 나누어 보는 편이 좋다. 보통은 탐색 노드 수, Open Set의 우선순위 처리, 노드 상태 초기화와 메모리 할당 그리고 매 프레임 반복 요청이 주요 원인이다.

먼저 줄여야 할 것은 탐색 노드 수다

이동 규칙에 맞는 휴리스틱 선택

4방향 이동만 허용하는 Grid라면 맨해튼 거리가 자연스럽다.

h(n) = |x_n - x_g| + |y_n - y_g|

대각선 이동까지 허용하고 가로·세로 비용이 10, 대각선 비용이 14라면 옥타일 거리를 사용할 수 있다.

h(n) = 14 \times \min(dx, dy) + 10 \times (\max(dx, dy) - \min(dx, dy))

여기서 $dx = |x_n - x_g|$ , $dy = |y_n - y_g|$ 다. 이동 비용과 휴리스틱의 단위가 맞지 않으면 탐색 범위가 불필요하게 넓어지거나 최단 경로 보장이 깨질 수 있다.

휴리스틱은 실제 최단 비용을 과대평가하지 않는 것이 안전하다. 예를 들어 장애물을 무시한 맨해튼 거리나 옥타일 거리는 일반적인 Grid 이동 규칙에서 좋은 하한값이 된다.

4방향과 8방향 Grid에서 맨해튼 거리와 옥타일 거리를 비교한 경로 탐색 예시

대각선 코너 통과를 명확히 막기

대각선 이동에서 두 직교 이웃이 모두 막혀 있는데 대각선 칸으로 이동하게 두면 벽 모서리를 비집고 지나가는 경로가 생긴다. 이를 나중에 보정하면 탐색과 후처리 비용이 늘어난다. 이웃을 추가할 때 규칙을 즉시 적용하는 편이 낫다.

bool CanMoveDiagonal(const Grid& grid, Int2 from, Int2 dir)
{
    const Int2 sideA{ from.x + dir.x, from.y };
    const Int2 sideB{ from.x, from.y + dir.y };

    return grid.IsWalkable(sideA) && grid.IsWalkable(sideB);
}

게임마다 한쪽만 비어 있어도 통과시키는 규칙을 쓸 수 있으므로 이 부분은 이동 판정과 충돌 규칙을 같은 기준으로 맞춰야 한다.

탐색 가능한 영역을 제한하기

전역 Grid 전체를 항상 탐색 대상으로 둘 필요는 없다. 시작점과 목표점 주변의 사각 영역에 여유 폭을 더해 탐색 영역을 만들면 먼 곳의 무관한 노드를 검사하지 않는다. 다만 장애물이 크게 우회해야 하는 맵에서는 잘린 영역 때문에 경로가 없다고 잘못 판단할 수 있다.

안전한 방법은 제한된 영역에서 먼저 탐색하고 실패했을 때만 여유 폭을 키워 재시도하는 방식이다. 단, 매번 작은 범위부터 여러 차례 재탐색하면 오히려 비용이 커질 수 있으므로 맵의 장애물 밀도와 예상 우회 거리를 기준으로 초기 여유 폭을 정한다.

Open Set은 선형 탐색하지 않는다

A*의 Open Set에서 가장 작은 $f(n)$ 을 꺼내는 작업은 매우 자주 일어난다. List나 배열을 매번 처음부터 끝까지 훑어 최솟값을 찾으면 탐색 노드가 많아질수록 비용이 빠르게 커진다.

이진 최소 힙을 사용하면 삽입과 최소값 추출이 모두 대략 로그 시간에 처리된다.

struct OpenEntry
{
    int nodeIndex;
    int fScore;
    int hScore;
};

struct OpenEntryLess
{
    bool operator()(const OpenEntry& a, const OpenEntry& b) const
    {
        if (a.fScore != b.fScore)
            return a.fScore > b.fScore; // priority_queue를 최소 힙처럼 사용

        return a.hScore > b.hScore;
    }
};

std::priority_queue<OpenEntry,
                    std::vector<OpenEntry>,
                    OpenEntryLess> openSet;

동일한 $f(n)$ 에서 $h(n)$ 이 작은 노드를 먼저 선택하면 목표 방향으로 더 곧게 진행하는 경향이 있다. 최단 경로 비용 자체는 바꾸지 않으면서 일부 맵에서 탐색 모양과 캐시 접근이 더 안정적일 수 있다.

중복 삽입을 허용하는 힙 전략

표준 우선순위 큐는 특정 노드의 우선순위를 직접 낮추는 연산이 불편하다. 이때 기존 항목을 찾아 수정하려고 선형 탐색을 추가하면 힙의 장점이 사라질 수 있다.

실무에서는 더 좋은 비용을 찾았을 때 새 항목을 다시 넣고 꺼낸 항목의 비용이 최신 gScore와 다르면 버리는 방식이 간단하고 빠른 경우가 많다.

while (!openSet.empty())
{
    const OpenEntry current = openSet.top();
    openSet.pop();

    if (current.fScore != gScore[current.nodeIndex] + hScore[current.nodeIndex])
        continue; // 이전에 넣은 오래된 항목

    if (current.nodeIndex == goalIndex)
        break;

    // 이웃 검사와 비용 갱신
}

이 방법은 힙에 중복 항목이 생길 수 있다. 그러나 노드 수가 제한된 Grid에서는 구현 복잡도와 실제 처리 시간을 함께 고려했을 때 좋은 선택이 되기 쉽다. 매우 큰 맵에서 중복이 문제가 된다면 노드가 힙 안에 있는 위치를 별도로 기록하는 인덱스드 힙을 검토할 수 있다.

flowchart TD
    A[시작 노드 삽입] --> B{Open Set이 비었는가?}
    B -- 예 --> Z[경로 없음]
    B -- 아니오 --> C[최소 f 노드 추출]
    C --> D{최신 비용 항목인가?}
    D -- 아니오 --> B
    D -- 예 --> E{목표 노드인가?}
    E -- 예 --> F[부모 포인터로 경로 복원]
    E -- 아니오 --> G[이웃의 이동 가능 여부와 비용 검사]
    G --> H[개선된 비용이면 점수와 부모 갱신]
    H --> B

노드 데이터를 연속 메모리로 관리한다

Grid의 각 칸을 개별 객체나 포인터 연결 구조로 만들면 메모리 접근이 흩어진다. 길찾기는 인접 칸을 반복해서 읽기 때문에 데이터를 연속 배열로 두는 편이 캐시 친화적이다.

2차원 좌표는 1차원 인덱스로 바꿔 관리할 수 있다.

int ToIndex(int x, int y, int width)
{
    return y * width + x;
}

struct NodeRecord
{
    int gScore;
    int parentIndex;
    uint32_t searchVersion;
};

walkable, 지형 비용, gScore, 부모 인덱스처럼 자주 쓰는 정보를 배열에 저장하면 좌표 변환과 포인터 추적 비용을 줄일 수 있다. 노드 객체를 매 탐색마다 생성하는 구조라면 먼저 이 부분부터 평면 배열 구조로 바꾸는 것이 효과가 큰 편이다.

전체 초기화 대신 검색 버전을 사용한다

탐색을 시작할 때마다 모든 노드의 방문 상태와 비용을 초기화하면 실제로 방문하지 않은 노드까지 매번 건드리게 된다. 특히 큰 맵에서 짧은 경로를 자주 찾으면 이 초기화가 탐색 자체보다 비싸질 수 있다.

각 노드에 마지막으로 사용된 검색 번호를 기록하고 현재 검색 번호와 다를 때만 기본값으로 취급한다.

void TouchNode(NodeRecord& node, uint32_t currentVersion)
{
    if (node.searchVersion == currentVersion)
        return;

    node.searchVersion = currentVersion;
    node.gScore = INT_MAX;
    node.parentIndex = -1;
}

검색 번호는 언젠가 한 바퀴 돌아간다. uint32_t를 사용한다면 오버플로 시점에만 전체 버전을 초기화하거나 서버처럼 장시간 실행되는 환경에서는 64비트 번호를 쓰는 식으로 처리한다.

할당과 후처리 비용도 경로 요청 횟수만큼 누적된다

경로 컨테이너를 재사용한다

매 요청마다 List, Vector, 임시 이웃 배열을 새로 만들면 GC나 할당기가 눈에 띄는 비용을 만들 수 있다. 경로 탐색기 인스턴스가 작업용 버퍼를 소유하고 예상 최대 크기만큼 미리 확보한 뒤 재사용하는 방식이 좋다.

Unity C#에서는 new List<Vector3>()를 반복하는 코드, Unreal/C++에서는 매 호출마다 늘어나는 TArray나 std::vector의 재할당을 프로파일링 대상에 넣어야 한다. 단, 여러 스레드가 같은 버퍼를 공유하면 데이터 경합이 생기므로 탐색기별 버퍼를 두거나 작업 단위로 분리한다.

부모 포인터로 한 번만 경로를 복원한다

목표에 도달한 뒤에는 목표 노드에서 시작 노드까지 부모 인덱스를 따라 역순으로 수집한 다음, 한 번만 뒤집는다. 탐색 중간에 매번 전체 경로를 복사하거나 좌표 목록을 갱신하지 않는다.

또한 Grid 경로는 꺾임이 많은 경우가 많다. 이동 규칙이 허용한다면 같은 방향으로 이어지는 중간 노드를 제거해 웨이포인트 수를 줄일 수 있다. 이는 A* 탐색을 빠르게 하지는 않지만 이후 캐릭터 조향과 네트워크 전송, 렌더링 디버그 비용을 줄인다.

부모 포인터로 복원한 Grid 경로에서 같은 방향의 중간 웨이포인트를 제거한 예시

요청 빈도를 제어하고 결과를 재사용한다

성능이 나쁜 길찾기 시스템은 알고리즘 하나가 느린 경우보다 필요 이상으로 자주 호출되는 경우가 많다. 목표가 바뀌지 않았는데 매 프레임 A*를 실행하거나 같은 목표를 향하는 다수의 유닛이 각각 완전한 경로를 찾는 구조가 대표적이다.

다음 기준을 적용해 요청 수를 줄일 수 있다.

목표 셀이나 출발 셀이 바뀌었을 때만 재탐색한다.
이동 중인 유닛은 일정 시간 또는 일정 거리마다만 재계산한다.
동적 장애물이 실제 경로와 겹칠 때만 재탐색한다.
같은 출발·목표 조합의 결과를 짧은 시간 동안 캐시한다.
많은 유닛이 같은 목적지를 향한다면 목적지에서 시작하는 흐름장 또는 공유 탐색을 검토한다.

캐시는 맵 상태를 함께 키로 관리해야 한다. 문이 열리거나 타일 비용이 바뀌었는데 이전 경로를 그대로 쓰면 잘못된 결과가 나온다. 전체 맵 버전이나 구역별 버전을 캐시 키에 포함하면 무효화 범위를 제어할 수 있다.

큰 맵과 많은 유닛에는 계층화가 필요하다

맵이 커질수록 단일 Grid에서 모든 길찾기를 해결하는 방식에는 한계가 있다. 이때는 맵을 구역으로 나누고 구역 사이의 연결 지점을 상위 그래프로 만든 뒤 필요한 구역에서만 세부 A*를 실행하는 계층형 길찾기를 고려할 수 있다.

예를 들어 방과 복도 단위의 상위 경로를 먼저 찾고 선택된 구역 안에서만 Grid 경로를 계산한다. 설계와 전처리는 복잡해지지만 장거리 경로 요청이 많은 게임에서는 탐색 노드 수를 크게 줄일 수 있다.

반대로 작은 전술 맵이나 요청 빈도가 낮은 게임이라면 계층 구조를 서둘러 도입할 이유가 없다. 먼저 휴리스틱, 최소 힙, 배열 기반 노드 저장, 요청 빈도 제한을 적용하고 프로파일러로 개선 여부를 확인하는 순서가 안전하다.

최적화 우선순위 체크리스트

이동 규칙과 같은 단위의 맨해튼 또는 옥타일 휴리스틱을 사용한다.
Open Set의 최소값 추출을 선형 탐색에서 이진 최소 힙으로 바꾼다.
노드 상태를 연속 배열에 저장하고 검색 버전으로 전체 초기화를 피한다.
경로 탐색 중 발생하는 임시 컨테이너와 객체 할당을 재사용 버퍼로 줄인다.
목표 변경, 경로 차단, 일정 주기 같은 명확한 조건에서만 재탐색한다.
프로파일러에서 탐색 노드 수, 힙 연산 시간, 할당 횟수, 요청 횟수를 함께 측정한다.

A* 최적화의 핵심은 특정 기법 하나가 아니다. 불필요한 탐색을 줄이고 남은 탐색을 빠른 자료구조와 연속 메모리로 처리하며 애초에 불필요한 요청을 만들지 않는 흐름을 갖추는 데 있다.