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.