My son wants labyrinths. Ok, let’s make them like it’s the first semester.
We need a class Labyrinth that holds the dimensions of our maze, and the actual maze, in grid - a List of Lists of integers. That’s not exactly a two-dimensional array (it can have a ragged right edge), but it will do for us.
A basic container for labyrinths
The integer Zero will indicate an unused cell. We then use bits to store passages to the four cardinal directions: 1 for a passage to the North, 2 for a passage to the East, 4 for a passage to the South, and 8 for a passage to the West.
When making a passage, we will need to tear down the wall in the current cell, and we will need to tear down the wall in the new cell, making a backwards passage. One could say that our maze is an undirected graph, and making passages connects the vertices forward and backward.
We will need to work with positions, and we define a type for that: A position is a Pos, a two-tuple of integers.
We will also need to work with the cardinal directions, and make a type for that: A direction is a Direction, a string. We will also make use of a number of things from random.
Using this, we can define a few useful things that we will be using a lot. Our bits to encode passages, for example:
Also, the back-connections, because we want an undirected graph of passages:
And we need to be able to translate a Direction into a change in coordinates, in order to be able to step:
We can now initialize our class:
Some basic Python wiring
We will probably suck and need to be able to dump a labyrinth object, so let’s build a __repr__() for it. If you have an instance and print it, Python will try to invoke __str__() for a human readable representation of the object. If that does not exist (or we print(repr(l))), Python will try __repr__() instead. This is supposed to produce a debug representation of a thing.
So let’s make one:
Our Labyrinth is mostly a container for these integers representing cells, with a bit of sugar on top. Let’s make the cells directly accessible:
I can now make me a l= Labyrinth and then p = Pos((10, 10)) and print(l[p]) to print a single element at position (10, 10). Python will invoke the __getitem__() with this Pos tuple and return me the element. Likeweise I can assign to l: l[p] = 10, and that will invoke __setitem__() with the proper parameters.
Some important predicates
The predicate position_valid() is still missing, and we will need similar things for Directions, too.
Let’s make them:
We also build a getter, directions() that returns the directions from the _directions bit encoder array above, and the same thing randomized under the name of random_directions(). We grab the list and apply Pythons shuffle().
Stepping into the Labyrinth
We now can make a step(pos, direction), which takes one Pos, and makes a step into the given Direction.
The new position is guaranteed to be valid. We will raise ValueError for all invalid things - wrong parameters, and wrong results. Some of them may arguably be IndexErrrors instead, but I actually have little need for this distinction here, and it will only make the code more complicated later on.
Tear down a wall
Now I can build me a function that makes a passage from a given Pos, into a given Direction:
It may also be useful to have this as a predicate can_make_passage(), which returns true if I can make a passage that is not there, yet.
This raises exceptions for invalid input values. It will return False for passages that would lead off grid, and also returns False is this is not a new, but already existing passage.
Now we can pretty easily and concisely write down a tunnel digging algorithm that will build us a fully connected labyrinth, a random minimal spanning tree for the grid.
At this point it is a subclass of Labyrinth, but it really should be a strategy of Labyrinth instead. Python on my system has a default recursion nesting limit of 1000, so the longest path can be 1000 steps until we overflow the stack. This is good for a 31x31 grid at best, and we would need to change sys.setrecursionlimit(new_value) for more.
What we have here is a function carve() that will dig a tunnel, starting at pos. If no pos is given, we default to the origin (0,0).
For the current position, we will check all possible directions in random order: can we step there? If so, we break down the walls and make a passage, then step there and recurse.
We have provided the option to supply a callback function show= (for which we skimped on the typing, tsk, tsk!). If such a function is supplied, we call it with the old and the new position as parameters. We need to make sure to pass on the show= function, if there is one, when we recurse.
Here is a labyrinth generation in progress:
Painting the labyrinth
Our Labyrinth Painter uses Pygame. It draws cells that are size= wide, and are framed with line_width= thick lines.
We start pygame, and make us a surface in a window:
We then implement a show function, which draws a bunch of squares in funny colors:
A square needs to find out what color it should be in, and then needs to be drawn. For that we need corners: North-East, North-West, South-East, and South-West.
We do not really have many dependencies on Labyrinth: Element access, and we should really use direction names instead of raw bits for decoding here.
Nothing of this will be visible until we call flip(). For debugging, we provide the flip() as part of two waiting functions:
The first function checks the Pygame event queue for a QUIT event (close button on the window has been hit) or an ESC key press. If either of them happened, we exit the program. Otherwise we delay a bit (and should make this a settable parameter).
The second method busy waits on a space bar press (and also allows quitting) before it continues. It will allow us to step through the program and observe how everything works at our leisure.
A small driver that puts everything together:
We make ourselves a labyrinth instance, and a painter instance. We define a starting position in the middle of the field, then start the carver with a callback. The callback will be activated by the carve() function with the old position pos as red and the new position np as green square. Untouched squares will show up in black, and carves squares will be shown in light blue.
In the end we display the final labyrinth, showing two random positions as start and end position. This will work because our labyrinth is an undirected minimal spanning tree of the grid, so any two positions are connected by exactly one path.
We can rewrite the original carve() function to not use recursion. It will look almost the same:
Instead of recursing we here have a local stack stack. On this stack we put pairs of (pos, directions): For each position we remember the directions at this position that still need checking. We prime this with the starting position and the full list of all four cardinal directions, randomly shuffled.
We then pop us the current work item, and check if there are still directions we have not processed (there are, we just started). We consume one, and try to go there. If this is a legal position to be in, and the position is empty (0), we tear down that wall.
Now we push this position and the remaining directions sans the one we just checked back. Then we add the new position and all four directions properly shuffled on top of that. Finally we break out of the while directions: loop.
This will move us to the outer loop, where we pop the new position and start working on that one: A depth-first search.
Our stack list is not subject to sys.recursionlimit and so we can process larger grids. We still use the same amount of memory: we remember the same things. On a 100x100 grid, the theoretical longest possible path is 10000 steps long and that would be the biggest possible stack for that grid.