Build a 2-player maze game with Python Part 2

2018-11-17 Programming

by Dan Duda

Requirements

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

Goto Part 1

Introduction

In part 1 of this tutorial series we setup our project and created a barebones PyGame script. In this tutorial I want to refactor our script into a class so that going forward we’ll have better separation of concerns. I also want to start setting things like screen resolution in a module level variable at the top of the file.

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
import pygame as pg


# Global Settings
SCREEN_WIDTH = 800
SCREEN_HEIGHT = 600


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')

    def generate_maze(self):
        pass

    def run_game(self):
        # 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()

Running this should bring up an empty window again as we saw in part 1 but now our code is a little more structured. On lines 5 and 6 we create some module level constants to store our screen size. Now technically they aren’t constants like in other languages. We could still change the values in code but making them all caps is a standard for signifying that they should only be read.

Starting on line 9 we create our main class, MazeGenerator. We do our initializion in the “init” method and put our main loop in the “run_game” method. Lines 34 and 35 create an isntance of our class and start our loop.

For now we’ve just stubbed out our “generate_maze” method with the “pass” keyword.

Drawing on the screen

All we need to draw our maze is a single method from the PyGame package called “draw.rect”. To see how it works let’s add the following code at line 30, inside our while loop.

1
2
pg.draw.rect(self.screen, (255, 255, 255), (50, 50, 100, 100))
pg.display.update()

Our “run_game” method should now look like this.

1
2
3
4
5
6
7
8
9
10
11
12
def run_game(self):
    # Main game loop
    run = True
    while run:
        for event in pg.event.get():
            if event.type == pg.QUIT:
                run = False

        pg.draw.rect(self.screen, (255, 255, 255), (50, 50, 100, 100))
        pg.display.update()

    pg.quit()

Running the program now should display a white rectangle in the display area. The “draw.rect” method takes 3 arguments. The first is the surface we want to draw to which we created in our class’s “init” method and saved in the variable “screen”. The second is a color which we pass using a tuple. It’s made up of three values representing the colors Red, Green, and Blue with values from 0 to 255. So (255, 255, 255) gives us white. (0, 0, 0) would be black, (255, 0, 0) full red and so on. The last parameter is a rectangle object again represented with a tuple. The first two values are the x and y cooridinate of the upper left corner of the rectangle and the last 2 values are the width and height of the rectangle. So our rectangle is 100 X 100 starting at 50, 50. The coordinates of our surface start at 0,0 in the top left corner of the window.

If we just had the draw.rect method and ran our program nothing would display. We still need to call display.update() after we’ve done all our drawing so that it displays.

But enough about drawing for now. Let’s learn how to generate our maze.

For now let’s comment out those two lines.

1
2
3
4
5
6
7
8
9
10
11
12
def run_game(self):
    # Main game loop
    run = True
    while run:
        for event in pg.event.get():
            if event.type == pg.QUIT:
                run = False

        # pg.draw.rect(self.screen, (255, 255, 255), (50, 50, 100, 100))
        # pg.display.update()

    pg.quit()

Stacks

In computer science a stack is a collection data structure where the last item in is the first item out. Sometimes referred to as LIFO (Last in, First Out). Think of stacking a bunch of books on the floor. The first book you place will be at the bottom. You stack one on top of the other. When you take a book you remove it from the top. The process of adding a book to the stack is called pushing or appending and removing a book is called popping. The Python List type has a method, “append” which adds an item to the end of the list and a method, “pop” which removes the last item in the list.

If we open up the Python IDLE (Shell) we can see this in action.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> my_list = []
>>> my_list.append(1)
>>> my_list.append(2)
>>> my_list.append(3)
>>> my_list
[1, 2, 3]
>>> my_list.pop()
3
>>> my_list
[1, 2]
>>> my_list.pop()
2
>>> my_list
[1]
>>>

We first create an empty list and then append the numbers 1, 2, and 3 to it. We display the list and see [1, 2, 3]. We then pop an item off the list. It returns the last item in the list which was 3. Then displaying the list again we see [1, 2]. And so on. So it’s like a stack on its side but functions the same way. We will be relying on stacks when we create the maze generation code.

The Recursive Back-Tracker Algorithm

First let’s visually look at how this algorithm works. Our maze will be a 2-dimensional grid with the top-left corner being 0,0. Think of a sheet of graph paper with each cell/square being one location in the maze. If we start at x,y = 0,0 in the top left corner then increasing the value of x moves us to the right and increasing the value of y moves us down. Let’s use a small 5 X 3 grid for demonstration.

We will need a stack to keep track of our path through the grid and a visited counter. If our maze is 5 X 3 then there are 15 cells. Our algorithm is finished when we’ve visited every cell which means our visited count is equal to 15.

The algoritm works as follows. We add our starting cell, in this case 0,0 to the stack. We mark it as visited and increase the visited count by one. We then randomly choose a neighbor cell that has not already been visited. We then add that new cell to the stack, mark it as visited, and increase the visited count by one. We go on until the visited count is equal to 15, meaning we’re done, or until there are no unvisited neighbors. If there are no unvisited neighbors we have the “back-track” which is where the name of this algorithm comes from. To back-track we pop a cell off of the stack and then check if there are any unvisited neighbors. We continue popping items off the stack until we find an unvisited neighbor.

Here’s our 5 X 3 grid before we start.


Step 1: Add the first cell to the stack and mark the cell as visited. Add one to the visited count.


Step 2: Randomly select next unvisited neighbor, add cell to the stack and mark the cell as visited. Add one to the visited count.


Step 3: Repeat, choosing 1,1.


Step 4: Repeat, choosing 2,1.


Step 5: Repeat, choosing 2,0.


Step 6: Repeat, choosing 1,0.


Step 7: Now we have no unvisted neighbors so we backtrack back to cell 2,0. The only unvisted neighbor from 2,0 is 3,0.


Step 8: We continue until the visited count is 15.


Step 9: Finally we remove all the walls where a path was made, leaving our maze.


Thanks to javidx9 and his youtube video “Programming Mazes” as inspiration for this tutorial.

Storing our maze

Now that you understand how the algorithm works we need to convert it to code. First we need to store the maze. For this we will use a simple Python list. Here we define an empty list.

1
maze = []

Now you may be wondering how we can store a 2-dimensional grid in a 1-dimensional list. Say we have a 3 X 3 maze. The position in the list will tell us the position on the grid. So the first item in the list will be the top-left corner of the grid. The first item in a list has the index of 0. We get the value of the first item in the list using maze[0]. The second value is maze[1], etc. Knowing the width and height of the maze we can convert to a index in a 1-dimensional list using the following equatiion.

index = y * WIDTH + x

So say we have the coordinate 2,1 in our maze. We need the index of that cell in our list. Our maze is 3X3 so the width is 3. x = 2 and y = 1. We take y=1 Width=3 + x=2 which gives us 1 3 + 2 = 5. If we wanted to find 0,2 we use 2 * 3 + 0 = 6. And so on.


So we have a way to store our maze in a simple list. But what will the values in the list be? Each value in our list represents a cell in our maze. A 3X3 maze might look like this.

1
maze = [value1, value2, value3, value4, value5, value6, value7, value8, value9]

We need to keep track of if the cell has been visited and we also need to know the available paths out of the cell. We might signify the paths with a letter for direction like ‘N’ for north, ‘E’ for east and so on. In Python we can use classes to make a type that encapsulates multiple values. We also have tuples. So using tuples we might have somthing like this where we’ve processed the first 2 cells of the maze.

1
maze = [(True, 'E'), (True, 'W'), (False), (False), (False), (False), (False), (False), (False)]

This seems a bit complicated. Some cells may have more paths out than others so our tuples would not all be the same size. We’d need a lot of code pack and unpack these tuples. A class called Cell might work.

1
2
3
4
5
6
7
8
9
10
11
12
class Cell:
    def __init__(self, visited, north, east, south, west):
        self.visited = visited
        self.north = north
        self.east = east
        self.south = south
        self.west = west

cell1 = Cell(False, False, False, False, False)
... etc...

maze = [cell1, cell2, cell3, cell4, cell5, cell6, cell7, cell8, cell9]

So for each cell in the maze we’d create an instance of our cell class and set its values approriately.

While this would work there’s actually a way we can make this simpler and just use the basic Python integer type as the value in our maze. If our maze is just a list of integers we’d only need 9 numbers to model a 3X3 maze. If 0 means that the cell has not been visited and has no exit paths then we could initialize our maze like this.

1
maze = [0] * 9

In the Python IDLE/shell we can see this.

1
2
3
>>> maze = [0] * 9
>>> maze
[0, 0, 0, 0, 0, 0, 0, 0, 0]

This is a very simple way to store an entire maze but how can we signigy multiple things in a single value? We’ll cover that in Part 3.

Goto Part 3

#Python #PyGame #Algorithms #Recursion