Breadth-first search on an 8x8 grid in Java

Question

What I'm trying to do is count how many moves it takes to get to the goal using the shortest path. It must be done using a breadth first search. I put the 8x8 grid into a 2d array which is filled with one of four chars, E for empty (can move into these spots), B for blocked (can't move here), R for robot (starting point), or G for goal. The algorithm had to check for movable spaces in the order up, left, right, then down, which I believe I've done correctly. After a node is checked it changes its contents to a 'B'. If the goal cannot be reached, 0 should be returned.

I have changed my code to implement what Kshitij told me, and it works beautifully. I was just too tired to see that I wasn't initializing my queue after every new data set lol. Thanks for the help!

public static int bfSearch(){
    Queue <int []> queue = new LinkedList <int []> ();
    int [] start = {roboty,robotx,0};
    queue.add(start);

    while (queue.peek() != null){
        int [] array = queue.remove();

            if(array[0]-1 >= 0 && grid[array[0]-1][array[1]] != 'B'){

                if (grid[array[0]-1][array[1]] == 'G'){
                    return array[2]+1; 
                }
                else{
                    grid[array[0]-1][array[1]] = 'B';
                    int [] temp = {array[0]-1, array[1], array[2]+1};
                    queue.add(temp);
                }
            }

            if(array[1]-1 >= 0 && grid[array[0]][array[1]-1] != 'B'){

                if (grid[array[0]][array[1]-1] == 'G'){
                    return array[2]+1;
                }
                else{
                    grid[array[0]][array[1]-1] = 'B';
                    int [] temp = {array[0], array[1]-1, array[2]+1};
                    queue.add(temp);
                }
            }

            if(array[1]+1 <= 7 && grid[array[0]][array[1]+1] != 'B'){

                if (grid[array[0]][array[1]+1] == 'G'){
                    return array[2]+1;
                }
                else{
                    grid[array[0]][array[1]+1] = 'B';
                    int [] temp = {array[0], array[1]+1, array[2]+1};
                    queue.add(temp);
                }
            }

            if(array[0]+1 <= 7 && grid[array[0]+1][array[1]] != 'B'){

                if (grid[array[0]+1][array[1]] == 'G'){
                    return array[2]+1;
                }
                else{
                    grid[array[0]+1][array[1]] = 'B';
                    int [] temp = {array[0]+1, array[1], array[2]+1};
                    queue.add(temp);
                }
            }
        }           
    return 0;
}

Answer 1

You'll need to store 2 things in your queue. Let's call each item in your queue a node.

1. position (which you already store)
2. count (moves needed to get to this position from the start position)

You start off by assigning the count of your start position to 0.

The way the algorithm works is:

1. you pop a node from the queue
2. you determine where you can go from the position specified by the node you just popped. That is, if you treat this as "making a tree on the fly", you're determining the children of the node you popped from the queue
3. you add these children to the queue.

In your 3rd step, when you add a node child to the queue, you'd have to determine the count that needs to be added to this node. This count is simply the count of the parent node (that you popped in step 1) + 1

Finally, your return value would be the count associated with the node that carries the destination position.

For instance, lets work with a 4x4 grid, where position [0,0] is the start, and position [0,3] is the destination.

S E E B
E B E E
B B B E
G E E E

Initially, your queue would be:

[{(0, 0), 0}]

where the value inside the () is the position, and the second value inside the {} is the count.

You pop this node from your queue, and you determine that you can get to positions (0,1) and (1,0). So you add items {(0, 1), 1} and {(1, 0), 1} to the queue. Note that the count is 1 because the count of the popped node was 0 and we incremented that by 1. Your queue now looks like:

[{(0, 1), 1},  {(1, 0), 1}]

You pop the first element, realize that it has no viable children, so you move on.

You pop the remaining element, and find out that it gives you one node you can get to, at position (2, 0). Since the node you popped has count 1, you add this new position paired with count = 1 + 1 = 2 to the queue.

Eventually, you'll pop the goal node from your queue, and it's count will be 9.

Edit

If you want to get the path from the source to the destination, the current encoding doesn't work as is. You'd need to maintain a separate 2D array of size 8x8 with the counts instead of encoding them in the node itself. And when you finally find the count for the destination, you backtrack from the destination to the source using he 2D count array. Essentially, if you can get to the destination in 9 moves, you can get to one of its adjacent positions in 8 moves. So you find the position that has count 8 and is adjacent to the destination. You iteratively repeat this until you get to the source.

The method you described, where you add an extra element to the nodes does not work. I'll leave it for you to find out why, since this is homework :)