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.

Box2D to Daedalus bridge

Things become interesting. Now Daedalus is equiped with 2 new components to cooperate closely with Box2D.

The first is a simple Box2D-body to Daedalus- object converter. It makes things very easy when you want to generate and update a constrained Delaunay triangulation as a mirror of a Box2D world.

The second is more complex. We can see it as a Box2D body object "drived" by the Daedalus pathfinder. It applies Box2D forces to the object to ensure it closely follows a path and reach a destination. This is the first attempt and many other "driver" must be created now according to the nature of the entities we want to simulate (a pedestrian, a car, a spaceship, a robot...).

I hope you will enjoy the demo:

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:

Cartoons into Daedalus Lib

I recently added a bitmap segmentation algorithm into Daedalus Lib. Inspired by the Potrace algorithm, the main purpose was to use automatic generation of large meshes to check the reliability of  the algorithms inside Daedalus.

Some interesting results:

Mickey

Astérix

Doraemon

Bob

Daedalus : group pathfinding and FOV

Today 2 new demos made with Daedalus, showing in action 2 new components: group pathfinding and field of view.

The group pathfinding has many interesting features:
- it can manage any number of entities
- it can manage any size of entities
- generated paths are automatically sampled in order to synchronise the entities and avoid collision between them

We could just reproach the single common path the entities use. Indeed, if the entities have different sizes, it could be legitimate to expect them to reach the goals by different optimized paths and keep synchronisation to avoid collision. But in fact, this behavior is the subject of a new component coming soon, more focused on synchronisation for entities having completely different start and goal positions.


Then the field of view, while looking not so impressive, is a very important component to give awareness to AI entities, allowing them to detect cleverly the other entities. The features are:
- radius, opening angle, position and direction as dynamic properties
- the FOV is broken by constrained edges (other entities can hide behind walls)
- it manages non-null size entites

In the details, the FOV implementation is simply an accurate clipping system. So it can really manages the visibility of an entity through very complex situation with partially overlapping walls.

Demo : fully dynamic Delaunay triangulation

Demo : pathfinding on Delaunay constrained triangulation

A simple planar mesh primitive with half-edge

In a previous article, I explained why and how to implement the half-edge data structure. This article will focus on the implemention of a simple primitive: a 2 polygons rectangular planar mesh. Later we will see how to add some useful tools allowing us to expand the primitive by adding/removing vertices and flipping edges,

The implementation of a simple 2 polygons rectangle primitive could look easy at first glimpse. In reality, with half-edge, it is not so obvious. We need to be very careful and set all the relevant adjacency relations between the 4 vertices, the 10 oriented edges and the 2 faces:

Remember that each edge must references 4 datas: the origin vertex, the opposite edge, the next left edge and the left face:

We immediatly face an annoying problem : the 4 border edges e01, e12, e23 and e30 have neither left face nor next left edge. We could think that leaving null references as datas for these edges is safe, but in fact it would lead to several problems because the missing core datas would break the way we hope to iterate through the mesh. That's why I suggest rather to extend the rectangle in order to obtain a complete closed and consistent mesh:

We just added 2 new edges e13, e31 and 2 new faces f2 (bounded by e12, e23, e31) and f3 (bounded by e30, e01, e13)  This figure could look strange at first glimpse, but in fact it is really intuitive if you imagine our planar mesh lying on a sphere:

Finally, if these 4 new elements are convenient to get a mesh with a complete adjacency structure, they can be cumbersome when you display your mesh on screen or when you iterate in order to navigate from element to element. So feel free to add a new visible property to your classes and set it to false for any object lying outside the rectangle v0, v1, v2, v3. In this way you will be able to simply skip them.

As a conclusion, we will simply give now the complete declarations necessary to implement this simple rectangular primitive:

// (x, y) is any 2d coordinates system
// w is the rectangle width
// h is the rectangle heighy

v0.position = (0, 0)
v0.edge = e01 // or e02 or e03

v0.visible = true

v1.position = (w, 0)
v1.edge = e12 // or e10 or e13

v1.visible = true

v2.position = (w, h)
v2.edge = e23 // or e21 or e20

v2.visible = true

v3.position = (0, h)

v3.edge = e30 // or e32 or e31

v3.visible = true

e01.originVertex = v0
e01.oppositeEdge = e10
e01.nextLeftEdge = e13
e01.leftFace = f3
e01.visible = true

