Shortest path on a real-world 3D map

This project finds the shortest path between the start and end points on a 3D terrain considering the changes due to different seasons.

The map I've chosen is of the Mendon Ponds Park of Rochester, NY.

Satellite Image	Elevation Image

As we can see, it has a different elevation. It has deep ponds and small hills.

The elevations dataset is gathered from National Elevation Dataset.

Rochester has four seasons:

• Summer, which is when these images were taken.
• Fall, the land near any tree is cover with leaves.
• Winter can get harsh, and most of the water bodies freeze.
• Spring, where the snow begins to melt, and it gets muddy.

Considering these scenarios, the map changes.

The park has various terrains; from open lands, rough meadows, forests, impassable vegetation, lake, paved roads. The movement speed will be different for different terrain. To make things easier, these different terrains are portrayed with colors on a map.

Table	Summer (Base map)

This 395x500 map will be used to consider the various terrains. The text file mpp.txt is used for the elevation.

The interpixel distance to real world distance is 10.29 m in X-axis & 7.55 m in Y-axis.

The code takes input as

$python3 path_finder.py terrain.png elevations.txt check_points.txt season_name output_image_file_name

• terrain.png is the color-coded image for representing different vegetations.
• elevations.txt contains the elevation of each point corresponding to the pixel in the map
• check_points.txt contains the start point, all/no check points, end point.
• season_name can either be Winter, summer, fall, or spring.
• output_image_file_name is the name of the output image to be generated.

The seasons change the map in the following way:

• In winter, a 7-pixel wide ice layer is formed on the water where the water meets land.

• In Spring, all points within a 15-pixel radius of a waterbody and with less than 1-meter elevation from the neighboring waterbody is covered in mud due to all the ice/snow melting from the winter season.

Spring	Winter

• In Fall, the movement speed along the paths near the forested areas is decreased as the leaves have covered all the visible paths. The base map is the summer season.

How the algorithm works:

Let's assume only a start and end point coordinate.

Our goal is to reach the end point in least amount of time.

In this case, [230, 327] is the start point (big green point) & [350, 139] is the end point (big red point). To see how the algorithm chooses this path:

- All the neighboring points to the start point are considered.

- Now, we have 8 coordinates with their respective elevations.

- As we already know the location of the end point, we can calculate a heuristic cost based on that.

Heuristic cost (h): The direct distance between the selected point and the destination point assuming a level and direct paved path between them. We need this cost to basically guide the algorithm in the right direction. We need the distance in 2D space and the maximum speed that is achievable on this map, hence we use those parameters to calculate the time required to go from A to B.

Path cost (g): We use the 3D distance, this time we need the actual time required to go from A to B considering the difference in elevations and terrains, the final time taken changes drastically. Distance (D) = Speed = [(speed)A + (speed)B]/2 Hence, we get the path cost (g) and heuristic cost (h).

- Now, we have a bunch of points in a queue with their respective function costs (f).

- The point at the top of the queue will the point with the lowest function cost. We select that point and then considers its neighbors. This way we always consider the points with the best chance of being considered in the best path first.

- This procedure is continued until we've reached the final point.

Actual Map with only the path marked	Red area shows the points the algorithm considered

The algorithm does a basic best-first search; always considers the coordinates with the lowest cost (f = g + h). By doing an informed heuristic search like A* the answer might not be the best possible result, but it provides a good-enough result in the shortest time possible by traversing the least possible nodes/coordinates. As we can see, the heuristic function chosen does it's job by guiding the algorithm in the correct direction. The distance travelled was 2200 m. It's the best path considering the distance travelled and the time taken to reach there.

This is a sample output

$python3 path_find.py terrain.png elevations.txt check_points.txt season_name output_image_file_name

When using multiple checkpoints between start and end, the total distance covered, and path is displayed. The coordinates from the text-file (check_points.txt) are:

Points to be traversed	Map

Here, the path between the individual check points is highlighted in light-pink and points are black dots.