A* 알고리즘과 플로우 필드

지즈·2025년 6월 14일

알고리즘

목록 보기

5/6

A* 알고리즘

언제 사용되는가?

A* 알고리즘은 그래프에서 시작점부터 목표 지점까지의 최단 경로를 찾는 데 사용된다. 특히 게임 개발에서의 길찾기(Pathfinding) 문제에 자주 쓰이며, NPC가 장애물을 피해 목표 지점까지 이동하는 경우에 활용된다. 기본적으로 다익스트라 알고리즘을 기반으로 하면서도, 목표까지의 예상 거리(휴리스틱)를 활용하여 탐색 효율을 높인다.

적용 가능한 그래프

방향 그래프 또는 무방향 그래프
가중치 있는 그래프
2D 격자 맵, 3D 공간, 웨이포인트 그래프, 내비게이션 메시 등 다양한 환경에서 적용 가능

핵심 아이디어

A* 알고리즘은 현재까지의 실제 거리 g(n)와 목표까지의 예상 거리 h(n)를 더한 값을 기준으로 경로를 탐색한다.
총 비용 함수는 다음과 같다.

f(n) = g(n) + h(n)
g(n) : 시작 노드에서 현재 노드까지의 실제 거리

h(n) : 현재 노드에서 목표 노드까지의 예상 거리(휴리스틱)

f(n) : 현재 노드를 거쳐 목표까지 도달할 것으로 예상되는 총 비용

우선순위 큐(또는 최소 힙)를 사용하여 f(n)이 가장 작은 노드를 우선적으로 탐색한다. 일반적으로 h(n)으로는 맨해튼 거리, 유클리드 거리, 체비셰프 거리 등이 사용된다.

복잡도

A* 알고리즘의 시간 복잡도는 휴리스틱 함수에 따라 달라진다.
최악의 경우는 다익스트라와 동일하게 O(E)에 가깝지만, 휴리스틱이 잘 설계되어 있으면 훨씬 적은 탐색만으로도 목표에 도달할 수 있다.

시간 복잡도 (최악의 경우): O(E)
공간 복잡도: O(V)

예제 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

struct Node {
    int x, y;
    int g, h;
    Node* parent;

    Node(int x, int y, int g, int h, Node* p) : x(x), y(y), g(g), h(h), parent(p) {}

    int f() const {
        return g + h;
    }

    bool operator>(const Node& other) const {
        return f() > other.f();
    }
};

int heuristic(int x1, int y1, int x2, int y2) {
    // 맨해튼 거리
    return abs(x1 - x2) + abs(y1 - y2);
}

bool isInBounds(int x, int y, int rows, int cols) {
    return (0 <= x && x < rows && 0 <= y && y < cols);
}

vector<pair<int, int>> AStar(vector<vector<int>>& grid, pair<int, int> start, pair<int, int> goal) {
    int rows = grid.size();
    int cols = grid[0].size();

    priority_queue<Node*, vector<Node*>, function<bool(Node*, Node*)>> open(
        [](Node* a, Node* b) { return *a > *b; });

    vector<vector<bool>> closed(rows, vector<bool>(cols, false));

    Node* startNode = new Node(start.first, start.second, 0, heuristic(start.first, start.second, goal.first, goal.second), nullptr);
    open.push(startNode);

    int dx[4] = { -1, 1, 0, 0 };
    int dy[4] = { 0, 0, -1, 1 };

    while (!open.empty()) {
        Node* current = open.top();
        open.pop();

        if (closed[current->x][current->y])
            continue;

        closed[current->x][current->y] = true;

        if (current->x == goal.first && current->y == goal.second) {
            vector<pair<int, int>> path;
            while (current) {
                path.push_back({ current->x, current->y });
                current = current->parent;
            }
            reverse(path.begin(), path.end());
            return path;
        }

        for (int i = 0; i < 4; i++) {
            int nx = current->x + dx[i];
            int ny = current->y + dy[i];

            if (!isInBounds(nx, ny, rows, cols) || grid[nx][ny] == 1 || closed[nx][ny])
                continue;

            int g = current->g + 1;
            int h = heuristic(nx, ny, goal.first, goal.second);
            Node* neighbor = new Node(nx, ny, g, h, current);
            open.push(neighbor);
        }
    }

    return {}; // 경로 없음
}

주의할 점

휴리스틱 함수가 실제 거리보다 크면 최단 경로를 보장하지 못한다. 지나치게 낮은 휴리스틱은 다익스트라와 유사해져 성능 저하가 우려된다. 장애물, 이동 불가능 영역 등을 정확히 반영해야 실용적 경로 탐색 가능하다.

플로우 필드(Pathfinding)

언제 사용되는가?

대규모 유닛이 한꺼번에 동일한 목표를 향해 이동할 때 사용된다. RTS 게임처럼 수백~수천 개의 유닛이 동시에 움직여야 할 때, 각 유닛마다 A*를 돌리면 연산량이 너무 커지므로, 전체 맵에 한 번만 흐름(Field)을 계산해 놓고 각 유닛이 그 필드를 따라 움직이게 한다.

적용 가능한 그래프

2D/3D 격자 기반 지도 (Grid)
웨이포인트 그래프
NavMesh 등 임의의 이웃 연결 구조에도 적용 가능

핵심 아이디어

목표(Goal)로부터 시작해, Dijkstra 알고리즘을 변형한 방식으로 맵 전체의 최소 이동 비용(dist)를 계산한다.
각 칸(cell)은 이 dist 값만 보존한다.
흐름 벡터(flow direction): 각 칸에서 인접 칸 중 dist가 가장 낮은 방향으로 향하는 단위 벡터를 계산해 저장한다.
유닛은 매 프레임 자신의 위치 셀의 흐름 벡터를 따라 이동만 하면 되므로, 개별 경로 탐색 없이 부하가 크게 줄어든다.