Maze solving with breadth first search

Question

Can someone please explain how could I solve a maze using breadth first search? I need to use breadth first search to find shortest path through a maze, but I am so confused.

This is the pseudo code from my book:

void breadth_first_search(tree T) {
  queue!;
  node u, v;

  initialize(Q);
  v = root of T;
  visit v;
  enqueue(Q, v);

  while (!empty(Q)) {
    dequeue(Q, v);
    for (each child u of v) {
      visit u;
      enqueue(Q, u);
    }
  }
}

So if I have a maze that is stored in a 2D matrix, is the "root" (i.e. the starting point), going to be in maze[x][y]?

Answer 1

Here's a full BFS Maze solver. It returns a full shortest path to the end point if found. In the maze array arr: 0 denotes unexplored spaces, 5 is a wall space, and 9 is the goal space. Spaces are marked with a -1 after they have been visited.

import java.util.*;

public class Maze {

  public static int[][] arr = new int[][] {
            {0,0,0,0,0,0,0,0,0},
            {5,5,5,0,0,0,0,0,0},
            {0,0,0,5,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,9},
    };

  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 String toString() {
            return "x = " + x + " y = " + y;
        }
  }

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

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

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

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

            if (arr[p.x][p.y] == 9) {
                System.out.println("Exit is reached!");
                return p;
            }

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

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

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

             if(isFree(p.x,p.y-1)) {
                arr[p.x][p.y] = -1;
                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 < arr.length) && (y >= 0 && y < arr[x].length) && (arr[x][y] == 0 || arr[x][y] == 9)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {

        Point p = getPathBFS(0,0);

         for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }

        while(p.getParent() != null) {
            System.out.println(p);
            p = p.getParent();
        }

    }

}

Answer 2

Short answer: yes

Explanation:

That pseudo code is representing the path through the maze as a path to the leaf of a tree. Each spot in the maze is a node on the tree and each new spot you can go to from there is a child of that node.

In order to do breadth first search, an algorithm first has to consider all paths through the tree of length one, then length two, etc. until it reaches the end, which will cause the algorithm to stop since the end has no children, resulting in an empty queue.

The code keeps track of the nodes it needs to visit by using a queue (Q). It first sets the start of the maze to the root of the tree, visits it (checks if it is the end), then removes the root from the queue and repeats the process with each child. In this way, it visits the nodes in post-order i.e. root, (each child of root), (each child of first child), (each child of second child), etc. until it gets to the end.

edit: As it stands, the algorithm may not terminate when it reaches the end because of other nodes after it in the queue. You will have to wright the condition for termination yourself.