게임 알고리즘 핵심 정리

wayhope Game

게임에서 알고리즘이라고 하면 보통 복잡한 수학이나 코딩 테스트부터 떠올리기 쉽다.

그런데 게임 개발에서 실제로 자주 만나는 알고리즘은 조금 다르다.

플레이어가 이동할 위치를 찾거나, 적이 플레이어를 추적하거나, 여러 오브젝트 중 가장 가까운 대상을 찾거나, 맵에서 이동 가능한 경로를 계산하는 것처럼 게임의 규칙과 시스템을 실제 동작으로 바꾸는 과정에서 알고리즘이 계속 등장한다.

특히 게임에서는 같은 문제라도 성능과 상황에 따라 적절한 알고리즘을 선택해야 한다.

게임에서 알고리즘이 필요한 이유

게임은 매 순간 상태가 변한다.

플레이어가 움직이고, 적이 움직이고, 투사체가 날아가고, 맵의 상태가 바뀐다.

예를 들어 적 AI가 플레이어를 따라간다고 하자.

단순하게 생각하면

적 위치 -> 플레이어 위치 확인 -> 플레이어 방향으로 이동

이면 될 것 같다.

그런데 벽이 있다면 이야기가 달라진다.

적이 플레이어 방향으로 직선 이동하면 벽에 막힌다.

따라서

현재 위치 -> 이동 가능한 공간 탐색 -> 플레이어까지의 경로 계산 -> 경로를 따라 이동

이라는 별도의 문제가 생긴다.

이때 사용하는 대표적인 알고리즘이 Pathfinding이다.

탐색과 최적화

게임 알고리즘에서 자주 나오는 문제는 결국 몇 가지 형태로 정리할 수 있다.

무엇을 찾을 것인가?
-> 어떻게 찾을 것인가?
-> 얼마나 빠르게 찾을 것인가?
-> 어떤 결과를 선택할 것인가?

예를 들어 적 AI가 가장 가까운 플레이어를 찾아야 한다면 모든 플레이어를 확인할 수 있다.

Player nearest = null;
float nearestDistance = float.MaxValue;

foreach (var player in players)
{
    float distance = Vector3.Distance(transform.position, player.position);

    if (distance < nearestDistance)
    {
        nearestDistance = distance;
        nearest = player;
    }
}

플레이어가 몇 명 없다면 충분하다.

하지만 수천 개의 대상 중 매 프레임마다 가장 가까운 대상을 찾아야 한다면 이야기가 달라진다.

알고리즘 자체가 틀린 것은 아니지만 문제의 크기와 실행 빈도에 맞는 방법인지를 생각해야 한다.

시간 복잡도

알고리즘의 성능을 이야기할 때 자주 사용하는 개념이 시간 복잡도다.

예를 들어 배열의 모든 원소를 한 번씩 확인한다면 데이터가 N개일 때 대략 N번의 작업이 필요하다.

이를

O(N)

으로 표현한다.

반면 데이터가 정렬되어 있고 이진 탐색을 사용할 수 있다면 검색 범위를 절반씩 줄일 수 있다.

O(log N)

이 된다.

게임에서는 이런 차이가 꽤 중요하다.

한 번 실행하는 코드라면 큰 문제가 아닐 수 있다.

하지만 다음 코드가

Update()

에서 매 프레임 실행된다면 이야기가 달라진다.

1회 실행
-> O(N)

초당 60회 실행
-> O(N) * 60

대상이 많아질수록 비용도 커진다.

그래서 게임 알고리즘에서는 알고리즘의 복잡도뿐만 아니라 얼마나 자주 실행되는지도 같이 봐야 한다.

게임에서 자주 사용하는 알고리즘

게임 개발에서 자주 접하는 알고리즘은 상당히 많다.

대표적인 것만 보면 다음과 같다.

탐색
-> DFS
-> BFS
-> Binary Search

경로 탐색
-> Dijkstra
-> A*

자료구조
-> Hash Table
-> Heap
-> Priority Queue

공간 분할
-> Grid
-> Quadtree
-> Octree
-> Spatial Hash

