Alex Rivera | Logout

Breadth-first search on an 8x8 grid in Java

Asked 2012-04-11T02:58:32.287
11

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'){
java breadth-first-search maze
Edit
Report

1 Answer

16

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 yo

answered 2012-04-11T03:24:52.573

Your Answer