How to structure an adjacency list for this A* program

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.

Here is where I get stuck:

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

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?

Solution

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)

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:

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.

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

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])

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)