AI
-> Finite State Machine
-> Behavior Tree
-> Utility AI

그래프
-> Graph Traversal
-> Shortest Path

이들이 전부 별개의 지식처럼 보이지만 실제로는 서로 연결되어 있다.

특히 게임에서는 Graph와 Search를 이해하는 것이 중요하다.

게임 맵을 Graph로 볼 수 있다

길찾기를 이해하려면 먼저 맵을 Graph로 생각해볼 수 있다.

예를 들어 이런 Grid가 있다고 하자.

각 칸을 하나의 Node라고 생각한다.

그리고 서로 이동할 수 있는 칸을 Edge로 연결한다.

이렇게 보면 게임 맵이 하나의 Graph가 된다.

그다음 문제는 간단해진다.

Start Node
-> Goal Node

두 Node 사이를 연결하는 경로를 찾으면 된다.

이 관점은 Grid 기반 게임뿐만 아니라 NavMesh 기반 이동이나 복잡한 AI 이동 시스템을 이해할 때도 도움이 된다.

BFS

BFS(Breadth-First Search)는 가까운 노드부터 차례대로 탐색하는 방식이다.

예를 들어 다음과 같은 그래프가 있다고 하자.

A에서 시작하면

A
-> B, C
-> D, E, F

순서로 탐색한다.

Queue를 사용해서 구현할 수 있다.

Queue

A
-> B, C
-> C, D, E
-> D, E, F

BFS는 모든 간선의 비용이 동일한 경우 최단 경로를 찾는 데 사용할 수 있다.

Grid에서 한 칸 이동할 때 비용이 모두 동일하다면 BFS로 시작점에서 목표까지 최소 이동 횟수의 경로를 찾을 수 있다.

DFS

DFS(Depth-First Search)는 한 방향으로 깊게 들어간 뒤 더 이상 갈 수 없으면 돌아오는 방식이다.

A -> B -> D ...

재귀 또는 Stack으로 구현할 수 있다.

DFS는 미로 탐색이나 연결된 영역 찾기, 그래프 탐색 등에 사용할 수 있다.

다만 BFS와 달리 일반적인 가중치가 동일한 Graph에서 최단 경로를 찾는 용도로 사용하는 알고리즘은 아니다.

게임에서는 Flood Fill이나 맵 영역 탐색 같은 곳에서도 비슷한 형태의 탐색을 볼 수 있다.

Dijkstra

게임에서 이동 비용이 모두 같지 않다면 BFS만으로는 부족하다.

예를 들어

평지 -> 이동 비용 1
숲   -> 이동 비용 3
늪   -> 이동 비용 5

이라고 해보자.

단순히 지나가는 칸의 개수만 최소화하면

평지 4칸

보다

평지 1칸 + 늪 1칸

을 더 짧다고 판단할 수도 있다.

하지만 실제 비용은 각각

4
6

이다.

Dijkstra 알고리즘은 이런 가중치가 있는 Graph에서 최소 비용 경로를 찾는 데 사용할 수 있다.

핵심은 현재까지 계산된 비용이 가장 작은 Node부터 탐색하는 것이다.

이 때문에 Priority Queue 같은 자료구조를 함께 사용하는 경우가 많다.

A*

게임에서 가장 많이 접하게 되는 경로 탐색 알고리즘 중 하나가 A*다.

A*는 Dijkstra와 비슷하게 실제 이동 비용을 고려하면서도 목적지까지의 예상 비용을 함께 사용한다.

각 Node에 대해 대략 다음 값을 사용한다.

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

여기서

g(n)-> 시작점에서 현재 Node까지 실제로 들어간 비용

h(n)-> 현재 Node에서 목표까지의 예상 비용

f(n)-> 둘을 합친 예상 전체 비용

예를 들어 현재 위치에서 목표가 오른쪽에 있다면 목표와 가까운 방향의 Node를 우선적으로 확인할 수 있다.

그래서 Dijkstra가 모든 방향을 비교적 넓게 탐색하는 상황에서도 A*는 목표 방향에 탐색을 집중할 수 있다.

A*에서 Heuristic이 중요하다

