Terrain Generation: Update

Well, I spent a good portion of the last few days working on the terrain generation system and I'm VERY pleased with the results I'm getting now. As is usually the case, what I had thought was a good idea turned out pretty crappy. The perlin noise idea I mentioned in the last post was very difficult to tune to produce interesting results. The image below is pretty much the best I could come up with that didn't look ridiculous:

Image1 "Improved" terrain generation. Note height-based tile selection.

The terrain was taking something like 25 seconds to generate, and looked pretty crappy which wasn't ideal. Around this point I decided to try something crazy, and I was blown away when it immediately produced much better results:

Image2. Crazy idea pays off.

I played around with the code alot at this point, stripping out entire sections, rewriting existing routines, adding totally new stuff and testing lots of new ideas and settings. I spent a good half a day optimising some of the really big number crunching routines and I managed to speed up one of the core routines I was using extensively by a factor of 3, which reduced the terrain generation time to a much nicer 10 or so seconds.

I then spent some time improving the tile selection code to place the different terrain tiles in a smoother fashion. Though I quite liked the "dirty" look of the terrain from a distance, if you zoomed in it looked odd, with tiles appearing to be scattered randomly amongst each other. This was due to the fact that the tile selection was based mostly on the slope of the terrain at that point. The new system uses layers of value noise where each tile type fights it out against the others and the winner is selected. Due to the smooth nature of the value noise function, you get larger regions of the same tile type and there is less oscillation between the different types.

I eventually added 3 additional tile types, a darker version of the grass texture, a rock texture and a pinker sand texture that represents sand dunes. The image below represents the current state of the terrain generator:

Image3. Latest version of the terrain generator.

There's still a fair bit to do, like doing rainfall calculations to generate rivers and lakes, but as I said at the beginning of the post, I'm VERY pleased with the results and wanted to share a better looking screenshot.

Procedural Texture Generation

As I mentioned in the introductory post, Bulldog is going to feature procedural content. This will cover things like terrain, random encounters and even textures.

At present, the only procedural content I've built for Bulldog is a texture generator class which generates textures from pre-defined templates. These templates specify a series of operations performed sequentially to produce the desired output. At present it is fairly naive and produces rudimentary results, but I hope to improve the texture generator's capabilities over time with more advanced synthesis techniques.

I've found that RGB is not a particularly good colour system for texture modelling, as you rarely want to adjust the redness, blueness or greenness of a particular pixel. You're more likely to want to adjust the brightness or other parameters. So I use the HSL colour system, which consists of Hue, Saturation and Luminance. This allows me to adjust the texture in a much more "natural" way. 

As an example of how the texture generation process works, consider a sand texture. Sand is a granular solid made up of tiny bits of rock. The grains are vaguely uniform in size, but vary in colour. I've modelled this in my texture generator by taking a sand-like base colour, then applying random noise to each pixel to adjust the hue, saturation and brightness accordingly. The image below shows the different parts that are generated by the texture generator class and combined to form the final texture.

Uniform vs Gaussian noise

The random noise function I used in the examples above is called Gaussian Noise. This is noise where the probability distribution follows the "normal" distribution. To generate Gaussian Noise, you need a random number generator that will produce random numbers that are biased in such a way that they follow the normal distribution, rather than a uniform distribution.

The random number generator in .net (found in System.Random), is typical of most random number functions found in modern languages in that it returns random numbers with a uniform probability distribution. This means that each value in the output range chosen has equal probability of being output. If you were to graph the probability of each value in the range appearing, the result would pretty much be a horizontal line.

The "normal" probability distribution on the other hand, has a symmetric, bell-shaped curve. Values around the mean have a higher probability of being output, and values at the very edges of the range have a much lower probability. I won't go into any more depth on the topic, for further reading look at something like
this wikipedia article.

Below are two examples of noise generated using Uniform and Gaussian Noise:

Uniform Noise

Gaussian Noise

At first glance it appears as though the uniform noise has a wider range, as it has significantly darker and lighter pixels than the gaussian noise. However, if you look closely at the Gaussian noise you can see that there are some pixels that are quite dark, and some that are quite light, however the majority are somewhere in between, ie, clustered around the mean value. Gaussian noise is a closer match for real-world applications, as the normal distribution appears very frequently in the real world.

For those that are interested, to generate the Gaussian random numbers I wrote a random number generator based on the Box-Muller Transform. It uses a standard uniform probability distribution random number generator and then remaps the values so the output has the normal distribution. The actual implementation I chose uses the Marsaglia Polar Method, which eliminates the need for the sin() and cos() functions.

An interesting quirk with this algorithm is that it needs 2 independent uniform random numbers to actually work, but the output is 2 independent normally distributed random numbers, so in my implementation I actually cache the second value and return that without the need for computation on the second call.

Bulldog

"Bulldog" is the codename I've given to the game project I'll be discussing in this blog.

My policy is to use codenames for software projects. Not to obfuscate the intention behind the project, but to provide a name other than "unnamed game project" when talking to other people about it. I frequently have many ideas on the go at once, so I use codenames. For games, I use breeds of dog. For other applications I use suburbs of Adelaide.

I won't go into heavy details of what Bulldog is meant to be at this stage, as some of the elements will change over time, However I can say:

• The main concept behind the game will be survival in a post-disaster setting. 
• The game world and content will be procedurally generated, and the gameplay will be 3rd Person, with a tile-based isometric view. 
• Currently thinking it will be single player only, but depending on interest I may make it multiplayer at a later date.
• It is being coded in C# using the SlimDX framework, targetting DirectX 9 and Shader Model 2.0.

I'll reveal more of the details as I get further through the development.

My current plan is to have a working version available for download by the end of 2011. I'm hoping it will happen sooner than that, but I'm taking the pessimistic approach with regard to my available time.