Shortest Path Planning using wavefront Propagation

This algorithm is guaranteed to find the shortest path

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

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;
    }
};

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