Alternate Graph Generators

After some research and testing, I found two new graph generating algorithms that now have been implemented and added to Yggdrasil. They all work in a similar manner, yet still produce vastly different results. Below is a description of the two new algorithms and some comparison screenshots.

Gabriel Graphs

Graph_Gabriel
A Gabriel graph is constructed in a similar manner to Delaunay Triangulation, yet more scaled down. It only uses two points to calculate a circle and uses that information in exactly same way as Delaunay Triangulation does to determine if a triangle works or not. Only, in this case it only results in a single edge, instead of a triangle. This seems to reduce the risk of overlapping edges and creates some interesting connections, as can be seen in the picture above.

Relative Neighborhood Graphs (RNG)

Graph_RelativeNeighborhood
A Relative Neighborhood Graph also works in a similar fashion to Delaunay Triangulation and like the Gabriel graph, it simply uses two points instead of three. The main difference between a Gabriel graph and a RNG is how they determine if a point is invalid. The RNG method ensures that the two points are closer to each other than any other point. From testing, this always results in a complete dungeon, without any risk of segmentation (unlike the two above, but the risk is still very low). It also generates a graph that barely requires the Minimum Spanning Tree algorithm and can be used directly after it finishes. When generating 100 rooms, only 25% of the edges are removed by the MST on average. Compare this too 50% of all edges on average from a Gabriel Graph and almost 70% of all edges on average from Delaunay Triangulation.

All of these methods are equally useful and can serve their own purpose and have their own use cases. Depending on what is required by the game creator, any one of them could be used.

http://en.wikipedia.org/wiki/Gabriel_graph
http://en.wikipedia.org/wiki/Relative_neighborhood_graph

Leave a Reply

Your email address will not be published. Required fields are marked *