5. Project: Maze Game

Here’s another project for the Sense HAT that involves building a full maze solving game. Initially this will be controlled with the joystick (because it’s easier for debugging), but at the end we’ll switch to use the IMU to roll the ball through the maze.

Let’s start at a high level and work our way down. We’ll construct the application in the same manner as our earlier demos: a transformation of inputs (initially from the joystick, later from the IMU) into a series of screens to be shown on the display.

First some design points:

  • The state of our maze can be represented as a large numpy array (larger than the screen anyway) which we’ll slice to show on the display.
  • We’ll need:
    • a color to represent walls (white)
    • a color to represent unvisited spaces (black)
    • a color to represent visited spaces (green)
    • a color to represent the player’s position (red)
    • a color to represent the goal (yellow)
  • We’ll also need:
    • a function to generate the maze
    • (possibly) a function to draw the generated maze as a numpy array
    • a transformation to convert joystick events / IMU readings into X+Y motion
    • a transformation to convert motions into new display states (essentially this is the “game logic”)
    • a function to render the display states including any requested animations (just like in the final monitor script previously)

Let’s start from the “top level” and work our way down. First, the imports:

import numpy as np
import pisense as ps
from random import sample
from colorzero import Color
from time import sleep

Our “main” function will define the colors we need, call a function to generate the maze, set up the motion transformation, the game transformation, and feed all this to the display renderer:

def main():
    width = height = 8
    colors = {
        'unvisited': Color('black'),
        'visited':   Color('green'),
        'wall':      Color('white'),
        'ball':      Color('red'),
        'goal':      Color('yellow'),
    }
    with ps.SenseHAT() as hat:
        maze = generate_maze(width, height, colors)
        inputs = moves(hat.stick)
        outputs = game(maze, colors, inputs)
        display(hat.screen, outputs)

You may recall from our earlier demos (specifically Joystick Movement) that we had a neat little function that converted joystick events into X and Y delta values. Let’s copy that in next:

def moves(stick):
    for event in stick:
        if event.pressed:
            try:
                delta_y, delta_x = {
                    'left': (0, -1),
                    'right': (0, 1),
                    'up': (-1, 0),
                    'down': (1, 0),
                }[event.direction]
                yield delta_y, delta_x
            except KeyError:
                break

So far, this may look rather strange! What does it mean to call a generator function like “moves” without a for loop? Quite simply: this creates an instance of the generator but doesn’t start evaluating it until it’s used in a loop. In other words nothing in the generator function will run … yet. The same goes for the “game” function which will also be a generator, looping over the movements yielded from “moves” and yielding screens for “display” to deal with.

Speaking of “display”, that should be easy enough to deal with. It’ll be a slightly expanded version of what we used in the previous monitor example with additional cases for zooming and scrolling text:

def display(screen, states):
    try:
        for anim, data in states:
            if anim == 'fade':
                screen.fade_to(data)
            elif anim == 'zoom':
                screen.zoom_to(data)
            elif anim == 'show':
                screen.array = data
            elif anim == 'scroll':
                screen.scroll_text(data, background=Color('red'))
            else:
                assert False
    finally:
        screen.fade_to(ps.array(Color('black')))

Now onto the game logic itself. Let’s assume that the player always starts at the top left (which will be (1, 1) given that (0, 0) will be an external wall) and must finish at the bottom right. We’ll assume the maze generator handles drawing the maze, including the goal, for us and we just need to handle drawing the player’s position and updating where the player has been.

We’ll handle reacting to motion from the “moves” generator, preventing the player from crossing walls (by checking the position they want to move to doesn’t have the “wall” color), and noticing when they’ve reached the goal (likewise by checking the color of the position they want to move to):

