I think my BFS adds all valid coordinates to list, not just shortest path

Question

So I'm working on a BFS algorithm to find the shortest path in a 2d binary maze and print the path in the form of coordinates. The code is running, but there must be some mistakes somewhere.

Basically the maze coordinates have either true or false values (where walls are false). The coordinates in the maze are given in the form of a custom class called Pos.

My goal is to find the path, add the points in a list (in form of Pos) and return the array list ArrayList<Pos> path

Here's what I got so far:

import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Queue;

class Node {
    int x;
    int y;
    int d;

    Node(int x, int y, int d) {
        this.x = x;
        this.y = y;
        this.d = d;
    }
};

public class Problem3{

    private static final int r[] = {-1, 0, 0, 1};
    private static final int c[] = {0, -1, 1, 0};

    public static ArrayList<Pos> findPath(Pos start, Pos end, boolean maze[][]){
        ArrayList<Pos> path = new ArrayList<Pos>();
        path.add(start);

        // Get the x and y values from both start and end Pos
        // currX and currY is initially start Pos
        int currX = start.x;
        int currY = start.y;
        int endX = end.x;
        int endY = end.y;

        // Set to size of maze
        boolean[][] visited = new boolean[6][6];

        Queue<Node> q = new ArrayDeque<>();

        visited[currX][currY] = true;
        q.add(new Node(currX, currY, 0));

        int min_d = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
        // Pop front node and process
            Node node = q.poll();

            currX = node.x;
            currY = node.y;
            int d = node.d;

            // If end is found, stop
            if (currX == endX && currY == endY)
            {   

                path.add(end);
                min_d = d;
                break;
            }

            // check all 4 directions from curr cell
            for (int k = 0; k < 4; k++)
            {
                if (isValid(maze, visited, currX + r[k], currY + c[k]))
                {
                    // mark as visited and add to path
                    visited[currX + r[k]][currY + c[k]] = true;
                    q.add(new Node(currX + r[k], currY + c[k], d + 1));
                    path.add(new Pos(currX, currY));
                }
            }
        }

        // If path is empty, return null. Else return path
        if (path.isEmpty()) {
            return null;
        }
        else {
            return path;
        }

    }


        // Checks if cell is traversable or visited
    private static boolean isValid(boolean maze[][], boolean visited[][], int r, int c) {
        return maze[r][c] && !visited[r][c];
    }   

}

The code is run in another class that reads the maze from an .in file and then runs my algorithm on said maze. If an ArrayList<Pos> pathis returned it will print each element. If not it just prints "Not solvable". Lets say I have the file test.in and run java driver < test.in:

6 6
######
#A...#
#.##.#
#.##.#
#.B..#
######

I want the output to be:

[1,1]
[2,1]
[3,1]
[4,1]
[4,2]

But this is what I'm getting:

[1,1]
[1,1]
[1,1]
[1,2]
[2,1]
[1,3]
[3,1]
[1,4]
[4,1]
[2,4]
[4,2]

By looking at the output, it seems like the algorithm finds the shortest path, but prints each coordinate twice. Additionally, x and y values flip and the start coordinate is printed 3 times. Any help with troubleshooting this is greatly appreciated.

Answer 1

Your problem is that path is never reset, only added to. You need somehow to keep track of the previous position of a Pos or the level.

Try this:

    while (!q.isEmpty()) {
    // Pop front node and process
        Node node = q.poll();

        currX = node.x;
        currY = node.y;
        int d = node.d;
        path.removeRange(d, path.size());
        path.add(new Pos(curX, curY));

        // If end is found, stop
        if (currX == endX && currY == endY)
        {   
            min_d = d;
            break;
        }

        // check all 4 directions from curr cell
        for (int k = 0; k < 4; k++)
        {
            if (isValid(maze, visited, currX + r[k], currY + c[k]))
            {
                // mark as visited and add to path
                visited[currX + r[k]][currY + c[k]] = true;
                q.add(new Node(currX + r[k], currY + c[k], d + 1));
            }
        }
    }

UPDATE:

class Node {
    int x;
    int y;
    Node prev;

    Node(int x, int y, Node prev) {
        this.x = x;
        this.y = y;
        this.prev = prev;
    }
};

...

    while (!q.isEmpty()) {
    // Pop front node and process
        Node node = q.poll();

        currX = node.x;
        currY = node.y;

        // If end is found, stop
        if (currX == endX && currY == endY)
        {   
            ArrayList<Pos> path = new ArrayList<>();
            do {
                path.add(0, new Pos(node.x,node.y));
                node = node.prev;
            } while (node != null);
            return path;
        }

        // check all 4 directions from curr cell
        for (int k = 0; k < 4; k++)
        {
            if (isValid(maze, visited, currX + r[k], currY + c[k]))
            {
                // mark as visited and add to path
                visited[currX + r[k]][currY + c[k]] = true;
                q.add(new Node(currX + r[k], currY + c[k], node));
            }
        }
    }
    return null;