격자 맵의 길찾기를 JPS+로 가속하려 합니다. 무엇을 미리 계산하며, 게임 중 문이 열리고 닫히면 어떤 정보가 낡아지나요?

JPS+는 정적인 격자에서 JPS가 방향별로 점프할 때 반복해서 스캔할 구간과 중요한 도착 지점을 미리 계산해 온라인 탐색을 빠르게 하는 방식입니다. 게임 중 모든 셀을 다시 훑는 비용을 줄이는 대신 맵 전처리 시간, 저장 공간, 변경 무효화 책임을 부담합니다. 따라서 문과 임시 장애물이 자주 바뀌는 맵에 정적 전처리 표를 그대로 적용하면 없는 길을 반환하거나 필요한 우회 경로를 누락할 수 있습니다. 이것을 전처리 데이터의 유효성 관리(preprocessed-data validity management)로 다뤄야 합니다.

무엇을 미리 계산하는가

JPS는 균일하거나 증명된 비용 규칙에서 대칭적인 중간 경로를 가지치기하고, 장애물 때문에 선택이 달라지는 강제 이웃이나 목적지 같은 지점까지 점프합니다. JPS+는 각 셀과 이동 방향에 대해 다음 의미 있는 점프 지점 또는 도달 불가 정보를 미리 저장합니다. 온라인에서는 이 표를 조회해 열린 복도를 한 셀씩 검사하는 일을 줄일 수 있습니다. 그러나 목표가 점프 구간의 중간 셀에 놓이면 목표를 통과하는 시점을 정확히 처리해야 하며, 대각 이동·모서리 통과·지형 비용이 전처리 때의 규칙과 같아야 합니다. 저장된 점프 값만 빠르다고 해서 목표 검사와 경로 비용 갱신을 생략할 수는 없습니다.

동적 변경과 버전

문 하나가 열리고 닫히면 바로 옆 셀만이 아니라 그 셀을 통과하거나 그 셀을 기준으로 강제 이웃이 생기는 여러 방향의 정보가 영향을 받습니다. 안전한 선택은 정적 지형과 동적 점유를 분리하고, 정적 부분만 JPS+로 탐색한 뒤 동적 장애물 구간을 별도 재검증하는 것입니다. 이 조합의 결과가 원래와 같은 최단 경로를 보장하는지는 별도 증명이 필요합니다. 동적 변경을 전처리 표에 반영하는 경우 영향 영역을 계산해 부분 재생성할 수 있지만, 영향 범위를 과소 추정하면 더 위험하므로 보수적으로 잡겠습니다. 전처리 데이터에는 원본 맵 버전, 이동 규칙 버전, 에이전트 크기나 clearance 유형을 붙입니다. 온라인 요청이 사용하는 버전과 다르면 표를 거절하고 기본 A*나 최신 전처리 결과를 기다립니다. 재생성 중에는 완성된 스냅샷만 교체해 일부 방향만 새 버전인 표를 공개하지 않으며, 이전 표를 읽는 탐색의 참조 수명도 보장하겠습니다.

작은 맵에서 기본 A*와 JPS+의 도달성·경로 비용을 비교하고, 장애물 변경 직후, 목표가 점프 구간 안에 있는 경우, 대각 모서리와 큰 에이전트를 시험합니다. 온라인 탐색 시간만 보지 말고 전처리 시간, 표 크기, 변경 후 재생성 지연, 오래된 결과 적용률을 측정하겠습니다. JPS+는 무료 최적화가 아니라 정적 맵을 전제로 한 시간-공간 교환(static-map time-space trade-off)입니다. 전처리 표의 저장 단위는 맵 전체일 필요가 없습니다. 정적 영역을 타일이나 청크로 나누고 경계 점프 정보를 별도 보관하면 일부 변경만 재생성할 수 있지만, 점프가 영역 밖으로 이어지면 이웃 버전도 확인해야 합니다. 압축할 때 도달 불가와 아직 계산하지 않음을 같은 값으로 표현하지 않고, 온라인에서 기본 탐색으로 되돌릴 수 있게 상태를 분리하겠습니다. 동적 장애물을 별도 검증으로 처리할 때 정적 JPS+ 경로의 중간 구간을 실제로 통과할 수 있는지 확인해야 합니다.

실패 지점 주변만 기본 A*로 우회하고 반복 실패 지역은 전처리 제외 목록에 올릴 수 있습니다. 전처리 버전과 이동 규칙·에이전트 프로필을 캐시 키에 포함해 잘못 재사용하지 않겠습니다.