def game(maze, colors, moves):
    height, width = maze.shape
    y, x = (1, 1)
    maze[y, x] = colors['ball']
    left, right = clamp(x, width)
    top, bottom = clamp(y, height)
    yield 'fade', maze[top:bottom, left:right]
    for delta_y, delta_x in moves:
        if Color(*maze[y + delta_y, x + delta_x]) != colors['wall']:
            maze[y, x] = colors['visited']
            y += delta_y
            x += delta_x
            if Color(*maze[y, x]) == colors['goal']:
                yield from winners_cup()
                break
            else:
                maze[y, x] = colors['ball']
                left, right = clamp(x, width)
                top, bottom = clamp(y, height)
                yield 'show', maze[top:bottom, left:right]
    yield 'fade', ps.array(Color('black'))

In the function above we’ve assumed the existence of two extra functions:

  • “clamp” which, given a position (either the user’s current X or Y coordinate) and a limit (the width or height of the maze), returns the lower and upper bounds we should display (on the fixed 8x8 LEDs).
  • “winners_cup” which will provide some fancy “You’ve won!” sort of animation. This is called with yield from which is equivalent to iterating over it and yielding each result.

Let’s construct “clamp” first as it’s pretty easy:

def clamp(pos, limit, window=8):
    low, high = pos - window // 2, pos + window // 2
    if low < 0:
        high += -low
        low = 0
    elif high > limit:
        low -= high - limit
        high = limit
    return low, high

Now let’s code some fancy animation for a user that’s won. We’ll zoom in to a golden cup on a red background, fade to red, and scroll “You win!” across the display:

def winners_cup():
    r = Color('red')
    y = Color('yellow')
    W = Color('white')
    yield 'zoom', ps.array([
        r, r, W, y, y, y, r, r,
        r, r, W, y, y, y, r, r,
        r, r, W, y, y, y, r, r,
        r, r, r, W, y, r, r, r,
        r, r, r, W, y, r, r, r,
        r, r, r, W, y, r, r, r,
        r, r, r, W, y, r, r, r,
        r, r, W, y, y, y, r, r,
    ])
    sleep(2)
    yield 'fade', ps.array(r)
    yield 'scroll', 'You win!'

Note

Not all generator functions need a loop in them!

Nearly there … now we’ve just got to generate the maze. There’s lots of ways of doing this but about the simplest is Kruskal’s Algorithm. Roughly speaking, it works like this:

  1. Start off assuming the maze has walls between every cell on every side:

    _images/maze_init.svg
  2. Construct a set of sets (S) each of which represents an individual cell, and the set of walls between them (W). Below we represent a wall as a set giving the cells it divides (there are more efficient representations, but this is easier to visualize). Note that we are only interested in walls dividing cells, not the exterior walls or walls that divide diagonally:

    \begin{aligned}S &= \{\{1\}, \{2\}, \{3\}, \{4\}\} \\
W &= \{\{1, 2\}, \{1, 3\}, \{2, 4\}, \{3, 4\}\}\end{aligned}

  3. Knock down a random wall where the cells either side of the wall don’t belong to the same set in S, and union together the sets in S containing the cells that have just been joined.

    \begin{aligned}S &= \{\{1, 3\}, \{2\}, \{4\}\} \\
W &= \{\{1, 2\}, \{2, 4\}, \{3, 4\}\}\end{aligned}

    _images/maze_during.svg
  4. Continue doing this until a single set remains in S, containing all cells. At this point any cell must be reachable from any other cell and the maze is complete; W will contain the set of walls that need to be rendered:

    \begin{aligned}S &= \{\{1, 2, 3, 4\}\} \\
W &= \{\{3, 4\}\}\end{aligned}

    _images/maze_final.svg

Here’s the implementation, with the actual drawing of the maze split out into its own function:

def generate_maze(width, height, colors):
    walls = generate_walls(width, height)
    maze = ps.array(shape=(2 * height + 1, 2 * width + 1))
    maze[...] = colors['unvisited']
    maze[::2, ::2] = colors['wall']
    for a, b in walls:
        ay, ax = a
        by, bx = b
        y = 2 * by + 1
        x = 2 * bx + 1
        if ay == by:
            maze[y, x - 1] = colors['wall']
        else:
            maze[y - 1, x] = colors['wall']
    maze[0, :] = maze[:, 0] = colors['wall']
    maze[-1, :] = maze[:, -1] = colors['wall']
    maze[-2, -2] = colors['goal']
    return maze
