Some Uses of Noise and Turbulence

By: Josh "VertexNormal" Tippetts

Overview

Random noise, as has been previously stated, is one of those areas of knowledge that is critical to random level generation. Noise comes in all sorts of flavors and forms, and one particularly useful form of noise is commonly called 'turbulence'. If you look up at a partly-cloud sky, you can see turbulence in action. Random and chaotic currents of air (turbulence) whip frothy white volumes of airborn water vapor into all sorts of lumpy, wispy, roiling shapes. We can mimic this sort of turbulent perturbation using mathematically generated noise, and use it in our work.

In the interests of speed, much of the code and many of the algorithms I will be discussing have been implemented in the Accidental Engine as part of the core engine code, rather than as Lua script. Even as engine code, much of it is processor intensive and may take a few seconds to execute. Consequently, the Accidental Engine binary has been updated for this lesson, so if you have an older version of Accidental, please upgrade to the latest or the scripts will not work. I initially wrote the noise and turbulence code presented here as Lua script, but some of the load times were simply awful.

As a matter of prerequisites, I assume at least a basic knowledge of 'Perlin noise', which we will use to generate our turbulence. I will touch on the particulars of Perlin noise only briefly; for a more in-depth discussion, you can read this or this. I highly recommend reading these links if you do not understand Perlin noise.

How can we use turbulence in our level generation bag of tricks? Well, Squint already detailed one simple method--use the noise map as a fractal map to delineate regions or areas. By cutting the noise map off at arbitrary thresholds, he defines areas in which to place walls, trees, terrain variations, etc... This technique is eminently useful, and should become a main staple of your collection of tricks.

In this article, I'm going to discuss another use: perturbation of another arbitrary pattern. This concept can best be understood using some pictures. This first image is an arbitrary grey-scale bitmap I created using the Gimp.

A simple map of straight lines

Just a few lines, really, but notice how unnatural it would look if used as a random level of some sort, due to all of the perfectly straight lines. In real life, perfectly straight lines are extremely rare. So what we need to do is 'noisify' the image up a little, to create a more natural appearance.

The same line map, perturbed using continuous Perlin noise.

To create this second image, I simply used 2 layers of 2D Perlin noise to perturb the original pattern. I iterated through the original image on X and Y coordinates, then used noise from the 2 layers of Perlin noise to perturb or modify these X and Y coordinates, extract the image pixel from the original buffer at the perturbed coordinate locations, and set that as the pixel for the final image.

Here is the technique in simple pseudo-code:

for x=0 to ImageWidth step 1
  for y=0 to ImageHeight step 1
   noisex = PerlinNoiseMap1[x][y]
   noisey = PerlinNoiseMap2[x][y]
   
   // Perturb our coordinates
   px = x + noisex*turbulence
   py = y + noisey*turbulence

   MapOut[x][y] = MapIn[px][py]
  endfor
endfor

In the above pseudo-code, we assume the existence of 2 distinct noise maps, one to modify X and one to modify Y. turbulence is simply a factor used to specify the strength of the turbulence; the higher it is, the more the noise map will perturb the coordinates, and the greater the turbulence will be. For the above image, I used a turbulence of 15.

Note that in reality, you will need to wrap the perturbed coordinates to keep them within the boundaries of the image map.

This next image does the same thing, but it uses just 'regular' chaotic noise (generated with rand()) to perturb the coordinates, rather than Perlin noise. It uses the same turbulence value of 15.

Same line map, using 'regular' noise for the perturbation.

It is a demonstration of why the fact that Perlin noise is smooth and continuous is so important for our needs. Because adjacent values in a Perlin noisemap are going to be fairly close to one another in value, the perturbations of adjacent pixels in the image map are going to be very close together as well, preserving the general shape and continuity of elements in the image far better than simple chaotic noise can. This is important to us, because if we are using the technique to noisify pathways we have lain down, for example, we need the pathways to remain continuous and... well... 'path-like'. Of course, that is not to say there wouldn't be a use at all for this sort of noise perturbation; I could definitely see it having uses in areas such as foliage population (placement of thickets of trees) and so forth. Especially in placement of such objects with a requirement for tighter control than fractal grouping would afford.

