JPS (Jump Point Search) 알고리즘

1. JPS의 기본 개념

• 목적:
  불필요한 노드 생성을 줄여 A* 알고리즘의 속도를 개선.
• 속도가 느린 이유(A*):
  모든 노드에 대해 경로를 계산하므로, 노드가 너무 많이 생성됨.
• 노드를 생략하는 경우:
  1. 직선 경로:
     방향이 일정하다면, 꺾이는 지점에서만 노드를 생성.
  2. 갈림길:
     막혔던 길이 새로 열렸을 때 노드를 생성.

---

2. 갈림길과 자식 노드 생성

• 갈림길 정의:
  부모 노드 기준으로 막혔던 길이 새로 열린 경우.
• 자식 노드 생성 규칙:
  1. 대각선 방향:
     • 기본 방향 + 부모 방향 기준 수직 대각선 2개 추가.
     • 코너에 벽이 있다면 수직 대각선 방향만 탐색.
       → 최대 5개 자식 노드 생성.
  2. 직선 방향:
     • 기본 방향 + 대각선 2개(대각선 조건 만족 시).
       → 최대 3개 자식 노드 생성.

---

3. 초기 노드 생성

• 시작 시:
  • 부모 노드가 없으므로 8방향으로 탐색.
• 대각선 이동 조건:
  • 원거리 코너(4방향 탐색 시 벽이 있는지) 여부를 추가로 확인.

---

4. 노드 탐색 알고리즘

• 목적지 도달:
  노드 생성 후 탐색 종료.
• 벽에 도달:
  해당 방향 탐색 종료.

---

5. 노드 간 연결 최적화

• 자연스러운 이동:
  • 현재 노드와 다음 노드 사이에 장애물이 없는 경우 중간 노드 제거.
  • 알고리즘 사용:
    • Bresenham 선 긋기 알고리즘.

Bresenham 알고리즘

• 기본 개념:
  x축 또는 y축 중 변화량이 큰 축을 기준으로 점을 찍음.
• 예제:
  • x 변화량 = 10, y 변화량 = 6.
  • 점의 위치 계산:

    초기값: P = 6 (y 변화량)
    P += 6 → P = 12 (10 초과) → y 증가
    P -= 10 → P = 2
    ...

• 한계:
  x축과 y축 변화량 차이가 크면 끝 지점에서만 변화 발생.
  → 이 문제는 알고리즘 최적화로 해결.

---

6. 길찾기 후 경로 처리

• 경로 확정 후:
  • 충돌 처리 없이 그대로 경로 이동.
• 문제:
  • 해상도 차이로 장애물을 뚫고 지나가는 것처럼 보일 수 있음.
• 해결 방안:
  1. 그리드 세분화:
     더 촘촘하게 나눠 장애물 반영.
  2. 장애물 처리:
     장애물이 경로에 있어도 어색하지 않도록 설계.

---

7. JPS 사용 조건

• 정적 환경:
  • 장애물이 고정된 경우, 네비게이션 메쉬를 사용하는 것이 효율적.
• 동적 환경:
  • 가변적인 장애물이 존재할 경우, 그리드 기반의 경로 탐색 필수.