def generate_walls(width, height):
    # Generate the maze with Kruskal's algorithm (there's better
    # choices, but this is a simple demo!)
    sets = {
        frozenset({(y, x)})
        for y in range(height)
        for x in range(width)
    }
    walls = set()
    for y in range(height):
        for x in range(width):
            if x > 0:
                # Add west wall
                walls.add(((y, x - 1), (y, x)))
            if y > 0:
                # Add north wall
                walls.add(((y - 1, x), (y, x)))
    for wall in sample(list(walls), k=len(walls)):
        # For a random wall, find the sets containing the adjacent cells
        a, b = wall
        set_a = set_b = None
        for s in sets:
            if {a, b} <= s:
                set_a = set_b = s
            elif a in s:
                set_a = s
            elif b in s:
                set_b = s
            if set_a is not None and set_b is not None:
                break
        # If the sets aren't the same, the cells aren't reachable;
        # remove the wall between them
        if set_a is not set_b:
            sets.add(set_a | set_b)
            sets.remove(set_a)
            sets.remove(set_b)
            walls.remove(wall)
        if len(sets) == 1:
            break
    assert len(sets) == 1
    assert sets.pop() == {
        (y, x)
        for y in range(height)
        for x in range(width)
    }
    return walls

At this point we should have a fully functioning maze game that looks quite pretty. You can play it simply by running main(). Once you’ve verified it works, it’s a simple matter to switch out the joystick for the IMU (in exactly the same manner as in Simple Demos). Here’s the updated moves function which queries the IMU instead of the joystick:

def moves(imu):
    for reading in imu:
        delta_x = int(round(max(-1, min(1, reading.accel.x))))
        delta_y = int(round(max(-1, min(1, reading.accel.y))))
        if delta_x != 0 or delta_y != 0:
            yield delta_y, delta_x
        sleep(1/10)

Finally, it would be nice to have the game run in a loop so that after the winners screen it resets with a new maze. It would also be nice to launch the script on boot so we can turn the Pi into a hand-held game. This is also simple to arrange:

  • We need to put an infinite loop in main to restart the game when it finishes
  • We need to add a signal handler to shut down the game nicely when systemd tells it to stop (which it does by sending the SIGTERM signal; we can handle this with some simple routines from the built-in signal module).

Here’s the final listing with the updated lines highlighted:

examples/maze_final.py
import numpy as np
import pisense as ps
from random import sample
from colorzero import Color
from time import sleep
from signal import signal, SIGTERM


def sigterm(signum, frame):
    raise SystemExit(0)


def main():
    signal(SIGTERM, sigterm)
    width = height = 8
    colors = {
        'unvisited': Color('black'),
        'visited':   Color('green'),
        'wall':      Color('white'),
        'ball':      Color('red'),
        'goal':      Color('yellow'),
    }
    with ps.SenseHAT() as hat:
        while True:
            maze = generate_maze(width, height, colors)
            inputs = moves(hat.imu)
            outputs = game(maze, colors, inputs)
            display(hat.screen, outputs)


def moves(imu):
    for reading in imu:
        delta_x = int(round(max(-1, min(1, reading.accel.x))))
        delta_y = int(round(max(-1, min(1, reading.accel.y))))
        if delta_x != 0 or delta_y != 0:
            yield delta_y, delta_x
        sleep(1/10)


def display(screen, states):
    try:
        for anim, data in states:
            if anim == 'fade':
                screen.fade_to(data)
            elif anim == 'zoom':
                screen.zoom_to(data)
            elif anim == 'show':
                screen.array = data
            elif anim == 'scroll':
                screen.scroll_text(data, background=Color('red'))
            else:
                assert False
    finally:
        screen.fade_to(ps.array(Color('black')))


