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: http://www.neocomputer.org/projects/eller.html
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
Top-down view