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]?

Cantrell

Here's an excellent visual demonstration of the algorithm (and a comparison with other search algorithms). There's also source code available. – Tourist

Answer 1

Short answer: Yes

Explanation:

That pseudocode 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 write the condition for termination yourself.

Fairman

The posted algorithm is more properly described as a breadth first traversal of the tree, as there's no comparison/test being done and the shortest path so far is not tracked. The algorithm won't terminate early if the search objective is found, so the entire tree is traversed. When applying this to a 2D maze, keep in mind that "visiting" a node should mark it and then you need to check if nodes have been marked before enqueing them to avoid looping forever (unless you define an order, in which case only enqueue in one direction) – Sitzmark

Answer 2

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

    }

}

Limen

What are 5 and 9? – Amplexicaul