Route Planning Project

---

Goals

The main goal of this project is to create a route planner that plots a path between two points on a map using real map data from the OpenStreeMap project so that street boundaries are respected. A starting code infrastructure was provided for with a map rendering example using the 2D graphics library IO2D, and also Googletest, Pugixml, cairo2, and graphicsmagick. Once the starter infrastructure was set up, the work performed to accomplish the goal was then focused extending the code to search for a path using the A* algorithm, and properly display that path on a map. Additionally, the application must pass unit tests provided by Udacity. Ultimately, a user running the application is able to input start and end point coordinates for the search.

Results

The heavy-lifting functionality of the development implements the following algorithm successfully.

A* ALGORITHM:

  Search( grid, initial_point, goal_point ) :

      * Initialize an empty list of open nodes.

      * Initialize a starting node with the following:
          * x and y values given by initial_point.
          * g = 0, where g is the cost for each move.
          * h given by the heuristic function (a function of the current
          coordinates and the goal).

      * Add the new node to the list of open nodes.

      * while the list of open nodes is not empty:
          * Sort the open list by f-value
          * Pop the optimal cell (called the current cell).
          * Mark the cell's coordinates in the grid as part of the path.

          * if the current cell is the goal cell:
              return the grid.

          * else, expand the search to the current node's neighbors.
              This includes the following steps:
                  * Check each neighbor cell in the grid to ensure that the
                  cell is empty: it hasn't been closed and is not an
                  obstacle.
                  * If the cell is empty, compute the cost (g value) and the
                  heuristic, and add to the list of open nodes.
                  * Mark the cell as closed.

      * If you exit the while loop because the list of open nodes is
      * empty, you have run out of new nodes to explore and haven't
      * found a path.

The A* search functionality then falls into the overall design as shown below:

More broadly, the association with other components that provide accessory functionality is as follows: