This lesson's interactive features are locked, please to keep using them

A* Code

A* search is very similar to Dijkstra's algorithm, except we add in a heuristic based on Manhattan distance, a.k.a. "taxicab distance." Our implementation of A* will, however, look quite a bit different from the Dijkstra's algorithm we wrote because we'll be using a priority queue this time.

Let's build our most effective route detection algorithm yet for Mappy! We'll be using the A* algorithm to efficiently find the shortest path through the grid, taking into account traffic jams.

Assignment

Complete heuristic(next: "Tile", dest: "Tile") -> int.

next and dest are Tile objects. Our heuristic will be the distance between the node we're considering moving to (next) and the destination. Return the result of the distance formula:
```
abs(next.x - dest.x) + abs(next.y - dest.y)
```
You'll notice the type hints use quotes around class names like "Tile" and "TrafficGrid". These are forward references – they let us reference classes that are defined later in the file.
Complete a_star_search(traffic_grid: "TrafficGrid", src: "Tile", dest: "Tile") -> list["Tile"].
1. Set up a PriorityQueue, and push the src tile onto it with a priority of 0.
2. Create a dictionary mapping Tiles to their predecessors, starting with src: None. (Keep in mind, we can use Tile objects as keys in sets and dictionaries because we provided a __hash__ method.)
3. Create a dictionary mapping Tiles to their lowest known costs from src, starting with src: 0.
4. To finish the initial setup, create a visited set to keep track of visited Tiles.
5. While the queue is not empty:
  1. Pop the next Tile off the queue, i.e., the lowest-cost tile to move to. If it's the destination, exit the loop.
  2. If this tile has already been visited, continue to the next loop iteration. Otherwise, add it to visited.
  3. For each of this tile's neighbors:
    1. Calculate the total cost to the neighbor by adding the value in the costs dictionary for the current Tile to the neighbor's cost().
    2. If the neighbor isn't yet in the costs dictionary, or if its new total cost is less than its previously known cost:
      1. Set the known cost for the neighbor to the newly calculated total cost.
      2. Calculate the priority of the neighbor by adding the total cost to its heuristic(), and push it onto the priority queue accordingly.
      3. Add the neighbor to the predecessors dictionary, pointing to the current Tile.
6. When the while loop exits, we will have found the best path; we need to extract that path from the predecessors dictionary. Create an empty list called path.
7. Create a variable called pred, initialized to dest. While pred is not None:
  1. Append pred to the path, and update pred to its predecessor.
8. Reverse the path and return it.