A*의 h(n)을 Heuristic이라고 한다.

Grid에서 상하좌우로만 움직인다면 Manhattan Distance를 사용할 수 있다.

h(n)
= |x1 - x2| + |y1 - y2|

대각선 이동이 가능하다면 문제에 맞는 다른 거리 함수를 사용할 수 있다.

여기서 중요한 것은 Heuristic이 어떤 값을 반환하느냐에 따라 A*의 탐색 특성이 달라진다는 것이다.

Heuristic이 너무 작으면 Dijkstra에 가까워진다.

반대로 실제 최소 비용보다 큰 값을 과하게 사용하면 최단 경로를 보장하지 못할 수 있다.

그래서 문제의 이동 규칙에 맞는 Heuristic을 선택해야 한다.

실제 게임에서는 A*만으로 끝나지 않는다

A* 자체를 구현하는 것은 어렵지 않다.

문제는 실제 게임에서 A*를 언제 실행할 것인가다.

예를 들어 적 500마리가 있고 모든 적이 매 프레임 A*를 실행한다면 상당한 계산량이 발생할 수 있다.

500 Agents x 60 FPS = 초당 30,000번의 Pathfinding 요청

물론 실제 비용은 맵 크기와 구현 방식 등에 따라 달라진다.

그래서 실제 게임에서는 여러 방법을 함께 사용한다.

Path Caching
Path Reuse
Path Update Interval
Hierarchical Pathfinding
Navigation Mesh
Path Smoothing

경로를 매 프레임 새로 계산하는 대신 일정 시간 동안 재사용할 수도 있다.

적이 움직였다고 해서 매 프레임 전체 경로를 다시 계산할 필요가 없는 경우도 많다.

NavMesh

게임에서 자유롭게 이동하는 캐릭터의 경로를 Grid로 처리하면 비효율적일 수 있다.

예를 들어 넓은 3D 맵을 작은 Grid로 전부 나누면 Node가 지나치게 많아진다.

그래서 이동 가능한 영역 자체를 하나의 그래프로 표현하는 방식이 사용된다.

그중 대표적인 것이 Navigation Mesh, 흔히 NavMesh라고 부른다.

개념적으로는

맵
-> 이동 가능한 영역 추출
-> Navigation Mesh 생성
-> 영역 간 연결 관계 구성
-> Pathfinding

형태다.

Grid가 공간을 일정한 크기의 칸으로 나누는 방식이라면 NavMesh는 캐릭터가 실제로 이동할 수 있는 영역을 중심으로 표현한다.

그래서 복잡한 3D 환경에서 이동 경로를 계산할 때 유용하다.

공간 분할

게임에서는 “가장 가까운 적을 찾아라” 같은 문제도 자주 발생한다.

단순하게 구현하면 모든 객체를 확인한다.

Player
-> Enemy 1 확인
-> Enemy 2 확인
-> Enemy 3 확인
-> ...

객체가 적다면 문제가 없다.

하지만 수만 개의 객체가 존재한다면 매번 전부 확인하는 것은 비효율적이다.

이때 사용하는 방법 중 하나가 Spatial Partitioning, 공간 분할이다.

맵을 여러 영역으로 나누고 객체가 어느 영역에 있는지 관리한다.

플레이어가 A 영역에 있다면 모든 영역을 검사하는 대신 A 주변 영역만 확인할 수 있다.

대표적인 구조로

Grid
Quadtree
Octree
Spatial Hash

등이 있다.

자료구조도 알고리즘의 일부다

알고리즘만 보고 자료구조를 따로 생각하면 실제 구현에서 연결이 잘 안 될 수 있다.

예를 들어 BFS는 Queue와 잘 맞는다.

BFS-> Queue

DFS는 Stack과 잘 맞는다.

DFS-> Stack

Dijkstra와 A*는 우선순위가 높은 Node를 빠르게 가져와야 하기 때문에 Priority Queue가 자주 사용된다.

A*-> Priority Queue

따라서 알고리즘을 공부할 때는

문제-> 알고리즘-> 필요한 자료구조

