A* 알고리즘 (+ 하다 만 JPS)

회사 일이 생각보다 엄청 고되는데.. 자투리 시간에 갑자기 생각나서 끄적여보겠다는 생각이 들어 포스팅 해본다.

그나저나 계란으로 바위치는 프로젝트 인 것 같은데... 에효... 어째 고렙이 스탯이 더 낮은 것 같지?

 

===

 

예~~~~전에 만들던 게임서버 알고리즘 개선해보겠답시고 공부 열심히 해봤는데, 나름 성과가 있어서 기억을 더듬어 포스트로 남겨본다.

조만간 또 쓸일이 있지 않을까 싶으면서..

 

이놈은 경로찾기에서 사용하는놈이다. 다익스트라는 알고리즘 연습한다고 스터디하면 한번쯤 접해볼 수 있는 당연한 녀석이지만.. 이놈은 이론만 깨우치고 실제로 구현한 사람이 많지는 않을거라 생각한다.

 

다익스트라 알고리즘 확장해서 만든 경로탐색 알고리즘이라고 나무위키에서 그런다.

ㅇㅇ 맞는듯 결국은 휴리스틱 함수를 써서 예상비용을 계산해가지고 찾고자 하는 경로 (목표 노드)를 추정해서 가는 방식이니께..

 

f(x)=g(x)+h(x) 이런 공식이라고까지만 배운 사람들이 많을 거다.

우리가 누구? 코드쟁이

 

30x30으로 구성된 X/Y 좌표계에서 (1,1)에서 (29,29)를 목표로 하는 길찾기가 시작된다.

단, 그냥 출발하면 a*고 나발이고 의미가 없으니, 중간에 랜덤 좌표에 장애물을 추가해주는 방식으로다가 접근해보겠다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <random>

// 바둑판 크기
const int rows = 30;
const int cols = 30;

// 랜덤 장애물 생성
void addRandomObstacles(std::vector<std::vector<int>>& grid, int numObstacles) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(1, rows - 2); // 장애물을 가장자리를 제외한 영역에 추가

    for (int i = 0; i < numObstacles; ++i) {
        int row = dis(gen);
        int col = dis(gen);
        grid[row][col] = -1; // 장애물
    }
}


// A* 알고리즘으로 길 찾기
std::vector<std::pair<int, int>> findPath(std::vector<std::vector<int>>& grid, std::pair<int, int> start, std::pair<int, int> goal) {
    // 이웃 노드 상하좌우
    const std::vector<int> dr = {-1, 1, 0, 0};
    const std::vector<int> dc = {0, 0, -1, 1};
    
    // 최소 우선순위 큐
    std::priority_queue<std::pair<int, std::pair<int, int>>> pq;
    
    // 시작 지점 추가
    pq.push({0, start});
    
    // 이전 노드 저장을 위한 배열
    std::vector<std::vector<std::pair<int, int>>> parent(rows, std::vector<std::pair<int, int>>(cols, {-1, -1}));
    
    while (!pq.empty()) {
        int r = pq.top().second.first;
        int c = pq.top().second.second;
        int cost = -pq.top().first;
        pq.pop();
        
        if (r == goal.first && c == goal.second) {
            // 목표 지점 도달
            std::vector<std::pair<int, int>> path;
            while (r != -1 && c != -1) {
                path.push_back({r, c});
                auto prev = parent[r][c];
                r = prev.first;
                c = prev.second;
            }
            std::reverse(path.begin(), path.end());
            return path;
        }
        
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 0) {
                int new_cost = cost + 1; // 이웃 노드로 이동하는 비용
                if (new_cost < grid[nr][nc] || grid[nr][nc] == 0) {
                    grid[nr][nc] = new_cost;
                    pq.push({-new_cost, {nr, nc}});
                    parent[nr][nc] = {r, c};
                }
            }
        }
    }
    
    return {}; // 경로를 찾을 수 없는 경우 빈 벡터 반환
}

int main() {
    std::vector<std::vector<int>> grid(rows, std::vector<int>(cols, 0));
    
    // 장애물 추가
    addRandomObstacles(grid, 100);
    
    std::pair<int, int> start = {1, 1};
    std::pair<int, int> goal = {29, 29};
    
    std::vector<std::pair<int, int>> path = findPath(grid, start, goal);
    
    if (path.empty()) {
        std::cout << "경로를 찾을 수 없습니다." << std::endl;
    } else {
        std::cout << "찾은 경로: ";
        for (const auto& p : path) {
            std::cout << "(" << p.first << ", " << p.second << ") ";
        }
        std::cout << std::endl;
    }
    
    return 0;
}

 

 

우선 정해진 벡터에 장애물을 추가하고 1,1 -> 29,29의 최단 경로를 찾는다.

모든건 인접 노드의 비용에 의해 움직인다.

결국 비용이 가장 적은 놈이 최단거리란 말씀.

 

 

다만 위의 A*를 그대로 써먹으면 경로를 탐색해야 할 벡터가 커지면 커질수록 계산에 필요한 연산량도 매우매우 높아진다.

