The Labyrinth Algorithm
Summary
The Labyrinth Algorithm is a custom algorithm that combines many sophisticated procedural generation techniques and blueprints to create vast, contigious, and interconnected dungeons. The algorithm utalizes 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
**Gameplay Demo Coming Soon**
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 contigiously. |
| 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 purley 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. |