Building a Maze using Test Driven Development

SECTION 1: Introduction

We will be first creating a maze using test driven development techniques. Each step of the way will begin with a test. As you follow along with this example, you can execute the code by clicking on the run buttons. You can also change the code and rerun any of them if you want to experiment or find out more.

The first thing we need to test for is a Maze class. Of course there is no Maze class. We haven’t written it yet. We test for it first.

This code should run without an error if there is a Maze class.

You should see an error when you run the code. It’s a pretty ugly NameError:

You are in what we call condition RED. The next step is to get into condition GREEN. We do this by writing the minimal amount of code we need to make the test pass.

Let’s make it a little prettier first and use the try statement as follows:

Much better.

Now let’s make this class exist.

We will use the turtle module to make our maze. You may need to read up a little on the turtle module to learn the features available to you.

The screen is created with the following command

When you run this code you will see the blue screen we created. A blue color means a wall. This is the visual representation of our maze. We don’t have any paths created yet. It’s all wall.

Now let’s put this into the maze class. First write the test for the screen.

Now add the screen.

Condition is now GREEN. We also need a turtle. Add a test for the turtle.

And you know the next step to get GREEN.

We will first be constructing our maze using the colors blue for a wall, white for a path, and yellow for the final goal. Since we are making a path, it seems like a good starting point would be to have nothing but walls. This means a blue screen. We can test by looking at the bgcolor method for Screen.

We also check the height and width of our screeen to be safe. You should now see the blue screen. (Note that I skipped the RED to GREEN and added both the test and the code)

So far we have discussed the RED and GREEN condition. It’s now time to think about YELLOW. This is the refactoring stage. Refactoring is when you modify your code to improve it without changing its function or behavior. Unlike this example, the tests we write persist through each iteration of your development cycle (RED-GREEN-YELLOW) To save space I leave out the prior tests. Normally you want all your tests to run all the time.

Anticipating change in your program is a good thing. If you can see ways to generalize parameters, it usually helps to make your code more flexible for future changes. For instance, notice how we are using the number 400. Hard-coded numbers like that are a warning sign. Usually you are helped by making that value a parameter such as “SIZE” for instance.

This is a very small refactoring example. We will see others as we continue.

Now we need to think about how we will represent our maze inside the program. The screen is the interface to people but internally we need to make decisions based on the current state of the maze.

I choose a matrix as the data type best suited. Each item in the matrix corresponds to a location in the maze. The size of the screen by default is 400x400. We will keep the default for now. The way we will draw on the screen is by using the stamp method in the turtle module and a square for the shape. (look into the documentation on the turtle module for more clarification on those methods.)

The default size for the square is 20x20. So we can have 20 rows and 20 columns in our matrix since the size of the screen is 400x400. The origin is in the middle. so -190,190 corresponds to the [0][0] location of the matrix. Let’s clarify our thinking a little by writing code to draw a white square in the upper left hand corner.

Here’s how we would draw a path along the top of the screen. Feel free to make changes to this code and experiment so you feel like you understand how the turtle works.

This is all useful for learning about the tools we have. Let’s create a test for our matrix, the internal representation of the maze.

Notice how we now use the parameter SIZE in our code.

This only checks for the height of our matrix but it’s good enough for now. You should weigh how much time you want to spend writing a test vs how risky is the failure. To make this test pass we want to add a matrix to our maze. Here’s the code that does that. Notice that all the values in the matrix are 1 which corresponds to everything being a wall. That’s an arbitrary decision I just made. Seems like 0 for no wall and 1 for a wall makes sense.

We will start our path from the upper left hand corner, (another arbitrary choice). Let’s imagine we are digging our path through the walls. When we dig into the space, we turn a 1 in our matrix to a 0. This indicates we have an empty space at that location. It’s easy to then consider a function called dig where we pass in a direction and the turtle will dig in that direction one space if possible.

Since we are starting from the upper left hand corner, matrix[0][0] should be 0 and the turtle location should be -190,190. Let’s put a reset function in so we can always get to this starting configuration.

Make it pass now.

Time to refactor. How can we improve on this code? We have some duplicate code in there. Let’s get rid of it.

I think of the turtle as sort-of digging it’s way through the walls to make the maze.

We are at a point where we can consider the dig function. I imagine m.dig(EAST) will move the turtle one square to the East on the screen. But what is EAST and why and I using capitals? In programming it is common to map words to constants and when we do that we often use all capitals to indicate that’s what is going on. The way we do this in python is simple.

