Saturday, September 20, 2014

Triangulated circular maze generation

Always in the way to find new ways to proceduraly build dungeons and mazes, here the circular maze.

You can find many demos on internet showing circular maze generation, but my own is original and has many benefits:
- it is triangulated with Daedalus Lib, so pathfinding can be used directly
- it has several parameters

But more than words, there is a playable demo :

The build random button allows you to generate new mazes very easily.

So now, if you are interested by the method, just read the rest.

Step 1:
We start from a basic rectangular mesh with Daedalus Lib.

Step 2:
We add concentric circles as constrained edges in the mesh. We start with the smallest circle using min radius parameter. Then we continue with larger circles, increasing the radius with dist circles parameter each times. The circles has edge counts being the maximum possible, but keeping edges length larger than min len edge parameter.

Step 3:
We connect the circles with constrained edges from vertex to vertex.

Step 4:
We start from any point and we explore the set of constrained edges with a custom pseudo randomized depth-first-search algorithm (use the seed parameter). We keep only the traversed edges and build a new mesh from them.

At this step, the result show us the navigation path of our maze.

Step 5:
We add central edges in addition to our previously generated navigation path. It makes the center an important place in the maze.

Step 6:
Finally we apply a chamfer algorithm.

Here is the result with high values: