Amazing

It turns out that the algorithms for creating a maze are quite diverse and complicated - wikipedia has much on this.

Basically, I have done it again - I found something that looks cool on thingiverse and decided to take it to the limit and do it myself. The thing was a simple labyrinth box. It was quite cool.

So I thought I would give it a try, and the issue is not really the actual 3D artwork and OpenSCAD stuff, it is the maze itself. How to make a maze that is challenging. Instead of a fixed thing that has a maze, I wanted a random maze so each one is different. OpenSCAD cannot quite manage that. So I used the source (Luke) and wrote C to make OpenSCAD.

The first thing is that this maze inherently wraps, i.e. mostly a maze is in a simple rectangle, but this is on a cylindrical shape so the X axis wraps. Easy enough for the maze generation logic.

My initial thought, and how I have made mazes before, is you have a path from origin and a point moves randomly where it can (i.e. to an empty cell). If it finds it cannot move at all it back tracks. This is a very simple algorithm to fill the whole space of a maze with no loops. The "no loops" part is pretty common as a basic principle. Maybe I'll deliberately throw in a loop some time.

My concern was that this made a maze that was going to be too simple. Or that did not "look nice", so I added a few variations.

For a start, when moving, I made a bias to continuing in a straight line rather than left or right. 25% of the time it continues, else it is random (including continuing). This makes for nice long runs in the maze.

I then added a bias for back-tracking even when not a dead end. This did make the maze more interesting but created a lot of one unit blind dead ends which are annoying and boring. You want your blind dead ends to be "interesting" and so long.

So I started again and made it that a set of all cells in the maze with somewhere to go, are picked from at random to continue the maze. This is not following the last point and backtracking, it is saying we have a set of points that can move, and picking one and moving.

This created a lot of short blind paths, hmmm... OK next trick was to add a random bias to use the last added point and continue from there, but not all of the time (just 75%). This made much longer blind runs which is what I wanted. I actually made it wander like this 100% initially until it hit a dead end or the top layer, then 75% leaving 25% of the time it picks any node at random to continue from making a fork.

Finally the trick was to then make the exit at the top the cell where it is the longest path from the start. This helped avoid accidentally having a straight line from start to finish or something that simple.

I am actually quite pleased with the result, which you can find at thingiverse. It is interesting how slight biases and choice of algorithm can massive change the nature and appearance of a maze.

P.S. You will note that there are a number of example STL files on that thingiverse entry. Obviously, as I have been tinkering, changing the artwork slightly, and changing the maze design logic slightly, I have wanted to update the thingiverse entry. But this is a set of about 10 designs as examples, so a tad tedious to load each one in to OpenSCAD and make an STL file. Thankfully OpenSCAD (even on a Mac) has a command line option, so with a simple script (and waiting several minutes) I can make a set of files automatically!

P.P.S. I did do a bit more tinkering, not just the artwork (changing from round to polygonal outer shape), but also to the maze. The one "knob" in the lid was not that good so I made the maze mirror on to the other side so allowing two knobs - this simply means as I generate the maze I add the same to the far side, but the maze can still going around the cylinder interacting with its other self even. I made it general to allow N paths. I also tweaked the bottom (end point) of the maze to be a right angle. I even scripted rendering several random boxes to make a video :-



Update: I had a call to make the maze more complex. One of the simple steps I did is, as you progress the maze, for each cell, you also have an indication of "length" which is how far from the start, increasing one each time. Then, for the exit at the top layer I pick the point with the greatest length.

However, this is not quite enough, and so I changed the logic to start the maze in the middle, and pick both the entry and exit as longest from that point. Unfortunately this allowed a common path from the start point and then a short path to entry and exit. But it did seem to make a more interesting maze overall.

The solution is creating the maze then working out the start point and exit point that create the "best" path. I decided simple length is not good enough, we want complexity. Scoring is therefor also based on how many branch points we pass as well as length.

I also made the middle a ring all the way around on the taller mazes to make a staging point where you had lots of possible options to escape, all but one of which are wrong.