[Unity6] RTS AI의 알고리즘과 최적화

a-a·2026년 8월 20일

알쓸신잡

목록 보기

35/35

Unity 6.3.21f1 기준으로 제작 중인 POC의 적 AI를 정리한 글이다.
흔히 사용하는 FSM 하나로 적의 행동을 나누기보다, 판단과 실행을 분리하고 이동 시간을 비용으로 환산하는 방식으로 구현했다.

이모저모 잡담

적 AI를 처음 생각하면 보통 이런 그림이 떠오른다.

Idle
↓
Chase
↓
Attack

대상이 보이면 쫓아가고, 사거리 안에 들어오면 공격한다.

여기까지만 보면 쉽다.

그런데 우리 게임에는 플레이어가 세운 구조물이 길을 막는다.

적 입장에서는 갑자기 고민할 것이 많아진다.

눈앞의 유닛을 공격할까?
열려 있는 길로 돌아갈까?
벽을 부수고 직진할까?
벽을 부순다면 어느 벽을 부술까?
이미 다른 적들이 때리는 벽에 합류할까?

이쯤 되면 단순히 Chase State 안에 if를 몇 개 넣는 것으로는 해결하기 어렵다.

무엇보다 적이 매 프레임 마음을 바꾸기 시작한다.

한 발짝 우회로로 갔다가, 다시 벽으로 갔다가, 또 눈앞의 유닛을 보고 방향을 틀어버린다.

뭔가 똑똑하게 판단하는 것 같은데 실제로 보면 우왕좌왕한다....
나는 이미 이 어려움을.. 졸작 때 겪어봤다...

결론부터 말하면 현재 구조의 중심은 다음과 같다.

감지
↓
전략 판단
↓
명령 생성
↓
이동·공격 실행
↓
실패 피드백
↓
재판단

그럼 하나씩 살펴보자.

전체 구조

적 하나는 크게 네 부분으로 나뉜다.

EnemyAgent
│
├─ EnemyBrain
│   ├─ 가까운 전투 대상 탐색
│   └─ EnemyAssaultPlanner 호출
│
├─ EnemyAssaultPlanner
│   ├─ 열린 길 비용 계산
│   ├─ 돌파 비용 계산
│   └─ 둘 중 더 빠른 전략 선택
│
├─ EnemyOrder
│   └─ 판단 결과를 담는 값
│
└─ EnemyOrderExecutor
    ├─ 경로 요청
    ├─ 이동
    ├─ 공격
    └─ 실패 결과 반환

EnemyAgent는 전체 흐름만 연결한다.

EnemyBrain은 무엇을 할지 정하고, EnemyOrderExecutor는 그 결정을 실제 행동으로 옮긴다.

여기서 중요한 것은 생각하는 코드와 몸을 움직이는 코드가 서로의 세부 구현을 모른다는 점이다.

비유하자면 EnemyBrain은 내비게이션을 보는 운전자이고, EnemyOrderExecutor는 자동차다.

운전자는 "저 벽 앞까지 가서 철거하자"라고 결정한다.

자동차는 엔진과 바퀴를 이용해 그 위치까지 이동한다.

자동차가 길을 갈 수 없다면 운전자에게 "이 경로는 막혔다"고 알려준다.

운전자가 직접 바퀴의 회전량까지 계산하기 시작하면 판단과 이동이 한 클래스에 엉켜버린다.

현재 구조에서는 다음과 같은 명령만 전달한다.

public enum EnemyOrderType
{
    Idle,
    Move,
    Hold,
    AttackMove,
    Attack,
    BreakBlocker
}

EnemyOrder는 readonly struct다.

명령 하나를 만들기 위해 별도의 클래스 인스턴스를 계속 생성하지 않고, 명령의 종류와 위치, 대상 참조만 값으로 전달한다.

판단 우선순위

적의 판단 순서는 생각보다 단순하다. POC니까..!
~~POC지만 그래도 최적화에 신경을 많이 썼다.~~

