CS 12 Assignment 2: Solving a Maze

How To Find the Shortest Path Through Any Maze

Here we will briefly discuss the concept of search, a common technique used in Computer Science in a variety of situations. We will demonstrate the concept of search with an example:

******   * - Wall
*S*  *   S - Start
*   **   D - Destination
* **D*
*    *
******

Here we have a very simple "maze". For this particularl maze, the program which moved "down" 3 spaces, "right" 4 spaces, and "up" 1 space, in that order, would solve the maze. However, there are (obviously) other mazes that can't be solved with this technique. We need to come up with something more general. Further, we want to find not just a solution for the maze, but a shortest solution for the maze. Interestingly, the "shortest" restriction makes the problem easier to think of.

In order to find a shortest path to solve the maze, we need to make sure that there are no paths shorter that reach the destination (obviously.) So we could do this by finding all the maze cells that are reachable on a length 1 path, checking to see if any of those are a solution, and then finding the cells that are reachable on a length 2 path, and so on. Lets look at what this looks like:

For our example, there is only 1 cell reachable in a single step.

******   *    - Wall
*S*  *   S    - Start
*1  **   D    - Destination
* **D*   1-9  - Path length to this point
*    *
******

This is obviously not a solution. Check the length 2 paths. Note that any length 2 path needs to have started with a length 1 path, but go one space further. Keep this in mind.

******   *    - Wall
*S*  *   S    - Start
*12 **   D    - Destination
*2**D*   1-9  - Path length to this point
*    *
******

Still no solution. Now let us check length 3 paths. These also must be an extension of the length 2 paths. In general, a length n path must build on a path of length n - 1. So to find the length n paths, since we visited the length n - 1 paths, we just have to know which open cells are adjacent to a length n - 1 path. Interesting.

******   *    - Wall
*S*  *   S    - Start
*123**   D    - Destination
*2**D*   1-9  - Path length to this point
*3   *
******

Examining the maze at this point, it seems that we can even tell how we got to our current state by backtracking. The "3" cells are all adjacent to a "2" cell, which are adjacent to the "1" cell, which is adjacent to the source. Good to know.

******   *    - Wall
*S*4 *   S    - Start
*123**   D    - Destination
*2**D*   1-9  - Path length to this point
*34  *
******

Getting closer.

******   *    - Wall
*S*45*   S    - Start
*123**   D    - Destination
*2**D*   1-9  - Path length to this point
*345 *
******

Almost there.

******   *    - Wall
*S*45*   S    - Start
*123**   D    - Destination
*2**D*   1-9  - Path length to this point
*3456*
******

Note that there is nothing for the path in the upper right corner to extend. We can ignore it now.

******   *    - Wall
*S*45*   S    - Start
*123**   D    - Destination
*2**7*   1-9  - Path length to this point
*3456*
******

Ah, we found the destination! Now we can track it back to the source. Let us clean up our current example a bit, and assume that each cell can remember which of its neighbors caused it to be visited.

D knows it was visited from the cell below it.

******   *    - Wall
*S*  *   S    - Start
*   **   D    - Destination
* **D*   X    - Path
*   X*
******

That cell knows it was visited from the cell to its left.

******   *    - Wall
*S*  *   S    - Start
*   **   D    - Destination
* **D*   X    - Path
*  XX*
******

And so on

******   *    - Wall
*S*  *   S    - Start
*X  **   D    - Destination
*X**D*   X    - Path
*XXXX*
******

Now we found the shortest path through the maze. Lets think about what it would take to automate this:

We need a way to remember which cells we have visited (the 1-9s)
We need a way to remember which cells we have not visited, but need to (the next extension of the path)
We need each cell to remember where it was visited from (the previous step on the path.)

Not a very tough set of requirements. We will introduce the concept of a "queue", where cells line up for their chance to be examined. Whenever a cell gets to the front of the queue, then we see if it is the destination, and if not we add all of it's unvisited neighbors to the queue. Lets see what the maze solver looks like with a queue. Let us use an even simpler maze, so we can see a complete example. We will start with the "Start" cell in the queue. We will number the cells starting from (0,0) in the upper left corner and increasing to the right and down. So the "Start" cell here is (1, 1). Mark it as being visited.

******   Queue: (1, 1)
*S** *
*    *
** ***
* D  *
******

Our first iteration, we get the next cell out of the queue. It is the start cell, (1, 1). This is not the destination, so we add its empty neighbors to the queue. The only neighbor it has is (1, 2). Mark it as being visited.

******   Queue: (1, 2)
*S** *
*v   *
** ***
* D  *
******

Next. New cell is (1, 2). Not the destination. Only unvisited empty cell is to the right, (2, 2). Mark (2, 2) as being visited.

******   Queue: (2, 2)
*S** *
*vv  *
** ***
* D  *
******

Get (2, 2) back from the queue. (Don't you love nice short lines at the mall or the movies? Maze cells love short lines too.) It has 3 open neighbors (1, 2), (2, 3), and (3, 2), but (1, 2) is already visited. Add (2, 3) and (3, 2) and mark them (Adding order doesn't really matter).

******   Queue: (2, 3), (3, 2)
*S** *
*vvv *
**v***
* D  *
******

Now we can dequeue (2, 3), the cell right above the destination. It has (2, 2) and (2, 4) as empty neighbors, but (2, 2) is visited. Add (2, 4) to the queue and mark it.

******   Queue: (3, 2), (2, 4)
*S** *
*vvv *
**v***
* D  *
******

(2, 4) is the destination, but it has to wait its turn (that's how queues work.) (3, 2) isn't the destination, but it has (4, 2) as an unvisited open neighbor, so we can add that to the queue and mark it.

******   Queue: (2, 4), (4, 2)
*S** *
*vvvv*
**v***
* D  *
******

Now we get (2, 4) off the queue. It is the destination, so we are done. Now we just have to backtrack. (2, 4) was added by (2, 3), which was added by (2, 2), which was added by (1, 2), which was added by (1, 1). Each cell remembers the one that added it, so we have the whole path, like so:

******   
*S** *
*XX  *
**X***
* D  *
******

And we are done. Now you have learned how to solve any maze, with just the help of a queue.