Inconsistent results in BFS in Java

Question

This code works fine when the first creation of a new maze object. However when the BFS is complete and the game is played again( by giving the user the option to play again) the algorithm does not work as effectively. The end goal is still met however x and y coordinates are added to the array that are not part of the shortest path. I have never seen my first run ever complete the search incorrectly, however subsequent instances do. It seems as if every time the new maze object is created the maze is left affected by the previous instance. Any input?

public class Maze {

    public static List<Integer> fx;
    public static List<Integer> fy;
    public static int listSize;
    public static Point p;

    public Maze(int x, int y) {

        p = getPathBFS(x, y);
        fx = new ArrayList<>();
        fy = new ArrayList<>();
        addPoint();

        System.out.print("next");
    }

    private static class Point {
        int x;
        int y;
        Point parent;

        public Point(int x, int y, Point parent) {
            this.x = x;
            this.y = y;
            this.parent = parent;
        }

        public Point getParent() {
            return this.parent;
        }
    }

    public static Queue<Point> q = new LinkedList<>();

    public static Point getPathBFS(int x, int y) {

        q.add(new Point(x, y, null));

        while (!q.isEmpty()) {
            Point p = q.remove();

            if (Level.cells[p.x][p.y] == 9) {
                return p;
            }

            if (isFree(p.x + 1, p.y)) {
                Level.cells[p.x][p.y] = 2;
                Point nextP = new Point(p.x + 1, p.y, p);
                q.add(nextP);
            }

            if (isFree(p.x - 1, p.y)) {
                Level.cells[p.x][p.y] = 2;
                Point nextP = new Point(p.x - 1, p.y, p);
                q.add(nextP);
            }

            if (isFree(p.x, p.y + 1)) {
                Level.cells[p.x][p.y] = 2;
                Point nextP = new Point(p.x, p.y + 1, p);
                q.add(nextP);
            }

            if (isFree(p.x, p.y - 1)) {
                Level.cells[p.x][p.y] = 2;
                Point nextP = new Point(p.x, p.y - 1, p);
                q.add(nextP);
            }    
        }
        return null;
    }

    public static boolean isFree(int x, int y) {
        if ((x >= 0 && x < Level.cells.length) && (y >= 0 && y < Level.cells[x].length) && (Level.cells[x][y] == 0 || Level.cells[x][y] == 9)) {
            return true;
        }
        return false;
    }

    public static void addPoint() {

        while ((p != null)) {

            System.out.println("x is " + p.x + " - y is " + p.y);

            fy.add(p.x);
            fx.add(p.y);
            p = p.getParent();
        }

    }

    public static int getListSize() {
        listSize = fx.size();

        return listSize;
    }
}

score 1 · Answer 1 · answered Jun 07 '18 at 14:05

It seems as if every time the new maze object is created the maze is left affected by the previous instance

Yes, exactly. All of your fields are declared as static. Static fields are common across all instances, not just one. You can remove the static keyword in all (or almost all) instances.

public static List<Integer> fx;
public static List<Integer> fy;
public static int listSize;
public static Point p;

It looks like your Level class is suffering from the same problems:

Level.cells.length

I'd look into what 'static' actually means because it seems like you're using it without really understanding it.

Inconsistent results in BFS in Java

1 Answers1