1. 적 또는 코어가 이미 죽었는가?
   └─ Idle

2. 공격 가능한 이동 유닛이 근처에 있는가?
   └─ Attack

3. 코어까지 열린 길이 있는가?
   └─ AttackMove

4. 길을 여는 구조물을 찾을 수 있는가?
   └─ BreakBlocker

5. 아무 계획도 만들 수 없는가?
   └─ Hold

즉 전술과 전략이 나뉘어 있다.

근처 유닛을 공격하는 것은 전술적 판단이고, 코어까지 어떤 길로 갈지는 전략적 판단이다.

군대로 비유하면 이렇다.

부대의 최종 목표는 성에 도착하는 것이다. 다만 이동 중 바로 옆에서 아군을 공격하는 병사가 있다면 잠시 그 병사부터 처리한다.

가까운 적을 찾았다고 무조건 달려들지는 않는다.

현재 위치에서 바로 공격할 수 없을 경우 NavigationGrid.CanReach()로 실제 도달 가능한 대상인지 확인한다.

갈 수 없는 적을 발견했다면 일정 시간 동안 같은 대상을 다시 선택하지 않는다.

이것이 unreachableAggroCooldown이다.

비유하자면 막다른 골목 너머의 사람을 보고 계속 벽에 박는 대신, "저쪽은 방금 확인했는데 못 간다"라고 잠깐 메모해 두는 것이다.

A* Pathfinding, 가장 싼 길을 찾는 방법

적의 실제 이동 경로는 NavigationGrid가 계산한다.

맵을 일정한 크기의 셀로 나누고, 구조물이 차지한 셀을 막힌 칸으로 표시한다.

□ □ □ □ □
□ ■ ■ □ □
S □ ■ □ G
□ □ □ □ □

S는 시작, G는 목적지, ■는 이동할 수 없는 칸이다.

이 위에서 사용하는 알고리즘이 A*, A Star다.

A*가 뭔데

A*는 지금까지 실제로 이동한 비용과, 목적지까지 남았을 것으로 예상되는 비용을 함께 본다.

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

g(n) : 시작점에서 현재 칸까지 실제로 사용한 비용
h(n) : 현재 칸에서 목적지까지 남았다고 예상하는 비용
f(n) : 이 칸을 경유했을 때의 전체 예상 비용

택배 기사로 비유하면 이해하기 쉽다.

이미 20분을 달려온 길이라도 목적지까지 1분 남았다면 좋은 후보일 수 있다.

반대로 지금까지 1분밖에 안 달렸어도 목적지 반대편으로 가고 있다면 좋은 후보가 아니다.

현재 구현에서는 상하좌우 이동 비용을 10, 대각선 이동 비용을 14로 사용한다.

대각선의 실제 길이인 √2 ≒ 1.414를 정수 비용으로 근사한 것이다.

Heuristic에는 대각선 이동이 가능한 8방향 Grid에 맞는 Octile Distance를 사용한다.

return 10 * (dx + dy) - 6 * Mathf.Min(dx, dy);

이름은 어려운데, 비유하면 바둑판에서 왕이 움직이는 거리를 예상하는 방식이다.

가로와 세로를 따로 돌아가지 않고 가능한 만큼 대각선으로 먼저 이동한다.

Binary Heap, 다음 후보를 빨리 꺼내기

A*는 매번 f(n)이 가장 작은 칸을 꺼내야 한다.

모든 후보를 처음부터 훑으면 후보가 많아질수록 비싸진다.

그래서 Binary Heap을 우선순위 큐로 사용한다.

병원 접수 창구를 떠올리면 된다.

새 환자가 들어올 때마다 모든 사람을 다시 정렬하는 것이 아니라, 우선순위가 높은 사람이 빠르게 앞으로 오도록 정리된 구조다.

삽입과 삭제의 시간 복잡도는 대략 O(log N)이다.

Corner Cutting 방지

