[알고리즘 알아보기] JPS(Jump Point Search)

개요

JPS알고리즘은 A*의 단점인 많은 노드 생성을 극복하는 알고리즘입니다.

https://basaeng.tistory.com/77

[알고리즘 알아보기] A* 알고리즘 알아보기

A*알고리즘 구현에서 보았듯이, A*는 f값을 기준으로 다음에 openlist에서 pop할 노드를 선정하지만, 선정한 노드의 주변 8방에 대해 (방문하지 않았거나 f값이 개선된 경우) 노드를 생성해 openlist에 추가합니다. 

 

JPS는 노드의 생성을 Jump Point를 찾아 해당 포인트에만 생성합니다.

---

Jump Point

JPS의 핵심 아이디어는 이름처럼 Jump Point입니다.

 

최단거리를 찾게 될 때 직선 지점은 노드를 생성할 필요가 없다는 아이디어입니다.

직선 진행 방향 내에서는 f = g + h일 때 Consistent heuristic 규칙에 의해 f값은 감소하지 않습니다.

만약에 진행방향이 최단거리라면 어짜피 해당 경로 내에서는 동일순서로 생성한 노드가 openlist에서 뽑힐 것이기 때문에 노드를 만들 필요가 없습니다. 

https://en.wikipedia.org/wiki/Consistent_heuristic?utm_source=chatgpt.com

Consistent heuristic - Wikipedia

다만 코너를 만나면 경로가 분기하는 지점이기 때문에 최단 경로의 확보(탐색)를 위해 해당 지점에 대해서는 노드의 생성이 필요합니다.

---

상하좌우 분기의 경우 

대각선이 아닌 상하좌우 분기의 경우 점프 포인트 생성은 비교적 간단합니다.

 

코너는 진행방향 옆에 장애물이 있어 갈림길이 생길 수 있는 지점입니다.

 

예시는 오른쪽으로 진행중이고 위쪽에 장애물이 있는 상황입니다.

 

위쪽에는(x, y+1) 장애물이 있지만 그 다음 지점(x+1, y+1)은 지나갈 수 있습니다.

따라서 이 이후에는 우상 방향으로 진행할 수 있습니다.

 

같은 방식으로 아래에 장애물이 있는경우도 고려할 수 있을 것입니다. 

 

이렇게 강제적으로 분기해야 하는 방향(이웃)을 forced neighbor라고 합니다.

	inline bool forcedH(int r, int c, int dc) { // 수평 진행 중
		return (!passable(r - 1, c) && passable(r - 1, c + dc)) ||
			(!passable(r + 1, c) && passable(r + 1, c + dc));
	}

	inline bool forcedV(int r, int c, int dr) { // 수직 진행 중
		return (!passable(r, c - 1) && passable(r + dr, c - 1)) ||
			(!passable(r, c + 1) && passable(r + dr, c + 1));
	}

 결론적으로는 위와 같은 함수를 사용해 상하좌우를 판단할 수 있습니다.

---

대각 분기의 경우 

대각 분기의 경우 코너에 대해 생각하기 전에 대각선 진행 방향에서의 탐색 범위에 대해서 알아야합니다.

대각선 분기에서는 단순히 대각선 진행방향으로만 가는 것이 아니라 모든 범위를 탐색하기 위해 대각선 진행마다 해당 위치에서의 수직 수평 보조 탐색또한 수행합니다.

 

결론적으로는 아래와 같은 탐색범위를 가집니다.

또한 알아야할 것은 대각선 진행 중 수직 수평 보조 탐색에서 코너를 발견했을 때입니다.

이 경우에는 해당 지점에 바로 노드를 생성하는 것이 아니라 보조 탐색을 시작한 위치에 노드를 생성합니다.

위의 예시는 대각방향 탐색(수평 보조탐색) 중 오른쪽 먼곳에 노드를 생성해야하는 코너가 보이기 때문에 보조 탐색을 시작한 위치에 노드를 생성한 상황입니다. 

---

 

이제 다시 코너 탐색에 대해 보겠습니다.

우상단 방향으로 탐색을 진행하고 있는 상황입니다.

이 경우에는 진행방향의 역방향인 왼쪽 또는 아래쪽에 있을 때 forced neighbor가 생깁니다.

	inline bool forcedDiag(int r, int c, int dr, int dc) { // 대각 진행 중
		return (!passable(r - dr, c) && freeCell(r - dr, c + dc)) ||
			(!passable(r, c - dc) && freeCell(r + dr, c - dc));
	}

코드는 위와 같습니다.

물론 수직 수평 대각 코드를 간단하게 통합할 수 있습니다.

---

JPS의 진행

기본적으로는 노드는 위치와 방향을 가지며, 가장 작은 f값을 가지는 노드를 openlist에서 뽑아 진행한다는 점은 A*와 같습니다.

초기 시작점에서는 8방향을 모두 탐색합니다.

 

이후 코너를 만든다면 노드를 생성하고 f값을 key로 하여 openlist에 넣습니다. 

이후 A*와 비슷하게 openlist와 closelist를 관리하며 목적지에 도달할 때 까지 반복합니다.

 

간단한 맵에서는 위와 같은 결과가 나옵니다.

위의 내용들을 잘 이해했다면 왜 노드가 저곳들에 생성되었는지 알 수 있을 것입니다.

 

좌측은 A*, 우측은 JPS를 통해 경로를 탐색한 과정입니다.

경로가 동일하지는 않지만 A*가 노드를 훨씬 많이 생성한다는 것은 알 수 있습니다.

 

일반적으로 JPS는 노드의 생성을 줄이기 때문에 A*에 비해 큰 성능 개선을 볼 수 있습니다.

다만 맵이 굴곡지지 않은 허허벌판인 경우 A*는 경로를 향해 바로 직진하지만, JPS는 모든 셀에 대해 코너인지를 확인하는 함수가 목적지를 확인하기 전까지 계속될 것이므로 오버헤드가 크게 생길 수 있습니다.

 

결론적으로는 일반적으로는 JPS가 성능상 좋지만 직접 테스트해봐야 어떤 알고리즘이 더 유용한지를 결정할 수 있다는 것이 되겠네요

---

JPS(B)와 JPS+

http://grastien.net/ban/articles/hg-icaps14.pdf

JPS(B)와 JPS+는 JPS를 개선한 알고리즘입니다.

 

JPS(B)는 맵의 탐색 포인트를 축소해 계산합니다 기존에는 탐색은 진행방향으로 이동하며 하나하나 검색했지만 만약에 8칸을 8비트 변수로 줄인다면 해당 값이 0일때 해당 지점은 탐색할 필요가 없다는 것을 알 수 있습니다.

이를 통해 성능을 개선해볼 수 있습니다.

 

JPS+는 정적 맵일 때 맵의 jump point를 모두 미리 계산해놓아 진행방향에 따른 jump point를 테이블에서 가져오는 방법입니다.

jump point를 가져오는게 매우 빨라지지만 정적맵한정이기 때문에 맵이 변형되는 경우에는 점프포인트를 맵전반적으로 다시 계산해야해 사실상 사용할 수 없다는 단점이 있습니다.

 

자세한 내용은 위의 논문을 참고하시면 됩니다