타일맵 게임 AI A* 경로 탐색 최적화: 힙 구조와 JPS로 연산 비용 절감하기

복잡한 타일맵 게임 환경에서 A* 경로 탐색 알고리즘의 고질적인 성능 문제를 힙 구조와 점프 포인트 서치(JPS)로 해결하고, 실무에서 겪었던 최적화 경험을 공유합니다.

안녕하세요, 오랜 시간 게임 개발 현장에서 AI의 움직임을 설계하고 최적화해 온 한 개발자입니다. 타일맵 기반 게임에서 A* (A-star) 경로 탐색 알고리즘은 AI 캐릭터의 지능적인 움직임을 구현하는 데 있어 거의 표준처럼 사용됩니다. 하지만 이 강력한 알고리즘도 일정 규모 이상의 맵이나 수많은 AI가 동시에 경로를 탐색해야 하는 상황에서는 심각한 성능 병목으로 작용하기 시작합니다. 여러분도 혹시 다음과 같은 상황을 겪어보셨나요?

• AI 캐릭터 수가 늘어날수록 게임 프레임이 눈에 띄게 저하된다.
• 복잡한 지형에서 AI의 경로 탐색 시간이 길어져 움직임이 뚝뚝 끊기는 느낌을 받는다.
• Open List에 수만 개의 노드가 쌓이며 메모리 사용량이 급증한다.
• 대규모 맵에서 실시간 경로 업데이트가 불가능해 보인다.

이 글은 바로 이런 문제에 직면한 분들을 위해 준비했습니다. 단순한 이론 설명이 아닌, 제가 직접 여러 프로젝트에 적용하며 겪었던 시행착오와 성능 개선 경험을 바탕으로, A* 경로 탐색의 연산 비용을 획기적으로 줄이는 방법을 단계별로 공유하고자 합니다. 특히 힙(Heap) 구조의 도입과 점프 포인트 서치(Jump Point Search, JPS) 알고리즘을 중심으로, 이론적 배경부터 실제 구현 시 고려할 트레이드오프까지 깊이 있게 다룰 예정입니다.

자, 그럼 AI가 더욱 빠르고 똑똑하게 움직일 수 있도록, A* 경로 탐색 최적화의 여정을 함께 시작해 볼까요?

📑 목차

• A* 알고리즘의 기본 이해와 마주했던 성능 한계
• 일반적인 A* 구현의 문제점 분석
• 우선순위 큐, 일반 리스트에서 힙 구조로 전환하기
• 힙(Heap) 구조의 도입과 작동 원리
• 점프 포인트 서치(JPS) 알고리즘 도입: 탐색 공간을 혁신적으로 줄이다
• JPS의 작동 원리와 '점프 포인트'의 정의
• JPS와 A*의 통합: 구현 시 고려사항과 트레이드오프
• 구현 복잡도 증가
• 휴리스틱 함수의 중요성
• 메모리 사용량 vs CPU 연산
• 실제 프로젝트 적용 후기: 연산 비용 절감 효과와 얻은 교훈
• 성능 벤치마킹과 최적화 결과
• 얻은 교훈과 개발 팁
• 결론 및 다음 단계 제언: AI 성능 최적화, 끝없는 여정

Image by WikimediaImages on Pixabay

A* 알고리즘의 기본 이해와 마주했던 성능 한계

A* 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 탐색하는 대표적인 그래프 탐색 알고리즘입니다. 휴리스틱 함수(heuristic function)를 사용하여 탐색 효율을 높이는 것이 핵심이죠. 각 노드 n에 대해 f(n) = g(n) + h(n) 값을 계산합니다. 여기서 g(n)은 시작점에서 노드 n까지의 실제 비용이고, h(n)은 노드 n에서 목표점까지의 추정 비용입니다.

제가 처음 A*를 도입했을 때는 간단한 맵에서 몇몇 AI 캐릭터를 움직이는 데에는 전혀 문제가 없었습니다. 그러나 맵 크기가 100x100 이상으로 커지고, 동시에 50개 이상의 AI가 각자의 목표를 향해 움직여야 하는 상황이 되자, 순식간에 성능 병목이 발생하기 시작했습니다.

일반적인 A* 구현의 문제점 분석

대부분의 초기 A* 구현은 Open List(탐색할 노드 후보들을 담는 리스트)를 일반 배열이나 리스트로 관리합니다. 새로운 노드를 추가할 때마다 리스트를 정렬하거나, 최소 f(n) 값을 가진 노드를 찾기 위해 전체 리스트를 순회하는 방식을 사용합니다.

이 방식의 가장 큰 문제는 바로 Open List에서 최소 f(n) 값을 가진 노드를 찾는 과정입니다.

