Python A* pathfinding, what is this line doing?

Question

I am reviewing this stack overflow post Python - Speed up an A Star Pathfinding Algorithm

I am trying to determine what the line for tile in graph[current]: represents. Namely what graph[] represents. I feel like graph should represent the entire grid, but I second guess this because we are giving current as argument to the [] operator on graph, so it has to be returning something, but im not sure what it should be. Maybe the tiles that we can travel to that are directly adjacent to current?

Also what does this syntax mean current = heapq.heappop(openHeap)[1]?

import heapq

def aStar(self, graph, current, end):
  openSet = set()
  openHeap = []
  closedSet = set()

  def retracePath(c):
    path = [c]
    while c.parent is not None:
        c = c.parent
        path.append(c)
    path.reverse()
    return path

  openSet.add(current)
  openHeap.append((0,current))
  while openSet:
      current = heapq.heappop(openHeap)[1]
      if current == end:
          return retracePath(current)
      openSet.remove(current)
      closedSet.add(current)
      for tile in graph[current]:
         if tile not in closedSet:
             tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
             if tile not in openSet:
                 openSet.add(tile)
                 heapq.heappush(openHeap, (tile.H,tile))
             tile.parent = current
  return []

score 0 · Accepted Answer · answered Sep 29 '13 at 17:56

I believe the graph variable is a dict of some sort where the key is the current tile, and the value is a list of all the valid neighboring tiles. That way, every node in the graph is easily accessible via simple dict lookup.

The pseudocode on Wikipedia the author linked to in the original post supports this hypothesis -- the functionally equivalent line is listed as for each neighbor in neighbor_nodes(current)

What the line current = heapq.heappop(openHeap)[1] is doing is returning the literal tile object. If you observe the lines openHeap.append((0,current)) and heapq.heappush(openHeap, (tile.H,tile)), you can observe that the author is adding a tuple of two elements to openHeap where the first element is the heuristic, and the second element is the literal tile object.

Therefore, the line current = heapq.heappop(openHeap)[1] is identical to writing:

temp = heapq.heappop(openHeap)
current = temp[1]

...or to writting:

h, current = heapq.heappop(openHeap)

What the heaqpq.heappop() function itself is doing is returning the smallest element in the heap. Presumably, it's using the first element in the tuple to index, and so will return the open tile with the smallest heuristic as a cheap O(1) operation.

Python A* pathfinding, what is this line doing?

1 Answers1