我找到了这个算法，但看起来它的创建者没有测试过是否存在无路径的情况。似乎如果没有路径，open_list的长度会越来越大，我不知道解决方案。这是我的第一篇帖子，所以如果有任何错误，请原谅我，非常感谢您的帮助。
class Node(): """A node class for A* Pathfinding""" def __init__(self, parent=None, position=None): self.parent = parent self.position = position self.g = 0 self.h = 0 self.f = 0 def __eq__(self, other): return self.position == other.positiondef astar(maze, start, end): """Returns a list of tuples as a path from the given start to the given end in the given maze""" # Create start and end node start_node = Node(None, start) start_node.g = start_node.h = start_node.f = 0 end_node = Node(None, end) end_node.g = end_node.h = end_node.f = 0 # Initialize both open and closed list open_list = [] closed_list = [] # Add the start node open_list.append(start_node) # Loop until you find the end while len(open_list) > 0: # Get the current node current_node = open_list[0] current_index = 0 for index, item in enumerate(open_list): if item.f < current_node.f: current_node = item current_index = index # Pop current off open list, add to closed list open_list.pop(current_index) closed_list.append(current_node) # Found the goal if current_node == end_node: path = [] current = current_node while current is not None: path.append(current.position) current = current.parent return path[::-1] # Return reversed path # Generate children children = [] for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares # Get node position node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1]) # Make sure within range if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0: continue # Make sure walkable terrain if maze[node_position[0]][node_position[1]] != 0: continue # Create new node new_node = Node(current_node, node_position) # Append children.append(new_node) # Loop through children for child in children: # Child is on the closed list for closed_child in closed_list: if child == closed_child: continue # Create the f, g, and h values child.g = current_node.g + 1 child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2) child.f = child.g + child.h # Child is already in the open list for open_node in open_list: if child == open_node and child.g > open_node.g: continue # Add the child to the open list open_list.append(child)def main(): maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]] start = (0, 0) end = (7, 6) path = astar(maze, start, end) return pathprint(main())回答：
closed_list 应该是一个 set，而不是 list，以检查一个 Node 是否已经被访问过。这样可以移除检查节点是否被访问过的内循环，并非常高效地执行此操作；
但这不仅仅是这里的一个优化：它使 continue 能够恢复执行到它应该的位置，即外循环的末尾。这就是您代码中的主要错误：continue 只会带您到内循环的末尾，实际上使访问检查无效：您不断地添加相同的节点，无论它们是否已经被访问过。
为了将 Node 放入 set 中，Node 必须是可哈希的。在这里，我返回 position 元组的哈希值
修改后的代码会返回一个路径（如果存在），否则返回 None。
class Node(): """A node class for A* Pathfinding""" def __init__(self, parent=None, position=None): self.parent = parent self.position = position self.g = 0 self.h = 0 self.f = 0 def __eq__(self, other): return self.position == other.position def __hash__(self): #<-- added a hash method return hash(self.position)def astar(maze, start, end): """Returns a list of tuples as a path from the given start to the given end in the given maze""" # Create start and end node start_node = Node(None, start) start_node.g = start_node.h = start_node.f = 0 end_node = Node(None, end) end_node.g = end_node.h = end_node.f = 0 # Initialize both open and closed list open_list = [] closed_list = set() # <-- closed_list must be a set # Add the start node open_list.append(start_node) # Loop until you find the end while len(open_list) > 0: # Get the current node current_node = open_list[0] current_index = 0 for index, item in enumerate(open_list): if item.f < current_node.f: current_node = item current_index = index # Pop current off open list, add to closed list open_list.pop(current_index) closed_list.add(current_node) # <-- change append to add # Found the goal if current_node == end_node: path = [] current = current_node while current is not None: path.append(current.position) current = current.parent return path[::-1] # Return reversed path # Generate children children = [] for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares # Get node position node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1]) # Make sure within range if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0: continue # Make sure walkable terrain if maze[node_position[0]][node_position[1]] != 0: continue # Create new node new_node = Node(current_node, node_position) # Append children.append(new_node) # Loop through children for child in children: # Child is on the closed list if child in closed_list: # <-- remove inner loop so continue takes you to the end of the outer loop continue # Create the f, g, and h values child.g = current_node.g + 1 child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2) child.f = child.g + child.h # Child is already in the open list for open_node in open_list: if child == open_node and child.g > open_node.g: continue # Add the child to the open list open_list.append(child)def main(): maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]] start = (0, 0) end = (7, 6) path = astar(maze, start, end) return pathprint(main())