Oct 2, 2012

Terrain Features : Pools of Water

For most of August I was working on modifications to the terrain generator. Previously I had to generate the entire world at once, and it had to be square and a power of 2 in size. There also wasn't much leeway for modifying the output data. With the new changes I've made it can generate what I call a "world region", which is a n x m sized region of the world and it has the ability to run feature placement over the output before it gets turned into the final heightmap/tilemap. This also brings it closer to the eventual goal of being able to specify biomes and make use of temperature/moisture maps based on the surrounding sea and mountains.

Feature Placement

The first feature placement algorithm I've been working on is for pools of water. Since fresh water is second only to oxygen in urgency of need for survival, I need to give the player access to water in some fashion otherwise the game will be rather short.

When it comes to terrain generation there's two different approaches you can use. Teleological or ontogenetic. Those sound complicated, but it comes down to asking the question, is the terrain generated as the result of simulating real world processes or is it faked to look like it was?

An example of simulating using real world processes would be to generate a height map using a plate tectonics simulation, then apply many passes of thermal and water erosion algorithms over the result. Next, add water to the world and if sufficient water flows into a local minimum, you have a pool of water.  That's not even the whole story, to be realistic you should also model the permeability of the surrounding rock, the level of the water table, the rainfall for the surrounding area, and so on...

As you can imagine this is pretty complex, as the forces that shape terrain in the real world come about as a result of processes involving physics, chemistry, biology  and geology. The other thing to note is that the terrain all around us was generated over approximately 4.5 billion years, so creating realistic looking terrain through simulation typically takes a lot of iterations even if you take shortcuts.

Faking it

The alternative is to fake the terrain. The general approach is that you use algorithms that have nothing to do with simulating how real terrain is formed. For example, generating some perlin noise, applying a mask to shape the noise to give it the right shape and then smoothing the result using a gaussian blur etc.

I decided to take this approach, since I'm trying to write a game, not a geological simulation of the Earth.  Following the "fake it" approach, my pool placement algorithm looks something like this:

  1. Pick a random spot in the world.
  2. Determine if the area is suitable for a pool of water, ie not too steep. If not, jump back to 1.
  3. Generate a pool shaped terrain depth mask.
  4. Blend the depth mask with the existing heightmap to introduce a depression to the terrain.
  5. Calculate a suitable water level for the pool.
  6. Loop over the lowered terrain adding water where the depth is below the calculated water level.

There are complications will this approach which I won't delve into here at this time as I'm still refining the algorithm. I ran into quite a few problems that I didn't anticipate, such as how to blend the depth mask with the surrounding terrain so that it looks like it's supposed to be there, not just splatted over the top. My initial approach was to smooth the terrain then apply the mask as is, but it tended to produce a flat area that looked out of place.  In the end I came up with a blending approach that uses the distance from the pool as a blending coefficient such that terrain 5 tiles away from the pool uses the local height map and anything closer uses a blend of the two.

Selecting a suitable candidate site was also very important, as some terrain is completely unsuited to forming a pool, for example, if the site has too much of a slope.  Pools placed here tended to look absolutely terrible and often leaked their water out into the rest of the world as the pool edges were too thin.

The part which gave me the most trouble was designating which tiles should be water. The pool placement affects the height map directly, but the game tiles take their height from the surrounding 4 height map values, so I needed a way to determine which tiles are affected by the height map changes and should now be water. I tried a few different "smart" approaches that took advantage of knowledge of the original water mask but found the best solution was actually "dumb", using a flood fill to find the lowest point and then use a recursive fill to process neighbouring height map values. (Thanks to my colleague Ben for suggesting that one). It works like a charm, and has the added benefit of being able to called on the original height map to generate seas or oceans.

Figure 1: The player character enjoys a little swim.

As you can see in the above image, the water renderer is pretty much as basic as you can get. In the future I'd like to add reflections, ripples, specular highlights, waves and a bunch of other effects that help to sell the idea that its actually water, not a flat alpha blended plane. For now though, it will have to do.