8
\$\begingroup\$

I'm trying to learn procedural generation technique's. Specifically for dungeons. I started off with a 2D array and I generate my rooms fine. Each room contains wall tiles as seen in the screenshot below.

![generated rooms]http://i.imgur.com/JpYLKip.png

Right now I use A* to link the rooms together. But this has some paths go straight through other rooms or around rooms. Having done some googling I found this demo which game me the idea of using Delaunay Triangulation to properly connect the rooms without going through already existing connections/rooms.

But how to apply it to my 2D array setup? My initial thinking is that I should think out side of the box (2d array haha) and grab my rooms and create a complete graph from this and then apply the Delaunay Triangulation.

I've never done anything with graphs before. So what I would to know is a) is my thinking correct in creating the graph with all the rooms linked and then to apply the triangulation and b) where should i start?

[small edit]after some more looking around stackoverflow i found this post explaining Graphs more in depth. https://stackoverflow.com/questions/15306040/generate-an-adjacency-matrix-for-a-weighted-graph

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ I don't quite follow what you want to use Delaunay triangulation for. Is the idea that you'll put in a vertex per room and use the edges of the triangulation as links between rooms? How does A* figure into all of this? Finally, if you want to know how to do Delaunay triangulation, just google it. There are tons of articles on it, not to mention libraries. \$\endgroup\$
    – Nathan Reed
    Aug 29, 2013 at 0:36
  • 3
    \$\begingroup\$ What have you tried? What is your actual question? This is a Q&A site, not a general discussion forum, so unfortunately just asking for tips or suggestions is off topic. \$\endgroup\$
    – Sean Middleditch
    Aug 29, 2013 at 0:36

1 Answer 1

Reset to default
10
\$\begingroup\$

That is a neat demo. The best reference for Delaunay triangulations and Voronoi diagrams that I've found is Jonathan Shewchuk's book and lecture notes. The book is significantly more advanced than the lecture notes, and talks more about mesh refinement. I suggest you start with the lecture notes.

Do you need to go to grad school to generate a Delaunay triangulation? Heck no! A delaunay triangulation is just the unique triangulation such that each triangle's circumcircle (scroll down to Shewchuk's answer) encloses only the 3 vertices of each triangle, and nothing more.

enter image description here (Picture from Shewchuk's lecture notes, linked above)

Algorithms

A paper outlining Two Algorithms for Constructing a Delaunay Triangulation is a good place to start.

The main way you'll see people talk about is first creating the Voronoi diagram.

enter image description here

Fortune's algorithm

I can only give you a few pointers here, having started working with Fortune's algorithm but abandoning the project because Fortune's code is extremely difficult to grok. There is a javascript implementation here.

A couple of other Fortune resources:

I know I posted a lot of links here, but my advice is to avoid Fortune's algorithm. An easier way to do it is to use flipping edges, described below.

Flipping edges

A much easier way to do it is called Flipping Edges. What you do is start with any triangulation, then simply "flip edges" so every triangle becomes "Delaunay" (circumcircle of each triangle contains no other points other than its own 3 vertices). Once all the tris are Delaunay, you have the Delaunay triangulation.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Thanks @bobobobo. Very informative! Do you have any resources that show how to start implementing some of these algorithms? I know now that i dont have to have a graph to perform triangulation, just a set of points, which I have. After i have the triangulated graph, i can perform things such as Minimal spanning trees to get more interesting results. \$\endgroup\$
    – Superflat
    Aug 29, 2013 at 9:33
  • \$\begingroup\$ If you only have a set of points, you can either use Fortune's algorithm O(nlogn) or just attempt to form triangles with all other pairs of points. Only really forming triangles when the triangle circumcircle doesn't enclose any other points \$\endgroup\$
    – bobobobo
    Aug 29, 2013 at 9:45
  • \$\begingroup\$ If you are using this to generate navmeshes then you have to be aware that Delaunay only works for convex polygons, so if you don't want to cut up your mesh and triangulate the convex sub-parts then look at this question for alternatives. Edit: there seem to be extended versions of Delaunay that support more complex structures apparently. \$\endgroup\$
    – PeterT
    Aug 29, 2013 at 10:03
  • \$\begingroup\$ @PeterT No it's just to determine room connectivity. I'd like to avoid using a navmesh and just use A* to iterate over the square grid... Although.. i could always combine the mesh after generation and then run a navmesh generator. \$\endgroup\$
    – Superflat
    Aug 29, 2013 at 10:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .