Sideband #49: A Mazing Python

I don’t know if it’s having been in the saddle so long, having all this retirement time, or the magic of Python (perhaps all three), but I’ve made major advances in personal projects that have been on my drawing board for a very long time. One of them, in fact, goes back to my earliest days of programming in late 70s!

It’s certainly true that 35 years of writing computer software teaches you a few tricks. At the very least, you learn all sorts of things not to do! On some level, the computer language doesn’t matter, but a highly expressive language makes some kinds of development not just easier, but actually fun!

And Python! I haven’t laughed with delight over a computer language since Lisp!

The delight comes from reading the language manual and learning about some amazing new feature of the language. Imagine a carpenter who has only ever used saws and hammers until the day he gets one of those all-in-one workbenches.

It boils down to elevating the work above the tedious, unchanging parts — the “scut work” —so you can focus on the design. (That’s what this xkcd comic is getting at.)

The project that goes back to the earliest days of computer programming is writing a chess move parser. I don’t mean the modern “B2-D4” kind of moves; I mean the old-fashioned “Pawn to  King-4” kind. For clarity, I just quoted the way it would be spoken. It would be written as “P-K4”, and that’s what I wanted to write a parser for.

I’ve always been fascinated by that protocol, in part because it’s ambiguous. In the move above, there is no explicit indication which Pawn is moved. It depends on the state of the game. In fact there is no ambiguity: the move protocol requires that only one Pawn fit the move description.  When more than one piece qualifies, the piece must be named explicitly, for example: “King Pawn to King-4” (KP-K4).

Time, experience, celestial juxtaposition and/or Python finally let me crack that nut! (I was going to just mention it in passing and be done with it, but I think it’s worth its own article. That frees me to get more into the next topic! (See, I do keep your attention span and free time in mind when I write!))

Another ‘what is the software like’ fascination that goes way back involves mazes. There’s a natural marriage between mazes and computer software in several regards.

Firstly, all mazes reduce to an important, general mathematical object, called a graph.

The word is the same, but doesn’t in this case refer to a chart, like a bar chart or XY chart, which are often called graphs.

In mathematics, a graph is a collection of points and lines connecting those points. (In graph theory, the points are called vertices, and the lines are called edges.)

So mazes are mathematically cool, is the point, and computer software is really just a kind of super-advanced logical math, so that’s a good solid marriage right there.

The left-hand rule takes the long way but gets there.

Secondly, for a very common type of maze, there is a simple (if tedious) process that is guaranteed to find a path through the maze. It’s called “the left hand rule.” As you enter the maze, put your left hand on the left wall and keep it there; never remove it. Now walk the maze (keeping your left hand always on the left wall).

You’ll be forced into plenty of dead-ends, but tracing the left wall always leads you back out. Eventually you trace the “left side” of the maze and end up at the exit. (There is a type of maze design that defeats this process and either returns you to the entrance or puts you on an infinite round and round loop.)

Computers are brilliant at simple, tedious tasks, so maze-walking algorithms (the computer term for “process”) are another great fit.  Writing the algorithm is part of the fun, but the real fun (and eventual goal) is some kind of visual display that lets you watch the maze be walked. And if you could do that in 3D and have the maze be 3D… well, I think that would be very cool to watch.

[A lot of the code projects I take on are for the challenge of solving the coding problem, but the end result is also part of it. There’s always a tool, toy or interesting thing that comes out the end. There’s the fun of coding, but also the fun of making stuff!]

For grins I tried a 100×100 matrix, and it worked!
[click for big]

Start with a maze that is fully blocked and has no paths from any point to any point. Begin at the beginning and create a random path connecting some series of points. Change direction randomly at random intervals and place a random limit on how long the path can be. If you hit a wall or existing path and can’t turn from it, stop.  Or if you hit the limit stop.

Such a path won’t find the exit, and it’s not intended to. It’s just the first branch of paths into the maze. Now comes the interesting part.

Iteratively consider the existing paths made so far and randomly pick one. Randomly pick a point along that path, and branch out to start cutting a new path. Follow the same rules as the first path.  In fact, the first path is just the special case first time through of this general process when there are no other paths to consider.