Now, I first implemented this technique to perturb basic 2D images or value buffers, since I find that ability to be the most useful. However, it can be applied to pretty much any arbitrary function as well. In the above examples, I was simply using Perlin noise to perturb the inputs (X and Y) to a function (the image), where f(X,Y)=ImageData[X][Y], to define the output of another function. You can swap any function for the image pixel lookup, such as cos(), sin(), or other arbitrary functions. The sin() function is commonly used in procedural texture generation to create textures with a veined or marbled look. Since images are, of course, more fun to look at, let's look at a few. Here's a bit of pseudocode that can generate a pretty cool (if smooth) canyon if you are generating height-map based levels for a 3D game--

for x=0 to ImageWidth step 1
  for y=0 to ImageHeight step 1
   xy = x/ImageWidth + y/ImageHeight
   cosval = cos(deg(xy*PI))  -- For some reason, Lua's trig functions use degrees rather than rads

   MapOut[x][y] = cosval
  endfor
endfor

The image generated by this pseudocode (converted to a greyscale bitmap, of course) would look something like this--

Sample output for a simple cosine function

for x=0 to ImageWidth step 1
  for y=0 to ImageHeight step 1
   xy = x/ImageWidth + y/ImageHeight + turbulence*PerlinNoise[x][y]   -- Perturb it a little
   cosval = cos(deg(xy*PI))


   MapOut[x][y] = cosval
  endfor
endfor

The output of this perturbed cos() function is pretty cool--

The same cosine function perturbed with a little noise.

Just about any other function can be finessed to use with this technique, and you can get some very interesting results from complex functions. It can be difficult to find 'pure' mathematical functions to use in this manner and generate levels to the exact pattern desired, which is why I frequently use the image turbulence technique I started the article with.

Implementational Details

In order to facilitate the use of Perlin noise in general, and the various techniques derivative from it, I implemented a class in the engine code called FloatBufferClass that encapsulates a simple 2D float array, and provides a few handy methods for manipulating it. The map builder object maintains a pool of these buffers, so that all our script needs to do is request one of a given size.

buffer = Builder:RequestFloatBuffer(Width, Height)

And, of course, if we don't need it anymore we can release it.

Builder:ReleaseFloatBuffer(buffer)

This is a list of the pertinent useful methods of this class that we can call.

Set(x, y, v);                                                  // Set accessor
Get(x, y);                                                     // Get accessor, returns value

GetWidth()                                                     // Get buffer dimensions
GetHeight()

Fill(v);                                                       // Fill with given value
Clear();                                                       // Clear to 0
Copy(b);                                                       // Copy values from b
AddBuffer(b);                                                  // Add values in b to buffer
SubtractBuffer(b);                                             // Subtract values in b from buffer
MultiplyBuffer(b);                                             // Multiply all values by values in b
Scale(f);                                                      // Scale all values by f
	 
Normalize();                                                   // Clamp values to range [0..1]
CenterAt0();                                                   // Clamp values to the range [-1..1]

GeneratePerlin(seed, frequency, persistence, numoctaves);      // Generate noise
GeneratePerlinTile(seed, frequency, persistence, numoctaves);  // Generate noise that tiles

DumpToTga(filename);                                           // Save to a greyscale .TGA file
LoadFromTga(filename);                                         // Load from a greyscale .TGA file

For now, we're not interested in all of these. Most of them are fairly obvious anyway. The really interesting ones are GeneratePerlin and GeneratePerlinTile. GeneratePerlin fills the buffer with a Perlin noise map, using the specified values for the random seed, the frequency, persistence and number of octaves to populate the map. GeneratePerlinTile does the same, but the generated noismap tiles seamlessly with itself along all 4 edges.

