JPS 알고리즘

JPS 알고리즘

개요

이전에 우리는 A* 알고리즘에 대해서 공부해보았다.
하지만 이러한 A* 알고리즘 역시 기본적으로 BFS에 가까운 알고리즘이고 매칸 마다 그다음 노드들을 탐색해야하기에 너무나 많은 시간이 걸린다.

이전 시간에 포스팅한 A* 알고리즘으로 탐색한 내용이다. 보면 알겠지만 BFS로 전체를 탐색한 것과 크게 차이가 나지 않아보인다. (물론 예시를 제대로 만들지 못한 것도 있겠지만)

그래서 이렇게 느린 A* 알고리즘의 문제점을 수정한 JPS(Jump Point Search)라는 알고리즘이 2011년에 Daniel Harabor과 Alban Grastien이라는 사람에 의해 만들어졌다.
이 JPS 알고리즘은 기존 A* 알고리즘의 10배의 성능을 자랑한다.
이 알고리즘은 노드 간의 거리가 별도의 에지로 나타난 형태의 그래프가 아닌 가로 세로 길이가 일정한 형태의 그리드 맵 형태에서 그 진가를 자랑하는데 이러한 그리드 맵에서 JPS 알고리즘은 체감상 A* 보다 10배 이상의 성능을 느낄 수 있다.

알고리즘 구동 방식

A * 알고리즘에서는 탐색 중인 노드에 바로 붙은 노드를 열린 노드로 추가한다.
하지만 이렇게 한칸 한칸 모두를 열린 노드에 추가하면 쓸데없이 확인해야할 노드만 늘릴뿐이라는게 JPS 알고리즘의 주요한 내용이다. 무시할만한 노드는 무시하고 정말로 체크해볼만한 노드만 탐색 대상에 넣으면 어떨까하는 생각에서 시작한게 아래의 가정이다.

기본 탐색시의 가정

특정 노드 한칸을 이동한다고 할때 이미 지나온 노드를 P라고 하고 현재 노드 탐색중인 노드를 X라 하자. P에서 X 방향으로 탐색한다고 할때 다음의 가정을 한다.

가정 1. P는 이미 지나온 노드이니 탐색 대상에서 제외한다.

가정 2. x에서 대각선 뒤에 있는 노드를 탐색 대상에서 제외한다.

대각선으로 뒤에 있는 노드는 P의 부모 노드를 통해 도달했다고 가정할 수 한다. 왜냐하면 그 노드는 P를 통과하는 경로보다 더 짧기 때문이다.

가정 3. x의 양 옆에 있는 노드를 탐색 대상에서 제외한다.

X의 양 옆 노드 역시 P에서 이동하는 것이 이동거리 2를 들인것보다 $\sqrt{2}$만 들여서 이동하는게 더 최적이다. 진짜로 그 방향으로 가야한다면 X의 대각선으로 뒤에 있는 노드에서 탐색하다가 그쪽 방향으로 이동할 것이다. 그렇기 때문에 다음 탐색에서 무시한다.

가정 4. x의 대각선 앞에 있는 노드를 탐색대상에서 제외한다.

X의 대각선 방향에 위치한 노드의 경우 X의 양 옆 노드를 통해 갈 수도 있다.
하지만 비용은 같으며 어차피 비용이 같다면 무시해도 되기 때문에 탐색 대상에서 제외해도 된다.

가정 5. 남은 직선 방향으로 탐색간 벽에 막히면 탐색을 종료한다.

만약 다른 길이 있다면 다른 노드 탐색 간에서 나올 것이기 때문이다.

가정 6. 대각선 탐색은 수평 성분과 수직 성분으로 나누어서 탐색한다.

위, 아래, 오른쪽, 왼쪽의 경우 그냥 한칸씩 나아가며 바로 앞이 막혔는지 체크를 하면 되지만 대각선의 경우 한칸 이동할때마다 수직, 수평 성분으로 분해하여 탐색이 필요하다.

그렇다면 이러한 가정들이 틀린 경우는 어떤 경우일까? 바로 아래와 같이 길이 막힌 경우이다.

가정 예외 1. 수직 수평간 예외

이전에 가정들에 의하면 직선으로 이동만한다면 해당 다른 노드들은 이전에 다른 노드 탐색에 의해서 모드 확인이 될 것이다라는 내용이었지만 다음과 같이 모서리에 벽이 있다면 해당 가정은 성립하지 않는다. 여기서 이러한 모서리 너머의 D점같은 노드를 강제이웃(forced neighbor)이라고 부르며 해당 점에 대해서 추가적인 탐색이 필요하다.

가정 예외 2. 대각선 탐색간 예외

대각선 탐색의 경우에도 이와 비슷한데
단, 다음과 같은 경우에는 수평 수직 탐색간 발생하는 강제이웃과 같은 경우이다.

강제이웃(forced neighbor)

추가적인 탐색이 필요한 점이며 사실상 탐색의 핵심이다.
진행하는 방향에서 대각산 오른쪽 혹은 대각선 왼쪽에 벽이 등장하면 발생하는 노드로 해당 벽 뒤의 빈 노드가 있다면 해당 점을 강제이웃 점으로 삼아서 대각선으로 점프롤 한다.
이 점을 발견한 현재 노드 기준를 열린 노드에 추가하며 현재 노드의 강제이웃점을 기준으로 직선 탐색 및 강제 이웃 탐색을 재귀적으로 진행한다.

알고리즘 동작 예시

사실 이렇게 말로만 설명하면 이해하기 힘들다.
알고리즘이 어떻게 동작하는 가를 보이기 위해서 이전에 포스팅했던 길거리를 갖고 오겠다.

이 길거리는 가로 10칸 세로 8칸의 정사각형 셀들로 이루어진 길거리이다. 이전에는 그래프로 단순화 시켰지만 JPS의 경우 그리드 맵 형태가 가장 효율적이므로 맵을 그래프 형태로 바꾸진 않겠다.
해당 맵에서 JPS를 구동하면 아래와 같은 형태로 경로가 나온다.
초록색 노드가 시작점이고 붉은색 노드가 도착점이다.

다음 경로를 하나하나 분석하면 아래와 같다.

참고 자료

• D. Harabor; A. Grastien (2011). Online Graph Pruning for Pathfinding on Grid Maps. 25th National Conference on Artificial Intelligence. AAAI.
• zerowidth positive lookahead - A Visual Explanation of Jump Point Search