Designing a Breadth First Search Maze Algorithm

Efficient maze algorithms have immense practical value. Think about the future; what do you see? I see a bunch of robots cleaning my house, vacuuming and gathering up all the stuff I left on the floor. But any house is bound to have a tangle of furniture sitting around. To an unthinking robot, this is a maze, an unknown area with impassable ‘walls’ seemingly randomly placed around. If we want our robot butlers, we’re going to have to design some sort of program that can solve this traversal puzzle.

First, we must establish the rules of the mazes we’ll be solving. Each maze will consist of any number of square tiles. Each tile will have up to three impassable walls on any of its sides. Each maze will have one start tile and one end tile. The goal is, of course, to travel from the start to the end. In pursuit of this, we will be able to move only straight up, down, left, or right. Never diagonally. Lastly, our vision will be limited to the tile we’re on, we can only tell if a tile is the end tile if we’re standing right on it.

With these new rules, let’s take a look at our first maze:dfs 1When we begin, the location of the end tile is unknown. Keeping this in mind, there’s clearly only one thing to do: we must systematically search every tile until we find the end tile. In other words, we must create a search algorithm

If we assume that there will be no dead ends, only two rules are needed to start:

  1. Go straight until you hit a wall, a previously visited tile, or the end tile. If you are on the end tile, stop. If you’re not on the end tile, go to rule 2.
  2. Turn and move to the next unvisited adjacent tile. Then go back to rule 1.

Let’s see what happens when we use these two rules on the maze from before:
dfs 2
This is the result we were looking for. But we’re not done yet. If you remember, we assumed with those rules that we would never reach a dead end, so now let’s look at an example where there is a dead end:dfs 3

We are now trapped, and neither of the two rules from before work in this situation. To come up with the next rule, let’s think about what we want. Clearly, we want to move up and around to the center tile. In this case, if we simply retrace our steps we’ll end up right next to the open space.This give us a possible third rule:

       3. Trace your moves back until there is a clear path to an unvisited tile, then move there.dfs 4You may think we’re finished, since we seem to be able to navigate through any problem we come up against, and to some extent, you’re correct. With the three rules we have so far, any maze that follows the format we’ve designed can be navigated. However, now certain inefficiencies must be dealt with. Take a look at this next map:dfs 5

Suddenly, our problem becomes apparent. The open space is only a few tiles away, but with the “retrace steps” rule, many more tiles will be checked then need to be.

So if the first version of rule 3 doesn’t work, what will? Well, instead of retracing, we will have use a list to evenly search the already traveled spaces. Let me show you how:dfs 6I want to pause for a second to talk about the type of list we just used. Please notice, whenever a tile was added to the list, we always put it at the end. Whenever we removed a tile to check it, it was taken from the beginning of the list. In Computer Science, this is known as a queue. A queue is a ‘first in, first out’ data structure, and in this case it serves the purpose of searching the maze evenly as we spread out, a breadth first search.

Look back at before. If we had not found that unvisited tile, what would have happened? Well, because we were using a queue, our search would have continued down the two paths; one tile from one side, then another tile from the other side. If we had not used a queue, depending on how else we designed rule 3, we might have the same inefficiency problem as when we were just going back along the path we came.

With that quick aside, let’s restate the rules with the new rule 3:

  1. Go straight until you hit a wall, a previously visited tile, or the end tile. If you are on the end tile, stop. If you’re not on the end tile, go to rule 2.
  2. If there is an adjacent unvisited tile, move to that tile, then go back to rule 1. If not, go on to rule 3.
  3. Add all adjacent tiles to a queue. Get the the next tile from the queue and add all of its adjacent tiles to the queue. Keep doing this until one of the tiles you remove from the queue is an unvisited tile. Then. go back to rule 1.

 

With this, we’re finally done with our maze algorithm! Rules 1 & 2 give us simple movement around the maze, and rule 3 will kick in whenever we hit a dead end. Because of the queue, rule 3 should work as quickly and efficiently as is reasonable. And, since we designed our rules well, any maze that follows the template from the beginning can be traversed by this simple maze algorithm. One step closer to robotic servants!

 

If you want to see my implementation of this algorithm, you can click here to view it on GitHub.

If you want to see more articles, click here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s