Wednesday, 21 June 2017

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.

8 comments:

  1. Have you seen https://pragprog.com/book/jbmaze/mazes-for-programmers?

    ReplyDelete
  2. It's impressive how short your lead time is between looking into something new and actually managing to make it work. I'd be dicking around with any one of these throwaway ideas of yours for months.

    ReplyDelete
    Replies
    1. Thanks. Once I get in to a daft idea like this I do tend to spend all day on it, and not happy until it is finished.

      Delete


  3. Isn't this is a 'Maze Box'? A labyrinth has a single, linear, but highly convoluted path, whereas a maze has branches, dead ends, etc.

    Of course like all the best words, the original labyrinth, from which we get the word, was not in fact a labyrinth. Bit like stonehenge not being a henge.

    In any case the boxes look brilliant. Easily the closest I've come to seeing something that might make me want to get a 3D printer...

    ReplyDelete
    Replies
    1. A fair point - I was going by the name on the original thing... Glad you like it.

      Delete
  4. I love your design. Great work!
    Any chance that you will release the "c" source code for this scad generator?
    It would be educational to see how you did it as opposed to the generated scad files themselves.
    By the way, I love the way you integrated your sig double "a" into the lid.

    ReplyDelete
  5. Very interesting!
    Your generated scad files are elegant.
    Any chance that you could explain how your "puzzlebox.cgi" script generates the random mazes?

    ReplyDelete