[C++ 게임 개발 시리즈] Day 19: 경로 찾기 알고리즘 (A* 알고리즘)

경로 찾기 알고리즘 (A* 알고리즘)

경로 찾기 알고리즘은 게임에서 캐릭터가 목적지까지 최적의 경로를 찾아가는 데 사용됩니다. A* 알고리즘은 이러한 경로 찾기 문제를 해결하는 데 널리 사용되는 알고리즘입니다. A* 알고리즘은 최단 경로를 찾기 위해 휴리스틱을 사용하는 탐색 알고리즘입니다.

A* 알고리즘 기초

A* 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 찾기 위해 다음과 같은 비용 함수를 사용합니다:

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

여기서:

• ( g(n) )은 시작 노드에서 현재 노드 ( n )까지의 실제 비용입니다.
• ( h(n) )은 현재 노드 ( n )에서 목표 노드까지의 추정 비용(휴리스틱)입니다.

A* 알고리즘 구현

다음 예제에서는 간단한 2D 격자 맵에서 A* 알고리즘을 사용하여 경로를 찾는 방법을 구현합니다.

노드 클래스 정의

먼저, 각 격자 셀을 나타내는 Node 클래스를 정의합니다.

#include <SFML/Graphics.hpp>
#include <SFML/Window.hpp>
#include <SFML/System.hpp>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_set>

struct Node {
    int x, y;
    float gCost, hCost;
    Node* parent;

    Node(int x, int y) : x(x), y(y), gCost(0), hCost(0), parent(nullptr) {}

    float fCost() const {
        return gCost + hCost;
    }

    bool operator==(const Node& other) const {
        return x == other.x && y == other.y;
    }
};

struct NodeHash {
    size_t operator()(const Node* node) const {
        return std::hash<int>()(node->x) ^ std::hash<int>()(node->y);
    }
};

struct NodeCompare {
    bool operator()(const Node* a, const Node* b) const {
        return a->fCost() > b->fCost();
    }
};

A* 알고리즘 구현

A* 알고리즘을 구현하는 함수입니다.

std::vector<Node*> getNeighbors(Node* node, const std::vector<std::vector<int>>& grid) {
    std::vector<Node*> neighbors;
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (auto& dir : dirs) {
        int nx = node->x + dir[0];
        int ny = node->y + dir[1];
        if (nx >= 0 && ny >= 0 && nx < grid.size() && ny < grid[0].size() && grid[nx][ny] == 0) {
            neighbors.push_back(new Node(nx, ny));
        }
    }
    return neighbors;
}

float heuristic(Node* a, Node* b) {
    return std::abs(a->x - b->x) + std::abs(a->y - b->y);
}

std::vector<Node*> aStar(Node* start, Node* goal, const std::vector<std::vector<int>>& grid) {
    std::priority_queue<Node*, std::vector<Node*>, NodeCompare> openSet;
    std::unordered_set<Node*, NodeHash> closedSet;

    start->gCost = 0;
    start->hCost = heuristic(start, goal);
    openSet.push(start);

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

        if (*current == *goal) {
            std::vector<Node*> path;
            while (current != nullptr) {
                path.push_back(current);
                current = current->parent;
            }
            return path;
        }

        closedSet.insert(current);

        for (Node* neighbor : getNeighbors(current, grid)) {
            if (closedSet.find(neighbor) != closedSet.end()) {
                delete neighbor;
                continue;
            }

            float tentativeGCost = current->gCost + 1;
            if (tentativeGCost < neighbor->gCost || std::find_if(openSet.begin(), openSet.end(), [neighbor](Node* n) { return *n == *neighbor; }) == openSet.end()) {
                neighbor->gCost = tentativeGCost;
                neighbor->hCost = heuristic(neighbor, goal);
                neighbor->parent = current;
                openSet.push(neighbor);
            } else {
                delete neighbor;
            }
        }
    }

    return std::vector<Node*>();
}

경로 찾기 예제

A* 알고리즘을 사용하여 격자 맵에서 경로를 찾는 예제입니다.

int main() {
    // 격자 맵 생성 (0: 빈 공간, 1: 장애물)
    std::vector<std::vector<int>> grid = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 0, 0}
    };

    // 시작과 목표 노드
    Node* start = new Node(0, 0);
    Node* goal = new Node(4, 4);

    // A* 알고리즘으로 경로 찾기
    std::vector<Node*> path = aStar(start, goal, grid);

    // 결과 출력
    if (!path.empty()) {
        std::cout << "Path found:" << std::endl;
        for (auto it = path.rbegin(); it != path.rend(); ++it) {
            std::cout << "(" << (*it)->x << ", " << (*it)->y << ")" << std::endl;
        }
    } else {
        std::cout << "No path found." << std::endl;
    }

    // 메모리 해제
    for (Node* node : path) {
        delete node;
    }
    delete start;
    delete goal;

    return 0;
}

결론

오늘은 A* 알고리즘을 사용하여 2D 격자 맵에서 최단 경로를 찾는 방법을 학습했습니다. A* 알고리즘은 휴리스틱을 사용하여 효율적으로 최단 경로를 찾는 알고리즘입니다. 질문이나 추가적인 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 20: AI 행동 트리"에 대해 학습하겠습니다.