ID:585163
 
I am trying to wrap my ahead around how to implement a Perlin noise function for a random map.

Let's say I have a 2 dimensional side view map. Further, there are three tile types. Air is non dense and must make up at least the player height above the other surfaces. Dirt should be below air. Stone can randomly occur among dirt (lower increases frequency).

Now I was looking at http://freespace.virgin.net/hugo.elias/models/m_perlin.htm and cannot figure out how to apply the concepts there. I understand that each octave is an iteration, but cannot translate the rest to practical application.

Anybody have any thoughts or experience and can dumb it down a bit for me?
You can make a heightmap using Perlin noise. The simplest island generator technique I can think of is to just assign tile types based solely on the height (z) of each coordinate. For example, from 0 to 100, any pixel with a z coordinate less than 60 is water.
I'm not too familiar with map generation or Perlin Noise, but this might be useful to you:

gamedev.stackexchange.com wrote:
To build a worms-like level, I would probably use a Perlin-Noise function though. If you generate a perlin noise image with the height of 1px and the width of your game-world, then you basically get a height map, ready to use. Perlin noise functions also always generate the same map with the same seed.

So you could effectively generate a 1D Perlin Noise wave, and use that as your map's heightmap, and fill it in with dirt based on that. Then you could just use a more typical weighted random function to swap dirt with stone.

This also looks like an interesting site:
http://pcg.wikidot.com/
If you want turfs to be stacked like this:

+-----------------+
| air |
+-----------------+
| dirt |
+-----------------+
| stone |
+-----------------+

With some random variation, I'd do something like this:

for(var/turf/t in world)

// Add a random value to the turf's y coordinate.
var/ty = t.y + noise(t.x, t.y)

// Put ty on the 0-1 scale.
ty = ty / world.maxy

if(ty < 0.3)
new /turf/stone(t)
else if(ty < 0.8)
new /turf/dirt(t)
else
new /turf/air(t)