대각선 이동을 허용하면 한 가지 문제가 생긴다.

■ ↗
S ■

수학적으로는 대각선 칸이 비어 있어도 실제 유닛은 두 장애물 사이의 모서리를 통과할 수 없다.

그래서 대각선으로 이동할 때는 옆의 가로·세로 셀도 함께 검사한다.

양쪽 중 하나라도 막혀 있으면 대각선 이동을 허용하지 않는다.

문틈 사이로 냉장고를 옮길 때 중심점만 통과한다고 냉장고 전체가 통과하는 것은 아닌 것과 같다.

Connected Component, 길찾기 전에 실패를 알아내기

A*를 아무리 최적화해도 애초에 갈 수 없는 목적지를 끝까지 찾으면 비용이 발생한다.

그래서 Grid가 갱신될 때 Connected Component, 연결 요소를 미리 계산한다.

서로 오갈 수 있는 모든 빈 셀에 같은 번호를 붙이는 방식이다.

1 1 1 ■ 2 2
1 1 1 ■ 2 2
1 1 1 ■ 2 2

시작점이 1번 구역, 목적지가 2번 구역이라면 A*를 실행할 필요도 없다.

두 구역 사이에는 길이 없기 때문이다.

섬의 이름을 먼저 확인하는 것과 비슷하다.

출발지와 목적지가 서로 다른 섬이라면 자동차 내비게이션을 켜기 전에 배가 필요하다는 것을 알 수 있다.

이 검사는 경로 전체를 찾는 것보다 훨씬 싸다.

적이 근처 유닛을 공격할 수 있는지 판단할 때도 동일한 연결 요소를 사용한다.

Path Smoothing과 Gate

Grid에서 찾은 원본 경로는 셀 중심을 따라가기 때문에 꺾임이 많다.

원본
S → □ → □
        ↓
        □ → G

현재 경로에서는 멀리 있는 노드까지 직선으로 통과할 수 있는지 확인하고, 보이는 중간 점들을 제거한다.

이를 Line of Sight Path Smoothing이라고 한다.

등산로 이정표를 생각하면 된다.

다음 이정표가 눈앞에 보이고 그 사이에 절벽도 없다면, 중간에 놓인 작은 표지판을 전부 들를 필요는 없다.

다만 단순한 점 목록만 따라가면 여러 유닛이 정확히 같은 선 위에 겹친다.

그래서 최종 경로를 NavGate의 배열로 바꾼다.

Gate는 통로의 중심, 진행 방향, 안전하게 사용할 수 있는 폭을 가진다.

벽       벽
│ A B C │  ← 같은 Gate의 서로 다른 Lane
│   ↓   │

각 적은 Instance ID에서 계산한 Lane Offset을 사용한다.

모두 같은 길을 공유하되 통로 안에서는 살짝 다른 차선을 타는 것이다.

고속도로 전체를 차량마다 새로 계산하지 않고, 같은 도로 위에서 차선만 다르게 사용하는 것과 같다.

통로가 좁아지면 Offset을 점차 중앙으로 수축한다.

그래도 안전하지 않다면 Gate 앞에서 정렬한 뒤 중앙으로 진입한다.

예쁜 이동보다 벽을 뚫고 지나가지 않는 것을 우선한 처리다.

벽을 부술지, 돌아갈지 어떻게 정할까

여기서부터가 이번 적 AI의 핵심이다.

길이 막혀 있을 때 무조건 가장 가까운 벽을 때리게 만들 수도 있다.

하지만 가장 가까운 벽이 반드시 가장 좋은 벽은 아니다.

벽을 부순 뒤 코어까지 훨씬 먼 길이 남아 있을 수도 있고, 체력이 높은 벽일 수도 있다.

그래서 모든 선택을 예상 소요 시간, ETA로 환산한다.

ETA는 Estimated Time of Arrival의 약자다.

쉽게 말하면 내비게이션에 표시되는 "도착까지 12분"이다.

