Guns !

I just upgraded my previous playable dungeon map generator demo with 6 new weapons ! I hope you will like them. You can go directly at the bottom of the article to play the demo.

Here is the complete list of weapons:

1. Energy gun
Very basic weapon. Given for free, it has infinte ammos.

2.  Shotgun
Very popular since Doom, the shotgun disperses a range of high-damage bullets.

3. Machine gun
It quicktly throws an accurate line of bullets.

4. Plasma gun
Faster and stronger version of the energy gun.

5. Rocket gun
The rockets are slow but accurate and the explosions are devastating. Do not use near the walls !

6. Flame thrower
Short range but pass through flock of enemys.

7. Multi-shots energy gun
Upgrade of the energy gun. It throws a range of 5 balls.

8. Chain gun
High-speed frequency and rotating barrel. Devastating.

9. Megablaster
A large and continuous blast of energy ! But it takes some time to charge...

10. Laser
Continuous and accurate ray of energy.

11. Tinyrocket gun
Hybridization between a chain gun and a rocket gun ! Definitely my favorite.

You can experiment the result below. Generate a map (with custom parameters or randomly) and then click  the "play it" button. You can directly catch the 11 weapons. Additionally, you can run by pushing quickly the UP key 2 times and dodge with LEFT or RIGHT keys quickly 2 times.

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.

61 Cygni - Game prototype

I hope you will enjoy this new prototype.

Some screen captures:

I built it in 2 months. I used Box2D for physics. I used musics from Super Metroid and sounds from Doom PS1.

I used Daedalus Lib to triangulate automatically the entire level. It made things fast and easy for pathfinding, fast bullet collision detection and fog of war. A great save of time allowing me to focus deeply on gameplay.

I would love to continue the production of that game. If you are producer or publisher, feel free to contact me. We could target Steam as well as mobile platform.

Click below to play the game (fullscreen mode)

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:

Introducing Daedalus Lib

Project on GitHub

Daedalus is a library I develop. It manages 2D environment modeling and pathfinding. I really hope this library will help designers and developers to invent new gameplays.

When I began to code Daedalus, I had many ideas in mind:

1- focus on 2D
2- fastness and accuracy
3- simplicity of use


1- Why focus only on 2D and not on 3D ? Because constraining to 2D allows to gain simplicity and efficiency. Many great games today are still based on 2D engines involving 2D mechanics, 2D physics and 2D display ; so I hope Daedalus will find his place as a new component for new 2D projects.


2- Fastness and accuracy are reached by using among the best techniques available in the fields of computational geometry : quad-edge structure and fully dynamic Delaunay triangulation. Daedalus algorithms are based on many research publications, among them:

Fully Dynamic Constrained Delaunay Triangulation by Kallmann, Bieri and Thalmann
An improved incremental algorithm for constructing... by Anglada
Efficient Triangulation-Based Pathfinding by Jon Demyen


3- For simplicity, I assumed that the library should work without any pre-generated data. Everything should work in real time : obstacles insertion/motion/deletion and path generation. Also I assumed that the library should be fault tolerant to designer/developer mistakes : obstacles can overlap and can be of any shape : open, convex, concave... At last, the path generation manages non-null size objects in order to avoid any obstacle collision.


Now the basics are exposed, I can show you some demos :

Today Daedalus is coded in Actionscript. But because the library has no dependancies from any other library (I wrote the whole mathematics), it can easily and quickly be translated in any other language. The project is not open-source at this moment, so not available for free download. I plan to use it in some new projects before release it in the open world.

So I am now looking for some collaboration. If you feel interested by Daedalus for your game engine, for a commercial game project or any other application, you can contact me directly at flash dot cedric at google mail service.

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.

Pathfinding on bitmap triangulation

Because large triangulated maps can be a pain to design by hand, I implemented into Daedalus an algorithm generating optimized triangulations from bitmap images. It is directly inspired by the bitmap segmentation in the Potrace algorithm.

How does-it work ?

Just give a picture made from black and white pixels to the algorithm. For example:

Then the algorithm returns to you a clean and beautiful triangulation:

Neither parameter nor configuration filling are required. Just give the bitmap and get the mesh.

However, black and white pictures are required. But we can consider the use of a threshold to easily convert gray scale and color images.

From that, I experimented with success the use of pathfinding on several triangulations generated from:

- a SNES Mario Kart circuit map

- a Doom map

- a picture of the labyrinth at Grace Cathedral

- a map of Paris created by artist Jazzberry Blue

I used Photoshop to extract properly black and white pictures from the previous maps. Then I just played with the algorithm and enjoyed the fast and accurate pathfinding implemented in Daedalus Lib.

As you can see by yourself:

Demo : pathfinding on Delaunay constrained triangulation

Maze generation in 3D

An example of maze generation in 3D. Click on "explore 3D" to build a maze and then navigate inside by pushing the arrows of your keyboard :

The maze generation algorithm is the same I previously illustrated on the blog. Then I use the cells informations (full or empty) in order to build the relevant 3D world.

I have 5 pre-built 3D meshes (done in 3D Studio Max) :




For each cell of the map, I analyse the neighborhood and choose the relevant mesh to apply. The meshes are obsiouvsly designed in order to fit perfectly when duplicated side by side. It gives us the illusion that the meshes are merged as a whole.

At last, some physics are used. I use Box2D for the walls and "player" simulation. I did this choice because Box2D is very powerful, allowing me to easily add new physic features in the future.

Labyrinth algorithm illustrated

I post here a step-by-step version of the maze generator, keeping only the "classic" maze version. Click on "generate" to see how the algorithm works :




It is inspired by the DFS algorithm. It can be seen as a miner digging into the rock cells, always choosing the next direction at random (using pseudo random number generation). You can see the current position of the miner (green square) and the "little stones" (pink squares) he drops in order to keep track of his last path.

I used the following fundamentals rules to process the DFS:

• the miner always digs the cells two at a time
• the miner never digs a cell if it communicates to a previous dug cell
• the miner always tries every directions before give-up and coming back

Maybe it could be interesting to tweak or relax some of these rules to generate some different maze patterns.

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.