순서로 보는 것이 좋다.

어떤 자료구조를 선택하느냐에 따라 같은 알고리즘도 실제 성능이 달라질 수 있다.

알고리즘의 선택은 상황에 따라 달라진다

어떤 알고리즘이 무조건 좋은 것은 아니다.

예를 들어 Grid에서 모든 이동 비용이 동일하고 목표까지 최소 이동 횟수만 필요하다면 BFS로 충분할 수 있다.

가중치가 있다면 Dijkstra를 고려할 수 있다.

목표 방향을 알고 있고 효율적인 탐색이 필요하다면 A*가 적합할 수 있다.

동일한 비용-> BFS

가중치 존재-> Dijkstra

가중치 + 목표 방향-> A*

하지만 실제 게임에서는 이것만 보고 결정하지 않는다.

맵 크기, Node 수, 이동 빈도, Agent 수, 메모리 사용량, 경로 갱신 주기까지 같이 봐야 한다.

알고리즘은 성능만의 문제가 아니다

게임 알고리즘에서 성능은 중요하지만 성능만 보는 것도 적절하지 않다.

예를 들어 가장 빠른 경로가 항상 플레이어가 원하는 경로는 아닐 수 있다.

적 AI가 매번 완벽하게 최단 경로만 선택하면 움직임이 지나치게 기계적으로 보일 수도 있다.

게임에서는 이런 경우 비용에 다른 요소를 넣을 수 있다.

이동 거리
+ 위험도
+ 적과의 거리
+ 지형 비용
+ 이동 시간

예를 들어 적이 있는 지역의 비용을 높이면 조금 돌아가더라도 안전한 경로를 선택하도록 만들 수 있다.

이런 식으로 알고리즘의 결과에 게임 디자인적인 의도를 반영할 수 있다.

알고리즘을 구현할 때 생각해야 하는 것

게임에서 알고리즘을 구현할 때는 보통 다음 순서로 생각하면 편하다.

문제 정의
-> 상태 정의
-> 탐색 공간 정의
-> 비용 정의
-> 알고리즘 선택
-> 자료구조 선택
-> 시간 복잡도 확인
-> 실제 실행 빈도 확인
-> 최적화

예를 들어 적이 목표까지 이동해야 한다면 먼저

Node는 무엇인가?
Edge는 무엇인가?

를 정해야 한다.

그다음

이동 비용은 동일한가?
목표까지의 예상 비용을 계산할 수 있는가?

를 본다.

그리고 BFS, Dijkstra, A* 같은 알고리즘을 선택한다.

여기까지가 알고리즘 선택이다.

그다음에는

몇 개의 Agent가 사용하는가?
몇 초마다 계산하는가?
맵 크기는 얼마나 되는가?

를 봐야 실제 게임에서 사용할 수 있는 구현이 나온다.

알고리즘을 공부하면서 느끼는 부분

실무 알고리즘은 단순히 알고리즘 이름을 외우는 것과는 조금 다르다.

BFS가 무엇인지 설명할 수 있는 것보다

왜 BFS를 사용하는가?

를 이해하는 것이 더 중요하다.

A*도 마찬가지다.

왜 Dijkstra가 아니라 A*인가?
왜 이 Heuristic을 사용하는가?
왜 매 프레임 실행하면 문제가 되는가?

이런 질문에 답할 수 있어야 실제 개발에서 알고리즘을 선택할 수 있다.

결국 알고리즘은 문제를 적절한 형태로 모델링하고, 그 문제에 맞는 탐색과 계산 방법을 선택하는 과정에 가깝다.

맵을 Graph로 바라보면 Pathfinding 문제가 보이고, 많은 객체가 있다면 공간 분할 문제가 보인다.

같은 기능도 데이터 규모와 실행 빈도에 따라 다른 알고리즘이 필요할 수 있다.

게임 문제-> 문제를 추상화-> 알고리즘 선택-> 자료구조 선택-> 구현-> 프로파일링-> 필요하면 개선

이 흐름을 익히는 것이 특정 알고리즘 하나를 외우는 것보다 훨씬 오래 남는다.