열린 길의 비용

열린 길 시간 = 코어까지 이동 거리 / 이동 속도

벽을 부수는 길의 비용

돌파 시간
= 벽 앞까지 이동 시간
+ 벽을 부수는 시간
+ 벽 뒤에서 코어까지 이동 시간

코드의 의미를 식으로 옮기면 다음과 같다.

T_breach
= DistanceToFront / MoveSpeed
+ BlockerHealth / FrontDPS
+ PostBreachDistance / MoveSpeed

이제 서로 성격이 다른 선택지를 같은 단위인 초로 비교할 수 있다.

거리 10m와 벽 체력 100을 그대로 비교하는 것은 사과와 의자를 비교하는 것과 같다.

하지만 둘을 "몇 초가 걸리는가"로 바꾸면 비교가 가능하다.

우회로 : 8.2초
벽 A   : 6.7초
벽 B   : 11.4초

선택 : 벽 A

이것은 거창한 머신러닝이 아니다.

명확하게 설계한 Utility Cost, 효용 비용 기반 의사결정에 가깝다.

AI가 똑똑해 보이는 이유는 복잡한 모델을 사용해서가 아니라, 게임의 목표에 맞는 비교 기준을 만들었기 때문이다.

Reverse Dijkstra Cost Field

벽 후보마다 "벽을 부순 뒤 코어까지 얼마나 남았는가"를 계산해야 한다.

후보가 10개라면 코어까지의 길찾기를 10번 해야 할까?

그렇게 만들면 적과 구조물이 늘어날수록 전략 판단 비용도 빠르게 커진다.

현재 구현에서는 코어를 시작점으로 역방향 Dijkstra 비용장을 한 번 만든다.

Dijkstra는 모든 방향으로 물이 퍼지는 모습과 비슷하다.

코어에서 물을 부으면 가까운 셀부터 차례로 물이 닿고, 각 셀에는 코어까지의 최단 비용이 남는다.

코어에서의 비용

40 30 20 10  0
50 40 30 20 10
60 50 40 30 20

이후 각 벽 뒤의 셀에서는 저장된 숫자만 읽으면 된다.

비용장 생성 1회
↓
벽 A 뒤의 비용 조회
벽 B 뒤의 비용 조회
벽 C 뒤의 비용 조회

이를 Many-to-One Query 최적화라고 볼 수 있다.

여러 출발점이 하나의 목적지인 코어를 바라보므로, 목적지 중심의 계산 결과를 공유하는 것이다.

비용장은 다음 조건이 같으면 재사용한다.

Navigation Grid 버전이 같음
Goal Cell이 같음

구조물이 생기거나 사라져 지형이 바뀌면 버전이 증가하고, 그때만 다시 만든다.

배달 기사 30명이 같은 물류센터로 돌아갈 때 각자 지도를 새로 조사하지 않고, 물류센터 기준 거리 지도를 한 장 공유하는 것과 같다.

Breach Front, 모두 같은 벽에 몰려도 빠르진 않다

벽 하나에 적이 많이 붙으면 DPS가 올라가므로 더 빨리 부술 수 있다.

그렇다고 적 100명이 작은 벽 하나에 동시에 붙을 수는 없다.

실제 공간에는 둘레와 유닛 크기로 결정되는 수용량이 있다.

그래서 BreachFrontRegistry는 벽마다 다음 정보를 기록한다.

Assigned : 이 벽에 배정된 적 수
Capacity : 실제로 공격 가능한 자리 수
DPS      : 배정된 적의 총 공격력

수용량을 초과하면 유효 DPS를 포화시킨다.

Saturation = min(1, Capacity / Assigned)
EffectiveDPS = max(OwnDPS, TotalDPS × Saturation)

엘리베이터에 20명이 도착했다고 해서 정원 8명의 엘리베이터가 20명을 한 번에 옮길 수는 없다.

