How to find path between two points on the map?

Finding path between the source and the destination on the map is the most common task for any map application. In this post, I am going to discuss how to use map data (vector data) to identify a path. This article is part of the series “How to roll out your own map sdk”. In the previous article we discuss about how to get map data (raster & Vector) and render it for map visualization. Vector data contains information about the roads. Most import of all the roads on map are represented in a form of segments. Everything on map is broken down to one unit called as “Tile”. One tile can have multiple segment of a road and one big road is constructed out of multiple segments of a road.

Each segment of a road consist of coordinates representing the points in that segment. These coordinates can be converted into a 3D or 2D space to draw a road on the map. If we remember form our last article we can draw over the map using graphics library. Depending upon how the vector data is created, we can also have additional information about roads type(primary,secondary, residential), name of the road, access restrictions( one way) etc..

Once the vector data for tiles is available we are ready to perform the path finding on the map.

There are some very popular algorithms which are used for path finding task. They are as follows

1. Dijkstra’s Shortest Path Algorithm
2. AStar
3. BFS : Breadth First Search

There is enough detail about these algorithm on internet, so lets not dwell into it. All of these algorithm does their job very well however given the complexity of the map data and rendering challenges, it becomes difficult for the map application to run such algorithm and find path.

Dijkstra’s finds all path from source to the destination and then selects the best path based on the shortest distance between the source and destination. This algorithm in “as is” format would require more “running time” since it is traversing through all possible paths so some optimization is must before this can be adopted for our mapping solution.

AStart on the other hand is highly optimized algorithm for path finding. AStart select the next node which is closer to the destination in this way we can reach the destination in optimal time. However on map there are possibilities of having points which appear closer but does not have any direct path to the destination. This problem is not address by AStar and if adopted “as is” we will often run into a situation where path searching will go around the destination point but not able to find the path or have more “running time”.

As shown in the image algorithm is trying to find out path to the destination but since there are many neighbors to a node it is kind of getting lost after some time. To avoid such problem some practical optimization are applied such as follows

1. Run path finding from source & destination
2. Combine BFS or Other traversing algorithm with AStar to reach the best next neighbor.

Once the path is identified it can be represented with line or quads and then all sort of interactive rendering can be applied.

Happy Mapping!