作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试在我的程序中实现 a* 寻路,但它返回以下输出。
这是输出图像
图中蓝色块是已访问块,带圆圈的块是尚未访问的块,黄色块是重新调整给我们的路径。
我无法弄清楚我的代码中的问题是我使用的以下代码。
class Node:
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 search(maze, cost, start, end): # Hear maze is a 2D list with 1 means a wall and 0 is a clear block
start_node = Node(None, tuple(start))
start_node.g = start_node.h = start_node.f = 0
end_node = Node(None, tuple(end))
end_node.g = end_node.h = end_node.f = 0
yet_to_visit_list = []
visited_list = []
yet_to_visit_list.append(start_node)
outer_iterations = 0
max_iterations = (len(maze) // 2) ** 10
move = [[-1, 0], [0, -1], [1, 0], [0, 1]]
no_rows, no_columns = np.shape(maze)
while len(yet_to_visit_list) > 0:
outer_iterations += 1
current_node = yet_to_visit_list[0]
current_index = 0
for index, item in enumerate(yet_to_visit_list):
if item.f < current_node.f:
current_node = item
current_index = index
if outer_iterations > max_iterations:
print("Cann't find the path... too many iterations")
return return_path(current_node, maze)
yet_to_visit_list.pop(current_index)
visited_list.append(current_node)
maze[current_node.position[0]][current_node.position[1]] = 2 # 1 wall 2 visited 3 yet to visit
if current_node == end_node:
return return_path(current_node, maze)
children = []
for new_position in move:
node_position = (current_node.position[0]+ new_position[0], current_node.position[1]+ new_position[1])
if (node_position[0] > (no_rows - 1) or node_position[0] < 0 or node_position[1]>(no_columns-1) or node_position[1] < 0):
continue
if maze[node_position[0]][node_position[1]] != 0:
continue
new_node = Node(current_node, node_position)
children.append(new_node)
for child in children:
if len([visited_child for visited_child in visited_list if visited_child == child]) > 0:
continue
child.g = current_node.g + cost
child.h = (((child.position[0] - end_node.position[0]) ** 2 ) +
((child.position[0] - end_node.position[0])) ** 2)
child.f = child.g + child.h
if len([i for i in yet_to_visit_list if child == i and child.g>i.g]) > 0:
continue
yet_to_visit_list.append(child)
以下函数返回路径
def return_path(current_node, maze):
path = []
no_rows, no_columns = np.shape(maze)
result = maze
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
path = path[::-1]
start_value = 0
for i in range(len(path)):
result[path[i][0]][path[i][1]] = start_value
start_value += 1
return result
最佳答案
在你的 for 循环中 move
,您排除了 maze[.][.] != 0
的邻居:即“墙”或“访问”的邻居。原来的A*算法需要你reconsider访问的节点,看看是否可以进一步降低成本。
此外,我觉得您应该从 visited_list
中删除项目。在你的程序中的某个时候,但我没有看到这种情况发生。
一旦您使程序输入可用,就可以更容易地准确判断出了什么问题,因为这样就可以使用调试器单步调试您的代码。
另一个问题是您使用平方距离作为启发式成本,这可能高估了成本。对于上下左右邻居,使用 Manhattan distance function (请参阅链接中有关使用平方欧几里得距离的警告)。不过,我认为这不是您的程序问题的核心。
关于python - A* 寻路算法给出了路径,但它不是最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68870966/
我是一名优秀的程序员,十分优秀!