적의 숫자만 보는 것이 아니라 실제로 벽 주변에 설 수 있는 자리를 함께 보는 것이다.

이 값을 돌파 ETA에 반영하면 각 적은 이미 형성된 공격 전선의 화력을 고려할 수 있다.

따라서 "가까운 벽"이 아니라 현재 아군 배치까지 포함했을 때 가장 빨리 열 수 있는 전선을 선택한다.

히스테리시스, 더 좋은 길이 생겼다고 바로 바꾸지 않는다

전략 AI에서 가장 보기 싫은 장면 중 하나는 결정이 계속 흔들리는 것이다.

벽 공격이 0.1초 빠름
↓
벽으로 이동
↓
이번에는 우회로가 0.05초 빠름
↓
다시 우회

이를 Thrashing, 또는 의사결정 진동이라고 한다.

전자레인지가 목표 온도에서 0.001도만 달라져도 매 순간 켜졌다 꺼진다고 생각해 보자.

고장 나지는 않더라도 좋은 제어 방식은 아니다.

현재 Planner는 벽을 부수기로 결정한 뒤, 열린 길이 생겨도 두 조건을 모두 만족할 때만 계획을 바꾼다.

새 경로가 현재 계획의 75% 이하인가?
그리고 최소 1.25초 이상 절약되는가?

비율과 절대 이득을 함께 본다.

현재 계획이 100초라면 1초 개선은 의미가 작고, 현재 계획이 2초라면 1초 개선은 매우 크다.

둘 중 하나만 사용하면 특정 구간에서 지나치게 민감하거나 둔해질 수 있다.

이처럼 상태를 바꿀 때 문턱을 두는 것을 Hysteresis, 히스테리시스라고 한다.

문이 바람에 덜컹거리지 않도록 약간의 마찰을 주는 것과 비슷하다.

모든 적이 같은 프레임에 생각하지 않게 하기

전략 계산을 매 프레임 할 필요는 없다.

사람도 목적지까지 걸어가면서 1초에 60번씩 새 경로를 검색하지 않는다.

현재 전략 재평가 간격은 기본적으로 약 0.45초다.

하지만 모든 적에게 정확히 같은 간격을 적용하면 다른 문제가 생긴다.

Frame N
적 100마리 전략 계산

Frame N+1 ~ N+26
계산 없음

Frame N+27
적 100마리 전략 계산

평균 비용은 낮아도 특정 프레임에 Spike가 생긴다.

그래서 Instance ID를 Seed로 사용해 각 적의 재평가 시점에 약간의 차이를 준다.

Enemy A : 0.39초 뒤
Enemy B : 0.44초 뒤
Enemy C : 0.51초 뒤

이를 Temporal Staggering, 시간 분산이라고 한다.

회사 점심시간을 전 직원이 정확히 12시에 시작하면 엘리베이터가 터진다.

11시 50분, 12시, 12시 10분으로 조금씩 나누면 같은 인원이 움직여도 순간 혼잡은 줄어든다.

전체 연산량뿐 아니라 한 프레임에 몰리는 연산량을 관리하는 최적화다.

Repath를 줄이는 Versioning

구조물이 설치되거나 파괴되면 Navigation Grid가 바뀐다.

가장 단순한 구현은 지형이 바뀔 때 모든 적이 즉시 경로를 다시 찾는 것이다.

적이 많아지면 한 프레임에 A* 요청이 몰린다.

현재 구조에서는 지형 변경을 세 가지 정보로 추적한다.

Version         : 전체 Navigation 변경
BlockingVersion : 새롭게 길을 막은 변경
OpeningVersion  : 새롭게 길을 연 변경

길이 열렸을 때와 막혔을 때의 의미는 다르다.

길이 열렸다면 현재 길이 없는 적이 다시 시도할 이유가 생긴다.

길이 막혔다면 현재 경로가 실제 변경 영역을 지나가는 적만 다시 계산하면 된다.

