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

Room Placing and Spacing

One issue with the generation process was how to determine where to place the newly generated rooms. Up until now, all rooms where placed randomly, which caused all sorts of problems with overlapping or rooms being to far away from each other. My first idea on how to fix this was from reading this (http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/). His solution was to generate all rooms very tightly, so that they overlap each other. Then he solved the overlapping with a steering behavior similar to those found in Artificial Intelligence. But I felt it was overly complex. Instead, I wrote my own algorithm, which produces a room layout which is pictured below.
Room_Tech8

The algorithm works like this:

  1. First room that is generated is randomly placed in the world space, does not matter where
  2. When a new room is generated, pick another random room that already exists and is placed in the world
  3. Pick a random angle from this room, and set the distance to the radius of both rooms(old and new)
  4. If no other room occupies the space, the room is placed, otherwise return to step 2
  5. Repeat until all rooms are placed

It has been working well thus far, but it has a few issues which will be fixed in the future and it is poorly optimized for larger sets of rooms(100+).

Cont. Delaunay Triangulation

DelaunayTriangulation2
The Delaunay Triangulation algorithm used in the dungeon generator preforms well in most circumstances, but there are a few exceptions and issues that requires attention. One issue can be seen highlighted in the picture above, where a very shallow triangle has been formed between three exterior points. This is a very undesirable behavior and the triangle is mostly useless. This is a very easy fix, simply check the radius of the circle formed. If the circle’s radius is larger than a predetermined threshold, ignore the triangle without even checking for points.
Another solution, which would be a lot more flexible, would be to look at the average circle radius. When the generation is finished, the algorithm looks for anomalies in the average and removes them, thus avoiding the issues outlined.

DelaunayTriangulation3
Another issue that sometimes occur, though quite rare, is edge overlapping as seen in the picture above. A fix for this is to check every edge for collisions with each other and simply remove one of the two in the case of a collision, but it would be quite expensive to do. More time is needed later on to look into this issue, but so far it will not cause any major issues with the dungeon generator.

Take 2 – New design, Gaussian Distribution and Delaunay Triangulation

After much thought and consideration, it was decided that the current design for the procedural generation system was not good enough, nor was it flexible enough to fit the requirements outlined by the project plan and design. Here is a very rough overview of how the new system will function. The flowchart is still a work in progress and will most likely change during the progress of the project, but the core is finished. It also omits steps such as decor for practical reasons, but they are included.
NewIdeaFlow

To achieve this new design, a more robust and predictable random number generator was needed. After some research, it landed upon a variation of Normal Distribution (also called Gaussian Distribution). A random uniform number between [-1, 1] is generated and feed into the algorithm and a distributed random number is returned. See the images down below for some examples of what the results can look like when this is repeated a few thousands of times. The “Marsaglia polar” method is used to preform a Normal Distribution computationally.
GaussianRandom1
GaussianRandom2
GaussianRandom3

The data generated from the Gaussian Distribution can then be used to more uniformly generate rooms of various sizes. For example, the curve could be divided into sections, where each section represent a predetermined size for the room. Thus, there could be a larger chance to create a small room, and a smaller chance to generate a larger room. This could have been done using normal random number generation as well, but the results would not be near as predictable as this method.
IntervalRandom1
IntervalRandom2

Now that the rooms have been generated using Gaussian Distribution, they need to be connected to each other in order to create a node graph. This node graph will later be used to generate corridors to connect these rooms. There are a few requirements that need to be meet for the rooms to be connected properly:

  1. The node graph segments cannot cross each other
  2. All rooms must have at least 1 neighbor in the graph

To achieve this, a algorithm called Delaunay Triangulation is used. There are quite a few variations of the algorithm, but it was decided upon a fairly simple to implement method. A circle is formed by choosing three different points and preforming some basic geometry calculations. Then a check is preformed to see if any of the other points is within the circle. If no points are found, a triangle is formed between the three points and they are connected to each other in a graph. If a point is found, it skips and tries three new points. This is done until all points have been tested. The results can be seen in the picture below. This method is however not without flaws. Certain issues can arise that will generated overlapping edges. The most probable reason for this is imprecision in the checks.
DelaunayTriangulation

http://en.wikipedia.org/wiki/Normal_distribution
http://en.wikipedia.org/wiki/Delaunay_triangulation

Layout and graph generation

The goal for this week is to be able to generate a dungeon, with rooms and corridors, that has a sensible layout.

Firstly, I tried to generate a layout using Binary Space Partitioning(BSP). It creates a large cell, and splits this cell down into a tree-like structure, until a specific condition is met. In this case, the condition is cell size. If a cell is to small to be split, it stops. Eventually, this condition is met in all cells and the splitting stops in the entire tree, thus marking the end of the layout generation. The results is a layout with many smaller rooms, but a general lack of larger ones. This can be seen in the picture below. This isn’t a very good way of generating interesting layouts for the dungeon, so alterations are in order.
Layout tech test 1

