DARTMOUTH.MAPS

GOAL: Find the shortest route between 2 locations at Dartmouth
SYNPOSIS: Individual project | Winter 2018 | Python
KEY SKILLS: Objects | Graphs, Dictionaries | BFS | Parsing data files | Responding to mouse input
VIDEO OF PROGRAM IN ACTION

Mouse is highlighted in cyan for clarity. In the video, I was clicking to set a start point & hovering to set a final destination.

Key Process:

  1. I was given a text file with the (x, y) value of all Dartmouth locations, and the adjacent places to each location
  2. Created a Vertex object with instance variables: vertex_name, x_location y_location, list_of_adjacent_locations
  3. Parsed the text file for these instance variable values. Created a dictionary where key = location, value = vertex
  4. Loaded an image of Dartmouth’s map (given)
  5. By looping through all keys in the dictionary, I graphed circles at the (x,y) value of each location & lines from the current location’s (x,y) value to the (x,y) value of all adjacent locations.
  6. Created a mouse response system with booleans. Made any location the user clicks the “start” point. If a start point has already been selected, made any location the user hovers over the “goal” point.
  7. Made the start location’s circle red.
  8. Ran a breadth first search between the start and goal vertices. In the BFS, created a dictionary to track what node preceeds each in the BFS. Once a path is found, backchained the dictionary to return a list of location names representing the shortest path between the start and goal locations.
  9. Made the circles and lines along the shortest path red.