The Labyrinth Algorithm

Summary

The Labyrinth Algorithm is a custom algorithm that combines many sophisticated procedural generation techniques and blueprints to create vast, contiguous, and interconnected dungeons. The algorithm utilizes time and memory efficiency, making dungeons with thousands of rooms generate in a matter of seconds. The algorithm is also built to be scalable and robust for future additions and gameplay mechanics.

Gameplay

*Toggle full-screen for the best experience*

Click on "Instant Generation" to generate a new dungeon. Use WASD to move the character. Utilize the console to toggle free cam. Press the tild key '~' to open the console, then type "tfc" and hit the enter key. This will allow you to fly around the map to observe the generated map better. Exit the free cam by repeating the process of opening the console and typing in the command once again.
To generate a new map click on the "Regenerate" button. If the algorithm fails to generate, it will retry running the algorithm. Fail-safes are in place to prevent browser crashes and memory leaks.

1 / 3
2 / 3
3 / 3

Implemented Features

Name Description
Delaunay Triangulation in 3D In two dimensions Delaunay Triangulation is a set of points and triangles that divides a plane into a Voronoi diagram where the triangle's angles are maximized. In three dimensions the plane is now a rectangular prism and the triangles are now tetrahedra. This subdivision algorithm is used commonly in the graphics space for surface rendering but here it is the perfect application for making paths in the dungeon.
Unique Room Placement The first step of the algorithm. Rooms are placed randomly in a specified rectangular volume. This rectangular volume is then used as the basis for the triangulation algorithm. The rooms then become the points that the triangulation must use to subdivide the space.
Prim's Algorithm Once the space is triangulated, Prim's Algorithm is used to find the shortest path between every point. We are left with a minimum spanning tree that contains no cycles; a basis for the rooms to be connected together contiguously.
A* Pathfinding Once the path between each room is determined, A* is used to link the starting and ending room of each edge together to form a sort of hallway between them. Different heuristic functions are used to produce paths with unique behaviors. For instance, the Manhatten function is used for the castle space to make the halls relatively straight while the Euclidean algorithm is used for the mines to make the halls rigid and cave-like.
Drunkard Walker Algorithm An additional algorithm is added to the process to produce additional edges that lead to objectives and rewards. This algorithm is purely random in it's choice of direction. It chooses between one of six vectors for each branch.
Blueprint Room Generation The "Blueprint" is a technique unique to this algorithm. Before a single room is generated, an entire blueprint is generated for the space using all of the techniques described above. The map is subdivided into a grid and each space of that grid can be occupied by a blueprint. Once the full blueprint for a space is generated, it is parsed using recursive descent. Similar to a compiler, the parser recognizes unique shapes and sizes and generates an appropriate room in the space.