e10.originVertex = v1
e10.oppositeEdge = e01
e10.nextLeftEdge = e02
e10.leftFace = f0
e10.visible = true

e12.originVertex = v1
e12.oppositeEdge = e21
e12.nextLeftEdge = e23
e12.leftFace = f2
e12.visible = true

e21.originVertex = v2
e21.oppositeEdge = e12
e21.nextLeftEdge = e10
e21.leftFace = f0
e21.visible = true

e23.originVertex = v2
e23.oppositeEdge = e32
e23.nextLeftEdge = e31
e23.leftFace = f2
e23.visible = true

e32.originVertex = v3
e32.oppositeEdge = e23
e32.nextLeftEdge = e20
e32.leftFace = f1
e32.visible = true

e30.originVertex = v3
e30.oppositeEdge = e03
e30.nextLeftEdge = e01
e30.leftFace = f3
e30.visible = true

e03.originVertex = v0
e03.oppositeEdge = e30
e03.nextLeftEdge = e32
e03.leftFace = f1
e03.visible = true

e02.originVertex = v0
e02.oppositeEdge = e20
e02.nextLeftEdge = e21
e02.leftFace = f0
e02.visible = true

e20.originVertex = v2
e20.oppositeEdge = e02
e20.nextLeftEdge = e03
e20.leftFace = f1
e20.visible = true

e13.originVertex = v1
e13.oppositeEdge = e31
e13.nextLeftEdge = e30
e13.leftFace = f3
e13.visible = false

e31.originVertex = v3
e31.oppositeEdge = e13
e31.nextLeftEdge = e12
e31.leftFace = f2
e31.visible = false

f0.edge = e10 // or e02 or e21
f0.visible = true

f1.edge = e32 // or e20 or e03
f1.visible = true

f2.edge = e31 // or e12 or e23
f2.visible = false

f3.edge = e13 // or e01 or e30
f3.visible = false

Doubly connected edge list implementation

If you are interested by the half-edge or curious about sophisticated data structures, this post is for you. I know it is very difficult for people new in the field of computational geometry to find relevant informations about implementation of half-edge structure, so I will try to explain the concepts very carefully.

First, what is the motivation behind the use of half-edge ? Maybe you already know data structures like linked-list, tree, or graph, but what is half-edge and why you would need to implement it ?

One answer I would give is the following: you need a half-edge structure when you need to navigate very quickly and easily inside a polygon mesh. Remember that you need polygon mesh not only for 3D, but also for some 2D complex datas representation like Delaunay triangulation (note that in this article we will deal only with 3 sides polygon mesh).

Now the problem is that in many libraries or softwares, the polygon mesh datas are stored inside 2 arrays: one that explicitly stores the vertices positions and one that stores vertices indexes for each triangle. For example, it is the case in Unity3D Mesh class. We can illustrate this by the following diagram:

This data structure is quite simple to understand and to implement, but it is a performance disaster when you need to write an algorithm that needs to navigate and search efficiently inside the mesh. One obvious example of navigation is pathfinding. But why is it not efficient ? Because the adjacency access is not. For example, if you want to find all the vertices connected by an edge to a given vertex, you need to scan the entire triangle array to find the relevant indexes ; so the time you spend to do it increases by the size of your mesh.

But with half-edge you can access adjacency in constant time, because in this structure it becomes the explicit way to keep the datas. For this purpose, the main object you will implement will be not a vertex or a face, but an oriented edge. Think oriented edge as the core node of your data, as we can see in this illustration:

Given an Edge object current edge, a descent half-edge API should give you access to the complete adjacency: Vertex, Edge and Face objects adjacent to current edge. For example, my own interface for half-edge structure as a library contains 4 core classes: Vertex, Edge, Face and Mesh with the following public methods :

public class Vertex

• public get position : Vector // (can be any 2D or 3D coordinates data)
• public get edge : Edge // (any Edge with this Vertex as origin)

public class Edge

• public get originVertex : Vertex
• public get destinationVertex : Vertex
• public get oppositeEdge : Edge
• public get nextLeftEdge : Edge
• public get prevLeftEdge : Edge
• public get nextRightEdge : Edge
• public get prevRightEdge : Edge
• public get rotLeftEdge : Edge
• public get rotRightEdge : Edge
• public get leftFace : Face
• public get rightFace : Face

public class Face

• public get edge : Edge // (any Edge with this face adjacent at left)

public class Mesh

• public get vertices : Vertex []
• public get edges : Edge []
• public get faces : Face []

