2

我试图了解 A* 寻路算法，以及如何在 python 程序中实现它。我发现这个网站很好地解释了算法本身的工作原理，并提供了一些示例代码。

这是我卡住的地方：

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

我不明白“ mapinfo ”对象的外观。我通过用一些数字替换 mapinfo 变量来管理程序的工作，但无法弄清楚整个列表将如何工作，特别是如果我们想要包括墙壁。你能提供一些澄清/例子吗？

4

1 回答 1

2

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

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

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

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

我能想到的两个选择是：

  • 更改语句make_graph()以通过键而不是属性访问字典元素，方法是将 all 更改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)
于 2013-01-18T01:56:23.010 回答