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;
}

Thao

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 :)

Oeuvre

Seems legit, thanks for the insight. I assume being able to print the viable paths would work the same way, by just adding the direction moved as a value in the queue. So that after popping (1,0) the queue would look like this: {(0,2),2,R}. In essence this should allow me to print the path once the goal is reached, correct? – Thao

@KshitijMehta what happens to the queue element {(0, 1), 1} where there is no viable childeren...when do you pop it OR it remains in the queue ? – Lordosis

Answer 2

Here's a nice short alternative to your code. Exactly the same idea but no need of the so many 'if' conditions where you check for validity of each coordinate. This all can be done in one go. Have a look.

I've commented the explanation as much as i could. It's readable even for people who don;t have the slightest idea. I happened to come across your question when i was implementing a solution for a similar(same?) problem where a guy trapped in a labyrinth had to find his way out. There were traps(B) and movable areas (E) in the grid. The goal was to reach his destination (G).

Anyways, here's the generalized code. I take in the no of rows, columns and then the complete grid. I'm only printing whether it's possible to REACH the destination or not. I leave the rest upto someone who's reading this as an exercise to make sure you've understood the code ;)

Mind the fact that the main objective of my answer is to show you that the size of your BFS function could be reduced. I'm posting my entire solution just to give the overall idea of BFS applied in a grid since i struggled while learning it. Hopefully, this will help out someone stuck in the same situation. If you want the postion or the path followed or anything, follow the instruction from the answers in this question. Do it yourself ;)

import java.util.*;

/**
 * Created by Shreyans on 4/30/2015 at 10:27 PM using IntelliJ IDEA
 */

class MAZE
{
    static int r,c,s1,s2,f1,f2;//Rows, Columns, Start Coordinates, Finish Coordinates
    static int[] dx={1,-1,0,0};//right, left, NA, NA
    static int[] dy={0,0,1,-1};//NA, NA, bottom, top
    static char[][] grid;//Main grid
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);//I suggest using faster IO if you have performance concerns. I did. Scanner is readable hence the choice
        r=sc.nextInt();
        c=sc.nextInt();
        grid=new char[r][c];
        for(int i=0;i<r;i++)
        {
            char[] s1=sc.next().toCharArray();//Reading a line of the Grid
            System.arraycopy(s1,0,grid[i],0,c);//Nice inbuilt function to copy contents of an array. Also doable manually
        }
        s1=sc.nextInt()-1;
        s2=sc.nextInt()-1;
        f1=sc.nextInt()-1;
        f2=sc.nextInt()-1;
        if(MAZEBFS())
        {
            System.out.println("PATH EXISTS");
        }
        else
        {
            System.out.println("PATH DOES NOT EXIST");
        }
    }
    private static boolean MAZEBFS()
    {
        if(s1==f1&&s2==f2)
        {
            return true;//He's already there
        }
        else
        {
            grid [f1][f2]='G';//finish
            Queue<int[]> q=new LinkedList<int[]>();
            int[]start={s1,s2};//Start Coordinates
            q.add(start);//Adding start to the queue since we're already visiting it
            grid[s1][s2]='B';
            while(q.peek()!=null)
            {
                int[]curr=q.poll();//poll or remove. Same thing
                for(int i=0;i<4;i++)//for each direction
                {
                    if((curr[0]+dx[i]>=0&&curr[0]+dx[i]<r)&&(curr[1]+dy[i]>=0&&curr[1]+dy[i]<c))
                    {
                        //Checked if x and y are correct. ALL IN 1 GO
                        int xc=curr[0]+dx[i];//Setting current x coordinate
                        int yc=curr[1]+dy[i];//Setting current y coordinate
                        if(grid[xc][yc]=='G')//Destination found
                        {
                            //System.out.println(xc+" "+yc);
                            return true;
                        }
                        else if(grid[xc][yc]=='E')//Movable. Can't return here again so setting it to 'B' now
                        {
                            //System.out.println(xc+" "+yc);
                            grid[xc][yc]='B';//now BLOCKED
                            int[]temp={xc,yc};
                            q.add(temp);//Adding current coordinates to the queue
                        }
                    }
                }
            }
            return false;//Will return false if no route possible
        }
    }
}

Code in action: http://ideone.com/jiZKzn

Any suggestions most welcome. Cheers :D

Fibster