Algorithm for generating Mazes that are fun to play

Hey, everyone!

Recently we added Maze game in Puzzle Hub, and in this post I want to share the approach I took for generating mazes that are fun to play.

This is the second tech post on this blog. If you have any feedback or comments, please contact us on contact@puzzlehub.app. You can check out the first post here.

The goal

The goal was to write an algorithm that efficiently generates maze puzzles which are fun to play. But what mazes are fun to play?

Well, my theory is that the mazes which are fun to play have a nice balance between the length of the solution path (the path from the start to the end), the length of the corridors along the path (a corridor is a part of the path that is surrounded by 2 walls, meaning that you can go only forwards or backwards) and the number of intersections (the points on the path where you can go in at least 3 directions, meaning that you need to make a choice what direction you will take). Let’s explain more:

The length of the solution path is important because it measures how straightforward the solution is. If the path is too short, the solution is way too simple and probably can be solved just by moving greedily in the direction of the end point. If the path is too long, it covers too much of the maze’s area, which results in less space for the “wrong turns”.

The length of the corridors and the number of intersections are what can make or break a good maze, and they are connected with each other. If there are long corridors, there are fewer intersections – and vice versa. Long corridors make a puzzle boring because there are only few intersections at which you need to make a decision what direction to take, so you are mostly moving only forward between two walls. On the other hand, short corridors result in more intersections, but that makes the puzzle too easy because it’s too obvious for the human eye to see which turns are wrong when there are only 3-4 steps in that path. The key is to find a good balance.

Popular algorithms and why they didn’t work

There are many algorithms and resources for maze generation on the internet, however they are mostly basic graph algorithms that don’t take fun into account (and most are written for educational purposes). I tried few of them, but none consistently generated mazes that are fun by the standards listed above. Here is a quick summary:

  1. Depth First Search – too long corridors, boring and easy
  2. Kruskal’s or Prim’s algorithm – too short corridors, easy to solve
  3. Aldous-Broder algorithm – inefficient, puzzles not consistent
  4. Recursive division – didn’t try it, but don’t like the look of the mazes

If you want to read more about these algorithms, I highly recommend checking out this blog.

Depth first search approach

The depth first search algorithm works as follows:

  1. Choose random start position
  2. Set the start position as current and mark it as visited
  3. Randomize the list of neighbours of the current position
  4. For each unvisited neighbour in the list:
    1. Mark the neighbour as visited
    2. Remove the wall between the current position and the neighbour
    3. Set the neighbour as current position

Here is an animation of how this algorithm works in practice:

Notice how the algorithm creates very long corridors because it explores the grid in a depth first manner (thank you captain obvious). It just adds positions to the path as long as it doesn’t hit a wall. This results in boring, easy mazes.

Depth limited search approach

The approach that ended up to work best is based on the depth limited search algorithm. The idea is to fix the problem of DFS by limiting the grid exploration at certain depths. Basically, when we reach a certain depth, we stop exploring that path and enqueue the neighbours of the position where we stopped in a queue. Then we get the next element from the queue and continue with the same process from there. This is slightly different from the standard depth limited search algorithm because we don’t restart the search from the start when the depth limit is reached.

This can be written in two procedures:

DepthLimitedSearch:

  1. Create empty queue
  2. Add a random start position to the queue
  3. While the queue is not empty:
    1. Get start_position from the queue
    2. Run the DepthLimitedSearchRecursive(start_position, 0) procedure

DepthLimitedSearchRecursive(start_position, depth):

  1. Set the start position as current and mark it as visited
  2. Randomize the list of neighbours for the current position
  3. For each unvisited neighbour in the list:
    1. Mark the neighbour as visited
    2. Remove the wall between the current position and the neighbour
    3. If depth < depth_limit
      1. Set the neighbour as current position
      2. Run DepthLimitedSearchRecursive(neighbour, depth + 1)
    1. If depth >= depth_limit
      1. Add the neighbour to the queue

Here is an animation of how this algorithm works in practice:

Notice how when a corridor reaches a certain length, the exploration of that path stops and the algorithm continues from some of the queued positions which are always at a lower depth. By controlling the depth limit, we can control how short or long the corridors of the maze will be.

Choosing nice values for the depth limit

Now that we have some control over the length of the corridors (by adjusting the depth limit), we need to find nice values for it. The way I calculated those values was to create a program that generates 1000 puzzles for each depth limit value in the range of [5% of the grid size, 30% of the grid size]. For each of these depth limit values, the average corridor length and number of interactions was calculated from the generated 1000 puzzles. In the final algorithm, the depth limit is chosen randomly in the ranges that produce the best corridor lengths and number of intersections from the tests. Of course, this is also dependent on the grid size.

Comparison

The following image shows comparison between two solved mazes generated with both algorithms. Notice the long corridors generated from the depth first algorithm, versus the balanced nature of the depth limited approach (along with fine tuned parameters for the rest of the algorithm).

Conclusion

This blog post describes the approach used to generate mazes in Puzzle Hub. It uses a version of the depth limited search algorithm to control the maze’s corridor lengths, which results in mazes that are more fun to solve.

I hope that you found the post interesting. You can send any feedback or questions to contact@puzzlehub.app.

If you want to try the Maze game, download Puzzle Hub from the links below: