python - 需要更改 A* 算法，以便它可以与代理轮换一起使用

Question

我正在编写一个简单的 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)

Answer 1

这里的主要问题是 A* 算法需要意识到“位于面向方向 d₁ 的位置 (x, y)”和“位于位置 (x, y)，面向 d₂ 方向。”如果算法不知道这一点，它就无法为您提供最佳的一系列可遵循的指令。

解决此问题的一种方法是想象您的世界不是 2D 网格，而实际上是一个 3D 空间，由四个相互堆叠的 2D 网格副本组成。正如您在 2D 空间中的位置由当前 (x, y) 坐标组成一样，您在 3D 空间中的位置也由当前 (x, y) 坐标与您所面对的方向相结合组成。

想象一下在这个空间中移动意味着什么。您可以执行的操作有两个选项 - “移动”或“旋转 90°”。“移动”操作将使您在当前所在的 2D 切片中向前移动一步，其中“向前”具有不同的含义换句话说，“移动”将使您纯粹在 X/Y 平面内移动，保持方向固定。 “转动”操作将使您的 X/Y 位置保持固定，但会改变您所在的平面(基于您当时面朝的方向)。

如果您将此信息显式编码到搜索中，则 A* 可以使用它来找到您要采取的最佳路径。您需要定义一些新的启发式方法来估计距目标的距离。一种选择是假设没有墙壁，并确定需要采取多少步以及所需的旋转次数才能到达目标。那时，A* 可以为您提供最佳路径，使用您的启发式方法来指导其搜索。

更一般地说，许多“我在世界上有一个位置，加上一些额外的状态(方向、速度等)”形式的问题可以从 2D 空间中的寻路转换为 3D 空间中的寻路，其中你的第三个维度就是额外的信息。或者，如果您有多个额外的信息，它可能会上升到 4D 或 5D 空间。

希望这有帮助!