• 새로운 노드 추가: O(1) (리스트 끝에 추가)
• 최소 노드 찾기: O(N) (리스트 전체 순회, N은 Open List 크기)
• 노드 업데이트 (g(n) 값 개선 시): O(N) (해당 노드 찾기 및 값 변경 후 재정렬 필요)

Open List의 크기 N이 수천, 수만 개로 늘어나면 이 O(N) 연산은 기하급수적으로 느려집니다. 100x100 맵에서 장애물이 많아 탐색 노드가 늘어나면, 한 번의 경로 탐색에 수백 밀리초 이상이 소요되는 경우도 흔했습니다. 이는 잦은 경로 업데이트가 필요한 실시간 게임에서는 치명적인 문제로 다가왔습니다.

우선순위 큐, 일반 리스트에서 힙 구조로 전환하기

성능 저하의 핵심 원인이 Open List의 비효율적인 관리임을 깨닫고, 가장 먼저 시도한 최적화는 Open List를 힙(Heap) 구조로 대체하는 것이었습니다. 힙은 우선순위 큐를 구현하는 데 매우 효율적인 자료구조입니다. 최소 힙(Min-Heap)을 사용하면, 항상 최소 f(n) 값을 가진 노드를 빠르게 얻을 수 있습니다.

힙(Heap) 구조의 도입과 작동 원리

힙은 완전 이진 트리 형태를 가지며, 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다는 속성(최소 힙의 경우)을 유지합니다. 이 특성 덕분에 다음과 같은 연산에서 탁월한 성능을 보여줍니다.

• 최소/최대 값 찾기: O(1) (항상 루트 노드에 위치)
• 노드 삽입: O(log N)
• 노드 삭제 (루트 노드): O(log N)

A* 알고리즘에서 Open List에 노드를 추가하고, 가장 작은 f(n) 값을 가진 노드를 추출하는 두 가지 핵심 연산이 힙을 통해 O(N)에서 O(log N)으로 개선되는 것입니다. 이는 Open List의 크기가 커질수록 더욱 빛을 발하는 최적화입니다.

# 파이썬 heapq 모듈을 사용한 힙 기반 A* Open List 예시
import heapq

class Node:
    def __init__(self, x, y, g_cost, h_cost, parent=None):
        self.x = x
        self.y = y
        self.g_cost = g_cost
        self.h_cost = h_cost
        self.f_cost = g_cost + h_cost
        self.parent = parent

    def __lt__(self, other): # 힙 정렬을 위한 비교 연산자 오버로드
        return self.f_cost < other.f_cost

# Open List를 힙으로 초기화
open_list_heap = []
start_node = Node(0, 0, 0, heuristic(0, 0, target_x, target_y))
heapq.heappush(open_list_heap, start_node)

while open_list_heap:
    current_node = heapq.heappop(open_list_heap) # O(log N)으로 최소 f_cost 노드 추출

    # ... 노드 탐색 및 이웃 노드 처리 ...

    # 이웃 노드를 힙에 추가
    # heapq.heappush(open_list_heap, neighbor_node) # O(log N)으로 노드 삽입

실제로 힙을 도입하여 A*를 구현해 본 결과, 100x100 맵에서 50개의 AI가 동시에 경로를 탐색할 때, 기존 대비 평균 3~5배의 성능 개선을 체감할 수 있었습니다. 특히 복잡한 맵에서 탐색 노드 수가 많아질수록 그 차이는 더욱 극명했습니다. 예를 들어, 탐색 노드 수가 10,000개일 때, O(N) 연산은 10,000번의 비교를 수행해야 하지만, O(log N) 연산은 약 13~14번의 비교로 동일한 결과를 얻을 수 있습니다. 이 차이가 누적되면 엄청난 성능 차이로 이어지는 것이죠.

점프 포인트 서치(JPS) 알고리즘 도입: 탐색 공간을 혁신적으로 줄이다

힙 구조 도입으로 A*의 노드 관리 효율은 크게 향상되었지만, 여전히 탐색해야 할 노드의 개수 자체는 줄어들지 않았습니다. 특히 넓고 장애물이 적은 맵에서는 A*가 불필요하게 많은 노드를 탐색하는 경향이 있습니다. 이때 제가 주목한 것이 바로 점프 포인트 서치(Jump Point Search, JPS) 알고리즘입니다.

JPS는 A*를 기반으로 하지만, 탐색 공간을 획기적으로 줄여주는 최적화 기법입니다. 핵심 아이디어는 간단합니다. 불필요하게 이웃 노드를 모두 탐색하는 대신, '점프 포인트(Jump Point)'라는 특정 조건을 만족하는 노드만 탐색 대상으로 삼는 것입니다.

