The Three Stages of Development

• Phase 1: Proof of Concept

  This short Python script was an exploration of the process behind the GPS. The intent of the program was to understand what would be required by a program which would be made later, and be capable of route finding over larger distances.
  
  This program downloads street data via the OpenStreetMaps Overpass API, stores it within a graph data structure, then runs Djikstra's algorithm, using the geographic distance between two points as the heuristic, to find the shortest path from one node to another. The script then displays the found route on a map in an HTMl webpage.
  
  If two points are far away from one another, this program takes too long to complete, as it has to download too much data to calculate the route. To solve this problem future renditions will use a graph database to store the downloaded street data to remove the need for downloading the data every time the user searches a route.

  

• Phase 2: Graph Database

  Using a graph database to store the graph data structure allows the program to more easily find the shortest path to the destination node, for datasets with many more nodes. In the example provided, the database facilitates pathfinding between any two nodes in Massachusetts, however larger numbers of nodes are possible with longer up front import times.

  

• Phase 3: Web Client and Backend

  A web client allows the user to select coordinates on a map, and sends those coordinates to the back end which queries the database to determine the shortest route. The calculated route is returned to the web client, and the path is displayed on a map.

  

• Demos

  The user places a start and an end point on the map. When calculate route is selected, the server is queried and the shortest route is displayed

  The user can then change the starting position by selecting the "Press to Select Starting Position" button.

  The user can also change the ending position by selecting the "Press to Select Ending Position" button.