有关A*算法问题提问

Question

from time import sleep
from IPython.display import clear_output
import numpy as np
import heapq

WALL = "#"
OPEN = "-"
MANHATTAN = True
EUCLIDEAN = False

DISPLAY_TIME = 0.1 # seconds
HEURISTIC_TYPE = EUCLIDEAN

# FILENAME = "maze1"
# START = (0, 1)
# GOAL = (2, 4)

# FILENAME = "maze2"
# START = (0, 0)
# GOAL = (3, 3)

# FILENAME = "maze3"
# START = (0, 0)
# GOAL = (4, 7)

# FILENAME = "maze4"
# START = (0, 0)
# GOAL = (2, 0)

FILENAME = "maze5"
START = (16, 0)
GOAL = (16, 16)

# FILENAME = "maze6"
# START = (1, 1)
# GOAL = (29, 35)

class Node:
    def __init__(self, x: int, y: int, g=0, h=0):
        self.x = x
        self.y = y
        self.g = g
        self.h = h
        self.f = g + h
        self.parent = None

    def __lt__(self, other):
        return self.f < other.f
    
    def coordinates(self):
        return (self.x, self.y)

def read_maze_file(filename: str):
    with open(filename + ".txt", "r") as file:
        maze = np.array([list(line.strip()) for line in file])

    if len(maze) == 0:
        raise Exception("Maze file is empty")
    
    for row in maze:
        if len(row) != len(maze[0]):
            raise Exception("Maze file is malformed")
    
    return maze

def position(coordinates: tuple[int, int], maze: np.ndarray):
    x = coordinates[0]
    y = coordinates[1]

    if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]) or maze[x][y] == WALL:
        raise ValueError("Invalid position")
    else:
        return Node(x, y)


def heuristic(a: Node, b: Node, type=MANHATTAN):
    if type == MANHATTAN:
        return abs(a.x - b.x) + abs(a.y - b.y)
    elif type == EUCLIDEAN:
        return ((a.x - b.x) ** 2 + (a.y - b.y) ** 2) ** 0.5

def print_maze(maze: np.ndarray, checked: set[tuple[int, int]], path: list[tuple[int, int]], start: Node, end: Node):
    clear_output(wait=False if DISPLAY_TIME > 0 else True)

    START_SYMBOL = "0"
    END_SYMBOL = "1"
    PATH_SYMBOL = "x"
    CHECKED_SYMBOL = "o"
    OPEN_SPACE_SYMBOL = "□"
    WALL_SYMBOL = "■"

    output = ""
    for i in range(len(maze)):
        for j in range(len(maze[i])):
            if (i, j) == start.coordinates():
                output += "\x1b[32m" + START_SYMBOL + "\x1b[0m "
            elif (i, j) == end.coordinates():
                output += "\x1b[31m" + END_SYMBOL + "\x1b[0m "
            elif (i, j) in path:
                output += "\x1b[33m" + PATH_SYMBOL + "\x1b[0m "
            elif (i, j) in checked:
                output += "\x1b[36m" + CHECKED_SYMBOL + "\x1b[0m "
            elif maze[i][j] == OPEN:
                output += OPEN_SPACE_SYMBOL + " "
            elif maze[i][j] == WALL:
                output += WALL_SYMBOL + " "
        output += "\n"

    print(output[:-1])


def a_star(maze: np.ndarray, start: Node, goal: Node, display_time=0.25, h_type=MANHATTAN):
    checked = set()
    open = [start]

    while len(open) > 0:
        heapq.heapify(open)
        current = heapq.heappop(open)
        checked.add((current.x, current.y))

        # Print maze at current step
        if display_time > 0:
            print_maze(maze, checked, [], start, goal)
            sleep(display_time)

        # If goal is reached
        if current.x == goal.x and current.y == goal.y:
            path = []
            while current is not None:
                path.append((current.x, current.y))
                current = current.parent

            # Print final maze with path
            print_maze(maze, checked, path[::-1], start, goal)
            return

        children = []

        # Generate children
        for dx, dy in [(-1, 0), (1, 0),(0, -1), (0, 1)]:
            node_position = (current.x + dx, current.y + dy)

            # If new position is out of bounds or a wall or already in checked set
            if (
                node_position[0] < 0 or node_position[0] >= len(maze) or
                node_position[1] < 0 or node_position[1] >= len(maze[0]) or
                maze[node_position[0]][node_position[1]] == WALL or
                node_position in checked
            ):
                continue

            heuristic_value = heuristic(
                Node(node_position[0], node_position[1]), goal, h_type)
            new_node = Node(
                node_position[0], node_position[1], current.g + 1, heuristic_value)
            new_node.parent = current
            children.append(new_node)

        # Loop through children
        for child in children:
            if (child.x, child.y) in checked:
                continue

            heapq.heappush(open, child)
            checked.add((child.x, child.y))

maze = read_maze_file(FILENAME)
start = position(START, maze)
goal = position(GOAL, maze)

a_star(maze, start, goal, DISPLAY_TIME, HEURISTIC_TYPE)

请问这个A*迷宫寻路代码，在如下的maze中：

-----------------
-#-------------#-
--#-----------#--
---#---------#---
----#-------#----
-----#-----#-----
-----------------
-------#-#-------
--------#--------
--------#--------
--------#--------
-###############-
--------#--------
--------#--------
--------#--------
--------#--------
起-------#-------终

起点为(16,0),终点为(16,16).
按照曼哈顿启发的话，它应该先从倒数第一行遍历到倒数第两行的第八个的位置（此时F=G+H=8），之后因为有墙的存在，它将会从倒数第三行的第一个位置重新开始计算(此时F=G+H=2)。然而代码的运行过程中，它会从倒数第三行第一个位置开始（F=G+H=2），接着它会从倒数第三行第三个位置继续（F=G+H=4），而不是要求的从倒数第三行第二个位置继续（F=G+H=3），不符合要求，请问该如何修改？

按照欧几里得启发的话，它的探索似乎多了一些

Answer 1

代码中加

print(“相关变量名:”,相关变量);input("pause 当前行号")

自己调试