python - 如何为该 A* 程序构建邻接表

Question

我试图了解 A* 路径查找算法，以及如何在 python 程序中实现它。我发现this website它很好地解释了算法本身是如何工作的，并提供了一些示例代码。

这是我陷入困境的地方:

def make_graph(mapinfo):

nodes = [[AStarGridNode(x, y) for y in range(mapinfo.height)] for x in range(mapinfo.width)]
graph = {}
for x, y in product(range(mapinfo.width), range(mapinfo.height)):
    node = nodes[x][y]
    graph[node] = []
    for i, j in product([-1, 0, 1], [-1, 0, 1]):
        if not (0 <= x + i < mapinfo.width): continue
        if not (0 <= y + j < mapinfo.height): continue
        graph[nodes[x][y]].append(nodes[x+i][y+j])
return graph, nodes

graph, nodes = make_graph({"width": 8, "height": 8})
paths = AStarGrid(graph)
start, end = nodes[1][1], nodes[5][7]
path = paths.search(start, end)
if path is None:
    print "No path found"
else:
    print "Path found:", path

我不明白“ma​​pinfo”对象应该是什么样子。我通过用一些数字替换mapinfo变量来设法使程序工作，但无法弄清楚整个列表将如何工作，特别是如果我们想要包含墙壁的话。您能提供一些说明/示例吗？

Answer 1

mapinfo 对象(如给定代码中所示)是传递给 make_graph() 函数的字典参数，用于存储尺寸(宽度和尺寸)。待搜索网格的高度)。

您可以在函数调用之前定义它，然后将其传递给函数，例如:

mapinfo = {"width": 8, "height": 8}
graph, nodes = make_graph(mapinfo)

问题是 make_graph() 函数尝试访问 mapinfo 中的 width 和 height 值直接(例如通过mapinfo.height)，这会导致异常AttributeError: 'dict' object has no attribute 'height'。

我能想到的两个选择是:

• 更改 make_graph() 中的语句，通过将所有 mapinfo.height 更改为 mapinfo['height' 来按键而不是按属性访问字典元素] 宽度也类似)，或者

• 使用所需的属性创建一个 MapInfo 类，并将其实例而不是字典传递给 make_graph() 函数。

  class MapInfo(object):
      def __init__(self, width, height):
          self.width = width
          self.height = height
  
  # ...
  
  mapinfo = MapInfo(width=8, height=8)
  graph, nodes = make_graph(mapinfo)
  

如果您想包含不可通行的地形(例如墙壁)，您将需要做更多工作。

也许可以通过赋予另一个属性来扩展 MapInfo 类:

def __init__(self, width, height, impassable=[]):
    """Create a MapInfo object representing the search area and obstacles.

        Args:
            width: Integer representing the width of the area
            height: Integer representing the height of the area
            impassable: List of (x, y) tuples representing impassable obstacles.
    """
    self.width = width
    self.height = height
    self.impassable = impassable

接下来，您需要修改 make_graph() 函数，以便仅在目标区域不是不可通行的情况下在两个网格空间之间添加边缘。

for i, j in product([-1, 0, 1], [-1, 0, 1]):
    # Check that we are inside the grid area.
    if not (0 <= x + i < mapinfo.width): continue
    if not (0 <= y + j < mapinfo.height): continue
    # Check if the target area is impassable.
    if (x + i, y + j) in mapinfo.impassable: continue
    # All looks good. Add target space as reachable from current (x, y) space.
    graph[nodes[x][y]].append(nodes[x+i][y+j])

然后，您可以根据需要修改 mapinfo 实例定义，添加其他不可通行区域:

impassable = [(3, 3), (3, 4), (3, 5)]  # modify to your needs
mapinfo = MapInfo(width=8, height=8, impassable=impassable)