Equiped with that, you must be able to iterate efficiently in order to navigate through the whole mesh. For example, from any Vertex v, you can iterate to any direct adjacent Vertex by calling a sequence like:

v.edge.destinationVertex // 1st adjacent vertex
v.edge.rotLeftEdge.destinationVertex // 2nd adjacent vertex at left
v.edge.rotLeftEdge.rotLeftEdge.destinationVertex // 3rd adjacent vertex at left

v.edge.rotLeftEdge. ... .rotLeftEdge.destinationVertex // n-th adjacent vertex at left


The same idea works for faces. From any Face f, you can reach the 3 direct adjacent Face just by:

f.edge.rightFace // 1st adjacent face at left
f.edge.nextLeftEdge.rightFace // 2nd adjacent face at left
f.edge.nextLeftEdge.nextLeftEdge.rightFace // 3rd adjacent face at left

When you understand the basic principles of navigation, then maybe you want to expose a compliant API in order to iterate more easily through your mesh. So it can be done very easily by implementing a collection of iterators on top of the half-edge structure. For example, some ideas of iterators you can add to your library:

public class IteratorFromVertexToNeighbourVertices

• public function set fromVertex(value:Vertex)
• public function get next : Vertex

public class IteratorFromFaceToNeighbourFaces

• public function set fromFace(value:Face)
• public function get next : Face

public class IteratorFromEdgeToRotatedEdges

• public function set fromEdge(value:Edge)
• public function get next : Edge

public class IteratorFromVertexToHoldingFaces

• public function set fromVertex(value:Vertex)
• public function get next : Face

Now come back to low level half-edge implementation. We saw that the list of 11 getter methods exposed by the Edge class is quite useful to use. But at first look, it will imply a lot of datas to maintain and in consequence a nightmare to implement. But don't worry, because in reality almost of the adjacency relations between the objects can be deduced from the very small core of datas showed in this illustration:

You can see here that given an Edge object current edge, only 4 datas are required: origin vertex opposite edge, next left edge and left face. As a justification, I will simply give you a possible implementation of the Edge class with the complete deduced adjacency relations:

public class Edge
// core datas:

• private var _originVertex : Vertex
• private var _oppositeEdge : Edge
• private var _nextLeftEdge : Edge
• private var _leftFace : Face

// public interface:

• public get originVertex : Vertex { return _originVertex }
• public get destinationVertex : Vertex { return _oppositeEdge.originVertex }
• public get oppositeEdge : Edge { return _oppositeEdge }
• public get nextLeftEdge : Edge { return _nextLeftEdge }
• public get prevLeftEdge : Edge { return _nextLeftEdge.nextLeftEdge }
• public get nextRightEdge : Edge { return _oppositeEdge.nextLeftEdge.nextLeftEdge.oppositeEdge }
• public get prevRightEdge : Edge { return _oppositeEdge.nextLeftEdge.oppositeEdge }
• public get rotLeftEdge : Edge { return _nextLeftEdge.nextLeftEdge.oppositeEdge }
• public get rotRightEdge : Edge { return _oppositeEdge.nextLeftEdge }
• public get leftFace : Face { return _leftFace  }
• public get rightFace : Face { return _oppositeEdge.leftFace }

This proves that only 4 datas need to be maintained in order to implement a complete half-edge structure.

So now that we have a descent core API, we need some additionnal tools to comfortably build concrete structures. For example, we could code a parser that generates a complete half-edge structured Mesh from a .3ds file (3D Studio Max native export format). An other possibility is to code some simple primitives and tools allowing us to expand them. We choose this second approach and it is the subject of the next articles:

A simple planar mesh primitive with half-edge

Incremental constrained Delaunay triangulation prototype

Delaunay triangulation is a huge subject and it can become very hard when we reach some refinements like constrained triangulation, incremental algorithm, quad-edge data structure... that are globally part of the computational geometry theory.

But there are several applications and they can be very impressive. Of course my mind is focused on artificial intelligence and I think especially of the pathfinding through navigation mesh.

This article is the first of a serie about concepts and algorithms related to computational geometry. It is an illustration of Delaunay triangulation through a demo prototype.

Just click on the board to add new constrained edges:



This demo and the underlying library I wrote are direct implementations of the following article:

Fully Dynamic Constrained Delaunay Triangulation (2003)

The underlying data structure behind the library is the quad-edge:

Quad-edge core implementation explained

A simple planar mesh primitive with quad-edge