Printing PacMan steps on maze, Breadth First Search - Java

Question

I'm trying to create some sort of PacMan simulation without ghosts, where it's represented by the matrix of 6x10. I've implemented a variation of BFS, where I'm recursively calling algorithm between two nodes being searched for, and it's giving me satisfying results. However, what I really want to do is print state of the maze after each PacMan movement, where PacMan is represented by "2", boxes by "3", walls by "1", and free way by "0". I was trying to change each node's sign to "2", for each new movement, and then change its parent node sign to "0", however that didn't work as intended, and it gave me some strange results.

I think I know where the problem is though, although I still haven't managed to solve it. So, for each explored node, I'm putting it into a list(could've done it much more efficient, this is just a first run-through), and the problem is that it won't visit already visited nodes, so it can't print every step of PacMan movement. I've tried to change node signs before they are checked if they were already explored, though it didn't work very well.

I guess this sounds fairly confusing, so I'll try to draw a few of steps of how I want it to look.

Here is a starting maze:

1 1 1 1 1 1 1 1 1 1

2 0 0 3 1 0 0 0 3 1

1 3 1 1 1 3 1 1 0 1

1 0 1 0 3 0 1 1 3 1

1 3 0 3 1 3 0 1 0 1

1 1 1 1 1 1 0 3 0 1

And this is how solution looks:

1 1 1 1 1 1 1 1 1 1

0 0 0 0 1 0 0 0 0 1

1 0 1 1 1 2 1 1 0 1

1 0 1 0 0 0 1 1 0 1

1 0 0 0 1 0 0 1 0 1

1 1 1 1 1 1 0 0 0 1

Now, I'd like it to print a new maze for each step pacman takes:

1 1 1 1 1 1 1 1 1 1///////1 1 1 1 1 1 1 1 1 1///////1 1 1 1 1 1 1 1 1 1

0 2 0 3 1 0 0 0 3 1///////0 0 2 3 1 0 0 0 3 1///////0 0 0 2 1 0 0 0 3 1

1 3 1 1 1 3 1 1 0 1///////1 3 1 1 1 3 1 1 0 1///////1 3 1 1 1 3 1 1 0 1

1 0 1 0 3 0 1 1 3 1/////// .

1 3 0 3 1 3 0 1 0 1/////// .

1 1 1 1 1 1 0 3 0 1///////

/////////

1 1 1 1 1 1 1 1 1 1

0 0 2 0 1 0 0 0 3 1

1 3 1 1 1 3 1 1 0 1

and so on, sorry for the confusing pictures, I only wrote first 3 rows .

Here is a code of a function and all of the relevant functions, and also a link to the full source code. I've also made some comments, and block-commented last thing I've tried. Any suggestion will do. Thanks.

Source code: http://www.speedyshare.com/DkXgQ/BreadthFirstSearch.rar

public static boolean breadthFirstSearch(Node root, Node[][] mazeGrid, int boxCounter) {

    root.setSign("0");
    toExplore.add(root);
    int[] x_coord = { 0, 1, 0, -1};
    int[] y_coord = {1, 0, -1, 0 };
    while(!toExplore.isEmpty()) {

        Node node = toExplore.poll();
        explored.add(node);
        //for moving!!!!!

        /*if(node.getParent() != null) {
            node.getParent().setSign("0");
        }
        node.setSign("2");*/
            for(int i = 0; i < 4; i++) {
                //new coordinates
                int x = node.getX_coord() + x_coord[i];
                int y = node.getY_coord() + y_coord[i];

                if(x >= 0 && y >=0 && x < 6 && y < 10) {
                    Node child = maze[x][y];
                    //show moving steps!!!!!

                    /*System.out.println("\nStep : \n");
                    for(int xx = 0; xx < 6; xx++) {
                        for(int j = 0; j < 10; j++) {
                            System.out.print(maze[xx][j].getSign() + " ");
                        }
                        System.out.print("\n");
                    }*/
                    //is current node explored?
                    if(!isExplored(child) && !child.getSign().equals("1")) {
                        //save parent for the shortest path between root and node being searched for
                        child.setParent(node);

                        //have we found a box?
                        if(child.getSign().equals("3")) {
                            System.out.println("Node number " + boxCounter + " has been found : " +
                                        child.getX_coord() + " , " + child.getY_coord());
                            //counter for rest of the existing boxes
                            boxCounter--;
                            Node temp = child;
                            printPath(temp);
                            //this is used for path printing between two nodes, and not from the main root and last node being found
                            temp.setParent(null);
                            //just jumping from box to box, so I can print where the last position on the maze is
                            child.setSign("2");
                            if(boxCounter != 0) {
                                //if there are more boxes on the maze, recursion
                                breadthFirstSearch(child, mazeGrid, boxCounter);
                            }
                            return true;

                        }
                        if(child.getSign().equals("0")) {
                            //new node to explore
                            toExplore.add(child);

                        }
                    }
                }
            }
    }

    System.out.println("Node not found!");
    return false;
}

public static void printPath(Node child) {
    while(child.getParent() != null) {
        path.add(0, child);
        child = child.getParent();
    }
    System.out.println("Shortest path : ");
    for(Node n: path) {
        System.out.println(n.getX_coord() + " - " + n.getY_coord());
    }
    path.clear();
}

public static boolean isExplored(Node node) {
    for(Node n : explored) {
        if(n.getX_coord() == node.getX_coord() && n.getY_coord() == node.getY_coord()) {
            return true;
        }
    }
    return false;
}

Answer 1

The problem is that, for a true BFS, you have to save the entire state of the maze for each element in the queue. That includes the entire map, the set of visited nodes, and especially the number and position of un-eaten boxes. This is because there is no concept of 'backtracking' in BFS, so you have to basically create multiple states of the maze.

The alternative is to use DFS. That way, you can update the state of the maze before each recursive call, and then revert the state before returning from the method. In that way, you can keep only one copy of the maze state. Of course, to get the shortest path in a DFS, you will have to try all possible paths, of which there may be very many. Also you have to avoid repeating loops if your maze contains looping paths.