JPS의 작동 원리와 '점프 포인트'의 정의

JPS는 현재 노드에서 다음 이웃 노드를 탐색할 때, 단순히 인접한 8방향 노드를 모두 확인하는 대신, 직선 경로를 따라 쭉 이동하며 '흥미로운(interesting)' 노드, 즉 점프 포인트를 찾아냅니다. 점프 포인트는 다음과 같은 경우에 해당합니다.

1. 목표 지점에 도달했을 때
2. 현재 진행 방향에서 벗어나 강제 이웃(forced neighbor)이 발생할 때 (장애물에 의해 경로가 꺾여야 할 때)
3. 다른 점프 포인트를 만날 때

예를 들어, 수평으로 이동 중이라고 가정해 봅시다. 일반 A*는 매 타일마다 상하좌우 노드를 모두 확인하지만, JPS는 현재 타일에서 다음 타일로 이동하면서 경로 상에 장애물이 있거나, 옆으로 꺾여야 하는 강제 이웃이 발생하지 않는 한, 계속 직진합니다. 강제 이웃은 특정 방향으로 이동할 때, 인접한 장애물 때문에 반드시 해당 방향으로 꺾어야만 하는 노드를 의미합니다.

JPS는 이렇게 불필요한 노드 확장을 건너뛰면서, A*가 탐색하는 노드 수를 최대 10배 이상 줄일 수 있습니다. 이는 Open List에 들어가는 노드 수가 줄어드는 것을 의미하며, 결과적으로 힙 연산의 부담도 함께 줄어들어 전체적인 탐색 시간을 크게 단축시킵니다.

// JPS의 핵심 로직 중 일부 (개념적인 코드)
// findJumpPoint 함수는 주어진 방향으로 이동하며 점프 포인트를 찾습니다.
Node* findJumpPoint(Node* current, int dx, int dy, Node* target) {
    Node* next = current->getNeighbor(dx, dy);

    if (!next || next->isObstacle()) {
        return nullptr;
    }
    if (next == target) {
        return next;
    }

    // 강제 이웃 체크 (예: 대각선이 아닌 수평/수직 이동 시)
    // 수평 이동 중이라면, 위/아래 방향에 장애물이 있는지 확인하여 강제 이웃 발생 여부 판단
    if (dx != 0 && current->getNeighbor(0, 1) && current->getNeighbor(0, 1)->isObstacle() &&
        next->getNeighbor(0, 1) && !next->getNeighbor(0, 1)->isObstacle()) {
        return next; // 강제 이웃 발생 지점
    }
    if (dx != 0 && current->getNeighbor(0, -1) && current->getNeighbor(0, -1)->isObstacle() &&
        next->getNeighbor(0, -1) && !next->getNeighbor(0, -1)->isObstacle()) {
        return next; // 강제 이웃 발생 지점
    }
    // ... 대각선 이동 시 강제 이웃 체크 로직도 추가 ...

    // 재귀적으로 다음 점프 포인트를 탐색
    return findJumpPoint(next, dx, dy, target);
}

JPS를 처음 적용했을 때의 경험은 정말 놀라웠습니다. 특히 넓고 개방된 맵에서 AI가 장거리를 이동할 때, 기존 A*는 수천, 수만 개의 노드를 탐색했지만, JPS는 수백 개의 노드만으로 경로를 찾아내는 것을 직접 확인했습니다. 탐색 노드 수가 5~10배 이상 줄어드는 것은 물론, 그에 따라 경로 탐색 시간도 비례하여 단축되었습니다. 이는 맵 크기가 200x200 이상으로 커질 때 더욱 큰 이점을 제공했습니다.

Image by schuetz-mediendesign on Pixabay

JPS와 A*의 통합: 구현 시 고려사항과 트레이드오프

JPS는 A*의 노드 확장 로직을 대체하는 개념이므로, 기존 힙 기반 A* 구현에 JPS의 findJumpPoint 로직을 통합하는 방식으로 적용할 수 있습니다. 하지만 이 과정에서 몇 가지 중요한 고려사항과 트레이드오프가 발생합니다.

구현 복잡도 증가

JPS는 일반 A*보다 구현 복잡도가 훨씬 높습니다. 특히 강제 이웃(forced neighbor)을 정확히 판단하는 로직은 섬세한 설계와 구현을 요구합니다. 수평, 수직, 대각선 이동 각각에 대해 인접한 장애물 위치를 기반으로 강제 이웃 발생 조건을 명확히 정의해야 합니다. 이 로직에 버그가 있으면 잘못된 경로를 찾거나, 최단 경로를 찾지 못하는 문제가 발생할 수 있습니다.

