DEV Community

Cover image for Shortest Path Planning using wavefront Propagation
Saptarshi Dey
Saptarshi Dey

Posted on

Shortest Path Planning using wavefront Propagation

This algorithm is guaranteed to find the shortest path

Demonstration

The basic idea is to explore all possible neighboring cells and calculating the minimum cost (represented by their d-value) of getting to that cell.
If the d-value of a cell is -1, that means it's a obstruction

Updating d-values

This is the class that handles most of the computing

// Wrapper class for tuple
class tuple implements Comparable<tuple>{
    public int x,y,d;
    tuple(int a,int b,int c){
        x = a; y = b; d = c;
    }
    @Override
    int compareTo(tuple other) {
      return this.d - other.d;
    }
};
Enter fullscreen mode Exit fullscreen mode

The d-values are computed by the updateAllDvalues() function and the shortest path is computed by the drawRetracePath() function.

Source Code
If you like this short project, consider following me on GitHub

Top comments (0)