Wake up to reality

Saptarshi Dey — Tue, 09 May 2023 16:55:26 +0000

Shortest Path Planning using wavefront Propagation

Saptarshi Dey — Sat, 31 Dec 2022 17:00:11 +0000

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

DEV Community: Saptarshi Dey

Wake up to reality

Shortest Path Planning using wavefront Propagation