top of page

Route Planner: A* Search
 

Created a route planner that plots a path between two points on a map using real map data from the OpenStreeMap project. 

My Tasks

  • Simple A* Search in Grid

  • Overview of the OpenStreetMap Project

    • Data format

    • Element types​

  • Building and running the project​

​​

  • Testing code​​​​

​

  • The src directory

    • Code walkthroughs

​

Github Repo (See Repo on how to run it)

https://github.com/ZhouShen2489/CppND-Route-Planning-Project

Simple A* Search in Grid

In my portfolio, I demonstrated my proficiency in C++ programming by developing a basic A* search algorithm that can generate paths in a grid format.

​

To make the demonstration more visually appealing, I utilized emojis to represent various elements such as the starting point, the endpoint, the car, and the obstacles.

​

Furthermore, the algorithm can accommodate both four-direction and eight-direction movements for the car.

Eight-directional movement of a car

Four-directional movement of a car

Overview of the OpenStreetMap Project

OpenStreetMap Data

The data used for the project is in the form of an OSM XML file (.osm file).

​

Three element types in the XML map data

  • node

  • way

  • relation

The src Directory (TODOs)

openstreetmap_overall_class_structure.png

In order to generate the path connecting the start and end nodes, I successfully addressed the TODOs within the src directory. This allowed me to effectively develop the necessary code to produce the desired path.

​

Steps include:

  • CalculateHvalue function

  • AddNeighbors function

  • NextNode function

  • AStarSearch function

  • ConstrucFinalPath function

Router Planner Results

Build, Run, and Test

In my portfolio, I documented a project that involved building, running, and testing a route planner that plots a path between two points on a map. The project came equipped with CMakeLists, third-party packages, and all the necessary project prerequisites.

​

Challenges

Although the project provided many helper functions, I faced the challenge of familiarizing myself with the route model and its attributes and functions in order to write the A* search algorithm.

​

Results

Upon completion of the algorithm, A* search successfully generated a path that was often the most optimal. In most cases, the shortest path was found. However, due to the limitations of A* search, it could not always guarantee the optimal solution.

​

Route Planner in Central Park, New York

Sample from the project

Route Planner at Columbia University area, New York

bottom of page