그걸 방지하기 위해 A*의 개선판이 있는데, JPS (Jump Point Search)다.

 

JPS는 장애물이 없는 길을 먼저 찾고, 장애물을 피하는 노드로 확장해나간다. 이렇게 하면 경로 확장에 써먹는 연산량을 줄일 수 있어 더 빠르게 도달할 수 있다. 특히 X,Y 좌표계는 A*처럼 상하좌우를 찾는게 아니고 대각선으로도 접근이 가능해서 대각선이동에도 용이하다.

무엇보다 Jump라는 단계가 있어 node간 이동(현재노드에서 다음 가장자리 노드로)을 수행하여 jump하기 때매 장애물 주변을 좀 더 효율적으로 찾을 수 있다.

 

말만 들으면 겁나 좋아보이지만.. 일단 구현하기 빡세다.

 

https://zerowidth.com/2013/a-visual-explanation-of-jump-point-search.html

zerowidth positive lookahead | A Visual Explanation of Jump Point Search

 

이 방식대로 따라해보자.

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

const int rows = 30;
const int cols = 30;

struct Node {
    int x, y;
    int g; // 비용
    int h; // 휴리스틱
    int f; // f = g + h
    Node* parent;

    Node(int x, int y, int g, int h, Node* parent = nullptr)
        : x(x), y(y), g(g), h(h), f(g + h), parent(parent) {}

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

std::vector<std::vector<int>> grid(rows, std::vector<int>(cols, 0));
std::vector<std::vector<Node*>> nodes(rows, std::vector<Node*>(cols, nullptr));

// 휴리스틱 계산용 
int heuristic(int x1, int y1, int x2, int y2) {
    return std::abs(x1 - x2) + std::abs(y1 - y2);
}

// 노드 이동 가능한지?
bool isWalkable(int x, int y) {
    if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 0) {
        return true;
    }
    return false;
}

// JPS
std::vector<std::pair<int, int>> aStar(int startX, int startY, int goalX, int goalY) {
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> openSet;
    std::vector<std::pair<int, int>> path;

    openSet.push(Node(startX, startY, 0, heuristic(startX, startY, goalX, goalY)));

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

        if (current.x == goalX && current.y == goalY) {
            Node* node = &current;
            while (node) {
                path.emplace_back(node->x, node->y);
                node = node->parent;
            }
            std::reverse(path.begin(), path.end);
            return path;
        }

        //여기다가 이제 로직 구현할거임
        //
    }

    return path;
}

int main() {
    int startX = 1;
    int startY = 1;
    int goalX = 29;
    int goalY = 29;

    std::vector<std::pair<int, int>> path = aStar(startX, startY, goalX, goalY);

    if (path.empty()) {
        std::cout << "경로를 찾을 수 없다." << std::endl;
    } else {
        std::cout << "경로 찾음: ";
        for (const auto& p : path) {
            std::cout << "(" << p.first << ", " << p.second << ") ";
        }
        std::cout << std::endl;
    }

    return 0;
}

 

우선 A*와 비슷하게 작성하되, 핵심 로직을 다르게 구현할거다.

위 포스팅에서는 직선탐색 하고, 대각선탐색하라고 한다.

 

로직 구현할 영역에 직선탐색과 대각선탐색에 대한 로직을 넣어보자.

 

//일단 이렇게!
 const std::vector<int> dx = {0, 1, 0, -1, 1, -1, -1, 1};
        const std::vector<int> dy = {1, 0, -1, 0, 1, 1, -1, -1};

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

            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && isWalkable(nx, ny)) {
                int newG = current.g + (i < 4 ? 1 : 1.414); // 직선 탐색은 비용 1, 대각선 탐색은 비용 sqrt(2)로 설정

                if (!nodes[nx][ny] || newG < nodes[nx][ny]->g) {
                    int newH = heuristic(nx, ny, goalX, goalY);
                    Node* newNode = new Node(nx, ny, newG, newH, &current);

                    if (!nodes[nx][ny]) {
                        openSet.push(*newNode);
                    } else {
                        // If the new path is better, update the node's values
                        *nodes[nx][ny] = *newNode;
                    }

                    nodes[nx][ny] = newNode;
                }
            }
        }

 

로직 구현 영역에 직선경로와 대각선경로에 대해 처리를 했다.

대각선의 비용은 루트2라서 대충 1.414로 줬다.

 

JPS는 인접 노드 간 Jump 할 수 있는 지점을 식별하고, 이에 대해 접근하는 코드를 작성해야 한다.

 

그 러 나

 

솔직히 여기서부터는 이해를 못했다. 그치만 관련된 다른 언어로 작성되어 있는 예제 코드가 있는걸로 보아 스터디가 좀 더 필요하다

 

https://www.gamedev.net/tutorials/programming/artificial-intelligence/jump-point-search-fast-a-pathfinding-for-uniform-cost-grids-r4220/

Jump Point Search: Fast A* Pathfinding for Uniform Cost Grids

 

python 코드인 것 같긴 한데.. 시간날때 좀 더 파보고 c++ 코드로 작성해서 업뎃하겠음.. ㅠ