Labyrinth Generation


Randomly generated labyrinth in Minecraft

I’ve been making mods for Minecraft for a long time but now I started a bigger project called The Elysium. It’s a good opportunity to try out new methods and algorithms.

I came up with the Labyrinth idea recently based on Greek Mythology. A randomly generated Labyrinth System stretching out bellow the whole dimension. This holy dungeon would hold captive the fallen heroes of The Elysium. Sounds cool, huh?

A Minecraft world is made up of chunks (16×16 blocks) so I decided to generate a separate maze for every chunk and connect them together somehow.

After a little bit of research I realized that I have to make Perfect Mazes. It means that any two points are connected by exactly one path (without any loops, and inaccessible areas). Because of these properties two adjacent mazes can be connected anywhere. For the sake of simplicity and design I decided to connect them at the middle. As a result there are more possibilities to move from one point to another making it a little less unsettling.

The Algorithm

Now I had to find an algorithm suitable for my problem. Fortunately I came across this page which described a lot of different algorithms with its properties. Here are some I considered:

Algorithm Dead End % Type Focus Bias Free? Memory Time Solution %
Binary Tree 25 Set Either no 0* 7 2.0
Sidewinder 27 Set Either no 0* 8 2.6
Eller’s Algorithm 28 Set Either no N* 10 4.2 (3.2)
Kruskal’s Algorithm 30 Set Either Yes N^2 32 4.1
Prim’s Algorithm 36 (31) Tree Either Yes N^2 21 2.3

Since I have to generate an “infinite” number of small labyrinths, I choose Eller’s algorithm for this task. It has very minimal memory need and very fast (linear time complexity) which is crucial for worldgen.

I worked based on this page which helped me understand the algorithm:

The Result

Here are some pictures of the results in Minecraft.

It turned out to make you feel truly lost and mad (so goal accomplished 🙂 ). If you would like to try it yourself you can download it here.

First Person View of the labyrinth

First Person View

Top-down view of the labyrinth

Top-down view