Build a 2-player maze game with Python Part 3

by Dan Duda

Requirements

• Python 3.7
• PyCharm Community (optional)
• Basic Python knowledge

Goto Part 2

Introduction

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.

Bitwise flags

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:

1
2
3
4
5
6
7
8
9

0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000

Now if we just look at powers of 2 we have:

1
2
3
4
5

0 = 0000
1 = 0001
2 = 0010
4 = 0100
8 = 1000

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.

1
2
3
4
5

>>> red_key = 1
>>> blue_key = 2
>>> silver_key = 4
>>> gold_key = 8
>>> player_keys = 0

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.

1
2
3

>>> player_keys = player_keys | silver_key
>>> player_keys
4

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:

1
2
3

>>> player_keys = player_keys | gold_key
>>> player_keys
12

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.

1
2
3
4
5
6
7
8
9

True AND True = True
True AND False = False
False AND True = False
False AND False = False

True OR True = True
True OR False = True
False OR True = True
False OR False = False

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.

1
2
3
4
5
6
7

player_keys = 4 = 0100
gold_key    = 8 = 1000

   0100
OR 1000
-------
   1100

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.

1
2

>>> player_keys & red_key
0

1
2
3
4
5
6
7

player_keys = 12 = 1100
red_key     =  1 = 0001

    1100
AND 0001
--------
    0000

We “AND” the player’s keys value with the red key value and get zero. So the player doesn’t have the red key.

Enumerations

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

from enum import Enum
import pygame as pg


# Global Settings
SCREEN_WIDTH = 800
SCREEN_HEIGHT = 600


class CellProp(Enum):
    Path_N = 1
    Path_E = 2
    Path_S = 4
    Path_W = 8
    Visited = 16

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:

1
2
3
4
5
6
7
8
9
10
11

# initialize a 3x3 maze with 0's
maze = [0] * 9

# set the first cell to visited
maze[0] |= CellProp.Visited.value

# now we've randomly chosen the cell below (south) of this cell
# we set the new cell's visited property and set the original cell's Path_S and the new cell's Path_N to link them
maze[3] |= CellProp.Visited.value
maze[3] |= CellProp.Path_N.value
maze[0] |= CellProp.Path_S.value

If you’re wondering about the operator |= that is just a shortcut to “OR” something with itself.

1
2
3
4
5

maze[3] = maze[3] | CellProp.Visited.value

is equivalent to writing

maze[3] |= 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:

1

maze[3] |= CellProp.Visited.value | CellProp.Path_N.value

Generating our Maze

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

from enum import Enum
import random
import pygame as pg


# Global Settings
SCREEN_WIDTH = 800
SCREEN_HEIGHT = 600
MAZE_WIDTH = 5  # in cells
MAZE_HEIGHT = 3  # in cells
CELL_COUNT = MAZE_WIDTH * MAZE_HEIGHT


class CellProp(Enum):
    Path_N = 1
    Path_E = 2
    Path_S = 4
    Path_W = 8
    Visited = 16

And in the “init” method of our MazeGenerator class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class MazeGenerator:
    def __init__(self):
        # Need to initialize pygame before using it
        pg.init()

        # Create a display surface to draw our game on
        self.screen = pg.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))

        # Set the title on the window
        pg.display.set_caption('PyMaze')

        # Use a single list to store 2D array
        self.maze = []

        # Seed random number generator with current time
        random.seed()

And now let’s start working on the “generate_maze” method.

1
2
3
4
5
6
7
8
9
10
11
12

def generate_maze(self):
    # Initialize maze with zero values
    self.maze = [0] * CELL_COUNT
    visited_count = 0

    # Add the first cell (0,0) onto the stack and increase the visited count
    process_stack = [(0, 0)]
    self.maze[0] |= CellProp.Visited.value

    visited_count += 1
    while visited_count < CELL_COUNT:
        pass

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.

1

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:

1
2
3

def get_cell_index(self, position):
    x, y = position
    return y * MAZE_WIDTH + x

Back in “generate_maze” we can now do the following:

1
2
3
4
5
6
7
8

while visited_count < CELL_COUNT:
    # Step 1 - Create a list of the unvisited neighbors
    x, y = process_stack[-1]  # get position of top item on stack
    current_cell_index = self.get_cell_index((x, y))  # get the cell's index

    # Find all unvisited neighbors
    neighbors = []
    # Check each direction ???

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.

1
2
3
4
5

class Direction(Enum):
    North = ?
    East = ?
    South = ?
    West = ?

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?

1
2
3
4
5

class Direction(Enum):
    North = (0, -1)
    East = (1, 0)
    South = (0, 1)
    West = (-1, 0)

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:

1
2
3
4
5
6
7
8
9
10

# Find all unvisited neighbors
neighbors = []
for direction in Direction:
    dir = direction.value
    new_x, new_y = (x + dir[0], y + dir[1])
    if 0 <= new_x < MAZE_WIDTH and 0 <= new_y < MAZE_HEIGHT:
        index = self.get_cell_index((new_x, new_y))
        if not self.maze[index] & CellProp.Visited.value:
            # Cell was not already visited so add to neighbors list with the direction
            neighbors.append((new_x, new_y, direction))

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.

