JPS 길 찾기

JPS는 A* 알고리즘에서 개선된 버전의 길 찾기 알고리즘이다.
A*가 시작 지점부터 계속해서 노드를 생성하면서 목적지까지의 길을 찾아가는 반면 JPS는 이 노드 생성의 시행 횟수를 줄이고자 나왔다. 그로 인해 탐색 범위가 더 많아졌다는 단점이 존재하게 되었지만 메모리 활용 측면에서 노드 생성의 횟수가 줄어드는 이점이 더 큰 경우가 많기 때문에 활용성이 더 좋다고 할 수 있다.
아래는 윈도우 창으로 A*와 JPS를 시각화한 결과물의 사진이다.

 

A* 길찾기 알고리즘

표시된 칸이 전부 생성된 노드, 노란색 칸은 방문한 노드이며 아래의 JPS와 비교했을 때 생성 및 탐색하는 노드 수가 확연히 많다

 

JPS를 활용한 길찾기 결과

 

경로 탐색 일부 코드 - 노드의 메모리 사용량을 줄여보기 위해 탐색 조건인 reason을 UCHAR로 1바이트만 사용하도록 한 후 비트 연산으로 분기를 나눔

 

우측 방향 탐색 코드 - JPS 노드 생성 조건에 맞을 경우 중단, 그 외에는 계속 탐색