Also useful is the Normalize function, which will normalize the buffer to the range [0..1]. Similarly, CenterAt0 will normalize the buffer to the range [-1..1], centering it at 0. The function DumpToTga works on a normalized buffer, and writes the buffer out as a greyscale .TGA bitmap file, for easy visualization. This is how all the perturbed images in the above discussion were generated. Similarly, LoadFromTga will load a greyscale bitmap into the buffer. Note that it will only load an image if the image is greyscale, and if it matches the buffer in dimensions.

Hopefully, using this class should simplify those cases when Perlin noise is needed; it may come in handy in other cases as well.

With this new class in hand, we can finally start looking at some actual real-world script code. First of all, let's take a look at a function with which we can perturb a given buffer, using specified turbulence and seed values.

perturb_buffer()-- Found in data/scripts/perturb.lua

function perturb_buffer(buf, turbulence, seed1, seed2)
 
 width=buf:GetWidth()
 height=buf:GetHeight()

 -- Request an output buffer
 out = Builder:RequestFloatBuffer(width, height)

 -- First, build the Perlin noise maps. 2 of them, one for each axis (X and Y).
 noise1 = Builder:RequestFloatBuffer(width, height)
 noise2 = Builder:RequestFloatBuffer(width, height)

 -- Some reasonable Perlin generation values
 noise1:GeneratePerlin(seed1, 0.00390625, 0.6, 8)
 noise2:GeneratePerlin(seed2, 0.00390625, 0.6, 8)

 -- Clamp to the range [-1..1]
 noise1:CenterAt0()
 noise2:CenterAt0()

 -- Now, iterate
 for x=0,width,1 do
  for y=0,height,1 do
   n1 = noise1:Get(x,y)
   n2 = noise2:Get(x,y)

   -- Perturb the (x,y) coordinate
   px = x+turbulence*n1
   py = y+turbulence*n2

   -- Wrap perturbed coordinates to stay in range 
   while (px<0) do px=px+width-1 end
   while (px>width-1) do px=px-(width-1) end
   while (py<0) do py=py+height-1 end
   while (py>height-1) do py=py-(height-1) end

   -- Now, get the noise value at the perturbed location
   out:Set(x,y,buf:Get(px,py))
  end
 end

 Builder:ReleaseFloatBuffer(noise1)
 Builder:ReleaseFloatBuffer(noise2)
 return out
end

This function takes a given input buffer, a turbulence parameter and two random seeds, and returns a new output buffer holding the perturbed result. To do so, it sets up a couple of noise maps (using some reasonable hard-coded magic numbers; parameterization might be desirable here, but I've found these defaults to be fairly workable for most things). Once it is finished, it releases the noise maps and returns a newly requested buffer holding the result of the operation.

How Can We Apply It?

So now that we know what we are trying to do, let's start talking about why we want to do it. How is this useful to us?

I hinted at one possible use earlier: pathways. Say we are trying to generate a forest level. We want glades and clearings, with pathways meandering in between. These pathways should go places, important places, though there can of course be dead ends where the trail tapers off. We can lay down a collection of lines and circles in a buffer using simple geometric primitives (circles, lines, boxes, etc...) then apply a noisification filter across it to make it look more natural.

If you want to see the technique in action, grab the latest binary of the engine here. Execute and in the console window enter the command dofile("data/scripts/perturb_map.lua"). This simple test script creates a new map and plunks down a bunch of random rectangles of terrain, then applies the perturbation technique to the buffer before translating the terrain values into the map. The script also dumps both versions of the terrain buffer (perturbed and non-perturbed) as greyscale .TGAs in the base directory in case you are interested in seeing the before and after patterns.

Feel free to tinker with the script as you see fit. Try calling perturb_buffer() with different values for turbulence to see how this factor controls the output.

Sample before and after buffer shots from perturb_map.lua

And of course, the obligatory (and pretty non-illustrative) screenshot--

Bloody brilliant and visually stimulating screenshot.

And that's it for this one. Hope you enjoyed it, and as always any feedback can be directed to me here.