20강 : 최적화의 근간 (2) – 알고리즘 이야기
이 글에서는 알고리즘의 개념과 게임 개발에서의 중요성을 설명한다.
알고리즘은 단순히 문제를 해결하는 절차이며, 좋은 알고리즘은 소프트웨어의 성능, 메모리 관리, 반응 속도에 직접적인 영향을 준다.
특히 게임은 실시간 연산이 요구되므로, 효율적인 알고리즘 선택이 필수적이다.
1. 알고리즘이란?
알고리즘은 주어진 문제를 해결하기 위한 명확하고 유한한 단계이다.
예를 들어 정렬, 탐색, 경로 탐색 등 우리가 자주 접하는 문제를 해결하는 방법들이 모두 알고리즘이다.
프로그래밍에서는 이러한 알고리즘을 코드로 구현하여 문제를 해결한다.
2. 게임에서 알고리즘의 중요성
게임은 렌더링, 물리 계산, AI 처리 등 많은 연산을 실시간으로 수행해야 한다.
예를 들어 60 FPS의 게임이라면 매 프레임 16.6ms 안에 모든 연산을 마쳐야 한다.
따라서 빠르고 효율적인 알고리즘이 게임의 성능 최적화, 메모리 관리, 반응 속도에 결정적이다.
- 성능 최적화: 매 프레임마다 연산 속도가 느리면 프레임 드랍이나 게임 버벅임이 발생한다.
- 메모리 관리: 대용량 데이터를 처리하는 게임에서는 메모리를 효율적으로 사용하는 것이 중요하다.
- 반응 속도: 유저의 입력에 빠르게 반응해야 하므로, 알고리즘의 선택이 게임 플레이의 부드러움에 직접 영향을 미친다.
3. 게임에서 자주 쓰이는 알고리즘
3.1 탐색 알고리즘 (Search Algorithms)
3.1.1 선형 탐색 (Linear Search)
선형 탐색은 데이터를 처음부터 끝까지 하나씩 확인하며 원하는 값을 찾는다.
시간 복잡도는 O(n)이다.
#include <iostream>
#include <vector>
int linearSearch(const std::vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target)
return i;
}
return -1;
}
int main() {
std::vector<int> data = {3, 5, 1, 8, 4};
int target = 8;
std::cout << "타겟 " << target << "의 인덱스: " << linearSearch(data, target) << std::endl;
return 0;
}
### 3.1.2 이진 탐색 (Binary Search)
이진 탐색은 정렬된 배열에서 중간값을 기준으로 절반씩 나눠서 탐색한다.
시간 복잡도는 O(log n)이다.
**C++ 예시:**
```cpp
#include <iostream>
#include <vector>
int binarySearch(const std::vector<int>& arr, int target) {
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main() {
std::vector<int> sortedData = {1, 3, 5, 7, 9, 11};
int target = 7;
std::cout << "타겟 " << target << "의 인덱스: " << binarySearch(sortedData, target) << std::endl;
return 0;
}3.1.2 이진 탐색 (Binary Search)
이진 탐색은 정렬된 배열에서 중간값을 기준으로 절반씩 나눠서 탐색한다.
시간 복잡도는 O(log n)이다.
C++ 예시:
#include <iostream>
#include <vector>
int binarySearch(const std::vector<int>& arr, int target) {
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main() {
std::vector<int> sortedData = {1, 3, 5, 7, 9, 11};
int target = 7;
std::cout << "타겟 " << target << "의 인덱스: " << binarySearch(sortedData, target) << std::endl;
return 0;
}3.1.3 공간 분할 탐색 (Spatial Partitioning Search)
게임에서는 많은 공간 데이터를 효율적으로 관리하기 위해, 공간을 일정 영역으로 나누어 탐색과 충돌 검사를 빠르게 수행한다.
대표적으로 Quad-Tree, Oct-Tree, BSP Tree 등이 있다.
예를 들어 2D 게임에서는 Quad-Tree를 사용해 수십 또는 수백 개의 객체 중 충돌 가능성이 있는 객체를 빠르게 찾는다.
C++ 예시 (Quad-Tree 개념 증명 수준):
#include <iostream>
#include <vector>
#include <memory>
struct Point {
float x, y;
};
struct Rect {
float x, y, w, h;
bool contains(const Point& p) const {
return (p.x >= x && p.x < x + w && p.y >= y && p.y < y + h);
}
};
class QuadTree {
public:
QuadTree(const Rect& boundary, int capacity)
: boundary(boundary), capacity(capacity), divided(false) {}
bool insert(const Point& point) {
if (!boundary.contains(point))
return false;
if (points.size() < capacity) {
points.push_back(point);
return true;
} else {
if (!divided)
subdivide();
if (northeast->insert(point)) return true;
if (northwest->insert(point)) return true;
if (southeast->insert(point)) return true;
if (southwest->insert(point)) return true;
}
return false;
}
private:
void subdivide() {
float x = boundary.x;
float y = boundary.y;
float w = boundary.w / 2;
float h = boundary.h / 2;
Rect ne {x + w, y, w, h};
Rect nw {x, y, w, h};
Rect se {x + w, y + h, w, h};
Rect sw {x, y + h, w, h};
northeast = std::make_unique<QuadTree>(ne, capacity);
northwest = std::make_unique<QuadTree>(nw, capacity);
southeast = std::make_unique<QuadTree>(se, capacity);
southwest = std::make_unique<QuadTree>(sw, capacity);
divided = true;
}
Rect boundary;
int capacity;
bool divided;
std::vector<Point> points;
std::unique_ptr<QuadTree> northeast, northwest, southeast, southwest;
};
int main() {
Rect boundary {0, 0, 200, 200};
QuadTree qt(boundary, 4);
std::vector<Point> points = { {50, 50}, {100, 100}, {150, 150}, {75, 75}, {125, 125} };
for (const auto& pt : points) {
qt.insert(pt);
}
std::cout << "QuadTree에 점 삽입 완료" << std::endl;
return 0;
}
## 3.2 경로 탐색 알고리즘 (Pathfinding Algorithms)
게임에서는 NPC나 유닛이 장애물을 피해 목표에 도달하도록 경로를 탐색할 필요가 있다.
여러 가지 알고리즘이 사용되며, 여기서는 대표적인 두 가지를 설명한다.
### 3.2.1 A* 알고리즘 (A-Star)
A*는 휴리스틱을 사용해 시작점에서 목표 지점까지의 최적 경로를 찾는다.
구현에 따라 시간 복잡도는 달라질 수 있다.
**C++ 예시 (간단한 A* 개념):**
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <limits>
struct Node {
int id;
float f, g, h;
int parent;
};
float heuristic(int a, int b) {
// 간단한 예시를 위한 더미 휴리스틱 (실제 상황에 맞게 수정)
return 0.0f;
}
std::vector<int> AStar(int start, int goal, const std::vector<std::vector<std::pair<int, float>>>& graph) {
int n = graph.size();
std::vector<float> gScore(n, std::numeric_limits<float>::infinity());
std::vector<float> fScore(n, std::numeric_limits<float>::infinity());
std::vector<int> cameFrom(n, -1);
auto cmp = [&](int left, int right){ return fScore[left] > fScore[right]; };
std::priority_queue<int, std::vector<int>, decltype(cmp)> openSet(cmp);
gScore[start] = 0;
fScore[start] = heuristic(start, goal);
openSet.push(start);
while (!openSet.empty()) {
int current = openSet.top();
openSet.pop();
if (current == goal) {
std::vector<int> path;
while (current != -1) {
path.push_back(current);
current = cameFrom[current];
}
std::reverse(path.begin(), path.end());
return path;
}
for (auto& edge : graph[current]) {
int neighbor = edge.first;
float weight = edge.second;
float tentative_g = gScore[current] + weight;
if (tentative_g < gScore[neighbor]) {
cameFrom[neighbor] = current;
gScore[neighbor] = tentative_g;
fScore[neighbor] = tentative_g + heuristic(neighbor, goal);
openSet.push(neighbor);
}
}
}
return {}; // 경로 탐색 실패 시 빈 벡터 반환
}
int main() {
// 그래프: 각 노드별로 (이웃 노드, 가중치) 쌍을 저장
std::vector<std::vector<std::pair<int, float>>> graph = {
{ {1, 1.0f}, {2, 4.0f} },
{ {0, 1.0f}, {2, 2.0f}, {3, 5.0f} },
{ {0, 4.0f}, {1, 2.0f}, {3, 1.0f} },
{ {1, 5.0f}, {2, 1.0f} }
};
auto path = AStar(0, 3, graph);
std::cout << "A* 경로: ";
for (int node : path)
std::cout << node << " ";
std::cout << std::endl;
return 0;
}
3.2.2 Dijkstra 알고리즘
Dijkstra 알고리즘은 시작점에서 모든 노드까지의 최단 경로를 구하는 알고리즘이다.
여러 목적지까지의 경로 계산에 유용하며, 우선순위 큐(최소 힙)를 사용하여 효율적으로 구현한다.
C++ 예시:
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
std::vector<float> dijkstra(const std::vector<std::vector<std::pair<int, float>>>& graph, int start) {
int n = graph.size();
std::vector<float> distances(n, std::numeric_limits<float>::infinity());
distances[start] = 0;
using P = std::pair<float, int>;
std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto [dist, u] = pq.top();
pq.pop();
if (dist > distances[u])
continue;
for (auto& edge : graph[u]) {
int v = edge.first;
float w = edge.second;
if (distances[u] + w < distances[v]) {
distances[v] = distances[u] + w;
pq.push({distances[v], v});
}
}
}
return distances;
}
int main() {
std::vector<std::vector<std::pair<int, float>>> graph = {
{ {1, 1.0f}, {2, 4.0f} },
{ {0, 1.0f}, {2, 2.0f}, {3, 5.0f} },
{ {0, 4.0f}, {1, 2.0f}, {3, 1.0f} },
{ {1, 5.0f}, {2, 1.0f} }
};
auto distances = dijkstra(graph, 0);
std::cout << "각 노드까지의 최단 거리: ";
for (float d : distances)
std::cout << d << " ";
std::cout << std::endl;
return 0;
}
3.3 정렬 알고리즘 (Sorting Algorithms)
정렬 알고리즘은 게임 데이터 관리나 렌더링 순서 결정에 사용된다.
대표적으로 삽입 정렬, 퀵 정렬, 병합 정렬, 카운팅 정렬 등이 있다.
3.3.1 삽입 정렬 (Insertion Sort)
삽입 정렬은 작은 데이터셋에서 효율적으로 동작하며, 시간 복잡도는 O(n²)이다.
C++ 예시:
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
for (int i = 1; i < arr.size(); i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
std::vector<int> data = {5, 2, 9, 1, 5, 6};
insertionSort(data);
std::cout << "정렬 결과: ";
for (int num : data)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}3.3.2 퀵 정렬 (Quick Sort)
퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 대규모 데이터셋에 효과적이다.
C++ 예시:
#include <iostream>
#include <vector>
#include <algorithm>
void quickSort(std::vector<int>& arr, int left, int right) {
if (left >= right)
return;
int pivot = arr[(left + right) / 2];
int i = left, j = right;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
std::swap(arr[i], arr[j]);
i++;
j--;
}
}
quickSort(arr, left, j);
quickSort(arr, i, right);
}
int main() {
std::vector<int> data = {3, 6, 8, 10, 1, 2, 1};
quickSort(data, 0, data.size() - 1);
std::cout << "정렬 결과: ";
for (int num : data)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}3.3.3 병합 정렬 (Merge Sort)
병합 정렬은 안정적인 정렬 방법으로, 시간 복잡도는 O(n log n)이다.
단, 메모리 사용량이 증가할 수 있다.
C++ 예시:
#include <iostream>
#include <vector>
std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
std::vector<int> result;
int i = 0, j = 0;
while (i < left.size() && j < right.size()) {
if (left[i] < right[j]) {
result.push_back(left[i]);
i++;
} else {
result.push_back(right[j]);
j++;
}
}
while (i < left.size()) {
result.push_back(left[i]);
i++;
}
while (j < right.size()) {
result.push_back(right[j]);
j++;
}
return result;
}
std::vector<int> mergeSort(const std::vector<int>& arr) {
if (arr.size() <= 1)
return arr;
int mid = arr.size() / 2;
std::vector<int> left(arr.begin(), arr.begin() + mid);
std::vector<int> right(arr.begin() + mid, arr.end());
return merge(mergeSort(left), mergeSort(right));
}
int main() {
std::vector<int> data = {12, 11, 13, 5, 6, 7};
std::vector<int> sorted = mergeSort(data);
std::cout << "정렬 결과: ";
for (int num : sorted)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}3.3.4 카운팅 정렬 (Counting Sort)
카운팅 정렬은 범위가 한정된 정수형 데이터를 정렬할 때 O(n)의 시간 복잡도를 보인다.
C++ 예시:
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> countingSort(const std::vector<int>& arr) {
if (arr.empty())
return arr;
int maxVal = *std::max_element(arr.begin(), arr.end());
int minVal = *std::min_element(arr.begin(), arr.end());
int range = maxVal - minVal + 1;
std::vector<int> count(range, 0);
std::vector<int> output(arr.size(), 0);
// 각 수의 개수를 저장
for (int number : arr) {
count[number - minVal]++;
}
// 누적 합 계산
for (int i = 1; i < count.size(); i++) {
count[i] += count[i - 1];
}
// 정렬된 배열 만들기
for (int i = arr.size() - 1; i >= 0; i--) {
output[count[arr[i] - minVal] - 1] = arr[i];
count[arr[i] - minVal]--;
}
return output;
}
int main() {
std::vector<int> data = {4, 2, 2, 8, 3, 3, 1};
std::vector<int> sorted = countingSort(data);
std::cout << "정렬 결과: ";
for (int num : sorted)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}3.4 물리 및 충돌 알고리즘 (Physics & Collision Algorithms)
게임에서 물리 연산과 충돌 검사는 알고리즘에 크게 의존한다.
대표적으로 다음과 같은 방법이 있다:
- AABB (Axis-Aligned Bounding Box): 객체를 축에 평행한 사각형으로 감싸 충돌 여부를 판단한다.
- OBB (Oriented Bounding Box): 객체를 회전된 사각형으로 감싸 보다 정밀한 충돌 판정을 수행한다.
- 구 충돌 (Sphere Collision): 객체를 구 형태로 감싸 충돌 검사를 단순화한다.
- SAT (Separating Axis Theorem): 분리 축이 존재하면 두 다각형이 충돌하지 않는다고 판단한다.
C++ 예시 (AABB 충돌 검사):
#include <iostream>
struct Box {
int x, y, width, height;
};
bool aabbCollision(const Box& box1, const Box& box2) {
if (box1.x < box2.x + box2.width &&
box1.x + box1.width > box2.x &&
box1.y < box2.y + box2.height &&
box1.y + box1.height > box2.y)
return true;
return false;
}
int main() {
Box boxA {10, 10, 50, 50};
Box boxB {30, 30, 50, 50};
std::cout << "충돌 발생: " << (aabbCollision(boxA, boxB) ? "true" : "false") << std::endl;
return 0;
}마무리
게임 개발은 실시간 연산과 방대한 데이터 처리가 필요한 분야이다.
좋은 알고리즘을 선택하면 성능 최적화, 메모리 관리, 반응 속도 등에서 큰 이점을 얻을 수 있다.
위에서 소개한 알고리즘과 C++ 예시 코드를 참고하여, 다양한 상황에 맞게 알고리즘을 응용할 수 있도록 하자.
이 글이 벨로그 정리에 도움이 되길 바란다. 수정이나 질문이 있으면 댓글로 남기길 바란다.
