TIL: 경로탐색 알고리즘

게임 내 캐릭터, NPC, 유닛 등이 장애물을 피해 목표 지점까지 이동하는 최적 혹은 근사 최적의 경로를 찾기 위한 기법을 정리한다.

오늘 학습한 주요 내용

• 너비 우선 탐색 (BFS)
• 깊이 우선 탐색 (DFS)
• 다익스트라 알고리즘 (Dijkstra)
• A* 알고리즘 (A-Star)

---

1. 너비 우선 탐색 (Breadth-First Search, BFS)

• 용도: 비가중치 그래프에서 최단 경로(노드 수 기준) 보장
• 동작 원리: 시작 노드에서 물결처럼 한 층씩(레벨별) 탐색
• 시간 복잡도: O(V + E)
• 메모리: 큐에 같은 레벨의 노드를 모두 저장하므로 큰 맵에서 메모리 부담 증가

#include <queue>
#include <vector>
#include <algorithm>
struct Node {
    int id;
    std::vector<int> neighbors;
};
std::vector<int> BFS(const std::vector<Node>& graph, int start, int goal) {
    int n = graph.size();
    std::vector<bool> visited(n, false);
    std::vector<int> parent(n, -1);
    std::queue<int> frontier;
    visited[start] = true;
    frontier.push(start);
    while (!frontier.empty()) {
        int current = frontier.front(); frontier.pop();
        if (current == goal) {
            std::vector<int> path;
            for (int node = goal; node != -1; node = parent[node])
                path.push_back(node);
            std::reverse(path.begin(), path.end());
            return path;
        }
        for (int next : graph[current].neighbors) {
            if (!visited[next]) {
                visited[next] = true;
                parent[next] = current;
                frontier.push(next);
            }
        }
    }
    return {};
}

---

2. 깊이 우선 탐색 (Depth-First Search, DFS)

• 용도: 가능한 모든 경로 탐색 또는 특정 조건을 만족하는 해답 찾기
• 동작 원리: 한 방향으로 깊이 탐색 후 막히면 백트래킹
• 시간 복잡도: O(V + E)
• 메모리: 재귀 호출 스택 또는 명시적 스택 사용

#include <vector>
// 재귀 유틸 함수
bool DFSUtil(const std::vector<std::vector<int>>& graph, int current, int goal,
             std::vector<bool>& visited, std::vector<int>& path) {
    visited[current] = true;
    path.push_back(current);
    if (current == goal) return true;
    for (int next : graph[current]) {
        if (!visited[next] && DFSUtil(graph, next, goal, visited, path))
            return true;
    }
    path.pop_back();
    return false;
}std::vector<int> DFS(const std::vector<std::vector<int>>& graph, int start, int goal) {
    std::vector<bool> visited(graph.size(), false);
    std::vector<int> path;
    if (DFSUtil(graph, start, goal, visited, path))
        return path;
    return {};
}

---

3. 다익스트라 알고리즘 (Dijkstra’s Algorithm)

• 용도: 각 간선에 가중치가 있는 그래프에서 시작점부터 모든 노드까지 최단 경로 계산
• 자료구조: 최소 힙 기반 우선순위 큐
• 시간 복잡도: O((V + E) log V)

#include <queue>
#include <vector>
#include <limits>
#include <algorithm>
struct Edge {
    int destination;
    int weight;
};
struct GraphNode {
    std::vector<Edge> edges;
};
std::vector<int> Dijkstra(const std::vector<GraphNode>& graph, int start, int goal) {
    int n = graph.size();
    const int INF = std::numeric_limits<int>::max();
    std::vector<int> dist(n, INF), parent(n, -1);
    using P = std::pair<int,int>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (u == goal) break;
        if (d > dist[u]) continue;
        for (auto& e : graph[u].edges) {
            int v = e.destination, w = e.weight;
            if (d + w < dist[v]) {
                dist[v] = d + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
    std::vector<int> path;
    if (dist[goal] == INF) return path;
    for (int v = goal; v != -1; v = parent[v])
        path.push_back(v);
    std::reverse(path.begin(), path.end());
    return path;
}

---

4. A* (A-Star) 알고리즘

• 용도: 휴리스틱을 더해 Dijkstra보다 목표 지점에 더 빠르게 도달
• 평가 함수:
  • g(n): 시작점→현재 노드 실제 비용
  • h(n): 현재 노드→목표 노드 예상 비용 (휴리스틱)
  • f(n) = g(n) + h(n)
• 시간 복잡도: 휴리스틱 품질에 따라 크게 달라짐

#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
struct AStarNode {
    int id, x, y;
    float gCost = INFINITY, hCost = INFINITY;
    AStarNode* parent = nullptr;
    float fCost() const { return gCost + hCost; }
};
struct Compare {
    bool operator()(const AStarNode* a, const AStarNode* b) const {
        return a->fCost() > b->fCost();
    }
};
float Heuristic(int x1, int y1, int x2, int y2) {
    return std::abs(x1 - x2) + std::abs(y1 - y2);
}std::vector<AStarNode*> AStarSearch(std::vector<AStarNode*>& nodes, int startID, int goalID) {
    auto cmp = Compare();
    std::priority_queue<AStarNode*, std::vector<AStarNode*>, Compare> openList(cmp);
    std::vector<bool> closed(nodes.size(), false);
    AStarNode* start = nodes[startID];
    AStarNode* goal  = nodes[goalID];
    start->gCost = 0;
    start->hCost = Heuristic(start->x, start->y, goal->x, goal->y);
    openList.push(start);
    while (!openList.empty()) {
        AStarNode* cur = openList.top(); openList.pop();
        if (cur->id == goalID) {
            std::vector<AStarNode*> path;
            for (auto p = cur; p; p = p->parent) path.push_back(p);
            std::reverse(path.begin(), path.end());
            return path;
        }
        closed[cur->id] = true;
        for (AStarNode* nei : /*인접 노드 리스트*/) {
            if (closed[nei->id]) continue;
            float tentative = cur->gCost + Heuristic(cur->x, cur->y, nei->x, nei->y);
            if (tentative < nei->gCost) {
                nei->parent = cur;
                nei->gCost  = tentative;
                nei->hCost  = Heuristic(nei->x, nei->y, goal->x, goal->y);
                openList.push(nei);
            }
        }
    }
    return {};
}

---

휴리스틱 설계 포인트

• 맨해튼 거리: 4방향 이동만 가능할 때
• 유클리드 거리: 대각선 이동 허용할 때
• 체비셰프 거리: 대각선·직선 비용 동일할 때
• 도메인 특화: 지형, 교통량, 위험도 등 추가 반영

---