Fractals
Introduction
There are many interesting applications for noise and fractals in RL games, not just for terrain generation, but for adding natural-feeling patterns to monster behavior, treasure drops, and many other features.
In this article I will give a brief overview of fractals and how they can be implemented in RL games. There is also some code available and a set of references for further study.
Midpoint Displacement
The easiest way to generate fracta-like behavior is to use midpoint displacement.
Midpoint displacement takes a straight line and turns it into a ragged line that can look like the outline of a mountain range. The resulting fractal has a dimension between 1 and 2. Start with a straight line between points A and B. Create the midpoint, M, half way between A and B. Then displace the midpoint up or down by a random value. This creates two new lines joined at the midpoint. We then repeat this displacement algorithm recursively for each new line segment. At each step, we also adjust the amplitude of the displacement by some method. One usually reduces it by an exponential function.
The result of this process resembles jagged terrain. However it is fairly homogenous and isotropic. It tends to look fake to the eye. You can search online for examples of this terrain.
Midpoint displacement can be done in higher dimensions as well, but the process gets more and more complex. For 2D terrain, which is useful for RL terrain generation, we need to displace the midpoint of a square and partition the square into four smaller ones, which are then recursively displaced. The algorithm is know as Diamond-Square, referring to the two steps of displacement then partitioning.
Here is rough pseudo-code for the midpoint displacement algorithm in 1D.
void midpoint(VECTOR a, b, float scale)
{
VECTOR m, d;
float amount;
.
// Find the midpoint
m = (a + b) / 2;
.
// This is the displacement direction.
// We are displacing along the y axis.
d.assign(0, 1, 0);
.
// Find the amount to displace.
// We start with a random number -1..1
amount = rand(-1, 1);
.
// We now scale by the current scale amount
amount *= scale;
.
// We now update our scale amount. If we left the
// scale unchanged, we'd end up with increasingly
// spiky line.
// Because we cut the length of the line in half with
// every iteration, multiplying the scale by .5 will
// maintain the same "spikiness" at all levels. A value
// less than .5 will cause things to quickly smooth out.
scale *= 0.5;
.
// And do the displacement.
m += d * amount;
.
// Now, create & displace the two resulting
// linesegments am & mb...
midpoint(a, m, scale);
midpoint(m, b, scale);
}
Fractal Brownian Motion
A much better way to generate natural looking fractal patterns is to use a Fractal Brownian Motion, or Fractional Brownian Motion (fbm). It is essentially a generalization of Brownian motion, the fractal zig-zag path small particles make in liquids. The implementations are varied, but the simplest system to understand is presented by Perlin (see resources below). He starts with a noise generation function, which provides white noise in a random-enough pattern. This noise is then churned through a fractal algorithm, in particular one that generates fractal brownian motion. The result is a pattern that looks superior to that generated by midpoint displacement.
Although fbm is more computationally expensive, it is much simpler to implement than midpoint displacement. This is because fbm and noise generation can be generalized to any number of dimensions without altering the algorithms significantly, as must be done in midpoint displacement. For instance, we could use a 4D fbm to generate time-evolving textures, like a burning tree. To accomplish this with midpoint displacement, we need to worry about pixels in a hypercube and how to partition hypercubes. But with fbm, we simply increase the number of noise dimensions to 4, tweak the math a little, and plug in our 4D points.
Multifractals
Fractals can be generated by a vast array of techniques. Provided we have a good source of noise, we can convolute the noise in a huge variety of ways. For instance, Perlin's method of generating fbm is to take the sum of a series of noises of increasing frequency and decreasing amplitude. Instead of taking the sum, we could multiply each term instead. Or we could take the sum of the absolute value of each noise term. There are so many options, it's hard to know where to start. The results of these ad-hoc convolutions are known as Multifractals. Perlin's notes contain some basic multifractals, such as using a sine function to simulate the texture of marble.
RL Applications
Besides generating terrain, we could use fractals to add natural-feeling patterns to many other aspects of the game. For instance, we could improve the monster AI by giving it fractal behavior. Suppose we have monster spellcasters that can cast any spell. We could select a fractal set of these spells to give each individual spellcaster a "flavor". One might favor greatly the fire school with a few acid and lightning spells and perhaps a teleport spell or two.
To implement this, we can use a one dimensoinal fractal with N points where N is the number of spells available. We then scale the points and adjust the fractal parameters randomly for each spellcaster, then run the fbm generator for each point(spell). The output will be a value between -1 and 1 with a fractal pattern. We then select spells that have value of, say, 0.5 or greater.
Such patterns can also be applied to movement, generation of monsters, treasure drops, and so on. The only limitation is the imagination, and perhaps computatinal power.
FBM Exploration Tool
I have created a simple tool to explore fractal terrain generation for text-mode roguelikes. It uses Perlin noise and fbm to generate a fractal, plus handy routines to interact with the parameters. The results are drawn either as pixels or as rendered glyphs simulating a roguelike text-mode map.
To use it, you will need SDL, SDL_ttf, and a C89 compiler that implements Amendament I for unicode wchar_t support. (Check to see if you have wchar.h in your include directory.) It was developed on Linux, Debian in particular, and might need to be tweaked to compile on your system. Even if you can't run it, the code is useful to study. It is released under the GPL.
Resources
- Perlin's notes on noise and fbm. Includes lots of pictures and some code.
- GameDev article about using fbm to generate planet terrains
- [1] About Perlin Noise (as gradient noise, not value noise!) done in C#, with a step by step explanation.
Notes
LeonTorres: This is a quickie article, more of a place to share my notes. Feel free to modify it a-la wikipedia, for clarity and extra info. I didn't proof it much.