如何将递归实现的Jump Point Search转换为迭代版本？

我现有一个递归实现的函数，希望将其转换为迭代版本。请问该如何实现？

def jump(grid: np.ndarray, current: Point, parent: Point, end: Point) -> Point | None:
    if not reachable(grid, *current):
        return None

    if current == end:
        return current

    dx, dy = current.x - parent.x, current.y - parent.y
    if dx != 0 and dy != 0:
        if jump(grid, Point(current.x + dx, current.y), current, end) or jump(
            grid, Point(current.x, current.y + dy), current, end
        ):
            return current
    elif dx != 0:
        if (
            not reachable(grid, current.x - dx, current.y - 1)
            and reachable(grid, current.x, current.y - 1)
        ) or (
            not reachable(grid, current.x - dx, current.y + 1)
            and reachable(grid, current.x, current.y + 1)
        ):
            return current
    else:
        if (
            not reachable(grid, current.x - 1, current.y - dy)
            and reachable(grid, current.x - 1, current.y)
        ) or (
            not reachable(grid, current.x + 1, current.y - dy)
            and reachable(grid, current.x + 1, current.y)
        ):
            return current

    if reachable(grid, current.x + dx, current.y) and reachable(
        grid, current.x, current.y + dy
    ):
        return jump(grid, Point(current.x + dx, current.y + dy), current, end)
    else:
        return None

以下是Point类和reachable函数的实现：

OBSTACLE_ID = 1

class Point(NamedTuple):
    x: int
    y: int


def reachable(grid: np.ndarray, x: int, y: int) -> bool:
    return (
        0 <= x < grid.shape[1]
        and 0 <= y < grid.shape[0]
        and grid[y][x] != OBSTACLE_ID
    )

以下是运行Jump Point Search的代码：

INTERCARDINAL_OFFSETS = (
    (-1, -1),
    (0, -1),
    (1, -1),
    (-1, 0),
    (1, 0),
    (-1, 1),
    (0, 1),
    (1, 1),
)

grid = [
    [10, 11, 4, 13, 14, -3, 16, 17, 18, 19],
    [20, 21, 22, 23, 24, 25, 26, 27, 4, 29],
    [30, 31, 32, 33, 4, 35, 36, 37, 38, 4],
    [40, 41, 42, 43, 44, 45, 46, 4, 48, 49],
    [50, 4, 52, 53, 54, 55, 56, 4, 58, 59],
    [60, 61, 62, 63, 64, 65, 66, 67, 68, 69],
    [70, 4, 72, 73, 74, 75, 76, 77, 78, 79],
    [80, -2, 82, 83, 84, 85, 86, 87, 88, 89],
    [90, 91, 92, 93, 4, 95, 4, 97, 98, 99],
    ]


def find_neighbours(
    current: Point, parent: Point | None
) -> Generator[Point, None, None]:
    if parent:
        dx, dy = (
            (current.x - parent.x) // max(abs(current.x - parent.x), 1),
            (current.y - parent.y) // max(abs(current.y - parent.y), 1),
        )

        if dx != 0 and dy != 0:
            x_mods = (dx, 0, dx)
            y_mods = (0, dy, dy)
        elif dx != 0:
            x_mods = (dx, dx, dx)
            y_mods = (0, 1, -1)
        else:
            x_mods = (0, 1, -1)
            y_mods = (dy, dy, dy)
        yield from (
            Point(current.x + x_mod, current.y + y_mod)
            for x_mod, y_mod in zip(x_mods, y_mods)
        )
    else:
        yield from (
            Point(current.x + dx, current.y + dy) for dx, dy in INTERCARDINAL_OFFSETS
        )

def calculate_astar_path(grid: np.ndarray, start: Point, end: Point) -> list[Point]:
    heap: list[tuple[int, Point, Point | None]] = [(0, start, None)]
    came_from: dict[Point, Point] = {start: start}
    distances: dict[Point, int] = {start: 0}

    while heap:
        _, current, parent = heappop(heap)

        if current == end:
            result = []
            while True:
                result.append(current)

                if came_from[current] != current:
                    current = came_from[current]
                else:
                    break
            return result

        for neighbour in find_neighbours(current, parent):
            jump_point = jump(grid, neighbour, current, end)
            if jump_point is not None and jump_point not in came_from:
                came_from[jump_point] = current
                distances[jump_point] = distances[came_from[jump_point]] + 1
                f_cost = distances[jump_point] + max(
                    abs(neighbour.x - current.x), abs(neighbour.y - current.y)
                )
                heappush(heap, (f_cost, jump_point, current))

    return []