Adding some additional conditions in the decision between vertical and horizontal splitting does improve the layout slightly, but it still feels out of place. Another issue that I have started to notice, is a clear pattern or repetition in the layouts. This can clearly be seen in the picture below. While the layout does not represent the final rooms that will be generated, I still feel the need to look into it. Optionally, I could go for another approach to generating the layout.
Layout tech test 2

Secondly, after the layout has been generated, we need to connect the individual layout cells to each other in order to create corridors. The are several ways to do this, the easiest being to use the existing structure of the BSP tree that was generated. The drawback to this is that the resulting node graph will be non-looping, meaning no matter what direction you take, you will find an end. It could be used directly to generate corridors, but it would not allow for further generation options.
Another option is to preform a polygonal edge-edge test between all the node cells. This will create large node graph of neighbors for each cell. This is however, a very CPU intensive algorithm, and does not scale well with larger amounts of cells. This due to the fact that all cells need to check all other cells. We could take advantage of the fact that the layout still has the BSP tree structure, but that is a future topic.
The resulting node graph from the edge testing is still not very usable to generate corridors. It would more or less connect all the rooms to each other, allowing the player easily traverse the map(see the picture below for a visual representation). The node graph needs to be trimmed into something more usable. Prim’s Algorithm is perfect for this, as it is a Minimum Spanning Tree(MST) algorithm. A MST is the graph that connects all the nodes with the lowest edge weights in a larger node graph(for more information, see http://en.wikipedia.org/wiki/Minimum_spanning_tree). The difference can be seen in the picture below. This new graph could now be used to generate corridors to connect the rooms and it would look OK.
Layout Tech Test 2

As you might have noticed in the picture above, the edge testing is not perfect. It is very picky that the edges must be a perfect match in order to be considered connecting. While not a problem due to the nature of the BSP tree generation, it does cause some unwanted behavior. A fix for this will be updated at a later time.

Milestone 1 and Presentation

Today we had a small seminar, where each group had a chance to present their project plan, concept and time scheme in front of the other project groups. Roughly 20 minutes were allotted per group, with added time for questions and feedback.

Presentation 2015 01 23 We all received some form of direct feedback once our presentations where over. They had a few minor issues they wanted me to address or at least take into account before I did any further progress with the project.

  1. Specify what types of files will be delivered at each milestone, instead of writing generic topics
  2. Plan less for future research areas and focus more on the current topics I have chosen. This was mostly referring to my slideshow presentation
  3. Structure the time plan better. As of now, it is very cluttered and a bit hard to follow

We will receive further feedback next Tuesday (01/27), once the handlers have read our documents and have had time to reflect. Until then, we are to continue working on the project.

Milestone 2 is the prototype stage of the project. At the end of Milestone 2, we should have some proof of concept or similar material ready to showcase in front of the other groups and to upload to the blogs. My goal is to have a functional dungeon generator working, without the framework and the modules. Those are for Milestone 3.

Here is a link to all documents that are related to Milestone 1. It contains the project plan, the concept and research, the time plan and the presentation slideshow. Ideas and feedback is much appreciated.

Rapid prototyping modelling with Qubicle 2

If you are a programmer like me, you most likely aren’t very good at working with 3D graphics and modelling. I have however found a solution that works great for making simple models in rapid prototyping purposes.

The software is called Qubicle 2 and is a type of voxelbased 3D modelling software. It is easy to use and makes usable block models fast, perfect for someone like me. Down below is a render of a test model, which took 10 minutes to make, including some poking around and testing.
Testing Qubicle 2

And here is said model loaded into Unity3D.
Qubicle 2 model in Unity3D

Qubicle will be used to create various miscellaneous models, such as tables, doorways, items, pickups and so on.

Design, concepts and research

Hello, this will be my own development blog for my specialization project called “Yggdrasil World Generation”. More information about the project can be found under “About” in the menu to the left. On here, I will post anything from research topics to development updates under the duration of this 2 month project. I will try and post on here every Tuesday and Friday, and any other day that I feel I have something relevant to discuss on here. Comments are welcome!

Testing the Unity game engineThis stating post will not contain much. Firstly, the choice of engine for the project has been made: Unity3D. Since I am new to this engine, I decided to learn some more about it and follow some tutorials. To the left is an image of a very basic “Collect the items” game, as seen in all MMORPGs. I choose Unity3D for its rapid prototyping capabilities and its ease-of-use. Others were considered, but eventually Unity3D came out on top.

Currently, I am reading up on various minimum spanning tree algorithms. They are used in weighed node graphs to find the lowest cost node tree. This will hopefully be useful when generating structural entities such as corridors and portals. At the time of writing, two variations of this algorithm look particularly inetersting: Prim’s algorithm and Kruskal’s algorithm. A post covering this subject will come along as the project progresses.