So I’ve been struggling with making 2D Perlin Noise for about a week. Most of the stuff on the web seems to assume you have a degree in mathematics… kinda daunting. Ken Perlin’s source code is heavily optimized to the point of obfuscation so it wasn’t much help either. However I did find the following resources helpful:
Ken Perlin’s slideshow about Perlin Noise – This gave me a high level view of what PN is and the images certainly inspired me to pursue it a little further.
Hugo Elias’s page – This gives a good visual understanding of the concept behind Perlin Noise, and helped me implement the 1D version. However the 2D algorithm doesn’t seem to corespond to Perlin’s implementation ( I could be wrong).
Matt Zucker’s page – a pretty thorough and clear explanation of Perlin’s implementation (as far as I can tell.) My implementation is directly following this explanation.
I also did some research into Psuedo Random number generators… ultimately found the Park Miller Carta generator to be the one of choice. It boils down to a single line of code:
seed = seed * 16807 % 0x7FFFFFFF;
Which, when executed recursively, produces a sequence of numbers of sufficient randomness between 0 & 0x7FFFFFFF. I also found an AS3 PRNG implementation which is nicely done. However since it can be done in one line I decided to just do that. You do need to start it off with a random seed, so for that I just used plain old Math.random(). In fact I could probably have just used Math.random() for everything since it’s probably just a PRNG under the hood anyways…. whatever.
So here’s a demo of my implementation, with sliders for amplitude and frequency. Note that it is only one ‘layer’ of noise here : the next step is to add many layers together as I did in the 1D example previously.
You’ll need Flash Player 10 as I used the new Vector type. See previous posts for where to get it.
Here’s the code, first the demo itself:
package {
import flash.display.Sprite;
import flash.display.Bitmap;
import flash.display.StageScaleMode;
import flash.display.StageAlign;
import flash.display.BitmapData;
import flash.text.TextField;
import flash.events.Event;
import com.bit101.components.*;
import flash.geom.Rectangle;
[SWF(backgroundColor="0xFFFFFF", width="600", height="400", frameRate="30")]
public class PerlinNoise2D extends Sprite {
private const imgWidth:Number = 300;
private const imgHeight:Number = 300;
private var octaves:int = 8;
private var decay:Number= 1;
private var amplitude:Number=1;
private var frequency:Number=3;
private var bm:Bitmap;
private var bmd:BitmapData;
public function PerlinNoise2D() {
stage.scaleMode = StageScaleMode.NO_SCALE;
stage.align = StageAlign.TOP_LEFT;
//create a bitmap data
bmd = new BitmapData(imgWidth, imgHeight, false, 0x000000);
//create a bitmao using the data object
bm = new Bitmap(bmd);
addChild(bm);
drawGradient(amplitude,frequency);
drawUI();
}
private function drawUI():void {
var ui:Sprite = new Sprite();
//amplitude
var amplitude_sldr:HSlider = new HSlider(ui, 50, 20, function(e:Event):void {
amplitude = e.target.value;
amplitude_val.text = ""+amplitude;
drawGradient(amplitude,frequency);
});
amplitude_sldr.setSliderParams(0,1,1);
var amplitude_lbl:Label = new Label(ui, 0, 15, "amplitude");
var amplitude_val:Label = new Label(ui, 150, 15, "1");
//frequency - between 0 & 1
var frequency_sldr:HSlider = new HSlider(ui, 50, 40, function(e:Event):void {
frequency = Math.round(e.target.value);
frequency_val.text = ""+frequency;
drawGradient(amplitude,frequency);
});
frequency_sldr.setSliderParams(1,10,3);
var frequency_lbl:Label = new Label(ui, 0, 35, "frequency");
var frequency_val:Label = new Label(ui, 150, 35, "3");
ui.x = 300;
ui.y = 5;
ui.alpha= 0.8;
addChild(ui);
}
private function drawGradient(a:Number, f:Number):void {
var c:uint;
var perlin:PerlinNoise = new PerlinNoise();
bmd.fillRect(new Rectangle(0, 0, imgWidth, imgHeight), 0x000000);
//get 2D Perlin noise
var pNoise:Array = perlin.getPerlinNoise_2D(imgWidth,a/*amplitude*/,f/*frequency*/);
//loop through each point and draw
for(var x:int = 0; x < imgWidth; x++){
for(var y:int = 0; y < imgHeight; y++){
//normalize pNoise from -1 - 1 to 0-1 range (x255 for color)
var r:int = Math.floor((pNoise[x][y]/2 + 0.5)*256);
c = r << 16 | r << 8 | r;
bmd.setPixel(x,y,c);
}
}
}
}
}
// Copyright (c) 2008 David Wilhelm
// MIT license: http://www.opensource.org/licenses/mit-license.php
And now the PerlinNoise class that does all the hard work :)
package {
public class PerlinNoise {
//initialize random seed
public var seed:uint = prng(Math.random()*0x7fffffff);
public function PerlinNoise() {
/*call getPerlinNoise_1D*/
}
public function getPerlinNoise_1D(len:int=200, octaves:int=8, decay:Number=1):Array {
var graph:Array;
//totalGraph holds accumulated values
var totalGraph:Array = getNoiseFunctionResults(len, 1, 1);
var totalAmplitude:Number= 1;//used to normalize amplitude
for(var o:int = 1; o <= octaves; o++){
if(Math.pow(2,o) < len) {//cannot have frequency > len
graph = getNoiseFunctionResults(len, Math.pow(decay,o)/*amplitude*/, Math.pow(2,o)/*frequency*/);
totalAmplitude+=Math.pow(decay,o);
for(var g:int = 0; g < graph.length; g++){
//add the graphs together by shifting them so they are centred on y=0 (subtract their amplitude/2)
totalGraph[g] += graph[g];
}
}
}
//normalize values in totalGraph to be between -0.5 & 0.5 by dividing by accumulated amplitude
for(var i:int = 0; i < totalGraph.length; i++){
totalGraph[i] = totalGraph[i]/totalAmplitude;
}
return totalGraph;
}
public function getPerlinNoise_2D(size:int=200, amplitude:Number=1, frequency:int=5):Array {
var spacing:Number = size/frequency;
var gradient:Array = [];
var gp:Vector.<Number>;//grid point
var seed:uint;
var nextseed:uint = prng(Math.random()*0x7fffffff);
for(var g:int = 0; g <= frequency; g++){
gradient[g] = [];
for(var h:int = 0; h <= frequency; h++){
seed = prng(nextseed); //using 'old' nextseed ;-)
nextseed = prng(seed);
//each point in the gradient is a 2-point vector
gp = gradient[g][h] = new Vector.<Number>(2,true);//fixed length vector - maybe help memory use?
gp[0] = (seed/0x7fffffff)*2 - 1;
gp[1] = (nextseed/0x7fffffff)*2 - 1;
}
}
//calculate the resulting value for each x,y
var results:Array = []
var gx0:int;
var gx1:int;
var gy0:int;
var gy1:int;
var s:Number;
var t:Number;
var u:Number;
var v:Number;
for(var x:int= 0; x < size; x++){
results[x] = [];
for(var y:int = 0; y < size; y++){
//determine the surrounding gridpoints as multiples of spacing
gx0 = Math.floor(x/spacing);
gx1 = gx0+1;
gy0 = Math.floor(y/spacing);
gy1 = gy0 +1;
var xf:Number = (x - gx0)/spacing;//x as a fractional value of spacing
var yf:Number = (y - gy0)/spacing;//y as a fractional value of spacing
//calculate the dot-products of the 2 vectors
/*s = g(x0, y0) · ((x, y) - (x0, y0)) ,
t = g(x1, y0) · ((x, y) - (x1, y0)) ,
u = g(x0, y1) · ((x, y) - (x0, y1)) ,
v = g(x1, y1) · ((x, y) - (x1, y1)) . */
/*s = gradient[x0][y0] · [xf - gx0, yf - gy0];
t = gradient[x1][y0] · [xf - gx1, yf = gy0];
u = gradient[x0][y1] · [xf - gx0, yf - gy1];
v = gradient[x1][y1] · [xf - gx1, yf - gy1];*/
s = gradient[gx0][gy0][0]*(x/spacing - gx0)+ gradient[gx0][gy0][1]*(y/spacing - gy0);
t = gradient[gx1][gy0][0]*(x/spacing - gx1) + gradient[gx1][gy0][1]*(y/spacing - gy0);
u = gradient[gx0][gy1][0]*(x/spacing - gx0) + gradient[gx0][gy1][1]*(y/spacing - gy1);
v = gradient[gx1][gy1][0]*(x/spacing - gx1) + gradient[gx1][gy1][1]*(y/spacing -gy1);
//calcuate the weighted averages
var Sx:Number = S_curve(x/spacing-gx0);
var a:Number = s + Sx*(t - s);
var b:Number = u + Sx*(v - u);
var Sy:Number = S_curve(y/spacing - gy0);
var z:Number = a + Sy*(b - a);
results[x][y] = z;
}
}
return results;
}
// S-curve takes number between 0 & 1 and shifts its closer to 0 or 1
private function S_curve(p:Number):Number {
return 3*p*p - 2*p*p*p;
}
private function getNoiseFunctionResults(len:int=200, amplitude:Number=1, freq:int=1):Array {
//trace("getNoise(amplitude="+amp+",frequency"+freq+")");
var result:Number = 0;//between -0.5 & 0.5
var wavelength:Number= len/freq;//divide imgWidth by frequency to get wavelength
var results:Array = [];
//start with random seed
var seed:uint = Math.round(Math.random()*0x7FFFFFFF); //seed for prng... can be any uint (except 0)
//get next seed - used for interpolation
var nextseed:uint = prng(seed);
//for each x value
for(var x:int = 0; x < len; x++){
//if we are on a factor of wavelength ... get psuedorandom y value
if(x % wavelength == 0){
//store nextseed as seed
seed = nextseed;
//get next nextseed
nextseed = prng(seed);
//get y value from pseudorandom number
result = (seed/0x7FFFFFFF)*amplitude - amplitude/2;
} else {
//interpolate value between seed & nextseed
result = (interpolate(seed, nextseed, (x % wavelength)/wavelength)/0x7FFFFFFF)*amplitude - amplitude/2;
}
results.push(result);
}
return results;
}
private function prng(seed:uint):uint {
//to get a full period sequence you should feed back the seed
return seed * 16807 % 0x7FFFFFFF;
//return 0xCCCCCCCC;
//to get a value between 0 & 1, divide result / 0x7FFFFFFF
}
private function interpolate(a:int,b:int,i:Number):Number {
//cosine interpolation
var ft:Number = i*Math.PI;
var f:Number = (1 - Math.cos(ft)) * .5;
return a*(1-f) + b*f;
}
}
}
// Copyright (c) 2008 David Wilhelm
// MIT license: http://www.opensource.org/licenses/mit-license.php
There’s probably room for optimization, but I want to keep it fairly readable, and comprehensible.. at least for myself.