res = calculate_astar_path(np.array(grid), Point(1, 7), Point(0, 5))

迭代版本实现思路 #

递归函数的本质是调用栈的嵌套执行，我们可以手动用栈结构模拟这一过程。每个栈元素需要保存当前调用的上下文：当前点current、父节点parent、终点end，以及当前执行到的步骤（避免重复执行已完成的逻辑）。

迭代版jump函数代码

def jump_iterative(grid: np.ndarray, current: Point, parent: Point, end: Point) -> Point | None:
    # 栈元素：(current, parent, end, step, result)
    # step标记当前执行阶段：
    # 0: 初始检查（可达性、是否为终点）
    # 1: 处理方向分支的子调用（斜向的两个jump，或水平/垂直的强制跳跃判断）
    # 1.1: 处理斜向第一个子调用的返回结果
    # 1.2: 处理斜向第二个子调用的返回结果
    # 2: 处理最后的斜向跳跃调用
    stack = [(current, parent, end, 0, None)]
    
    while stack:
        curr, p, e, step, res = stack.pop()
        
        if step == 0:
            # 执行初始检查逻辑
            if not reachable(grid, *curr):
                continue
            if curr == e:
                return curr
            
            dx, dy = curr.x - p.x, curr.y - p.y
            # 进入step1，保存方向参数
            stack.append((curr, p, e, 1, (dx, dy)))
        
        elif step == 1:
            dx, dy = res
            if dx != 0 and dy != 0:
                # 斜向：先压入第二个子调用的后续处理，再压入第一个子调用
                stack.append((curr, p, e, 1.1, (dx, dy, None)))
                next_point = Point(curr.x + dx, curr.y)
                stack.append((next_point, curr, e, 0, None))
            elif dx != 0:
                # 水平方向：检查强制跳跃条件
                cond1 = not reachable(grid, curr.x - dx, curr.y -1) and reachable(grid, curr.x, curr.y -1)
                cond2 = not reachable(grid, curr.x - dx, curr.y +1) and reachable(grid, curr.x, curr.y +1)
                if cond1 or cond2:
                    return curr
                # 进入step2
                stack.append((curr, p, e, 2, (dx, dy)))
            else:
                # 垂直方向：检查强制跳跃条件
                cond1 = not reachable(grid, curr.x -1, curr.y - dy) and reachable(grid, curr.x -1, curr.y)
                cond2 = not reachable(grid, curr.x +1, curr.y - dy) and reachable(grid, curr.x +1, curr.y)
                if cond1 or cond2:
                    return curr
                # 进入step2
                stack.append((curr, p, e, 2, (dx, dy)))
        
        elif step == 1.1:
            dx, dy, _ = res
            # 第一个子调用返回非None，直接返回当前点
            if res is not None:
                return curr
            # 处理第二个子调用
            stack.append((curr, p, e, 1.2, (dx, dy)))
            next_point = Point(curr.x, curr.y + dy)
            stack.append((next_point, curr, e, 0, None))
        
        elif step == 1.2:
            dx, dy = res
            # 第二个子调用返回非None，直接返回当前点
            if res is not None:
                return curr
            # 进入step2
            stack.append((curr, p, e, 2, (dx, dy)))
        
        elif step == 2:
            dx, dy = res
            # 检查斜向下一步是否可达
            if reachable(grid, curr.x + dx, curr.y) and reachable(grid, curr.x, curr.y + dy):
                next_point = Point(curr.x + dx, curr.y + dy)
                stack.append((next_point, curr, e, 0, None))
            else:
                # 无跳跃点，继续遍历栈
                continue
    
    # 所有路径遍历完成，未找到有效跳跃点
    return None

关键逻辑说明

1. 栈状态管理：用step标记每个栈元素的执行阶段，避免重复执行初始检查、分支判断等逻辑。
2. 子调用处理：对于递归中的嵌套调用（比如斜向的两个jump），先将当前状态压入栈，再压入子调用的初始状态，确保子调用执行完成后回到当前状态处理结果。
3. 结果传递：栈元素中的result字段用于保存中间计算结果（比如方向参数、子调用的返回值），供后续阶段使用。

替换使用

将calculate_astar_path函数中的jump调用替换为jump_iterative即可：

jump_point = jump_iterative(grid, neighbour, current, end)

内容的提问来源于stack exchange，提问作者Aspect11