Roughly the bottom 30% of the map will be stone, the top 20% will be air, and the rest will be dirt. You can adjust the values in the if statements to adjust those percentages and you can multiply the noise value by a constant to make the variations bigger or smaller.
According to the article, the Perlin noise function is a sum of different smoothed and interpolated noise functions with increasing frequency and decreasing amplitude. I'll simply summarise and break down the terms and then explain how the author's implementation works (disclaimer: I've never heard of the term 'Perlin noise' before so it may be I got something wrong).

First, the introduction explains nicely what a noise function is; simply a random number generator, like rand() in DM, except that it takes some parameter p, and will always return the same value when fed that parameter. In essence it's just a function, f(x). The term 'different' simply means that we need several of these functions, that return different values for a given p. To create different functions one simply needs to change a few constants in the random number generator the author gives:

function IntNoise(32-bit integer: x)

x = (x<<13) ^ x;
return ( 1.0 - ( (x * (x * x * 15731 + 789221) + 1376312589) & 7fffffff) / 1073741824.0);

end IntNoise function


Instead of 15731, 789221, 1376312589 and 1073741824.0, put different prime numbers that are close in size. As to how many of these you will need... well, it is as you please. Add as many as you like, until you no longer notice a change in the visual endresult of the Perlin noise-generated map.

'Smoothed' simply means that the values of the functions are close to each other and don't abruptly 'jump'. In the article, the author is simply doing this by comparing the value of the noise function at p, p-1 and p+1, and taking a weighted average of those values. 'Interpolation' is a technique by which you create a continuous function from a bunch of discrete values (in other words, given a bunch of dots on a graph, you basically draw a line between them). Given that f(a)=x and f(b)=y for some function f, interpolation is simply a technique of guessing what f would equal for values between a and b. The author gives a few algorithms by which this might be done.

What does frequency means? It's simply how 'chaotic' or 'jumpy' the function is. The concept is pretty close to what we call variance in probability theory.

Amplitude could be seen as the general range of values a function 'returns'. E.g. if f(x) always equals a value between 0.0001 and -0.0001, one could say it has a pretty small amplitude.

The noise functions we successively add to the sum total have increasing frequency (they are increasingly chaotic) and decreasing amplitude (they affect the overall sum decreasingly). The author recommends making the frequency be 2^i, where i is the current iteration, and amplitude to be p^i, where 'p' is 'persistence', which is some value between 0 and 1. Since both the frequency and the amplitude are exponentially growing, one can see that our noise functions will very quickly become such that they are very very chaotic, but also return very very small values.

So let's break down the author's final implementation for 1-dimensional Perlin noise:

function Noise1(integer x)
x = (x<<13) ^ x;
return ( 1.0 - ( (x * (x * x * 15731 + 789221) + 1376312589) & 7fffffff) / 1073741824.0);
end function


This is simply one of the noise functions that will end up being smoothed, interpolated, and finally summed up. You'll want several of those. You'll want several of those.

 function SmoothedNoise_1(float x)
return Noise(x)/2 + Noise(x-1)/4 + Noise(x+1)/4
end function


We smooth a given noise function (say, Noise1) at x by taking a weighed average of its values at x-1, x, and x+1.

function InterpolatedNoise_1(float x)

integer_X = int(x)
fractional_X = x - integer_X

v1 = SmoothedNoise1(integer_X)
v2 = SmoothedNoise1(integer_X + 1)

return Interpolate(v1 , v2 , fractional_X)

end function


This is an interpolated and smoothed noise function. Given a float x, it converts it to an integer (since our Noise function can't take float values. This is why it needs to be interpolated in the first place!), turns that integer into a random value and smooths it. It does the same for the integer value + 1, and then it interpolates between the two (that is, it guesses what the noise function would be between [integer X] and [integer X + 1] if it was continuous and behaved 'sanely').

Finally, here is the Perlin noise implementation:

function PerlinNoise_1D(float x)

total = 0
p = persistence
n = Number_Of_Octaves - 1

loop i from 0 to n

frequency = 2i
amplitude = pi

total = total + InterpolatedNoisei(x * frequency) * amplitude

end of i loop

return total

end function


This is simply an exact implementation of the algorithm we described. Note how the author makes each InterpolatedNoise_i grow in frequency by multiplying 'x' by 'frequency' (intuitively this will make the function more chaotic since instead of spreading out its 'behaviour' over an interval [x,y], it now has to squeeze everything inside the interval [x/frequency,y/frequency]), and become smaller in amplitude by scaling the final result by a factor of [amplitude].

The Perlin noise function is simply that, a function, which ends up giving some nice, 'rational'-looking values which you can use in a random map generator (see Forum_account's post as to how).

Hope this helps!
If you need an implementation of Perlin noise, the Icon Processor library has one.
Then you should have said that and spared me reading that article :(.

Anyhow, your implementation seems interesting to me because (if I understood it correctly) you seem to be generalizing the algorithm described by the article to 3-dimensional space, doing the 'interpolated noise' process with random 3D gradient vectors.

Can you spare a few words on why you're doing it this way? Interestingly you also don't take the magnitude of the endresult vector in value() (it occurred to me that this might be precisely the reason), so I'm wondering whether and how you end up using the actual vector as well.

e- Okay, took a bit more time to look at the library and found out how it's used in the cloud demo. Very slick.
Thank you very much for the explanation- it really clarified things. Essentially Perlin is just a randomizer coupled with a gradient interpolation. So it essentially just generates random values and "smooths" them out.
Hey, so my work wasn't in vain after all :). Glad to help!

e- The Perlin noise is not exactly just a smoothed randomizer. In essence it is an interpolated, smoothed randomizer that has some chaos added to it as not to be 'boring' (thus allowing for pebbles to sometimes appear among dirt).
Toadfish wrote:
Anyhow, your implementation seems interesting to me because (if I understood it correctly) you seem to be generalizing the algorithm described by the article to 3-dimensional space, doing the 'interpolated noise' process with random 3D gradient vectors.

3D noise is about all you'll need for 2D icons. If you wanted to make animations (it's good for things like smoke or fire) you can use time as the z value when you get noise values.

[Edit: Here is an example of a fire animation. Animating smoke would be similar to the cloud demo except you'd make animated states by increasing the z value you use to sample the noise function, making the pixel offsets you apply gradually change.]

Can you spare a few words on why you're doing it this way? Interestingly you also don't take the magnitude of the endresult vector in value() (it occurred to me that this might be precisely the reason), so I'm wondering whether and how you end up using the actual vector as well.

Sometimes you care about the result as an actual vector, not just it's magnitude. The cloud demo is an example of this - it uses two components of the vector to offset each pixel.

Jmurph wrote:
Thank you very much for the explanation- it really clarified things. Essentially Perlin is just a randomizer coupled with a gradient interpolation. So it essentially just generates random values and "smooths" them out.

Also, by sampling the noise at multiple frequencies you can create more interesting things.