1
2
3
4
5

if len(neighbors) > 0:
    pass
else:
    # Backtrack since there were no unvisited neighbors
    process_stack.pop()

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

if len(neighbors) > 0:
    # Choose a random neighboring cell
    cell = neighbors[random.randrange(len(neighbors))]
    cell_x, cell_y, cell_direction = cell
    cell_position = (cell_x, cell_y)
    cell_index = self.get_cell_index(cell_position)

    # Create a path between the neighbor and the current cell by setting the direction property flag
    flag_to = MazeGenerator.direction_to_flag[cell_direction]
    flag_from = MazeGenerator.direction_to_flag[MazeGenerator.opposite_direction[cell_direction]]

    self.maze[current_cell_index] |= flag_to.value
    self.maze[cell_index] |= flag_from.value | CellProp.Visited.value

    process_stack.append(cell_position)
    visited_count += 1
else:
    # Backtrack since there were no unvisited neighbors
    process_stack.pop()

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class MazeGenerator:
    direction_to_flag = {
        Direction.North: CellProp.Path_N,
        Direction.East: CellProp.Path_E,
        Direction.South: CellProp.Path_S,
        Direction.West: CellProp.Path_W
    }

    opposite_direction = {
        Direction.North: Direction.South,
        Direction.East: Direction.West,
        Direction.South: Direction.North,
        Direction.West: Direction.East
    }

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.

1
2

self.generate_maze()
print(self.maze)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

from enum import Enum
import random
import pygame as pg


# Global Settings
SCREEN_WIDTH = 800
SCREEN_HEIGHT = 600
MAZE_WIDTH = 5  # in cells
MAZE_HEIGHT = 3  # in cells
CELL_COUNT = MAZE_WIDTH * MAZE_HEIGHT


class CellProp(Enum):
    Path_N = 1
    Path_E = 2
    Path_S = 4
    Path_W = 8
    Visited = 16


class Direction(Enum):
    North = (0, -1)
    East = (1, 0)
    South = (0, 1)
    West = (-1, 0)


class MazeGenerator:
    direction_to_flag = {
        Direction.North: CellProp.Path_N,
        Direction.East: CellProp.Path_E,
        Direction.South: CellProp.Path_S,
        Direction.West: CellProp.Path_W
    }

    opposite_direction = {
        Direction.North: Direction.South,
        Direction.East: Direction.West,
        Direction.South: Direction.North,
        Direction.West: Direction.East
    }

    def __init__(self):
        # Need to initialize pygame before using it
        pg.init()

        # Create a display surface to draw our game on
        self.screen = pg.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))

        # Set the title on the window
        pg.display.set_caption('PyMaze')

        # Use a single list to store 2D array
        self.maze = []

        random.seed()

    def get_cell_index(self, position):
        x, y = position
        return y * MAZE_WIDTH + x

    def generate_maze(self):
        # Initialize maze with zero values
        self.maze = [0] * CELL_COUNT
        visited_count = 0

        process_stack = [(0, 0)]
        self.maze[0] |= CellProp.Visited.value

        visited_count += 1
        while visited_count < CELL_COUNT:
            # Step 1 - Create a list of the unvisited neighbors
            x, y = process_stack[-1]  # get position of top item on stack
            current_cell_index = self.get_cell_index((x, y))

            # Find all unvisited neighbors
            neighbors = []
            for direction in Direction:
                dir = direction.value
                new_x, new_y = (x + dir[0], y + dir[1])
                if 0 <= new_x < MAZE_WIDTH and 0 <= new_y < MAZE_HEIGHT:
                    index = self.get_cell_index((new_x, new_y))
                    if not self.maze[index] & CellProp.Visited.value:
                        # Cell was not already visited so add to neighbors list with the direction
                        neighbors.append((new_x, new_y, direction))

            if len(neighbors) > 0:
                # Choose a random neighboring cell
                cell = neighbors[random.randrange(len(neighbors))]
                cell_x, cell_y, cell_direction = cell
                cell_position = (cell_x, cell_y)
                cell_index = self.get_cell_index(cell_position)

                # Create a path between the neighbor and the current cell by setting the direction property flag
                flag_to = MazeGenerator.direction_to_flag[cell_direction]
                flag_from = MazeGenerator.direction_to_flag[MazeGenerator.opposite_direction[cell_direction]]

                self.maze[current_cell_index] |= flag_to.value
                self.maze[cell_index] |= flag_from.value | CellProp.Visited.value

                process_stack.append(cell_position)
                visited_count += 1
            else:
                # Backtrack since there were no unvisited neighbors
                process_stack.pop()

    def run_game(self):
        self.generate_maze()
        print(self.maze)

        # Main game loop
        run = True
        while run:
            for event in pg.event.get():
                if event.type == pg.QUIT:
                    run = False

        pg.quit()


mg = MazeGenerator()
mg.run_game()

Download code: maze.zip

Goto Part 4