균일 비용의 격자에서 A*가 비슷한 경로를 많이 탐색합니다. JPS는 어떤 중간 탐색을 줄이며 어디에서 멈춰야 하나요?

균일 비용 격자에서 A*는 같은 비용의 이동 순서만 다른 경로를 여러 개 확장할 수 있습니다. JPS는 부모에서 온 방향과 장애물 배치를 이용해, 중간 셀을 모두 후보로 넣지 않고 경로 선택이 실제로 달라지는 지점까지 점프합니다. 점프는 캐릭터를 순간이동시키는 것이 아니라 탐색 그래프에서 대칭적인 중간 노드를 생략하는 것입니다. 이 최적화를 점프 포인트 탐색(Jump Point Search)이라고 부릅니다.

자연 이웃과 강제 이웃

부모에서 오른쪽으로 이동했다면 열린 평면에서 다시 왼쪽이나 위·오른쪽 조합의 모든 순서를 확장할 필요가 없습니다. JPS는 부모 방향으로 계속 갈 수 있는 자연 이웃을 남기고, 장애물 때문에 원래 대칭 경로가 막혀 반드시 보존해야 하는 이웃을 강제 이웃으로 추가합니다. 예를 들어 직진 경로 옆에 장애물이 있어 그 장애물을 돌아가는 방향만 부모 경로에서 놓치지 않도록 선택지를 남깁니다. 장애물을 만날 때까지 무조건 직선으로 가는 규칙은 아닙니다. 강제 이웃 판정은 대각 이동과 모서리 통과 규칙에 따라 달라지며, 필요한 이웃을 잘못 제거하면 도달성이나 최적성을 잃습니다. 점프는 목적지에 도달하거나, 강제 이웃이 생기거나, 더 진행할 수 없을 때 멈춥니다. 대각 이동 중에는 직교 방향의 점프에서 의미 있는 지점이 나오는지 검사해야 하므로 단순한 8방향 직선 스캔으로 끝나지 않습니다. 목표가 현재 점프 선분의 중간에 있으면 그 목표에서 멈춰야 하고, 맵 경계를 만나면 실패한 점프로 처리합니다. JPS가 적용되는 비용·이동 전제가 정확해야 하므로 지형마다 다른 가중치나 동적 비용을 넣을 때 기존 가지치기를 그대로 사용하지 않겠습니다.

선택 기준과 검증

넓고 균일한 격자에서 대칭 경로가 많을 때 JPS의 이점이 크지만, 장애물이 매우 복잡하거나 작은 맵이면 점프 스캔과 분기 비용이 A보다 클 수 있습니다. JPS+처럼 정적 맵의 방향별 점프를 전처리할 수도 있지만 변경 시 데이터가 낡습니다. 항상 노드 수만 비교하지 말고 실제 CPU 시간, 캐시·메모리, 경로 비용, 최악 장애물 패턴을 측정하겠습니다. 검증은 빈 공간, 벽 옆 강제 이웃, 대각 모서리, 좁은 통로, 목표가 점프 중간인 경우, 다양한 시작·목표를 포함합니다. 기준 A와 도달성·최단 비용·경로 재현성을 비교하고, 탐색 규칙을 바꿨다면 휴리스틱과 충돌 검사의 동일 전제도 확인합니다. JPS의 본질은 빠른 직선 이동이 아니라 대칭 경로의 안전한 가지치기(safe symmetry pruning)입니다. JPS의 가지치기는 이동 비용이 같은 경로를 대칭으로 볼 수 있을 때만 성립합니다.

지형별 비용이나 방향별 선회 비용이 있으면 이동 순서가 비용을 바꿀 수 있으므로 기본 A로 전환하거나 새 가지치기 증명을 마련해야 합니다. 경로를 점프 포인트 연결로만 저장하면 실행 시 중간 셀을 복원해 충돌·애니메이션·예약을 확인해야 합니다. 점프 중간에 동적 장애물이 생겼을 때 통째로 통과했다고 처리하지 않고 다음 실행 구간을 일반 이동 검사로 쪼개겠습니다. 빈 공간 속도만 강조하지 말고 강제 이웃 패턴과 실제 추종 시간을 기준 A와 비교하겠습니다. 작은 맵에서 모든 시작·목표 쌍을 열거해 기본 A*와 비용 및 도달성을 비교하겠습니다. 경로 모양은 달라도 되지만 찾을 수 있는 길을 놓치거나 벽을 통과하면 안 됩니다. 이어서 긴 복도와 촘촘한 장애물에서 점프 스캔 횟수, 힙 연산, 전체 CPU 시간을 비교해 적용 범위를 정합니다.