If we do this, it makes it easier since we don’t have to remember 0 is East. So we know we want one argument for dig. What do we want back? If we get back the position of the turtle, we can tell if it succeeded in moving and we can tell where it is also. After a reset we should be able to dig East. So calling m.dig(EAST) should return (-170,190). Now we know how to write our test.

To create a passing test, we need to add the code for dig. One thing that becomes very obvious is that we need to map the position of the turtle into the matrix locations because we can’t use the turtle position to index the matrix directly. What would be convenient is to be able to access the matrix with the turtle position. Something like

At reset conditions, the matrix value would be 0 at [0][0] because we have a space there. Our test should be

Make it pass.

Now for setMatrixValueAt(pos).

Nice! Now we can just use our turtle position to set the matrix. But after we set the matrix to 1, we should see the white square dissappear if it properly represents our matrix. Let’s fix that.

Now we can map turtle position to matrix element. Remember we are trying to implement dig ultimately. Let’s manually do a little digging.

So now with this code we see that digging east moves the turtle to -170,190 and sets the value of the matrix at that point to 0.

Let’s add our test and code to make it pass.

Now let’s do a reset and dig south. I’m showing both the test and the code to make it pass here.

We can’t dig west from the reset condition so let’s make sure that is understood by the function. We need to assert that digging west just returns the original location of the turtle so we know it didn’t move. Note that the previous code is included in the following.

Well this test actually passed without us doing anything but it’s just a fluke because we ignore WEST and in this case that’s what we want to do. Let’s get a little more involved with our testing. We can go East and South, so let’s try going East, South, and then West. We should see our failure then.

Of course we can see how ignoring WEST was just a fluke here. Sometimes writing tests is a little more involved than at first perceived. Now let’s get this test to pass.

We have dug ourselves a nice square. One last direction to test, NORTH. Here’s both the test and the solution.

Here is our Maze class.

Our code examples will now just include that invisibly and we will override functions.

We now have our dig method. We can dig in all 4 directions. There are more tests we can add for more complete confidence in the method but for now, let’s move on. We may go back and add some more tests for dig if we find things are breaking.

One thing we need to be careful about when digging our paths in the maze is that we need to make sure we don’t go into another preexisting path. Our tests make a big square in the upper left hand corner but we really don’t want that to happen. We want some wall between paths. Lets prevent digging if it means we connect to a preexisting path. This means that the 3 locations surrounding the new space must be walls. Spaces outside the boundary of the screen are considered walls.

How do we test this? If we make a space at location m.matrix[0][2] then we should not be able to dig EAST from m.matrix[0][0].

This passes but why don’t we see the white square appearing at location (-150,190)? We assumed the turtle was where it should be to stamp the value but we need to move the turtle to that location first and then move the turtle back. So we correct the setMatrixValueAt method.

Now we see the white square at (-150,190). I will leave it to you to handle the other directions. After you are done, you should have a class that looks like this.

And the tests.

Again, there could be more testing. It’s a judgement call as to how much you want to test. How much energy you have and how important something is, etc.

Now it’s a good idea to not reinvent the wheel! Look up algorithms for maze generation and you will find a number of web sites. We will use the depth-first search algorithm


  1. Start at the upper left hand corner

  2. Mark that cell as visited and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor
    • if that neighbor hasn’t been visited, remove the wall between this cell and that neighborand then recur with that neighbor as the current cell.

It might be nice to have a method called neighbors which returns the state of the cells neighboring the current cell.

neighbors should return 4 values, the neighbors in all 4 directions. At the boundaries, the values outside the matrix should be -1 to indicate invalid locations.

A neighbor is actually 2 cells away since walls take up a cell’s width.

At reset condition then, neighbors should return [-1,1,1,-1] for the NORTH, SOUTH, EAST, and WEST neighbors.

Now to implement.

Now that we have added neighbors, let’s put it into our Maze class rather than just overloading it.

Now with these constants added we can make the code a little more readable.

We are now ready to start implementing the algorithm. We will call the method create(). It will be recursively calling itself but to start we will just have it run one iteration. That way we can test it.

Our Maze class as it stands now.

Let’s just say for test number one, we will have the first part dug. So either it will be a path to the right or a path down. Our test should check both directions and see if one has been successfully dug.

Now the algorithm says we should recur what we just did. So let’s try.


Now let’s put it all together in our Maze model

Next part: Part 2 Part 2: SOLVING THE MAZE

In this part, we will be adding to the Maze class to solve the maze we just built.