구조물 변경 Bounds와 현재 Route 선분이 교차하지 않으면 기존 경로를 유지한다.

서울의 도로 하나가 공사에 들어갔다고 부산의 모든 내비게이션이 경로를 다시 찾을 필요는 없는 것과 같다.

그리고 막힘으로 인한 경로 재계산은 기본적으로 프레임당 6개까지만 허용한다.

Frame N     : 6개 Repath
Frame N + 1 : 6개 Repath
Frame N + 2 : 6개 Repath

작업 총량이 같더라도 여러 프레임으로 나누면 순간적인 Frame Spike를 줄일 수 있다.

Spatial Hashing, 모든 유닛을 전부 찾지 않기

가장 가까운 적을 찾는 단순한 방법은 모든 Combatant를 순회하는 것이다.

유닛이 N마리이고 모든 유닛이 서로를 검사하면 대략 O(N²)에 가까워진다.

유닛 10마리   → 최대 100번 수준
유닛 100마리  → 최대 10,000번 수준
유닛 1,000마리 → 최대 1,000,000번 수준

그래서 CombatSpatialIndex는 월드 공간을 큰 셀로 나눈다.

┌─────┬─────┬─────┐
│     │ E E │     │
├─────┼─────┼─────┤
│ F   │ F E │     │
├─────┼─────┼─────┤
│     │     │ E   │
└─────┴─────┴─────┘

적을 찾을 때는 공격 범위가 겹치는 셀만 조회한다.

전화번호부 전체를 처음부터 읽는 대신, 먼저 지역과 성씨로 페이지를 좁히는 것이다.

RtsMovementSystem의 유닛 간 Separation도 같은 방식의 공간 해싱을 사용한다.

주변 3×3 셀만 검사해서 가까운 유닛과 겹치지 않도록 옆 방향 힘을 더한다.

전방 이동 속도는 유지하고 측면 성분만 조정하기 때문에, 서로 밀어내느라 목적지 반대편으로 후퇴하는 현상도 줄인다.

GC와 메모리 최적화

AI 로직은 한 번의 계산보다 반복 횟수가 무섭다.

적 1마리에게는 사소한 할당도 100마리, 60FPS가 되면 다르게 보인다.

현재 코드에는 다음과 같은 재사용 전략이 들어가 있다.

1. 검색 배열 재사용

A*의 g, f, parent, seen, closed, Heap 배열을 Grid 크기에 맞춰 한 번 만들고 계속 사용한다.

경로 요청마다 새 배열을 만들지 않는다.

2. Search ID Stamping

매 검색마다 seen과 closed 배열 전체를 Clear()하는 대신 검색 번호를 증가시킨다.

1번 검색에서 방문 → seen[node] = 1
2번 검색에서 방문 → seen[node] = 2

현재 검색 번호와 값이 같을 때만 이번 검색에서 방문한 것으로 본다.

호텔의 모든 방문 기록을 지우는 대신, 손님의 입장 날짜를 적어 오늘 방문자인지 확인하는 방식이다.

검색 번호가 int.MaxValue에 도달했을 때만 배열을 초기화한다.

3. Dictionary의 List 재사용

Spatial Hash Grid를 갱신할 때 Dictionary와 Cell List를 버리지 않는다.

이번 프레임에 사용한 List만 Clear()하고 다시 채운다.

컨테이너를 매번 버리고 새로 사는 것이 아니라, 내용물만 비우고 다시 쓰는 것이다.

4. 제곱 거리 비교

단순히 범위 안에 있는지 확인할 때는 Vector2.Distance() 대신 sqrMagnitude를 사용한다.

제곱근 계산 없이도 거리의 대소 비교가 가능하기 때문이다.

5. 명령을 값 타입으로 전달

EnemyOrder, EnemyExecutionSnapshot, EnemyExecutionFeedback은 readonly struct다.

판단과 실행 사이에서 짧게 오가는 메시지를 매번 Heap 객체로 만들 필요가 없다.

