Triangulation for dungeon generation

[Bioniclefreak25]

Hey guys.
I've been working on creating a random level generator based on this site.
So far, I have been able to randomly generate rooms and position them so they do not overlap, as such.

And as you may notice, I have also implemented the ability to distinguish which rooms are "main rooms" and those that are not.
Now about those lines. This is the beginning of my attempt at a Delaunay Triangulation algorithm. Unfortunately, I am stuck and don't know how to implement triangulation into GML. Does anyone have an idea of how I might be able to implement triangulation into the code?
If you need more info, let me know.

 

[TheouAegis]

Damn. That is very interesting! But I'm also at a loss. I understood the terminology, but not how to implement it. I tried reading the LUA code he provided, but maybe I'm just too tired to understand it.

Fiirst off, those bottom rooms should not be separate from the rest of the rooms. You don't explode out uniformly, you simply move them away from each other if they touch each other.

Second, it looks like you didn't implement Delaunay triangulation properly, as each of your main rooms is connected to all the other main rooms. The definition of a Delaunay triangulation is...

a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P).

As far as I can tell, the idea is each main room is a circumcircle and the center point of each is a node. A ray connects one node to another if and only if the ray does not pass through any other rooms. In your image, that's not the case obviously.

Let's label your map from left to right, top to bottom. Like so:

         AB
          C
         ED
F   G    H
I         J
  K


      L

A can connect to B, C, E, F, G and H without passing through any other rooms. If it tries to connect to any other room, then it'd pass through a room on the way, which is a no-no. L can connect to K, G, H and J, but any other room is off-limits.

So for each ray, you need to check if there are any collisions with room_phys_objects other than the ones serving as nodes.

I'm not sure in what way he's adding the rooms to a data structure, but basically you save all the rays so that you know which rooms are connected to each other legally.

The next step is a minimum spanning tree and that is fairly straightforward. (If you study maze generation, a lot of mazes are based on minimum spanning tree algorithms.) Basically, for each node, you find the shortest ray in your Delaunay triangulation and save that. In some cases, this would be enough, but this causes a lot of dead ends and semi-linear pathing. To vary it up, he then chooses a few rays from the Delaunay triangulation that aren't in the minimum spanning tree and adds them to the minimum spanning tree.

The rest of the info I think you can figure out for yourself.