A playable dungeon map generator

Last days I recycled my dungeon map generator and I plugged it to the engine of my proto 61 Cygni.

You can experiment the result below. Generate a map (with custom parameters or randomly) and then click  the "play it" button.

Just for fun, you can directly catch 4 weapons: the shotgun, the machine gun, the plasmagun and the rocketgun ! You will use these to kill the bots ditributed on the level. Additionally, you can run by pushing quickly the UP key 2 times and dodge with LEFT or RIGHT keys quickly 2 times.

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:

A dungeon map generator

I try to find new methods and algorithms to proceduraly build dungeons and mazes. Something that definitevely breaks up with the boring square and rectangular aligned patterns.

Finaly I had interesting results using Daedalus lib, as illustrated in the examples below:

The method I used to generate this map has many interesting properties. These are easier to understand by looking the steps of generation.

Step 1:

We generate a simple Delaunay triangulation. We use an algorithm that iterates through a nxm grid of points and add some of them in the triangulation according to a fixed probability P. With P=1, the triangulation would be a full regulat grid. With P=0, the triangulation would be empty. See a result below with a 20x20 grid and P=0.5 :

Step 2:

Considering the triangluation as a graph, starting from the vertex in the center, we use a custom depth-first algorithm to extract a sub-graph. At depth n, the next node at n+1 is choosen at random among unvisited nodes. Paramaters used are the total nodes count NC, the maximum branch depth BD and the maximum branches count BC. See a result below with NC=24 :

See that sub-graph as the underlying navigation graph of our futur dungeon. Nodes represent rooms and edges represent accessibility bewteen them.

Step 3:

We build the dual of the triangulation. It is similar to the Voronoi diagram but for better results we use the average positions instead of circumcircles centers:

The dual represents the real shape that will be used for the dungeon.

Step 4:

We keep only the dual cells surrounding the previously generated sub-graph at step 2. Then we build a fresh new triangulation from them. Additionally, we dig a door in the edges shared by connected rooms :

Step 5:

Finally we use a chamfer algorithm to add thickness to the walls :

Notice 2 importants properties of the resulting map:

1. It is directly built on a Delaunay triangulation

2: The navigation graph is given

In conclusion, navigation and pathfinding algorithms are ready to use, without any extra cost. It means that AI can navigate efficiently and accurately through the generated map using the pathfinding solution included in Daedalus.

Demo : pathfinding on Delaunay constrained triangulation

A Maze Generator

I did it because it was a test to win a job *. I wrote it in 2 days (the time allowed), without pain.

The main features are:

• choice of the size : both width and height are configurable

• a pseudo random number generator (PRNG) allows you to deterministically generate a wide set of mazes (one seed for one maze). An easy solution for this is to use a hash algorithm (like md5) ; but I chose to code one from scratch. The solution I used was the combination of a middle square method and a big array (~#500) of random pre-drawed values. By this way I had a short simple algorithm with a decent period.

• 6 types of pattern. Each "simulating" a kind of environment. At first you will recognize the very famous classic labyrinth approach. Then the "noisy" is just the way I used to intensely test my PRNG. The "lines" is in my mind a kind of french city map generator, The "rectangular" could be seen as generating small village as we can see in old RPG games. The "bubbles" is a not very convincing way to build a lunar ground. And finally "manhattan", which I think doesn't need deep explanations. Note that if "classical" works well at any size, you will have more convincing results with other patterns if you set width and height at minimum 60x60.

• if you look closely to the map, you will see 2 colored squares : the green acting as a starting point and the blue as an end point. So you can finally generate a path between the two squares. The search is implemented with the famous A* algorithm. The path generated this way is not always the shortest, but is very efficient.

Now let's play:

In spite of the short time The project has a safe structure (MVC). Maybe I will reuse all or some parts of it to explore some new directions for a game.


*  I must admit I infinitely prefer this kind of test, which let you be creative and demonstrate that you code professionnally, compared to some fuc**** ugly listing of artificial technical questions that nobody cares in real life.