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:
I was given a text file with the (x, y) value of all Dartmouth locations, and the adjacent places to each location
Created a Vertex object with instance variables: vertex_name, x_location y_location, list_of_adjacent_locations
Parsed the text file for these instance variable values. Created a dictionary where key = location, value = vertex
Loaded an image of Dartmouth’s map (given)
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.
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.
Made the start location’s circle red.
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.
Made the circles and lines along the shortest path red.