After completing my foray into terrain rendering progress on building a 3D engine has been slower than I had anticipated. This was in part due to me traveling for a bit, but was mainly caused by finding out once more that there are many layers of complexity involved with this undertaking. Usually, when trying to get from point A to point B, I end up having to visit at least points C, D, and E – but let me elaborate on this.
So far I had used real-world heightmap data, but I wanted to try out generating synthetic terrain for my game world. Ideally, I’d like to be able to set a bunch of parameters such as terrain type (hills, mountains, islands, etc.) and end up with a unique landscape. The first mechanism for this that I came across is the diamond-square algorithm – so called because it divides the terrain grid into a series of diamonds and squares in order to displace individual positions on it. I won’t go into any more detail. Instead, here are some screenshots of the type of terrain I was able to synthesize that way:
Overall, this method generates a fairly realistic looking terrain. As you can see, there are some hills and valleys without any noticeable artifacts. While I found it fairly easy to implement, this method doesn’t offer much control over the terrain features. Also, when used on a large scale, the generated terrain is a bit too noisy and thus tends to feel feels a little boring because it is too uniform lacking distinct features like mountains and cliffs. There may be ways to counter this by changing the parameters (primarily the elevation used during the subdivisions) based on the global position, so I’m planning to revisit the algorithm in the future.
Looking for something that would give me better control over the high level features, I came across this great article on using polygons to as the basis for different terrain types. The algorithm starts off with a set of randomly distributed points and then partitions the surrounding space into cells:
Each of these cells has a set of distinct properties, such as elevation and moisture level, which can later be used to determine its high-level characteristics – for example, a high-elevation / high moisture cell would be a snowy area, whereas a low-elevation / low moisture cell represents a desert. These are just examples of property combinations as they will vary depending on what the game mechanics require.
Since the algorithm described seemed very promising, I decided to port it to be used in my project. In order to generate the cells from the set of input points, the original method used a Voronoi diagram. Again, I’ll spare you much of the technical detail. You can think of a Voronoi diagram as a graph that partitions a space. It has quite a few different uses, for example it is used to generate 3D meshes from a set of randomly distributed points. There are a few different methods documented on how to generate it in two dimensions, a sweep line algorithm being commonly used.
The original article’s source code was written in ActionScript, as was the library used to generate the Voronoi diagram, so I had to find a different solution that would work with my C++ code base. I started looking into existing open-source implementations, but found most of them lacking in either documentation or flexibility. I then considered implementing the algorithm myself, but thankfully came to my senses and took another look at the Boost Voronoi implementation. It turned out that it actually did about 80% of what I needed – that is, it took a set of input coordinates and generated the edges of the Voronoi graph for them.
What it didn’t do was to perform clipping, so that some of the edges were defined as going from some point towards infinity. After adding this missing additional functionality, the graph is now bounded by a rectangular box:
I also wrote some code that would allow me to run multiple iterations of the Voronoi algorithm to improve the spacing of the input points. As suggested by the author of the original article, this recomputes the points as the center of the cell after each run to generate a more evenly spaced graph:
Once all this was completed, I resumed work on porting the actual map generated code to C++. Thankfully, this was fairly straightforward. In my current implementation there is a lot of room for optimizations, but it does generate some good results. You will notice that for now the terrain is always island-shaped, which is not an inherent constraint of the original algorithm, but which actually suits me fine for now. Here are some examples of what the generated terrains look like:
The next step will be to try to combine the terrain rendered with this map generation algorithm. I’m thinking I should be able to generate the high-level map, the convert it into a height-map that can be used as one of the coarser levels in the clip map. For the finer levels, I should be able to synthesize terrain details using either the diamond square method or another noise-based algorithm – as always, I’m hoping to post more soon.
Looks nifty
cheers!