我正在编写一个简单的A *算法来寻找最短路径。但我需要更复杂的东西。代理人只能前进并旋转(90度)。它会影响路径还是我可以使用简单的A *?谢谢大家。
def astar(maze, start, end):
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
open_list = []
closed_list = []
open_list.append(start_node)
while len(open_list) > 0:
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
open_list.pop(current_index)
closed_list.append(current_node)
if current_node == end_node:
path = []
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
return path[::-1]
children = []
for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
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
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:
for closed_child in closed_list:
if child == closed_child:
continue
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
for open_node in open_list:
if child == open_node and child.g > open_node.g:
continue
open_list.append(child)
这里的主要问题是需要让A *算法意识到“面向方向d1的位置(x,y)”和面向方向的位置(x,y)之间存在差异这一事实D2“。如果算法不知道这一点,它就无法回复你要遵循的最佳指令系列。
您可以解决这个问题的一种方法是想象您的世界不是2D网格,而是实际上是一个3D空间,其中包含四个堆叠在一起的2D网格副本。就像您在2D空间中的位置由当前(x,y)坐标组成一样,您在3D空间中的位置由您当前的(x,y)坐标组成,并与您所面对的方向相结合。
想象一下在这个空间里走动意味着什么。您可以采取两种方式进行操作 - “移动”或“转90°”“移动”操作会使您在当前的2D切片中向前移动一步,其中“前进”具有不同的含义在你所在的切片上。换句话说,“移动”将使你纯粹在X / Y平面内移动,保持你的方向固定。 “转弯”操作将使您的X / Y位置保持固定,但会改变您所在的平面(根据您当时正面临的方向)。
如果您将此信息明确地编码到搜索中,那么A *可以使用它来找到您最佳路径。您需要定义一些估计目标距离的新启发式算法。一种选择是假设没有墙壁,并确定你需要采取多少步骤,加上所需的旋转次数,以达到目标。此时,A *可以为您提供最佳路径,使用您的启发式方法来指导其搜索。
更一般地,“我在世界上有一个位置,加上一些额外的状态(方向,速度等)”形式的许多问题可以从2D空间中的寻路转换为3D空间中的寻路,其中你的第三个维度将是额外的信息。或者如果您有多个额外的信息,它可能会达到4D或5D空间。
希望这可以帮助!
首先要做的是将源代码分为两个函数:代理的正向模型和(路径)规划算法本身。在前向模型中,指定了代理有三种可能的动作(前进,左转,旋转)。 A *规划器为代理创建游戏树。可能的顺序是:左,前,前。
这不是经典的路径规划问题,而是人工智能规划问题。实现这样的双层系统比通常的A *寻路算法更复杂,因为旋转动作不会使代理更接近目标。如果模拟动作改善了情况或者向后退了一步,则决定更复杂。
在现实生活场景中,即使所描述的前向模型和规划器的分离也无法解决问题,因为地图中的状态空间会非常快速地增长。需要额外的启发式方法来指导A *规划者进入最佳方向。