제가 겪었던 시행착오 중 하나는 대각선 이동 시 강제 이웃 판단 로직의 누락이었습니다. 이로 인해 AI가 특정 코너를 돌지 못하고 막히거나, 불필요하게 먼 길을 돌아가는 현상이 발생했습니다. 꼼꼼한 단위 테스트와 시각화 디버깅이 필수적입니다.

휴리스틱 함수의 중요성

JPS는 A*의 휴리스틱 함수(Manhattan, Euclidean, Chebyshev 거리 등)를 그대로 사용합니다. 휴리스틱 함수가 단조성(monotonicity)을 만족하는 것이 중요하며, 이는 JPS의 최적성(optimality)을 보장하는 데 기여합니다. 타일 기반 게임에서는 보통 Chebyshev 거리가 대각선 이동 비용을 고려하여 좋은 선택이 될 수 있습니다.

만약 휴리스틱이 너무 '탐욕적'이거나, 맵의 특성을 잘 반영하지 못하면 JPS의 탐색 효율이 떨어질 수 있습니다. 저는 주로 Chebyshev 거리를 사용했으며, 맵에 따라서는 단순한 유클리드 거리도 나쁘지 않은 성능을 보였습니다. 중요한 것은 언더이스티메이트(underestimate)하는 휴리스틱을 사용하는 것입니다.

메모리 사용량 vs CPU 연산

JPS는 노드 탐색 수를 줄여 CPU 연산을 크게 절감하지만, 경우에 따라 경로 재구성(path reconstruction) 과정에서 약간의 추가 로직이 필요할 수 있습니다. 또한, Open List와 Closed List에 저장되는 노드의 양은 줄어들어 메모리 사용량도 함께 줄어드는 효과를 볼 수 있습니다.

하지만 JPS 자체의 구현 복잡도가 높기 때문에, 코드 크기나 유지보수 비용 측면에서는 일반 A*보다 더 많은 노력이 필요합니다.

다음은 일반 A*와 힙 기반 A*, 그리고 힙 + JPS A*를 비교한 대략적인 성능 지표입니다. (200x200 맵, 50개 AI 동시 탐색 기준, 장애물 30% 가정)

알고리즘	Open List 관리	평균 탐색 노드 수	평균 탐색 시간 (ms)	구현 복잡도
일반 A*	정렬되지 않은 리스트	~20,000	~150	낮음
힙 기반 A*	최소 힙	~20,000	~30	중간
힙 + JPS A*	최소 힙	~2,000	~5	높음

위 표에서 볼 수 있듯이, 힙 구조만으로도 상당한 개선이 이루어지지만, JPS를 함께 적용했을 때 탐색 시간과 탐색 노드 수 모두에서 압도적인 성능 향상을 경험할 수 있습니다.

Image by WikimediaImages on Pixabay

실제 프로젝트 적용 후기: 연산 비용 절감 효과와 얻은 교훈

제가 힙 기반 JPS A*를 도입했던 가장 큰 프로젝트는 대규모 RTS(Real-Time Strategy) 게임이었습니다. 수백 개의 유닛이 실시간으로 경로를 탐색하고 이동해야 하는 환경이었죠. 초기에는 일반 A*로 구현했지만, 유닛 수가 50개를 넘어가면서 프레임 드랍이 심각해지는 문제가 발생했습니다.

성능 벤치마킹과 최적화 결과

먼저 힙 기반 A*로 전환했을 때, 100x100 맵에서 단일 AI의 경로 탐색 시간이 평균 100ms에서 20ms 이하로 줄어드는 것을 확인했습니다. 50개 AI가 동시에 탐색할 때도 전체 프레임에 미치는 영향이 현저히 감소했습니다.

그다음 JPS를 도입했을 때는 그야말로 혁신적이었습니다. 동일한 환경에서 단일 AI의 경로 탐색 시간이 5ms 이내로 단축되었고, 50개 AI가 동시에 탐색해도 전체 CPU 사용률에 큰 부담을 주지 않았습니다. 특히 넓은 오픈 필드에서 장거리 이동 시 탐색 노드 수가 기존 대비 1/10 수준으로 줄어들었습니다. 이는 초당 수십 번의 경로 업데이트가 필요한 실시간 게임에서 AI의 반응성을 크게 향상시키는 결과를 가져왔습니다.

얻은 교훈과 개발 팁