Output of the first trial of a “path cutter,” which produced a very good first path! It changed direction several times and finally stopped when it hit the north wall.

The process is a bit more detailed than that, but understanding how the maze is represented is crucial. Three matrices comprise the maze data structure. The first represents the points in the maze (the vertices of the graph). When you move from one point to another in the maze, you move from one cell to another in this matrix. The other two matrices represent the “doors” between cells. One represents the north-south doors, and the other the east-west doors.

The reason for the split comes from not wanting to model the same door in both connecting cells. The naive way to model the maze is to use the base matrix and give each cell four doors. The problem is that opening a path between two cells means opening the door on both sides. It would be like those hotel rooms that have double-doors connecting them.

That’s fine if you want to model that, but I didn’t. I wanted a single door between cells that was shut or open, and I didn’t want to have to synchronize doors between cells.  In viewing north-south doors separate from east-west doors, you end up with two nice matrices, one of them shy a row, the other shy a column.

More importantly, you have a fixed mathematical relationship between any cell’s row and column and that cell’s four doors:

1. North door = NS_Doors[row-1, col  ]
2. South door = NS_Doors[row  , col  ]
3. West door  = WE_Doors[row  , col-1]
4. East door  = WE_Doors[row  , col  ]

This makes opening and closing doors in the maze much easier!

The next step was to give it the ability to change direction when it hit a wall or an existing path. This turned out as hoped for also!

The end result is that we have one matrix that defines the size of the maze and tells us which cells have been explored and which have not, and we have two matrices that tell us whether doors are open or not. In all three cases we can use simple zero or non-zero values to provide “yes/no” states, or we can use numbers to represent multiple states.

A 3D maze is possible by adding another doors matrix for “up/down” doors. ! I haven’t done that yet, but it’s on the drawing board.

Going back to the details of the process, it starts with all cells unexplored and all doors closed. The “path cutter” picks a direction (which we assume has a closed door). If the cell on the other side has not been explored, the cutter opens the door and moves to that cell. It repeats this until it is unable to move or it reaches the randomly chosen limit.

Sometimes, randomly, it turns left or right, if possible. (The cell it wants to move to must be unexplored.) If it hits a door that leads to an explored cell, it must turn left or right. The cutter is never allowed to cut into the existing paths.

An early result suggesting that cutters need to change direction more often. As it turns out, best results seem to come from having them consider a direction change almost constantly.

The walls surrounding the maze have no doors, so if the cutter hits a wall and cannot turn left or right, it stops. There is also some randomness built into whether it will even try to turn left or right upon hitting a blockage.

The path it cuts it records as a list of (row,column) coordinates and stores in a list of paths. It is from this growing list of previous paths that each new cutter randomly selects a path on which to start. Once selected, the cutter randomly picks a (row,column) pair from the list as its starting point.

It’s possible the starting point doesn’t allow a branch. What the cutter has really done is taken the list of path coordinates from its randomly selected path and randomly shuffled them into a new list. It uses this list, starting with the first coordinate. If no branch is possible, it picks the next and so on until it finds a branch point.

Of course, maybe the entire path has no available branch point, so the new cutter returns to the list of paths and picks a new one. In fact, again, what really happens is that the cutter shuffles the list of paths and works it way down the shuffled list until it find a path with a branch point.

Seeing this pop up, I’m telling you, it was like a little mini-dream come true after decades dormancy!

This process guarantees that all cells get explored, and that the result is a fully connected graph. That is, from any point in the maze, you can get to any other point. And, of course, this also guarantees that there is a path from the entrance to the exit.

In retrospect, it almost seems obvious, but at the time it was astonishing to see how well it worked.  Truly a surprised, gleeful, laugh out loud moment when the first complete maze popped up!

This has gotten to be one of my longer articles, and I’ve really only just introduced the topic. If anyone is interested, I’m more than willing to get into details, either in the comments here or in another article. For now, this suffices as an introduction and overview.

But wait! There’s more! I’m making the Python code, and a number of mazes for you to play with, available for download.  You’ll find them here:

Stay amazing, my friends!