Understanding 1d Perlin Noise

Those intermediate points are generated by interpolating the values at the integer points.

For your example, if the point at 0 is assigned 0.3 and the point at one is assigned at 0.9, then the point at 0.5 would be equal to 0.3 + 0.5*(0.9-0.3) or 0.6.

A more general explanation:

If the input coordinate is called P, you can calculate the two bounding integral boundaries by:


P1=floor(P)
P2=P1+1


Then you call the function to obtain the values for P1 and P2. The interpolator is calculated as:


interp=P-P1


And the final interpolation (using a linear interpolation) is done as:

value=P1 + interp*(P2-P1)


Thanks for the answer, that clears up most of it.

To look at it in a way that's more applicable to what I'm trying to do, if I have a map that's 1000 units wide would I start out by assigning a random value to points at a specific distance apart (let's say every 100 spaces), then use an interpolation function to find the value of every point between those (1 to 99, 101 to 199, etc), and then finally plug every single point (0 to 1000) into the main Perlin Noise function? The code structure would look something like the following:

• Assign a random variable every 100 units, starting with 0 and working toward 1000.
• Loop through every single point and give it a value based on the interpolation of the value immediately before and after it. Do this until the maximum width is reached.
• Plug every integer value (0 to 1000) into the main Perlin Noise function. The value returned by this replaces the previous value for this point.

Your way seems to me to indicate a fundamental misunderstanding. The typical application of Perlin noise is as a function that operates separately from whatever you are applying it to. You supply the function with a set of coordinates, you get a value in return that you can store into an array. There is, and should be, no correlation between the function and the grid that you are filling from it.

The typical means I use to fill an Array from a given Perlin function is as follows:


RegionWidth: The width of the 2D region of the function to map to the grid
RegionHeight: The height of the 2D region of the function to map to the grid

MapWidth: The width of the 2D grid
MapHeight: The height of the 2D grid

PerlinFunc: 2D Perlin noise function

for x=0,MapWidth-1,1 do
for y=0,MapHeight-1,1 do
local nx=x/MapWidth
local ny=y/MapWidth
nx=nx*RegionWidth
ny=ny*RegionHeight

Array[x][y]=PerlinFunc:get(nx,ny)
end
end


Doing the mapping in this way allows me to easily specify a different size of area to map to the grid, and doesn't require multiple iterating of the grid to generate intermediate values.

I think that one of your misconception is that the values for the grid integer locations of the Perlin noise function need to be stored somewhere. They do not, but are simply calculated on the fly whenever they are needed. The Perlin noise function is basically a purely mathematical entity that doesn't store state, but merely calculates values on the fly as it is called.