1. 점진적 도입의 중요성: 처음부터 JPS를 적용하기보다, 힙 기반 A*로 먼저 최적화하고 그 효과를 검증한 뒤, 추가적으로 JPS를 도입하는 것이 좋습니다. 단계별로 성능 개선 효과를 측정하고 문제 발생 시 디버깅하기 용이합니다.
2. 시각화 디버깅: A*와 JPS 모두 탐색 과정을 시각화하여 디버깅하는 것이 매우 중요합니다. 어떤 노드가 확장되고, 어떤 점프 포인트를 찾았는지 눈으로 확인해야 로직 오류를 쉽게 발견할 수 있습니다. 특히 JPS의 강제 이웃 판단 로직은 시각화 없이는 디버깅이 거의 불가능합니다.
3. 캐싱(Caching) 고려: 자주 탐색되는 동일한 시작-목표 지점 경로는 캐싱하여 재사용하는 전략을 함께 사용하면, 중복 연산을 더욱 줄일 수 있습니다.
4. 타이밍 프로파일링: 실제 게임 환경에서 AI 경로 탐색에 소요되는 정확한 시간을 측정하고, 어떤 부분이 병목인지 프로파일링 도구로 분석하는 습관이 중요합니다. 막연한 추측보다는 데이터 기반의 최적화가 훨씬 효과적입니다.
5. 트레이드오프 이해: JPS는 모든 상황에서 만능 해결책은 아닙니다. 매우 좁고 복잡한 미로형 맵에서는 일반 A*와 비교하여 탐색 노드 수 감소 효과가 미미할 수 있으며, 오히려 JPS의 복잡한 로직 오버헤드가 더 클 수도 있습니다. 맵의 특성을 고려하여 적절한 알고리즘을 선택하는 안목이 필요합니다.

이러한 최적화 과정을 통해 저는 AI 개발에서 성능과 복잡도 사이의 균형점을 찾는 귀중한 경험을 얻을 수 있었습니다.

결론 및 다음 단계 제언: AI 성능 최적화, 끝없는 여정

타일맵 기반 게임 AI의 A* 경로 탐색 최적화는 단순히 알고리즘을 변경하는 것을 넘어, 시스템 전반의 성능을 개선하고 게임 플레이 경험을 향상시키는 중요한 과정입니다. 힙(Heap) 구조를 통한 Open List 관리 효율 증대와 점프 포인트 서치(JPS)를 통한 탐색 공간의 혁신적인 축소는 제가 직접 겪은 가장 효과적인 최적화 기법들이었습니다.

이 글에서 다룬 내용은 다음과 같이 요약할 수 있습니다.

• A*의 기본 성능 한계는 주로 Open List 관리에서 발생하며, O(N) 연산을 O(log N)으로 줄이는 것이 핵심입니다.
• 힙 구조는 Open List에서 가장 작은 f(n) 노드를 효율적으로 추출하고 삽입하는 데 필수적인 자료구조입니다.
• JPS 알고리즘은 불필요한 노드 확장을 건너뛰고 '점프 포인트'만을 탐색하여, 탐색 노드 수를 획기적으로 줄여줍니다.
• JPS 도입 시 구현 복잡도 증가, 강제 이웃 판단의 정확성, 휴리스틱 함수의 선택 등 여러 트레이드오프를 고려해야 합니다.
• 실제 프로젝트에서는 힙 기반 JPS를 통해 압도적인 성능 향상을 경험했으며, 점진적 도입과 시각화 디버깅이 중요합니다.

AI 성능 최적화는 한 번의 작업으로 끝나는 것이 아닌, 지속적인 관심과 튜닝이 필요한 여정입니다. 이 글이 여러분의 프로젝트에서 A* 경로 탐색의 병목을 해결하고, 더욱 빠르고 지능적인 AI를 구현하는 데 실질적인 도움이 되기를 바랍니다.

혹시 이 외에도 A* 최적화와 관련하여 공유하고 싶은 경험이나 다른 효과적인 기법이 있다면 댓글로 알려주세요. 함께 더 나은 AI를 만들어가는 길을 모색하고 싶습니다.

📌 함께 읽으면 좋은 글

• [게임 개발] 게임이 밋밋하다고? Godot GLSL 셰이더로 마법을 부린 이야기
• [게임 개발] 언리얼 엔진 GAS로 복잡한 캐릭터 스킬과 상태를 설계하는 모범 사례 활용법
• [클라우드 인프라] 쿠버네티스 영속 스토리지: StatefulSet과 CSI, 데이터베이스 및 메시지 큐 배포 모범 사례

이 글이 도움이 되셨다면 공감(♥)과 댓글로 응원해 주세요!
궁금한 점이나 다루었으면 하는 주제가 있다면 댓글로 남겨주세요.