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.
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.
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.
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--
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--
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.
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.
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.
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.
And of course, the obligatory (and pretty non-illustrative) screenshot--
And that's it for this one. Hope you enjoyed it, and as always any feedback can be directed to me here.