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.