def game(maze, colors, moves):
    height, width = maze.shape
    y, x = (1, 1)
    maze[y, x] = colors['ball']
    left, right = clamp(x, width)
    top, bottom = clamp(y, height)
    yield 'fade', maze[top:bottom, left:right]
    for delta_y, delta_x in moves:
        if Color(*maze[y + delta_y, x + delta_x]) != colors['wall']:
            maze[y, x] = colors['visited']
            y += delta_y
            x += delta_x
            if Color(*maze[y, x]) == colors['goal']:
                yield from winners_cup()
                break
            else:
                maze[y, x] = colors['ball']
                left, right = clamp(x, width)
                top, bottom = clamp(y, height)
                yield 'show', maze[top:bottom, left:right]
    yield 'fade', ps.array(Color('black'))


def generate_maze(width, height, colors):
    walls = generate_walls(width, height)
    maze = ps.array(shape=(2 * height + 1, 2 * width + 1))
    maze[...] = colors['unvisited']
    maze[::2, ::2] = colors['wall']
    for a, b in walls:
        ay, ax = a
        by, bx = b
        y = 2 * by + 1
        x = 2 * bx + 1
        if ay == by:
            maze[y, x - 1] = colors['wall']
        else:
            maze[y - 1, x] = colors['wall']
    maze[0, :] = maze[:, 0] = colors['wall']
    maze[-1, :] = maze[:, -1] = colors['wall']
    maze[-2, -2] = colors['goal']
    return maze


def generate_walls(width, height):
    # Generate the maze with Kruskal's algorithm (there's better
    # choices, but this is a simple demo!)
    sets = {
        frozenset({(y, x)})
        for y in range(height)
        for x in range(width)
    }
    walls = set()
    for y in range(height):
        for x in range(width):
            if x > 0:
                # Add west wall
                walls.add(((y, x - 1), (y, x)))
            if y > 0:
                # Add north wall
                walls.add(((y - 1, x), (y, x)))
    for wall in sample(list(walls), k=len(walls)):
        # For a random wall, find the sets containing the adjacent cells
        a, b = wall
        set_a = set_b = None
        for s in sets:
            if {a, b} <= s:
                set_a = set_b = s
            elif a in s:
                set_a = s
            elif b in s:
                set_b = s
            if set_a is not None and set_b is not None:
                break
        # If the sets aren't the same, the cells aren't reachable;
        # remove the wall between them
        if set_a is not set_b:
            sets.add(set_a | set_b)
            sets.remove(set_a)
            sets.remove(set_b)
            walls.remove(wall)
        if len(sets) == 1:
            break
    assert len(sets) == 1
    assert sets.pop() == {
        (y, x)
        for y in range(height)
        for x in range(width)
    }
    return walls


def clamp(pos, limit, window=8):
    low, high = pos - window // 2, pos + window // 2
    if low < 0:
        high += -low
        low = 0
    elif high > limit:
        low -= high - limit
        high = limit
    return low, high


def winners_cup():
    r = Color('red')
    y = Color('yellow')
    W = Color('white')
    yield 'zoom', ps.array([
        r, r, W, y, y, y, r, r,
        r, r, W, y, y, y, r, r,
        r, r, W, y, y, y, r, r,
        r, r, r, W, y, r, r, r,
        r, r, r, W, y, r, r, r,
        r, r, r, W, y, r, r, r,
        r, r, r, W, y, r, r, r,
        r, r, W, y, y, y, r, r,
    ])
    sleep(2)
    yield 'fade', ps.array(r)
    yield 'scroll', 'You win!'


if __name__ == '__main__':
    main()

Now to launch the game on boot, we’ll create a systemd service to execute it under the unprivileged “pi” user. Copy the following into /etc/systemd/system/maze.service:

examples/maze.service
[Unit]
Description=The Sense HAT Maze IMU game
After=local-fs.target

[Service]
ExecStart=/usr/bin/python3 /home/pi/maze_final.py
User=pi

[Install]
WantedBy=multi-user.target

Note

You’ll need to modify the path for ExecStart to point to the location of your maze_final.py script.

Finally, run the following command line to enable the service on boot:

$ sudo systemctl enable maze

If you ever wish to stop the script running on boot:

$ sudo systemctl disable maze