python 3d A*寻路无限循环
python 3d A* pathfinging infinite loop
我正在尝试调整我发现的应用程序 here，我想我只需要添加一个轴。问题是脚本似乎卡住了。谁能告诉我我做错了什么以及如何将 A* 与 3d 矩阵 (i j k) 一起使用？
这是我更改的 A* 函数的一部分
for new_position in [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]: # Adjacent squares, (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares removed to ignor diagonal movement
# Get node position
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1], current_node.position[2] + new_position[2])
# 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 or node_position[2] > (len(maze) - 1) or node_position[2] < 0 or node_position[2] > (len(maze[len(maze)-1]) -1):
continue
# Make sure walkable terrain
if maze[node_position[0]][node_position[1]][node_position[2]] != 0:
continue
原来是：
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
这是我修改后的整个脚本：
import numpy as np
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 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, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]: # Adjacent squares, (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares removed to ignor diagonal movement
# Get node position
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1], current_node.position[2] + new_position[2])
# 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 or node_position[2] > (len(maze) - 1) or node_position[2] < 0 or node_position[2] > (len(maze[len(maze)-1]) -1):
continue
# Make sure walkable terrain
if maze[node_position[0]][node_position[1]][node_position[2]] != 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.position[2] - end_node.position[2]) ** 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 = np.zeros((12,12,12))
start = (10, 9, 9)
end = (1, 1, 1)
path = astar(maze, start, end)
print(path)
if __name__ == '__main__':
main()
A* 可以处理任意数量的维度；这是一种图遍历算法，无论您的问题 space 有多少维度，将一个位置连接到另一个位置仍然会生成一个图。
但是，您在生成新节点时遇到了两个问题。
您在列表中包含了 (0, 0, 0)，因此 没有变化。您不断将当前位置放回队列中以供考虑。那只是工作忙，因为当前位置已经在关闭列表中了
你永远不会从你的任何坐标中减去，你只会加。因此，您的 x、y 和 z 值只能向上 。如果达到你的目标需要一条路径绕过一个障碍，那么你就有问题了，因为你的版本所能做的就是沿着任何给定的轴在一个方向上移动。
在一个3×3×3的三维矩阵中，当前位置在中间，有3乘3乘3减1 == 26个你一步可以到达的位置。您的代码只涉及其中的 7 个，外加一个保留的代码。
如果您将 for new_position in [...] 列表中的元组提取到一个单独的变量中并添加一些换行符，然后稍微重新排列它们以根据列表中有多少 1 对它们进行分组元组，你得到以下定义。我将其重命名为 deltas，因为它不是新位置，它是相对于旧位置的 change，或 delta。我重新排列了您的元组，以便更轻松地对它们进行逻辑分组：
deltas = [
(0, 0, 0), # no change,
(0, 0, 1), (0, 1, 0), (1, 0, 0), # add to a single axis
(0, 1, 1), (1, 0, 1), (1, 1, 0), # add to two axes
(1, 1, 1) # move in all 3 directions at once.
]
for delta in deltas:
# ...
您想删除第一个 ((0, 0, 0))，并且您需要添加其他变体的 -1 个版本。您需要 26 个不同的元组，但是手写这些元组会很麻烦，而且速度非常快。您可以使用 itertools.product() 来生成这些，而不是：
from itertools import product
# combinations of -1, 0 and 1, filtering out the (0, 0, 0) case:
deltas = [d for d in product((-1, 0, 1), repeat=3) if any(d)]
现在，您在循环旁边的评论是：
# Adjacent squares removed to ignor diagonal movement
不完全清楚你的意思，因为你的原始增量列表包括对角线（(0, 1, 1) 在 y 和 z 方向上移动，并且你有元组结合 x 加 y 和 x 加 z 轴的移动），甚至是通过递增所有 3 个轴来移动对角线的移动。如果你只想移动上、下、左、右, forward, and backward, 你想一次限制在一个轴上移动, deltas 应该是:
# movement without diagonals
deltas = [
(1, 0, 0), (-1, 0, 0), # only x
(0, 1, 0), (0, -1, 0), # only y
(0, 0, 1), (0, 0, -1), # only z
]
就个人而言，我会将生成新头寸的整个业务转移到 Node class:
上的单独方法
def possible_moves(self, map):
x, y, z = self.x, self.y, self.z
for dx, dy, dz in DELTAS:
newx, newy, newz = x + dx, y + dy, z + dz
try:
if maze[newx][newy][newz] != 0:
yield Node(self, (newx, newy, newz))
except IndexError:
# not inside the maze anymore, ignore
pass
这个方法假设有一个DELTAS全局变量定义了可能的走法，并且是一个生成器；每次到达 yield 时，都会将一个新的 Node() 实例返回给任何使用它作为迭代器的实例（就像 for 循环一样）。
然后就用那个方法代替你用for new_position in ...:循环填充的children = []列表，所以直接在使用原始children列表的部分：
# Loop through children
for child in current_node.possible_moves(map):
# Child is on the closed list
for closed_child in closed_list:
if child == closed_child:
continue
# etc.
我正在尝试调整我发现的应用程序 here，我想我只需要添加一个轴。问题是脚本似乎卡住了。谁能告诉我我做错了什么以及如何将 A* 与 3d 矩阵 (i j k) 一起使用？
这是我更改的 A* 函数的一部分
for new_position in [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]: # Adjacent squares, (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares removed to ignor diagonal movement
# Get node position
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1], current_node.position[2] + new_position[2])
# 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 or node_position[2] > (len(maze) - 1) or node_position[2] < 0 or node_position[2] > (len(maze[len(maze)-1]) -1):
continue
# Make sure walkable terrain
if maze[node_position[0]][node_position[1]][node_position[2]] != 0:
continue
原来是：
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
这是我修改后的整个脚本：
import numpy as np
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 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, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]: # Adjacent squares, (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares removed to ignor diagonal movement
# Get node position
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1], current_node.position[2] + new_position[2])
# 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 or node_position[2] > (len(maze) - 1) or node_position[2] < 0 or node_position[2] > (len(maze[len(maze)-1]) -1):
continue
# Make sure walkable terrain
if maze[node_position[0]][node_position[1]][node_position[2]] != 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.position[2] - end_node.position[2]) ** 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 = np.zeros((12,12,12))
start = (10, 9, 9)
end = (1, 1, 1)
path = astar(maze, start, end)
print(path)
if __name__ == '__main__':
main()
A* 可以处理任意数量的维度；这是一种图遍历算法，无论您的问题 space 有多少维度，将一个位置连接到另一个位置仍然会生成一个图。
但是，您在生成新节点时遇到了两个问题。
您在列表中包含了
(0, 0, 0)，因此 没有变化。您不断将当前位置放回队列中以供考虑。那只是工作忙，因为当前位置已经在关闭列表中了你永远不会从你的任何坐标中减去，你只会加。因此，您的
x、y和z值只能向上 。如果达到你的目标需要一条路径绕过一个障碍，那么你就有问题了，因为你的版本所能做的就是沿着任何给定的轴在一个方向上移动。
在一个3×3×3的三维矩阵中，当前位置在中间，有3乘3乘3减1 == 26个你一步可以到达的位置。您的代码只涉及其中的 7 个，外加一个保留的代码。
如果您将 for new_position in [...] 列表中的元组提取到一个单独的变量中并添加一些换行符，然后稍微重新排列它们以根据列表中有多少 1 对它们进行分组元组，你得到以下定义。我将其重命名为 deltas，因为它不是新位置，它是相对于旧位置的 change，或 delta。我重新排列了您的元组，以便更轻松地对它们进行逻辑分组：
deltas = [
(0, 0, 0), # no change,
(0, 0, 1), (0, 1, 0), (1, 0, 0), # add to a single axis
(0, 1, 1), (1, 0, 1), (1, 1, 0), # add to two axes
(1, 1, 1) # move in all 3 directions at once.
]
for delta in deltas:
# ...
您想删除第一个 ((0, 0, 0))，并且您需要添加其他变体的 -1 个版本。您需要 26 个不同的元组，但是手写这些元组会很麻烦，而且速度非常快。您可以使用 itertools.product() 来生成这些，而不是：
from itertools import product
# combinations of -1, 0 and 1, filtering out the (0, 0, 0) case:
deltas = [d for d in product((-1, 0, 1), repeat=3) if any(d)]
现在，您在循环旁边的评论是：
# Adjacent squares removed to ignor diagonal movement
不完全清楚你的意思，因为你的原始增量列表包括对角线（(0, 1, 1) 在 y 和 z 方向上移动，并且你有元组结合 x 加 y 和 x 加 z 轴的移动），甚至是通过递增所有 3 个轴来移动对角线的移动。如果你只想移动上、下、左、右, forward, and backward, 你想一次限制在一个轴上移动, deltas 应该是:
# movement without diagonals
deltas = [
(1, 0, 0), (-1, 0, 0), # only x
(0, 1, 0), (0, -1, 0), # only y
(0, 0, 1), (0, 0, -1), # only z
]
就个人而言，我会将生成新头寸的整个业务转移到 Node class:
def possible_moves(self, map):
x, y, z = self.x, self.y, self.z
for dx, dy, dz in DELTAS:
newx, newy, newz = x + dx, y + dy, z + dz
try:
if maze[newx][newy][newz] != 0:
yield Node(self, (newx, newy, newz))
except IndexError:
# not inside the maze anymore, ignore
pass
这个方法假设有一个DELTAS全局变量定义了可能的走法，并且是一个生成器；每次到达 yield 时，都会将一个新的 Node() 实例返回给任何使用它作为迭代器的实例（就像 for 循环一样）。
然后就用那个方法代替你用for new_position in ...:循环填充的children = []列表，所以直接在使用原始children列表的部分：
# Loop through children
for child in current_node.possible_moves(map):
# Child is on the closed list
for closed_child in closed_list:
if child == closed_child:
continue
# etc.