게임의 길찾기

A*

A-Star 알고리즘은 출발 지점부터 목표 지점까지 최단거리를 찾는 알고리즘이다.

f(n) = g(n) + h(n)이라는 공식으로 정리되는데, 꼭지점 N까지의 경로 가중치(g(n))와 지점 n부터 목표 지점까지의 추정 경로 가중치의 합계이다.

 

현재 지점부터 8방위(↖↑↗→↘↓↙←)방향으로 순회하며 가장 작은 가중치를 찾아가며 반복한다. 한 번 방문한 지점은 방문 목록에 넣어 다시 방문하지 않도록 한다.

 

의사 코드

pq.enqueue(start_node, g(start_node) + h(start_node))       // 우선순위 큐에 시작 노드를 삽입한다.

while pq is not empty       // 우선순위 큐가 비어있지 않은 동안
    node = pq.dequeue       // 우선순위 큐에서 pop한다.

    if node == goal_node    // 만약 해당 노드가 목표 노드이면 반복문을 빠져나온다.
        break

    for next_node in (next_node_begin...next_node_end)       // 해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안
        pq.enqueue(next_node, g(node) + cost + h(next_node)) // 우선순위 큐에 다음 노드를 삽입한다.

return goal_node_dist       // 시작 노드에서 목표 노드까지의 거리를 출력한다.

 

C++

// 이 소스 코드의 그래프는 인접 리스트 방식으로 그래프를 표현하였다.
using ii = pair<int, int>;

priority_queue<ii, greater<ii>, vector<ii> > pq;
/// N_VER은 그래프의 정점의 개수를 의미한다.
int dist[N_VER], cost[N_VER][N_VER]; /// dist[i]는 i번째 정점까지 가는 최단 거리를 의미한다.
vector<ii> edges[N_VER]; /// edges[i]는 i와 연결된 정점과 가중치를 묶어 저장하는 벡터이다.

int minDist(int src, int dst) {
    pq.push({0, src});
    bool success = false;
    while (!pq.empty()) {
        int v = pq.top(); pq.pop();
        if (v == dst) {
            success = true;
            break;
        }
        for (ii adj: edges[v]) {
            if (dist[adj.first] < g(v) + adj.second + h(adj.first)) {
                dist[adj.first] = g(v) + adj.second + h(adj.first); // 이완 (relaxation)
                pq.push({dist[adj], adj}); // 다음 정점 후보에 탐색하고 있는 정점을 넣는다.
            }
        }
    }
    if (!success) return -1;
    else return dist[dst];
}

 

더 자세한 설명

http://www.gisdeveloper.co.kr/?p=3897 

최단 경로 탐색 – A* 알고리즘 – GIS Developer

 

 

JumpPointSearch

JPS 알고리즘은 출발 지점부터 목표 지점까지의 최단 경로 탐색 알고리즘이다. A-Star 알고리즘에 기반을 두고있지만, 특정 노드를 선택적으로 탐색하기 때문에 조금 더 효율적인 탐색이 가능하다.

차후에 정리 예정이다.

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=zzing0907&logNo=220671022815 

길찾기 알고리즘(Pathfinding Algorithm)

https://napoliano.tistory.com/30

Jump Point Search(JPS) 알고리즘

https://joonleestudio.tistory.com/28

A*보다 빠른 JPS