1. JPS의 기본 개념
- 기본 목표 : JPS(Jump Point Search)는 A* 알고리즘의 확장 개념으로, 격자(grid)기반의 맵에서, 시작점부터 목표 지점까지의 최단 경로를 찾는 알고리즘이다.
- 점프 포인트(Jump Point)
- 직선이나 대각선으로 이동할 때 장애물이 나오거나 방향을 변경해야 할 때의 위치
- 탐색의 중간 노드를 건너뛰고, 필요한 경로만 탐색하여 속도를 높인다.
- A* 알고리즘과 주요 차이점 : A*는 모든 인접 노드를 확인하지만, JPS는 점프 가능한 경로를 건너뛰며 효율적으로 탐색한다.
2. JPS in Python 구현 로드맵
단계별 작업
- 맵 정의 및 초기 설정
- 점프 함수 작성 : 특정 방향으로 가능한 만큼 이동(점프)하고, 점프 포인트를 결정한다.
- JPS 탐색 함수 작성 : JPS는 A*와 유사하게 우선순위 큐(Priority Queue)를 사용하여 점프 포인트를 효율적으로 탐색한다.
- 최단 경로 재구성 : 목표에 도달하면
came_from구조를 사용해 경로를 추적한다. - 결과 출력
3. 코딩 과정
1단계 : 격자와 기본 설정
목표
- 격자 기반의 맵을 정의한다.
- 시작점과 목표 지점을 설정한다.
코드
# grid map 정의 (0 : 이동 가능, 1 : 장애물)
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]
]
# 시작점과 목표 지점 설정
start = (0, 0)
goal = (4, 4)2단계 : 휴리스틱 함수 정의
목표
- A*에서 사용하는 목표까지의 예상 거리(휴리스틱)을 정의한다.
- 여기서는 유클리드 거리(직선 거리)를 사용한다.
코드
import math
# 휴리스틱 함수 (유클리드 거리)
def heuristic(node1, node2) :
x1, y1 = node1
x2, y2 = node2
return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)node1과node2는 두 노드의 좌표.- 유클리드 거리 공식으로 두 노드 사이의 거리를 계산한다.
3단계 : 점프 함수 작성
목표
- 특정 방향으로 점프하며 점프 포인트를 찾는다.
- 점프는,
- 장애물에 막히거나,
- 목표에 도달하거나,
- 강제 점프 포인트를 만나면 멈춘다.
코드
def jump(grid, current, direction, goal) :
x, y = current
dx, dy = direction
while True :
x += dx
y += dy
# 맵 경계 체크
if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid [x][y] == 1:
return None # 장애물 또는 경계를 넘어섰을 경우
# 목표에 도달
if (x, y) == goal:
return (x, y)
# 강제 점프 포인트 체크
if dx != 0 and dy != 0 : # 대각선 이동
if (grid[x - dx][y] == 1 and grid[x][y - dy] == 0) or (grid[x][y - dy] == 1 and grid[x - dx][y] == 0):
return (x, y)
else : # 직선 이동
if dx != 0: # 수평 이동
if (grid[x][y - 1] == 1 and grid[x][y + 1] == 0) or (grid[x][y + 1] == 1 and grid[x][y - 1] == 0):
return (x, y)
elif dy != 0: # 수직 이동
if (grid[x - 1][y] == 1 and grid[x + 1][y] == 0) or (grid[x + 1][y] == 1 and grid[x - 1][y] == 0):
return (x, y)current: 현재 노드direction: 점프 방향(dx,dy로 정의)- 점프는 장애물, 경계, 강제 점프 포인트를 만날 때 멈춘다.
4단계 : JPS 탐색 함수
목표
- A* 알고리즘처럼 우선순위 큐를 사용하여 점프 포인트를 탐색한다.
- 각 점프 포인트를 기반으로 목표까지의 경로를 찾아간다.
코드
import heapq
def jps(grid, start, goal):
open_set = []
heapq.heappush(open_set, (0 + heuristic(start, goal), 0, start)) # (f, g, node)
came_from = {}
g_costs = {start: 0}
# 가능한 이동 방향
directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, 1), (1, -1), (-1, 1)]
while open_set :
_, g, current = heapq.heappop(open_set)
# 목표 지점 도달
if current == goal :
path = []
while current in came_from :
path.append(current)
current = came_from[current]
path.append(start)
return path[::-1] # 경로 반환
# 모든 방향 탐색
for direction in directions :
jump_point = jump(grid, current, direction, goal)
if jump_point :
tentative_g = g + heuristic(current, jump_point)
if jump_point not in g_costs or tentative_g < g_costs[jump_point] :
g_costs[jump_point] = tentative_g
f = tentative_g + heuristic(jump_point, goal)
heapq.heappush(open_set, (f, tentative_g, jump_point))
came_from[jump_point] = current
return None # 경로를 찾을 수 없는 경우open_set- 우선순위 큐로 탐색할 점프 포인트를 관리한다.
heapq를 사용하여(f, g, current)의 형태로 저장한다.
came_from- 경로 추적을 위해 각 점프 포인트의 부모 노드를 저장한다.
g_costs- 시작점에서 특정 점프 포인트까지의 누적 거리(
g)를 저장한다.
- 시작점에서 특정 점프 포인트까지의 누적 거리(
5단계 : 테스트
테스트 맵 및 실행
# grid map 정의 (0 : 이동 가능, 1 : 장애물)
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]
]
# 시작점과 목표 지점 설정
start = (0, 0)
goal = (4, 4)
path = jps(grid, start, goal)
if path:
print("최단 경로 : ", path)
else :
print("경로를 찾을 수 없습니다.")실행 결과
최단 경로 : [(0, 0), (1, 0), (2, 1), (3, 2), (3, 3), (4, 4)]문제점
- 점프 포인트 탐색 로직에서 최적 경로를 찾기 위한 조건이 제대로 설정되지 않은 것으로 보임.
- 방향 변경이 필요 없는 상황에서 점프가 너무 짧게 이루어짐.
수정할 사항
- 점프 종료 조건
- 점프가 끝날 조건(목표에 도달, 강제 점프 포인트 발견)을 좀더 정확하게 설정할 필요가 있음.
- 강제 점프 포인트를 올바르게 탐지하고 반환하여 최적 경로를 만들 수 있도록 한다.
- 점프 포인트 계산 방식
- 지금의 점프 로직은 점프 포인트를 지나치게 자주 반환한다.
- 불필요한 탐색을 추가로 발생시키고 있는 것으로 보인다.
- 경로 추적(
came_from)- 반환된 경로가 최적 경로인지 확인한다. 점프 포인트 간 이동은 제대로 기록되고 있는가?
4. 1차 코드 수정
점프 로직 및 강제 점프 포인트 체크 부분에 개선이 필요했다.
수정 코드
def jump(grid, current, direction, goal):
x, y = current
dx, dy = direction
while True:
x += dx
y += dy
# 맵 경계 체크
if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == 1:
return None # 장애물 또는 맵 경계에 도달
# 목표에 도달
if (x, y) == goal:
return (x, y)
# 강제 점프 포인트 체크
if dx != 0 and dy != 0: # 대각선 이동
if (grid[x - dx][y] == 1 and grid[x][y - dy] == 0) or (grid[x][y - dy] == 1 and grid[x - dx][y] == 0):
return (x, y)
elif dx != 0: # 수평 이동
if ((y - 1 >= 0 and grid[x][y - 1] == 1 and y + 1 < len(grid[0]) and grid[x][y + 1] == 0) or
(y + 1 < len(grid[0]) and grid[x][y + 1] == 1 and y - 1 >= 0 and grid[x][y - 1] == 0)):
return (x, y)
elif dy != 0: # 수직 이동
if ((x - 1 >= 0 and grid[x - 1][y] == 1 and x + 1 < len(grid) and grid[x + 1][y] == 0) or
(x + 1 < len(grid) and grid[x + 1][y] == 1 and x - 1 >= 0 and grid[x - 1][y] == 0)):
return (x, y)
# 대각선 이동 중 장애물이 없는 방향으로 점프
if dx != 0 and dy != 0:
if jump(grid, (x, y), (dx, 0), goal) or jump(grid, (x, y), (0, dy), goal):
return (x, y)점프 로직을 위와 같이 수정해보았다.
변경점
- 강제 점프 포인트 조건 강화
- 강제 점프 포인트를 발견할 수 있는 조건(장애물과 방향 전환 가능성)을 더 정확히 설정했다.
- 대각선 이동 중 상하좌우 이동이 필요한 경우를 추가로 점검한다.
- 대각선 점프 보완
- 대각선으로 점프할 때, 수평 또는 수직 방향으로의 점프도 가능하도록 변경해보았다.
수정 후 실행 결과
경로를 찾을 수 없습니다.ㅠㅠ
5. 2차 코드 수정
아마도 점프 함수(jump)가 유효한 점프 포인트를 제대로 반환해주지 못하고 있는 것으로 보인다. (None을 반환함)... 특히 대각선 이동 중 추가적인 점프 조건이 제대로 처리되고 있지 않은 것 같다. 이러한 문제를 해결하기 위해 점프 함수의 논리를 점검하고 수정해야 할 것 같다.
점검할 주요 부분
1. 경계 검사와 장애물 부분
- 현재 점프 함수에서 장애물이나 맵의 경계를 벗어날 경우
None을 반환하도록 설정했는데, 특정 방향에서 조건이 충족되지 않아서 강제로 점프 포인트를 지나치는 문제가 있을 수 있다.
2. 대각선 이동 조건
- 대각선 이동 중, 특정 방향으로 점프했을 때 대각선 경로가 아닌 다른 경로에서도 점프 포인트를 찾아야 하는 상황이 누락되었을 수 있다.
3. 목표에 도달하는 경로 확인
- 점프가 목표 지점에 도달했는지 확인하고 적절히 반환하도록 점검해야 한다.
수정 코드
def jump(grid, current, direction, goal) :
x, y = current
dx, dy = direction
while True :
x += dx
y += dy
# 맵 경계 체크
if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid [x][y] == 1:
return None # 장애물 또는 경계를 넘어섰을 경우
# 목표에 도달
if (x, y) == goal:
return (x, y)
# 강제 점프 포인트 체크
if dx != 0 and dy != 0 : # 대각선 이동
if (grid[x - dx][y] == 1 and grid[x][y - dy] == 0) or (grid[x][y - dy] == 1 and grid[x - dx][y] == 0):
return (x, y)
elif dx != 0 : # 수평 이동
if ((y - 1 >= 0 and grid[x][y - 1] == 1 and y + 1 < len(grid[0]) and grid[x][y + 1] == 0) or (y + 1 < len(grid[0]) and grid[x][y + 1] == 1 and y - 1 >=0 and grid[x][y - 1] == 0)) :
return (x, y)
elif dy != 0 : # 수직 이동
if ((x - 1 >= 0 and grid[x - 1][y] == 1 and x + 1 < len(grid) and grid[x + 1][y] == 0) or (x + 1 < len(grid) and grid[x + 1][y] == 1 and x - 1 >= 0 and grid[x - 1][y] == 0)) :
return (x, y)
# 대각선 이동 중 장애물이 없는 방향으로 점프
if dx != 0 and dy != 0 :
next_jump_x = jump(grid, (x, y), (dx, 0), goal)
next_jump_y = jump(grid, (x, y), (0, dy), goal)
if next_jump_x :
return next_jump_x
if next_jump_y :
return next_jump_y수정 후 실행 결과
경로를 찾을 수 없습니다.ㅠㅠㅠ
6. 3차 코드 수정 (디버깅 추가)
수정된 코드 전체
import math
import heapq
# 휴리스틱 함수 (유클리드 거리)
def heuristic(node1, node2):
x1, y1 = node1
x2, y2 = node2
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
# 점프 함수
def jump(grid, current, direction, goal):
x, y = current
dx, dy = direction
while True:
x += dx
y += dy
# 디버깅: 현재 위치와 방향
print(f"Jumping to ({x}, {y}) in direction ({dx}, {dy})")
# 맵 경계 체크
if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == 1:
print(f"Out of bounds or hit obstacle at ({x}, {y})")
return None
# 목표에 도달
if (x, y) == goal:
print(f"Reached goal at ({x}, {y})")
return (x, y)
# 강제 점프 포인트 체크
if dx != 0 and dy != 0: # 대각선 이동
if (grid[x - dx][y] == 1 and grid[x][y - dy] == 0) or (grid[x][y - dy] == 1 and grid[x - dx][y] == 0):
print(f"Found forced jump point at ({x}, {y}) (diagonal)")
return (x, y)
elif dx != 0: # 수평 이동
if (y > 0 and grid[x][y - 1] == 1) or (y < len(grid[0]) - 1 and grid[x][y + 1] == 1):
print(f"Found forced jump point at ({x}, {y}) (horizontal)")
return (x, y)
elif dy != 0: # 수직 이동
if (x > 0 and grid[x - 1][y] == 1) or (x < len(grid) - 1 and grid[x + 1][y] == 1):
print(f"Found forced jump point at ({x}, {y}) (vertical)")
return (x, y)
# 대각선 이동 중 추가 점프
if dx != 0 and dy != 0:
next_jump_x = jump(grid, (x, y), (dx, 0), goal)
next_jump_y = jump(grid, (x, y), (0, dy), goal)
if next_jump_x or next_jump_y:
print(f"Found diagonal jump point at ({x}, {y})")
return (x, y)
# JPS 탐색 함수
def jps(grid, start, goal):
open_set = []
heapq.heappush(open_set, (0 + heuristic(start, goal), 0, start)) # (f, g, node)
came_from = {}
g_costs = {start: 0}
# 가능한 이동 방향
directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, 1), (1, -1), (-1, 1)]
while open_set:
_, g, current = heapq.heappop(open_set)
# 디버깅: 현재 처리 중인 노드
print(f"Processing node: {current}, g = {g}")
# 목표 지점 도달
if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
print("Found path:", path[::-1])
return path[::-1] # 경로 반환
# 모든 방향 탐색
for direction in directions:
jump_point = jump(grid, current, direction, goal)
if jump_point:
tentative_g = g + heuristic(current, jump_point)
# 디버깅: 점프 포인트와 비용
print(f"Jump point: {jump_point}, tentative_g = {tentative_g}")
if jump_point not in g_costs or tentative_g < g_costs[jump_point]:
g_costs[jump_point] = tentative_g
f = tentative_g + heuristic(jump_point, goal)
heapq.heappush(open_set, (f, tentative_g, jump_point))
came_from[jump_point] = current
print(f"Added to open set: {jump_point} with f = {f}")
print("경로를 찾을 수 없습니다_jps.")
return None # 경로를 찾을 수 없는 경우
# 테스트 맵 정의
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]
]
start = (0, 0)
goal = (4, 4)
path = jps(grid, start, goal)
if path:
print("최단 경로:", path)
else:
print("경로를 찾을 수 없습니다.")
실행 결과 (디버깅)
Processing node: (0, 0), g = 0
Jumping to (-1, 0) in direction (-1, 0)
Out of bounds or hit obstacle at (-1, 0)
Jumping to (1, 0) in direction (1, 0)
Found forced jump point at (1, 0) (horizontal)
Jump point: (1, 0), tentative_g = 1.0
Added to open set: (1, 0) with f = 6.0
Jumping to (0, -1) in direction (0, -1)
Out of bounds or hit obstacle at (0, -1)
Jumping to (0, 1) in direction (0, 1)
Found forced jump point at (0, 1) (vertical)
Jump point: (0, 1), tentative_g = 1.0
Added to open set: (0, 1) with f = 6.0
Jumping to (-1, -1) in direction (-1, -1)
Out of bounds or hit obstacle at (-1, -1)
Jumping to (1, 1) in direction (1, 1)
Out of bounds or hit obstacle at (1, 1)
Jumping to (1, -1) in direction (1, -1)
Out of bounds or hit obstacle at (1, -1)
Jumping to (-1, 1) in direction (-1, 1)
Out of bounds or hit obstacle at (-1, 1)
Processing node: (0, 1), g = 1.0
Jumping to (-1, 1) in direction (-1, 0)
Out of bounds or hit obstacle at (-1, 1)
Jumping to (1, 1) in direction (1, 0)
Out of bounds or hit obstacle at (1, 1)
Jumping to (0, 0) in direction (0, -1)
Jumping to (0, -1) in direction (0, -1)
Out of bounds or hit obstacle at (0, -1)
Jumping to (0, 2) in direction (0, 1)
Found forced jump point at (0, 2) (vertical)
Jump point: (0, 2), tentative_g = 2.0
Added to open set: (0, 2) with f = 6.47213595499958
Jumping to (-1, 0) in direction (-1, -1)
Out of bounds or hit obstacle at (-1, 0)
Jumping to (1, 2) in direction (1, 1)
Out of bounds or hit obstacle at (1, 2)
Jumping to (1, 0) in direction (1, -1)
Found forced jump point at (1, 0) (diagonal)
Jump point: (1, 0), tentative_g = 2.414213562373095
Jumping to (-1, 2) in direction (-1, 1)
Out of bounds or hit obstacle at (-1, 2)
Processing node: (1, 0), g = 1.0
Jumping to (0, 0) in direction (-1, 0)
Jumping to (-1, 0) in direction (-1, 0)
Out of bounds or hit obstacle at (-1, 0)
Jumping to (2, 0) in direction (1, 0)
Jumping to (3, 0) in direction (1, 0)
Found forced jump point at (3, 0) (horizontal)
Jump point: (3, 0), tentative_g = 3.0
Added to open set: (3, 0) with f = 7.123105625617661
Jumping to (1, -1) in direction (0, -1)
Out of bounds or hit obstacle at (1, -1)
Jumping to (1, 1) in direction (0, 1)
Out of bounds or hit obstacle at (1, 1)
Jumping to (0, -1) in direction (-1, -1)
Out of bounds or hit obstacle at (0, -1)
Jumping to (2, 1) in direction (1, 1)
Found forced jump point at (2, 1) (diagonal)
Jump point: (2, 1), tentative_g = 2.414213562373095
Added to open set: (2, 1) with f = 6.019764837837084
Jumping to (2, -1) in direction (1, -1)
Out of bounds or hit obstacle at (2, -1)
Jumping to (0, 1) in direction (-1, 1)
Found forced jump point at (0, 1) (diagonal)
Jump point: (0, 1), tentative_g = 2.414213562373095
Processing node: (2, 1), g = 2.414213562373095
Jumping to (1, 1) in direction (-1, 0)
Out of bounds or hit obstacle at (1, 1)
Jumping to (3, 1) in direction (1, 0)
Out of bounds or hit obstacle at (3, 1)
Jumping to (2, 0) in direction (0, -1)
Jumping to (2, -1) in direction (0, -1)
Out of bounds or hit obstacle at (2, -1)
Jumping to (2, 2) in direction (0, 1)
Found forced jump point at (2, 2) (vertical)
Jump point: (2, 2), tentative_g = 3.414213562373095
Added to open set: (2, 2) with f = 6.242640687119286
Jumping to (1, 0) in direction (-1, -1)
Found forced jump point at (1, 0) (diagonal)
Jump point: (1, 0), tentative_g = 3.82842712474619
Jumping to (3, 2) in direction (1, 1)
Found forced jump point at (3, 2) (diagonal)
Jump point: (3, 2), tentative_g = 3.82842712474619
Added to open set: (3, 2) with f = 6.06449510224598
Jumping to (3, 0) in direction (1, -1)
Found forced jump point at (3, 0) (diagonal)
Jump point: (3, 0), tentative_g = 3.82842712474619
Jumping to (1, 2) in direction (-1, 1)
Out of bounds or hit obstacle at (1, 2)
Processing node: (3, 2), g = 3.82842712474619
Jumping to (2, 2) in direction (-1, 0)
Found forced jump point at (2, 2) (horizontal)
Jump point: (2, 2), tentative_g = 4.82842712474619
Jumping to (4, 2) in direction (1, 0)
Jumping to (5, 2) in direction (1, 0)
Out of bounds or hit obstacle at (5, 2)
Jumping to (3, 1) in direction (0, -1)
Out of bounds or hit obstacle at (3, 1)
Jumping to (3, 3) in direction (0, 1)
Found forced jump point at (3, 3) (vertical)
Jump point: (3, 3), tentative_g = 4.82842712474619
Added to open set: (3, 3) with f = 6.242640687119285
Jumping to (2, 1) in direction (-1, -1)
Found forced jump point at (2, 1) (diagonal)
Jump point: (2, 1), tentative_g = 5.242640687119285
Jumping to (4, 3) in direction (1, 1)
Jumping to (5, 3) in direction (1, 0)
Out of bounds or hit obstacle at (5, 3)
Jumping to (4, 4) in direction (0, 1)
Reached goal at (4, 4)
Found diagonal jump point at (4, 3)
Jump point: (4, 3), tentative_g = 5.242640687119285
Added to open set: (4, 3) with f = 6.242640687119285
Jumping to (4, 1) in direction (1, -1)
Found forced jump point at (4, 1) (diagonal)
Jump point: (4, 1), tentative_g = 5.242640687119285
Added to open set: (4, 1) with f = 8.242640687119284
Jumping to (2, 3) in direction (-1, 1)
Out of bounds or hit obstacle at (2, 3)
Processing node: (3, 3), g = 4.82842712474619
Jumping to (2, 3) in direction (-1, 0)
Out of bounds or hit obstacle at (2, 3)
Jumping to (4, 3) in direction (1, 0)
Jumping to (5, 3) in direction (1, 0)
Out of bounds or hit obstacle at (5, 3)
Jumping to (3, 2) in direction (0, -1)
Jumping to (3, 1) in direction (0, -1)
Out of bounds or hit obstacle at (3, 1)
Jumping to (3, 4) in direction (0, 1)
Jumping to (3, 5) in direction (0, 1)
Out of bounds or hit obstacle at (3, 5)
Jumping to (2, 2) in direction (-1, -1)
Found forced jump point at (2, 2) (diagonal)
Jump point: (2, 2), tentative_g = 6.242640687119285
Jumping to (4, 4) in direction (1, 1)
Reached goal at (4, 4)
Jump point: (4, 4), tentative_g = 6.242640687119285
Added to open set: (4, 4) with f = 6.242640687119285
Jumping to (4, 2) in direction (1, -1)
Jumping to (5, 2) in direction (1, 0)
Out of bounds or hit obstacle at (5, 2)
Jumping to (4, 1) in direction (0, -1)
Found forced jump point at (4, 1) (vertical)
Found diagonal jump point at (4, 2)
Jump point: (4, 2), tentative_g = 6.242640687119285
Added to open set: (4, 2) with f = 8.242640687119284
Jumping to (2, 4) in direction (-1, 1)
Found forced jump point at (2, 4) (diagonal)
Jump point: (2, 4), tentative_g = 6.242640687119285
Added to open set: (2, 4) with f = 8.242640687119284
Processing node: (4, 3), g = 5.242640687119285
Jumping to (3, 3) in direction (-1, 0)
Jumping to (2, 3) in direction (-1, 0)
Out of bounds or hit obstacle at (2, 3)
Jumping to (5, 3) in direction (1, 0)
Out of bounds or hit obstacle at (5, 3)
Jumping to (4, 2) in direction (0, -1)
Jumping to (4, 1) in direction (0, -1)
Found forced jump point at (4, 1) (vertical)
Jump point: (4, 1), tentative_g = 7.242640687119285
Jumping to (4, 4) in direction (0, 1)
Reached goal at (4, 4)
Jump point: (4, 4), tentative_g = 6.242640687119285
Jumping to (3, 2) in direction (-1, -1)
Jumping to (2, 2) in direction (-1, 0)
Found forced jump point at (2, 2) (horizontal)
Jumping to (3, 1) in direction (0, -1)
Out of bounds or hit obstacle at (3, 1)
Found diagonal jump point at (3, 2)
Jump point: (3, 2), tentative_g = 6.65685424949238
Jumping to (5, 4) in direction (1, 1)
Out of bounds or hit obstacle at (5, 4)
Jumping to (5, 2) in direction (1, -1)
Out of bounds or hit obstacle at (5, 2)
Jumping to (3, 4) in direction (-1, 1)
Jumping to (2, 4) in direction (-1, 0)
Found forced jump point at (2, 4) (horizontal)
Jumping to (3, 5) in direction (0, 1)
Out of bounds or hit obstacle at (3, 5)
Found diagonal jump point at (3, 4)
Jump point: (3, 4), tentative_g = 6.65685424949238
Added to open set: (3, 4) with f = 7.65685424949238
Processing node: (4, 4), g = 6.242640687119285
Found path: [(0, 0), (1, 0), (2, 1), (3, 2), (3, 3), (4, 4)]
최단 경로: [(0, 0), (1, 0), (2, 1), (3, 2), (3, 3), (4, 4)]디버깅 결과 분석
1. 점프 포인트 탐지
Found forced jump point at (2, 2) (horizontal)
...
Found forced jump point at (2, 4) (diagonal)- 점프 포인트가 강제 점프 포인트 조건에 따라 잘 탐지되고 있는 것으로 보임.
2. 최단 경로 확인
최단 경로: [(0, 0), (1, 0), (2, 1), (3, 2), (3, 3), (4, 4)]
출발점 -> (1, 0): 수직 이동(1, 0) -> (2, 1): 대각선 이동 (장애물(1, 1)회피)(2, 1) -> (3, 2): 대각선 이동(3, 2) -> (3, 3): 수평 이동(3, 3) -> (4, 4): 대각선 이동
3. 결론
처음에 나왔던 최단 경로가 맞았다... (1차 2차 수정 왜함?)
