I stumbled over an interesting book recently which inspired me to code up a simple python implementation to generate some mazes for my son to play around with.

I took the opportunity to use some lesser known python features and tried to solve most problems myself (instead of relying on the book to guide me).

The Algorithm I chose to implement first is the so called “growing tree” algorithm. It is really simple (and already discussed in many places). It is kinda nice because it can be parametrized to mimic different algorithms. But let’s start with the fun part first…

Rendering a maze

As you might know there are box drawing characters in unicode. So far so good. But how do we use these to draw a maze?

When thinking about how to represent the paths in a maze and the walls between them, you realize that Directions seem to be the right concept. So let’s start with some simple code …

from enum import Enum, auto

class Direction(Enum):
    N = auto()
    S = auto()
    W = auto()
    E = auto()

Sadly this does not allow us to describe walls in more than one direction. And if you look at the unicode box drawing characters ╶ ╴ ╷ ╵ └ ┌ ┘ ┐ ─ │ ┴ ┬ ┤ ├ ┼ you realize that they describe walls in any combination of directions. So we need to use a fancier enumerator:

from enum import IntFlag, auto

class Direction(IntFlag):
    N = auto()
    S = auto()
    W = auto()
    E = auto()

This allows us to describe combinations of directions

ALL = Direction.N | Direction.W | Direction.E | Direction.S
NOT_SOUTH = ALL & ~Direction.S

and so on. So we can in fact use a property to integrate the box drawing characters directly into the enum.

from enum import IntFlag, auto

class Direction(IntFlag):
    NONE = 0
    N = auto()
    S = auto()
    W = auto()
    E = auto()
    ALL = N | S | W | E

    @property
    def char(self):
        """
	if you represent walls as directions, 
	this property returns the appropriate unicode box 
	drawing char
	"""
        if self == Direction.E:
            return '╶'
        if self == Direction.W:
            return '╴'
        if self == Direction.S:
            return '╷'
        if self == Direction.N:
            return '╵'
        if self == (Direction.N | Direction.E):
            return '└'
        if self == (Direction.S | Direction.E):
            return '┌'
        if self == (Direction.N | Direction.W):
            return '┘'
        if self == (Direction.S | Direction.W):
            return '┐'
        if self == (Direction.E | Direction.W):
            return '─'
        if self == (Direction.N | Direction.S):
            return '│'
        if self == (Direction.ALL & ~Direction.S):
            return '┴'
        if self == (Direction.ALL & ~Direction.N):
            return '┬'
        if self == (Direction.ALL & ~Direction.E):
            return '┤'
        if self == (Direction.ALL & ~Direction.W):
            return '├'
        if self == Direction.ALL:
            return '┼'
        if self == ~Direction.ALL:
            return ' '

If you are using Python 3.10 or newer, this should probably be implemented with match / case to be a little less verbose. But anyways, now we can do something like

>>> (Direction.S | Direction.W).char
'┐'

Internally the values created by auto() are simply integers with a binary representation that has a 1 at the appropriate location. So the first value is 1 the next 2, then 4 and 8. If we want to check if a certain direction is set in a “combined” value we need to therefore use binary operations.

SW = Direction.S | Direction.W
contains_west = (SW & Direction.W) == Direction.W
assert contains_west

This is tedious to write over and over, so we can integrate it into the Direction class.


class Direction(IntFlag):
    ...

    def __contains__(self, item):
        """check if flag is set"""
        return self & item == item
    ...

This allows us to check like so

assert Direction.W in Direction.ALL

Note that simply checking for “truthy” or “falsy” evaluation of the expression like e.g. bool(Direction.ALL & Direction.W) will work for all cases except the case where you want to check if no flag is set.

query: Direction = create_mystery_direction()

print(Direction.NONE in query) # this will return True if no flag is set
print(bool(Direction.NONE & query)) # this will return False

Now the hardest part is done. We now simply have to generate a grid of directions (representing the paths in our maze). Then we loop over possible “wall junctions” and see in which directions the paths of the surrounding cells in the grid lead.

Example Maze

Here the thick lines represent walls, the cells show in which directions they have paths (note that having a path between two cells is a symmetric relation, so the cells that are not at the “ends” of this maze have paths in two directions respectively) and the marked locations are “wall junctions” where we might have to draw a box drawing character. To make things easier, let’s extend the maze by one “virtual” cell in each direction.

Example Maze Extended

Now, to see which box drawing character we have to draw at the marked location, we simply check

  • If the south east cell has a path in Direction.W (west)
  • If the south east cell has a path in Direction.N (north)
  • If the south west cell has a path in Direction.N (north)
  • If the north east cell has a path in Direction.W (west)

For each case, we add the appropriate wall if no path exists. So it might look something like this to calculate the box drawing char for a single junction location

def wall(cell, direction: Direction):
    return direction not in cell

walls = Direction.NONE

for direction, cell in neighbors(junction):
    if direction == (Directions.S | Directions.E) and wall(cell, Direction.W):
	# south east cell, with wall to west direction, add southern wall to junction
	walls |= Direction.S

    if direction == (Directions.S | Directions.W) and wall(cell, Direction.N):
	# south west cell, with wall to north direction, add western wall to junction
	walls |= Direction.W

    # continue for other cases
    ...

print(walls.char)

How the grid gets generated may be a topic for a future post, but you might also look at my implementation or search for codestare-maze on PyPi.