다만 현재 경로 생성이 완전히 Allocation-Free인 것은 아니다.

Path Smoothing 단계의 임시 List와 최종 NavGate[]는 경로를 새로 만들 때 생성된다.

그래서 이 시스템의 핵심은 "할당이 0이다"가 아니라, Repath 자체를 줄이고 대규모 검색용 버퍼를 재사용해 반복 비용을 통제한다는 데 있다.

최적화 수치는 Profiler로 별도 측정하기 전까지 과장하지 않는 것이 맞다.

같은 명령을 다시 시작하지 않기

Brain은 매 프레임 명령을 만들지만 Executor가 매번 이동을 처음부터 시작하지는 않는다.

SameIntent()로 이전 명령과 의도가 같은지 확인한다.

이전 : Attack(Target A)
현재 : Attack(Target A)

결과 : 같은 의도, 실행 유지

움직이는 대상을 공격할 때 대상의 좌표는 계속 바뀐다.

좌표가 조금 변했다는 이유로 매 프레임 새 명령으로 취급하면 경로와 실행 상태가 계속 초기화된다.

그래서 Attack과 AttackMove는 위치가 아니라 Target Identity, 대상의 정체성을 기준으로 같은 의도인지 판단한다.

친구와 카페에서 만나기로 했는데 친구가 의자에서 조금 움직였다고 약속 자체를 새로 잡지는 않는 것과 같다.

실패 피드백과 복구

Planner가 만든 계획이 항상 성공하는 것은 아니다.

판단 직후 구조물이 사라질 수도 있고, 이동 중 새로운 구조물이 생길 수도 있다.

Executor는 실패를 숨기지 않고 Brain으로 돌려보낸다.

UnreachableTarget
StrategicPlanInvalid

Brain은 도달할 수 없는 전술 대상을 잠시 제외한다.

Planner는 유효하지 않은 벽 돌파 계획을 폐기하고 다시 선택한다.

또한 Mover가 일정 시간 실제로 전진하지 못하면 Stuck을 감지한다.

이때 Lane Offset을 0으로 되돌리고 중앙 경로로 복구한 뒤 Repath를 시도한다.

즉 처음부터 완벽한 계획만 만들겠다는 방식이 아니다.

계획
↓
실행
↓
현실 확인
↓
수정

로봇 청소기가 가구 배치를 완벽히 예측하지 못해도, 부딪힌 뒤 방향을 바꿀 수 있으면 결국 청소를 계속할 수 있는 것과 같다.

알고리즘과 역할을 한 번에 정리하면

용어	프로젝트에서의 역할	쉽게 말하면
A*	개별 적의 최단 경로 탐색	예상 시간을 보며 길을 고르는 내비게이션
Octile Distance	8방향 이동의 예상 비용	대각선 지름길을 고려한 거리
Binary Heap	가장 유망한 탐색 셀 선택	우선순위 환자를 빠르게 꺼내는 대기열
Connected Component	도달 불가능한 목적지 조기 판정	서로 다른 섬인지 먼저 확인하기
Path Smoothing	불필요한 중간 경유지 제거	눈에 보이는 이정표는 건너뛰기
Gate / Lane	통로 폭 안에서 분산 이동	같은 도로를 여러 차선으로 사용하기
Reverse Dijkstra	코어까지의 공용 비용장 생성	물류센터 기준 거리 지도 한 장 공유하기
ETA Cost	우회와 돌파를 초 단위로 비교	내비게이션의 도착 예정 시간
Hysteresis	사소한 이득에 계획이 흔들리는 것 방지	바람에 문이 덜컹거리지 않게 마찰 주기
Temporal Staggering	전략 계산을 여러 프레임으로 분산	점심시간을 조금씩 다르게 잡기
Spatial Hashing	가까운 유닛 후보만 검사	전화번호부의 페이지부터 좁히기
Versioning	지형 변경 때 필요한 경로만 갱신	공사 구간을 지나는 차량만 재탐색하기
Search Stamping	검색 배열 전체 초기화 생략	기록을 지우지 않고 날짜로 구분하기