[color=#1C2837][size=2]Your way seems to me to indicate a fundamental misunderstanding.[/quote]


Yep, and that's putting it lightly haha!


Going off of your example, in the case of a 1d array, would the X input for the Perlin Noise function simply be its point in the array (0 to 1000)? If you're trying to create terrain for an entire map why would the region width be different from the map width (you may just be using the function differently than I am)?

Now what lead me to believe I needed to assign a value to each point along the way was the fact that in the example code on the page I linked above he has X as a float. I assumed this to be the random value from 0 to 1. Would it be more accurate then to say that the following is true, or is that random value assigned elsewhere in the code?


Array[x]=PerlinFunc:get(RandomNoiseFunc(nx))



If this is the case it brings me back to my earlier question since from my understanding at this point you need to run the Perlin Noise function for every single point on the X axis, and each of these points is given a unique value from 0 to 1. My terrain is going to be block based, so I'm concerned that by randomly assigning heights to every single point (representing the location of a block) it will vary wildly rather than be a smooth transition. Will the combined result of the different amplitudes/frequencies result in a smooth transition?

The reason for my approach is that if you use the array coordinate as the input to the Perlin function then you get exactly what you are afraid of getting: a wildly varying terrain where every point is different. It is a matter of scale. Perlin noise provides what is called "continuously varying" noise, but the scale of it is such that the features (hills, valleys, whatever) are 1-unit in size. Every 1 unit in the function, there is a new value. So if you use the array coordinate unmodified, you are essentially creating one feature (hill or valley) for every array element. The result of this looks very much like white noise, or regular random noise.

By using a different region width, one that is much smaller than array width, you are in essences zooming into the function so that the features of it will be spread out across several array elements.

Also, your code:


Array[x] = Perlin:get(RandomNoiseFunc(nx))


shows that you still don't quite get it. A Perlin function is self-contained; the random noise generation is part of it.


for x=0,MapWidth-1,1 do
local nx=x/MapWidth
nx=nx*RegionWidth

Array[x]=Perlin(nx)
end


So if you had a RegionWidth of 3, in essence this would fill your array with what amounts to approximately three hills or valleys across. The reason the noise function input is a float is because the function is defined for any input point, not just integral input coordinates. Inputs that include a fractional part are evaluated by interpolating the enclosing integral-boundary values.

The pieces seem to be fitting together finally thanks to your explanation; I actually have it at a point where I can use the data it outputs to create the blocks. However, there are a few things that just don't seem to be lining up for me still.

In the following function, what is the purpose of changing the values into integers?


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


In the random noise function, does it matter what the seed is? In particular, I'm not familiar with the meaning of this bit of code: [font="monospace"]x = (x<<13) ^ x; [/font] Is it just converting the X value somehow, or does it relate to setting the seed? In my tests when I set the seed to the X value that gets plugged into the function the RegionWidth has an effect on the final output, but when I set it to use a random seed the output is *completely* random, with each point not appearing to relate to the others. I've uploaded a screenshot that has a comparison of the two. The top screenshot is using a random seed, and the bottoms screenshot is using the X input as the seed, with the RegionWidth set to 50 (as an aside, when I have it at 3 it's more or less a strait line; is this to be expected?). The problem with this is that every single time I run the program the values are all the same.

The pieces seem to be fitting together finally thanks to your explanation; I actually have it at a point where I can use the data it outputs to create the blocks. However, there are a few things that just don't seem to be lining up for me still.

In the following function, what is the purpose of changing the values into integers?


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


The point is that pseudo-random values are generated for integral coordinate locations. What the above function does is it takes an arbitrary input point and finds the enclosing integer coordinates. For each of those coordinates, a pseudo-random value is calculated. Then the fractional part is used to interpolate those positions.

So imagine that you call the function with x=5.5; taking the int of x gives us the value of 5, so we know that the coordinates X1=5 and X2=6 are the integer coordinates that enclose 5.5. Now, we feed these values of X1 and X2 to the SmoothedNoise function, which generates a pseudo-random value based on the coordinate. For example sake, assume that SmoothedNoise(5) returns 0.26 and SmoothedNoise(6) returns -0.95. We calculate the interpolant as the fractional part of x. This is simply done by subtracting X1 from x, since X1 is the nearest integer that is less than x. interpolant = x - X1. The result with x=5.5 and X1=5 is interpolant=0.5. Now, we use this interpolant to interpolate between the values of 0.26 and -0.95: value = 0.26 + interpolant * (-0.95 - 0.26) = 0.345. So the value of the function at x=5.5 is equal to 0.345.

In the random noise function, does it matter what the seed is? In particular, I'm not familiar with the meaning of this bit of code: [font="monospace"]x = (x<<13) ^ x; [/font] Is it just converting the X value somehow, or does it relate to setting the seed? In my tests when I set the seed to the X value that gets plugged into the function the RegionWidth has an effect on the final output, but when I set it to use a random seed the output is *completely* random, with each point not appearing to relate to the others. I've uploaded a screenshot that has a comparison of the two. The top screenshot is using a random seed, and the bottoms screenshot is using the X input as the seed, with the RegionWidth set to 50 (as an aside, when I have it at 3 it's more or less a strait line; is this to be expected?). The problem with this is that every single time I run the program the values are all the same.
[/quote]


All of the stuff that you see in the noise function is just a series of operations intended to hash the input integer coordinate to a pseudo-random value. A pseudo-random value is a value that is seemingly random, and apparently has no perceptible correlation to the value it is generated from, and yet is repeatable; ie, everytime the function is called with a given input it will provide the same output. The noise function provided there just does some magical trickery, including a multiplication by 8192 (which is what << 2[sup]13[/sup] does ) then XORs the result with the original value of x. Then it does some additional trickery. The actual mechanics of this really aren't important; there are a thousand ways that you could perform this hash. The result is what is important: a seemingly random, repeatable value. The random-part of pseudo-random is what ensures that subsequent values (ie the function at x=5 and the function at x=6) have no relation to one another and thus will generate no visible patterns in the output.

What provides the "magic" of this technique is the deterministic aspect of it: that plugging in the coordinate to the noise function nets you the same output each time. Imagine the chaos that results if you evaluate the point x=4.5 where X1=4 and X2=5, and the randomized output of Noise(X2=5) was 0.26. But then you evaluated the point 5.5 where X1=5 and X2=6, but this time the value of Noise(X1=5) outputted 0.45 instead of 0.26 as it did initially. There would be not continuity, and the final output of the function would be chaos; or, basically, what you got in your top screenshot.

Now, if you do want to be able to provide a random seed to change the behavior of the function, you have to make it a part of the IntNoise function, and fold it into the hash somehow. And, of course, you have to ensure that you always provide the same seed for a given mapping or evaluation of the function across a map or array; if the seed changes all the time, then the result would be the same kind of chaos as using a random input to IntNoise.

Well, I now have a working Perlin Noise function. Just need to spend some time playing with the values until I get the results I want. On the topic of using a seed value, I ended up just plugging another value into the random noise function right before it multiplies x * x, so it's now var_SeedValue * x * x. I also need to figure out the best way to convert the output values into something I can use, though I think some simple cross-multiplication will do the trick.

A huge thank you for all your help! I like understanding the code I put into my program and your thorough explanations (and patience) got me to that point

You're welcome. I'm actually in the process of putting together several more articles about various uses of noise at http://accidentalnoise.sourceforge.net/ where my noise library is available for download. Currently, I've got a rework of my article on using 3D noise to generate cube-style worlds. It's based on an earlier set of journal posts I had made, as well as an article I wrote for the April 2011 issue of Game Developer Magazine. The article discusses generating 3D Minecraft-style worlds as well as 2D side view Minecraft-alikes as a composition of various functions. Might be of interest to you, and I have more stuff on the way as I find time for it.

Wow, looks like a fantastic source of info! Will definitely spend some time digging through there. Looking forward to more in the future too.

You probably won't see this comment, but in case you do, I'm not sure my Perlin Noise is functioning correctly. Despite me having the persistence value set at 1/4, the transition from one to another doesn't seem to be smoothed out (here's the image). Do you happen to know what's likely to cause this?

Can you post your code?

Thanks for the reply. I'm using DarkBasic Pro, but hopefully you can make sense of it. The value for glob_PerlinNoise_Persistance# is set at 0.25, and the value of glob_PerlinNoise_OctaveMax is set at 3.

Code that calls the function.


FOR var_PositionX = 0 TO var_WorldGen_WorldWidth - 1
var_X# = var_PositionX / var_WorldGen_WorldWidth#
var_X# = var_X# * var_WorldGen_Regions

arr_WorldGen_WidthData(var_PositionX) = var_WorldGen_Dirt_BorderStart + ((((func_PerlinNoise1D_Combined(var_X#) + 1.0) * var_WorldGen_HeightVariation) / 2.0) - (var_WorldGen_HeightVariation / 2))
NEXT var_PositionX


Perlin Noise code.


FUNCTION func_PerlinNoise1D_Combined(var_X#)
var_Total# = 0

FOR var_Octave = 0 TO glob_PerlinNoise_OctaveMax
var_Frequency = 2 ^ var_Octave
var_Amplitude# = glob_PerlinNoise_Persistance# ^ var_Octave

var_Total# = var_Total# + func_PerlinNoise1D_Interpolate(var_X# * var_Frequency) * var_Amplitude#
NEXT var_Octave

ENDFUNCTION var_Total#

FUNCTION func_PerlinNoise1D_Interpolate(var_X#)
var_X_Integer = INT(var_X#)
var_X_Fraction# = var_X# - var_X_Integer

var_SmoothNoise_1# = func_PerlinNoise1D_Smooth(var_X_Integer)
var_SmoothNoise_2# = func_PerlinNoise1D_Smooth(var_X_Integer + 1)

var_Interpolate# = func_PerlinNoise1D_InterpolateCosine(var_SmoothNoise_1#, var_SmoothNoise_2#, var_X_Fraction#)
ENDFUNCTION var_Interpolate#

FUNCTION func_PerlinNoise1D_InterpolateCosine(var_SmoothNoise_1#, var_SmoothNoise_2#, var_X_Fraction#)
var_Value1# = var_X_Fraction# * 3.1415927
var_Value2# = (1 - COS(var_Value1#)) * 0.5

var_InterpolateCosine# = var_SmoothNoise_1# * (1 - var_Value2#) + var_SmoothNoise_2# * var_Value2#
ENDFUNCTION var_InterpolateCosine#

FUNCTION func_PerlinNoise1D_Smooth(var_X)
var_SmoothNoise# = func_PerlinNoise1D_Random(var_X) / 2.0 + func_PerlinNoise1D_Random(var_X - 1) / 4.0 + func_PerlinNoise1D_Random(var_X + 1) / 4.0
ENDFUNCTION var_SmoothNoise#

FUNCTION func_PerlinNoise1D_Random(var_X)
var_X = (var_X << 13) ~~ var_X
var_Random# = (1.0 - ((var_X * (glob_WorldGen_Seed * var_X * var_X * 15731 + 789221) + 1376312589) && 0x7fffffff) / 1073741824.0)
ENDFUNCTION var_Random#


In the image that you posted, how many array samples are represented? Does one height sample represent a column of pixels, or a column of larger blocks? I'm not seeing anything in the posted code that jumps out at me, but it would be useful to see what you are doing to between the posted code and drawing to the screen.

That's determined using your "region" method. This is the code that converts the output from the Perlin Noise (which will be a value from -1.0 to 1.0) into something that's usable.

[color=#1C2837][size=2][color=#000000]arr_WorldGen_WidthData[color=#666600]([color=#000000]var_PositionX[color=#666600])[color=#000000] [color=#666600]=[color=#000000] var_WorldGen_Dirt_BorderStart [color=#666600]+[color=#000000] [color=#666600](((([color=#000000]func_PerlinNoise1D_Combined[color=#666600]([color=#000000]var_X[color=#880000]#) + 1.0) * var_WorldGen_HeightVariation) / 2.0) - (var_WorldGen_HeightVariation / 2))

To break it down a bit, there are three main values being combined in the code, but only this one is relevant to my problem: [color=#1C2837][font=CourierNew, monospace][size=2][color=#666600](((([color=#000000]func_PerlinNoise1D_Combined[color=#666600]([color=#000000]var_X[color=#880000]#) + 1.0) * var_WorldGen_HeightVariation) / 2.0)[/font]". Here you see the value "[color=#880000][font=CourierNew, monospace][size=2]var_WorldGen_HeightVariation[/font]" appear; this is the maximum amount of blocks I want the border to be able to vary, which is set at 0.05% of the total map height. The Perlin Noise function is called, and immediately after being called the value it returns (again, -1.0 to 1.0) is increased by 1.0. This gets multiplied by "[color=#880000][font=CourierNew, monospace][size=2]var_WorldGen_HeightVariation[/font]" and then divided by 2.0. I'm making it sound more complicated then it really is, since It's pretty much just cross multiplication.

Hopefully I answered your question, but if not let me know. Off to work for now, but I'll be able to elaborate further after I'm back.

What I'm asking is how are you converting the array full of noise values to the image that is shown on screen? Does each element in the array correspond to the height of one column of pixels in the output image? If that is the case, then it seems you have an interpolation problem. Or is one element in the array correspond to a column of blocks, where the blocks are comprised of some MxN pixels? If this is the case, then it is possible you don't really have a problem, since "magnifying" what is essentially a pixel array would serve to also magnify the stepped jaggedness of a function.

Oh sorry, I understand now. One element in the array is equivalent to one column of blocks. I was using the Cosine interpolation method (which was probably unnecessary to begin with since I'm dealing with blocks, not smooth lines), but I switched it to Linear and it's working wonderfully now. Thanks yet again!

You're welcome, glad that you got it working.