by Dan Duda
- Python 3.7
- PyCharm Community (optional)
- Basic Python knowledge
In part 2 of this tutorial series we saw how the the Recursive Back-Tracker algorithm works and started to look out how to store our maze in code. We had decided to use the simple integer to store each cell of our maze and were left with the question of how to signify multiple properties of the cell with a single number. Recall the only properties we need to store for a cell are whether it has been visited and what are its exit paths. If each cell was a collection of of 5 boolean properties we could specify each cell with:
Visited = True or False
North Exit = True or False
East Exit = True or False
South Exit = True or False
West Exit = True or False
These 5 fields would tell us everything we need to know about a cell.
Behind the scenes everything in your computer’s memory is binary. Just a collection of one’s and zero’s. This can also be thought of as on or off or True or False. So an integer number is actually stored in binary. If we look at the numbers 0 through 8 and their binary representations we see:
0 = 0000
Now if we just look at powers of 2 we have:
0 = 0000
Notice that none of the numbers share an “on” bit with any of the others. Meaning that for each power of 2 the 1 bit moves over one place to the left. This is significant because if we give a meaning to the location or place/column that the 1 is set in then we can store multiple True or False values in a single number. For example, let’s say we’re playing an adventure game and we need to collect colored keys. Starting from the right let’s say the 1st position signifies the red key, the 2nd the blue key, the third the silver key, and the 4th the gold key. Now say each player in the adventure has a property called keys that starts out with the value of 0. If player 1 finds the blue key (position 2) we’d set the second bit so his keys value would be 2 (0010). If he then found the red key (position 1) we’d set the frist bit so his keys value would now be 3 (0011). Once he has collected all 4 keys his keys value would be 15 (1111).
Python makes it easy to work this way with the binary bitwise operators & (Binary AND) and | (Binary OR).
Let’s open up the Pythin IDLE/Shell again and use our keys example. We’ll define the 4 keys and initialize the player keys to 0.
>>> red_key = 1
To give the player the silver_key we could just set the player_keys value to silver_key but what if the player already had the blue key. It would overwrite his keys value and now he’d only have the silver key. We want both bits to be set if he had 2 keys. This is where the bitwise operators come into play. We want to take the players current keys value and “OR” it with the new key value.
>>> player_keys = player_keys | silver_key
The player’s keys value started out with the value 0 and we “OR’d” it with the silver key value of 4 and now the player’s key value is 4. If we now give the player the gold key we have:
>>> player_keys = player_keys | gold_key
The gold key has the value 8 but the player’s keys value is now 12 because both the silver and gold keys are set.
Why did we use the OR operator instead of the AND operator? Let’s look at how boolean logic works.
True AND True = True
So when both values are True we get True using AND or OR operators. But when the values are different, meaning one is set and one is not set, we get False when using AND and True when using OR. So if only value is set using OR results in True.
player_keys = 4 = 0100
So where there is at least a single one set in a place it stays set in the result.
Now say we want to check if the player has the red key. Currently the player keys value is 12. Instead of “ORing” we can “AND” it with the red key value. If the result is not zero then the player does have the red key. If the value is zero then he does not posess the red key. The value will actually be zero (if he does not have it) or the value of the key we’re “ANDing” it with if he does.
>>> player_keys & red_key
player_keys = 12 = 1100
We “AND” the player’s keys value with the red key value and get zero. So the player doesn’t have the red key.
There’s one more feature we need to talk about that will make using these bitwise “flags” a little easier. Enumerations give us a way to alias a bunch of values with a common name prefix. So instead of typing red_key we might type KeyEnum.red_key. It’s a little more typing but if using an IDE like PyCharm we also get intellisense so after typing “KeyEnum.” we’ll see a list of available values. It also makes it a little more readable and less prone to variable spelling mistakes.
To use enumerations we need to include the enum package. We then define an enumeration using a class that inherits from enum. So at the top of our script we’ll add the import and the new class.
from enum import Enum
We’ve defined our bitwise flags in an enumeration named CellProp. To access the value of an enumeration we use the “value” property. So for example, CellProp.Path_S.value would return the value 4.
So back to our maze, say we have the empty initialized 3X3 maze where all the values are zeros. We’re generating our maze and want to set the frist cell to visited. We would do the following:
# initialize a 3x3 maze with 0's
If you’re wondering about the operator |= that is just a shortcut to “OR” something with itself.
maze = maze | CellProp.Visited.value
If you are setting multiple flags at once as we do on the new cell above you could also write it as:
maze |= CellProp.Visited.value | CellProp.Path_N.value
We now have just about all the pieces needed to generate our maze. Let’s add some more constants to the top of our script to help us define the maze. We’ll need to know the width and height of the maze. We can then calculate the number of cells in the maze. We also want to be able to randomly choose a neighboring cell so we’ll need to import the random module.
from enum import Enum
And in the “init” method of our MazeGenerator class.
And now let’s start working on the “generate_maze” method.
We first initialize our maze with zeros. The number of zeros in the list is the number of cells in our maze which is width * height. We calculate this in our constants as CELL_COUNT. We set the visited count to zero. Next we add the first cell (0,0) to the process_stack list. This will be the bottom of the stack. We also set the visited flag on the first cell using our bitwise logic on line 8 and increase the visited count by one on line 10. Now we loop until the visited count reaches the number of cells in our maze.
The first step in our loop is to look for all neighbors that have not been visited yet. We’ll need to know what the current cell is that we’re working on. To get the current cell we just need to grab the top item on the stack. Recall the items on the stack are just tuples containing the x and y coordinates of each cell.
x, y = process_stack[-1] # get position of top item on stack
Using [-1] gives us the last item. If this syntax is unfamiliar to you, look up indexing and slicing in Python.
Since the value returned is a tuple we can “unpack” it into separate x and y variables using the “x, y = “ syntax.
We will also want to know the index in our “maze” list that the cell occupies. Let’s create a helper method to do that.
In our MazeGenerator class we’ll add the following method:
def get_cell_index(self, position):
Back in “generate_maze” we can now do the following:
while visited_count < CELL_COUNT:
If would be nice if we could loop over a list of directions so that we don’t have to have 4 separate blocks of code, one for each direction. Let’s bring back our friend, the Enum.
But what should the values be. We could just make them 0, 1, 2, 3. Then in our code we check which direction and look at the cell in that direction. What if we stored the value that when added to our current cell would give us the cell in that direction?
Now given a current cell x,y value we can add the direction’s x,y to get the new cell.
For example if we’re at cell 0,0 and want to go east, we add 1,0 and get 1,0 which is the next cell to the right.
So now the code to find all the unvisited neighbors is:
# Find all unvisited neighbors
We can loop through enums just like we can loop through any other list in python. The type of each item in the enumeration is an enum so we get the actual value by using the value property in line 4. The value will be a tuple made up of the two values x and y. Line 5 creates the new x and y values by adding the corresponding values in the dir tuple. Line 6 makes sure that the new x and y are not out of bounds. If we were in the first cell 0,0 and tried to go west or north we’d be out of bounds. If we’re in bounds then line 7 gets the index into our maze list for the new cell using our helper method “get_cell_index”. Line 8 checks if the cell has already been visited using our bitwise logic. If it hasn’t been visited we add the new x and y as well as the direction that was used to get there since we’ll need that later.
Our next step is to check if there are any unvisited neighbors. We’ve created the list named “neighbors” above so we just need to check it.
if len(neighbors) > 0:
We use the “len” method to get the length or number of items in the neighbors list. If it’s empty then we need to “back-track”. All we need to do is “pop” the top item off the stack and then the loop will continue.
If there are unvisted neighbors we need to choose one at random and process it.
if len(neighbors) > 0:
In line 3 we choose a random neighbor and call it “cell” using the “randrange” method. “randrange” will return a number from 0 to one less than the number we pass in. We pass in the length of the neighbors list so it will return a valid index to an item in that list. Line 4 unpacks the 3 values we stored, x, y, and direction. Line 5 just creates a “packed” tuple containing the x and y values. And line 6 gets the index into our maze list of the cell.
Lines 9 and 10 just store the CellProp value of the path to and from the cells. direction_to_flag and opposite_direction are just dictionary lookups to map the direction to a CellProp path property. We’ll define them in a minute.
Lines 12 - 14 set the CellProp values on the current and new cells using our bitwise logic.
Line 16 adds the new cell onto the stack and line 17 increments the visited count.
We’ll add the direction_to_flag lookup and opposite_direction lookups as class members before our “init” method. Since they’re class members we use the name of the class as a prefix to use them instead of the “self” prefix.
In the next part we will work on displaying our maze but for now let’s just print out the list that we created. In our “run_game” method let’s add the following code before our main loop.
Running the code should bring up an empty window but in the console in PyCharm we should see our maze list. Sinice we randomly build the maze your values may differ from mine.
The full code so far
from enum import Enum
Download code: maze.zip