如何为该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

我不明白" mapinfo "对象的外观.我通过用一些数字替换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()函数的字典参数，用于存储尺寸(宽度和高度).

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:

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

• 使用所需的属性创建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屋！