Putting the maze to bed...

I have tinkered on and off with the maze box stuff since Christmas, and we have actually found a really good use for the lottery ticket boxes for a small project (more on that after the event).

I have done loads to fine tune the clearance between the lid and the box, with lots of testing (each test takes hours, during which I have other work to do). It is a bit of a trade off - you need the lid to not scrape on the maze, or be too tight to move, but also not be too loose, and you also need to adjust the "nub" a bit and the "ridge" where it parks when complete. All these are now options on https://www.me.uk/puzzlebox anyway, and tested on my TAZ6. I will have to test on a Makerbot Replicator 2 to confirm if they work on the current defaults, or need more tweaks.

I have also gone for three nubs on the maze by default (again, this is a setting), to be more stable, especially as it is now a tad looser. This works well, but means less maze area and so simpler mazes. Even so, I think the new maze logic does create a good puzzle. I find it hard to tell as I don't have any problem solving these, sorry.

I changed the park ridge and nubs to directly calculated polyhedrons to make them the exact correct shape and size and skew to fit the maze, that was a challenge. It is quite fun getting your head around three dimensional geometry though.

Some of the tinkering has been a bit more complex. One of the changes I made was to allow any number of sides on the outer box. It used to insist on a multiple of the nubs - this ensured you could make the maze any way around (e.g. if 3 nubs, any of the 3 ways to start the maze would work). However, I thought it would be more fun to allow for other combinations, so as per the image above, 7 sides and 3 nubs. This means only one of the 3 ways to start will line up with the base at the end. To help, I added a subtle mark on the lid and the maze for alignment as you may be able to see. That was a slight challenge to code as the starting point of the maze could be wrapped around several times compared to the end point, and the combinations of maze inside, outside, both or neither, made for some fun testing.

Also, I found the lettering was not ideal on the ends. I have an option to do a proper chiselled effect (45 degree angle) in to the letters, but you ideally need a thin/fine font. I have made an ExtraThin variant of my 5x9 font for this now - and overall the 5x9 JTD font looks pretty good in 3D print I find.

I also used parallel command to make the sample boxes without trashing my machine in device waits!

All in all I am running out of things to improve. I have one idea which is to do with fonts: I made a bodge to use Noto Emoji if the string starts with top bit set, which is to allow some hearts and rings, but ideally each block of text should use fontconfig to find if the chosen font has the glyph and have fallbacks and make OpenSCAD for each separate block (as OpenSCAD does not seem to allow a list of fonts with fallback). Doing that could also ensure text does not go off the end of the space. Not sure if I'll go that far yet as the text is usually fixed, and I have already added a scale setting.

Apologies to the many people downloading from thingiverse. I have tried to ensure the various versions I have uploaded are all "good" even if they have slight changes, but just a few times I have messed up and only realised when the test print finished. Thingiverse is very slow at deleting and uploading new models, so I am sure it looked wrong at times. I included a "version" box (as shown above) in the uploads for reference. There are a good selection of test boxes on thingiverse but always best to make a new maze yourself as they will all be different. Still loads of accesses, likes, comments and makes on this puzzle, and even some people making the code direct from github (thought some of the comments were verging on trolling).

I was actually surprised to find at least two people selling these on ETSY! I hope they like the new version.

I did have fun making one the right size for an Annoy-A-Tron though - not sure where to put it :-)

Anyway, I have a bit of printing to get done for this small project :-)

Maze complexity

Making a maze is relatively simple, or so you would think. In this case the maze only has one path to get from start to end, and no loops, and all squares are occupied.

Firstly I have to consider what makes the maze "hard" or "easy", and I did a lot on this when I coded the first version of my maze back in 2017. In that case I created random mazes and "scored" them, including factors like how many dead-ends there were. I picked one with a good score.

The issue is that some of the factors are not obvious. E.g. a good factor is how long the solution path is - longer the better, or so you would think. The problem is that the longer the path is, the fewer "squares" on the maze are occupied with dead-ends. The longest path has no dead ends so whilst it takes a while, the maze is ultimately very easy as you cannot take any wrong turns.

Similarly if the path is too short, e.g. straight line from start to end, it is far too easy to find the solution, especially if you can see the maze. So there is a compromise.

The number of dead-ends is also not an ideal metric - you want dead-ends, but they need to be long enough not to be obvious as dead-ends, especially if you can see the maze.

The simple algorithm

The basic algorithm I have used to make mazes in the past is one where we have a current point on the maze (you can start anywhere as ultimately every square is used, and so it will always create a path from any arbitrary start point to any arbitrary end point). You consider the options of moving to an adjacent vacant square, and pick one at random, drawing the maze to that next point. When you find you cannot move you back track until you can. Ultimately you back track to the start and the maze is full.

A minor enhancement is to bias the directional choice. E.g. starting at bottom of maze a bias to go back down can create a maze that has more ups and downs than just random. Similarly, with a wrapped maze (as we have here) a bias to left and right can create long horizontal paths which are fun.

Another minor enhancement is to pick the exit point at the longest path, if that is an option.

However, the algorithm as a whole as a major flaw - because, when you reach a dead-end, you back track until you can move, you are making dead-ends as short as possible. You always back-track as little as possible. The result is a path from start to end which has lots of short and obvious dead ends.

A simple fix

A very simple enhancement was to start two paths in parallel from the start point of solving the maze. This allows two long paths to exist and creates a "wrong direction" from square one, which is not obvious. The trick of picking the longest point for exit helps ensure the longest of these paths is the solution.

A more complex algorithm

I have now come up with a more complex algorithm. This works by having a set (queue) of points, each of which looks at the adjacent empty squares and picks a direction (as before), but the new point is added to the end of the queue of points to consider next. This means the maze spreads out like a tree from the start point. The trick of picking the longest point for exit helps ensure the longest of these branches is the solution.

This does not work in itself, as you create a maze that is way too simple - far too many paths at once means that they have no choice where to go and hence have to be simple. Even picking the direction randomly, the results are all stupidly simple.

When adding the next point to the queue, I can add to the start of the queue (for immediate consideration) or to the end of the queue (considering all other points in the queue first). If added to the start, then it makes for a long path that can travel unimpeded around empty space before the other paths are tried. If added to the end, then the other paths are handle in parallel with the above result. The same decision applies to the current point considering other directions it could take.

This creates an opportunity for a parameter - one that controls a random chance of adding to start or end. I have added this as a maze-complexity setting.

By allowing a bias as to which end of the queue is used, it creates a range of maze complexities. However, even at one extreme, always adding the next point to the start so it can continue (much like the original algorithm) the key difference is what happens when a dead end is reached - in this case the alternative path is the earliest added to the end of the queue, i.e. the longest "back-track" we can do. This alone makes for more complex mazes.

Of course if you push it too far towards short dead-ends you get some very odd mazes...

Needless to say, this makes for more challenging maze puzzles now.