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!