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

Solution 1:

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.

  classMapInfo(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): continueif 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 needsmapinfo = MapInfo(width=8, height=8, impassable=impassable)