Pathfinding algorithm for cheapest path in 2d matrix maze

Question

I have to find the path with the minimum cost of a matrix and implement the solution in Java. I'm not sure which algorithm is the best to solve this problem.

I have a MxN matrix that can contain a 0, 1, 2, 3 or 4 in every cell as the input, as well as a start position and a destination (for example: start position (0, 0) and destination (5, 7)).

The 0 means that the cost to get through that cell is 1.

The 1 means that the cost to get through that cell is 2.

The 2 means that the cost to get through that cell is 3.

The 3 means that the cost to get through that cell is 4.

The 4 means there is a wall, so you cannot go through it.

You can move up, down, left, right and vertically in any direction (but if you move vertically, the cost to get through any cell is doubled).

Is BFS a good algorithm or it works best with binary mazes?

I suspect that the reason that your teacher set you this exercise is that he or she wants >>you<< to figure out a good algorithm. (My guess would be that simple BFS won't work, and that you should look at something like alpha-beta pruning.) — Stephen C, Jun 24 '19 at 03:25
Possible duplicate of [Cheapest path algorithm](https://stackoverflow.com/questions/2207987/cheapest-path-algorithm) — tkruse, Jun 24 '19 at 04:22
See [this](https://stackoverflow.com/a/54148140/3992939) example — c0der, Jun 24 '19 at 09:04
Possible duplicate of [Calculating distance between non directly-connected nodes in matrix](https://stackoverflow.com/questions/54126099/calculating-distance-between-non-directly-connected-nodes-in-matrix) — c0der, Jun 24 '19 at 09:05
Check my solution to a similar question: https://stackoverflow.com/questions/37466738/pathfinding-on-large-map/37815362#37815362 — Felipe Sulser, Jun 24 '19 at 09:05

Thomas GM · Accepted Answer · 2019-06-25T01:40:30.623

Thanks for the advice! I could solve it (or at least it's working for me) using the following code:

public class Pathfinder {
private static final int M = 5;
private static final int N = 5;
private static final int fila[] = {-1, 0, 0, 1, -1, -1, 1, 1};
private static final int columna[] = {0, -1, 1, 0, -1, 1, -1, 1};
private static boolean esValido(int matriz[][], boolean visitado[][], int fil, int col, int k) {
    if(k < 4)
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col]);
    else if (k == 4)
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col] && esValido(matriz, visitado, fil, col + 1, 0) && esValido(matriz, visitado, fil + 1, col, 0));
    else if (k == 5)
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col] && esValido(matriz, visitado, fil, col - 1, 0) && esValido(matriz, visitado, fil + 1, col, 0));
    else if (k == 6)
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col] && esValido(matriz, visitado, fil, col + 1, 0) && esValido(matriz, visitado, fil - 1, col, 0));
    else
        return ((fil >= 0) && (fil < M) && (col >= 0) && (col < N) && matriz[fil][col] < 4 && !visitado[fil][col] && esValido(matriz, visitado, fil, col - 1, 0) && esValido(matriz, visitado, fil - 1, col, 0));
}
private static int absoluto (int n) {
    return n > 0 ? n : -n;
}

public static void BFS(int matriz[][], int i, int j, int x, int y) {
    boolean [][] visitado = new boolean [M][N];
    PriorityQueue<Nodo> cola = new PriorityQueue<Nodo>();
    visitado[i][j] = true;
    cola.add(new Nodo(i, j, 0, absoluto(x - i) + absoluto(y - j)));
    int mincost = Integer.MAX_VALUE;
    int cost, aux;
    while(!cola.isEmpty()) {
        Nodo nodo = cola.poll();
        i = nodo.x;
        j = nodo.y;
        cost = nodo.cost;
        if(i == x && j == y) {
            mincost = cost;
            break;
        }
        for(int k = 0; k < 8; k++) {
            aux = 0;
            if(esValido(matriz, visitado, i + fila[k], j + columna[k], k)) {
                if(k < 4)
                    aux = 1;
                else
                    aux = 2;
                visitado[i + fila[k]][j + columna[k]] = true;
                switch(matriz[i + fila[k]][j + columna[k]]) {
                case 0:
                    cola.add(new Nodo(i + fila[k], j + columna[k], cost + aux, absoluto(x - i + fila[k]) + absoluto(y - j + columna[k])));
                case 1:
                    cola.add(new Nodo(i + fila[k], j + columna[k], cost + aux*2, absoluto(x - i + fila[k]) + absoluto(y - j + columna[k])));
                case 2:
                    cola.add(new Nodo(i + fila[k], j + columna[k], cost + aux*3, absoluto(x - i + fila[k]) + absoluto(y - j + columna[k])));
                case 3:
                    cola.add(new Nodo(i + fila[k], j + columna[k], cost + aux*4, absoluto(x - i + fila[k]) + absoluto(y - j + columna[k])));
                }   
            }
        }
    }

    if(mincost != Integer.MAX_VALUE)
        System.out.print("The path of minimum cost to the destination is " + mincost + ".");
    else
        System.out.print("Destination cannot be reached.");
}
}

The node structure I used is the following:

public class Nodo implements Comparable<Nodo> {
public int x, y, cost, dist, total;
public Nodo(int x, int y, int cost, int dist){
    this.x = x;
    this.y = y;
    this.cost = cost;
    this.dist = dist;
    this.total = this.cost + this.dist;
}
public int compareTo(Nodo n) {
    if(this.total < n.total)
        return -1;
    else if(this.total > n.total)
        return 1;
    else
        return 0;
}
}

Pathfinding algorithm for cheapest path in 2d matrix maze

1 Answers1