시간 복잡도도 대략 살펴보자

정확한 실행 시간은 맵 크기와 장애물 배치, 유닛 수에 따라 달라진다.

그래도 구조적인 비용은 대략 다음처럼 볼 수 있다.

작업	대략적인 비용
Connected Component 재구축	`O(V + E)`
A* 경로 탐색	일반적으로 `O((V + E) log V)`
Reverse Dijkstra 비용장	`O((V + E) log V)`
비용장 생성 후 거리 조회	`O(1)`
Spatial Hash 재구축	`O(N)`
주변 대상 탐색	전체 N이 아닌 겹치는 셀의 후보 수에 비례
벽 후보 평가	유효한 `NavObstacle` 후보 수에 비례

V는 Walkable Cell 수, E는 셀 사이 연결 수, N은 유닛 수다.

여기서 중요한 점은 Big-O 하나만 보는 것이 아니다.

같은 O(N)이라도 매 프레임 새 List를 생성하는 것과 기존 List를 재사용하는 것은 GC 관점에서 다르다.

반대로 이론상 빠른 알고리즘이라도 모든 적이 같은 프레임에 실행하면 Spike가 생길 수 있다.

결국 실시간 게임에서는 다음 세 가지를 함께 봐야 한다.

총 연산량
+ 한 프레임에 몰리는 양
+ 반복 과정에서 생기는 메모리 할당

결과적으로 얻은 것

처음에는 적이 코어까지 걸어가다가 벽을 만나면 벽을 때리게 만들면 된다고 생각했다.

하지만 실제로 만들어보니 문제는 "벽을 때릴 수 있는가"가 아니었다.

어느 벽을 선택할 것인가
↓
언제 기존 계획을 버릴 것인가
↓
많은 적이 같은 판단을 해도 버틸 수 있는가
↓
이동 중 지형이 바뀌면 어떻게 복구할 것인가

가 더 중요했다.

이번 구조에서 가장 마음에 드는 부분은 모든 판단을 가능한 한 시간 비용으로 바꾼 것이다.

벽의 거리, 체력, 아군 화력, 벽 뒤의 남은 거리처럼 단위가 다른 값을 초로 통일하니 선택 기준이 명확해졌다.

그리고 최적화는 마지막에 별도의 장치를 하나 붙인 것이 아니었다.

도달 가능성 사전 판정
비용장 공유
경로 버전 관리
재평가 시간 분산
공간 해싱
검색 버퍼 재사용

처럼 구조 안에 나누어 들어가 있다.

물론 아직 모든 것이 끝난 것은 아니다.

경로 결과 배열의 Pooling, 다수 적의 전략 결과 공유, 실제 기기에서의 Profiler 측정 등 더 확인할 부분은 남아 있다.

다만 무작정 "AI니까 매 프레임 똑똑하게 생각하게 하자"에서 벗어나,

필요한 순간에만 생각하고, 같은 계산은 공유하고, 실행이 실패하면 다시 판단한다.

라는 기준은 잡힌 것 같다.

똑똑한 AI는 어려운 알고리즘 하나로 만들어지는 것이 아니라, 좋은 질문을 싸게 반복할 수 있는 구조에서 나오는 것 아닐까?... 싶다.

프로젝트를 하나 마무리해보니 어차피 생길 병목은 미리 잡고 가는 것이 좋은 것 같다.
그때가서 래거시를 잔뜩 생성해가며 최적화를 넣을 바에야 미리 잡는게 시간을 더 아끼는 것 같다.

a-a

인디 게임 개발로 먹고 살기

이전 포스트

[Unity6] Singleton 초기화 시 `OnEnable`에서 `null`이 나올 수 있는가

2개의 댓글

임선구

2026년 8월 28일

이번 글은 지피티 향이 좀 진하네요?

1개의 답글