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

Leave a Reply

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