如何为这个 A* 程序构建一个邻接表 [英] How to structure an adjacency list for this A* program

问题描述

我正在尝试了解 A* 寻路算法，以及如何在 Python 程序中实现它.我发现 这个网站 做得很好解释算法本身如何工作的工作，以及提供一些示例代码.

I'm trying to understand the A* path finding algorithm, and how to implement it in a python program. I found this website which does a pretty good job explaining how the algorithm itself works, as well as providing some example code.

这里是我卡住的地方:

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 变量来使程序工作，但无法弄清楚整个列表将如何工作，特别是如果我们想要包括墙壁.您能提供一些说明/示例吗?

I don't understand how the "mapinfo" object is supposed to look. I manage to the the program working by replacing the mapinfo variables with some numbers, but can't figure out how an entire list would work, especially if we want walls included. Can you provide some clarification / examples?

推荐答案

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

The mapinfo object (as presented in the code given) is a dictionary argument passed into the make_graph() function and is being used to store the dimensions (width and height) of the grid to be searched.

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

You could define it before the function call and then pass it to the function like:

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

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

The problem is that the make_graph() function tries to access the width and height values in mapinfo directly (such as by mapinfo.height), which results in an exception AttributeError: 'dict' object has no attribute 'height'.

我能想到的两个选项是:

Two options I can think of are:

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

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

• Change the statements in make_graph() to access the dictionary elements by key instead of by attribute by changing all mapinfo.height to mapinfo['height'] and similarly for the width), or

• Create a MapInfo class with the attributes you need, and pass an instance of it to the make_graph() function instead of a dictionary.

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)

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

You'll have to do more if you want to include impassable terrain, such as walls.

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

Perhaps extend the MapInfo class by giving it another attribute:

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() 函数，以便仅在目标区域不可通行的情况下在两个网格空间之间添加边.

Next you would need to modify the make_graph() function to only add edges between two grid spaces if the target area is not impassable.

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 实例定义，并添加不可通过的区域:

You would then modify your mapinfo instance definition as necessary with the additional impassable areas:

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

这篇关于如何为这个 A* 程序构建一个邻接表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！