Skip to content

Instantly share code, notes, and snippets.

@agrothe

agrothe/perlinNoise.ts

Created December 26, 2019 16:17
Show Gist options
  • Save agrothe/868f0c99bbd07eb6e94c5b369a064109 to your computer and use it in GitHub Desktop.
Save agrothe/868f0c99bbd07eb6e94c5b369a064109 to your computer and use it in GitHub Desktop.
Download ZIP
Perlin Noise 4: Procedurally Generated Terrain (via David Logue)
Raw
perlinNoise.ts
/*
____ _ _ _ _ _
/ ___|| | _____ _| | | | __ _ __| | ___ | | _____ _ __
\___ \| |/ _ \ \ /\ / / |_| |/ _` |/ _` |/ _ \| |/ / _ \ '_ \
___) | | (_) \ V V /| _ | (_| | (_| | (_) | < __/ | | |
|____/|_|\___/ \_/\_/ |_| |_|\__,_|\__,_|\___/|_|\_\___|_| |_|
Original by David Logue: https://codepen.io/Daboo/pen/JNbpwq?editors=0010#0
TypeScriptified by https://github.com/agrothe
Usage:
let noise = new SlowHadoken.PerlinNoise();
let offset = noise.vector3d({x: 0, y: 0, z: 0});
let seed = (new Date()).getTime();
let map = noise.create2dHeightMap(500,400,seed,200,4,0.5,3,offset);
console.log(map);
*/
export namespace SlowHadoken {
export interface vector {
x: number;
y: number;
z: number;
}
// Hash lookup table as defined by Ken Perlin.
// Randomly arranged array of all numbers from 0-255 inclusive.
const permutation = [ 151,160,137,91,90,15,
131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
];
// Amplitude, y axis.
// Frequency, x axis.
// Octave, noise map as layer. Layering multiple octaves preserves general shape while adding detail.
// Persistence, controls decrease in amplitude of octaves.
// Lacunarity, controls increase in frequency of octaves.
export class PerlinNoise {
// doubled permutation to avoid overflow
p: Array<number> = [];
constructor(){
for (let i = 0; i < 256; i++) {
this.p[256+i] = this.p[i] = permutation[i];
}
}
// vector object used for offset
vector3d(v: vector): vector {
return {
x: v.x || 0,
y: v.y || 0,
z: v.z || 0
}
}
// Fade function as defined by Ken Perlin.
// Smooths out coordinates so they ease towards integral values.
fade(t:number) : number {
return t * t * t * (t * (t * 6 - 15) + 10); // 6t^5 - 15t^4 + 10t^3
}
// Linear interpolation
lerp(t:number, a:number, b:number): number {
return a + t * (b - a);
}
// Calculates the product of a randomly selected gradient vector and the 8 location vectors.
grad(hash: number, x: number, y: number, z: number): number {
// Take the hashed value and it's first 4 bits (15 == 0b1111)
let h = hash & 15;
// If the most significant bit (MSB) of the hash is 0 then set u = x. Otherwise u = y.
let u = h < 8 /* 0b1000 */ ? x : y;
// If the first and second significant bits are 0 set v = y
// If the first and second significant bits are 1 set v = x
// If the first and second significant bits are not equal (0/1, 1/0) set v = z
let v = h < 4 /* 0b0100 */ ? y : h == 12 /* 0b1100 */ || h == 14 /* 0b1110*/ ? x : z;
// Use the last 2 bits to decide if u and v are positive or negative.
// Then return their addition.
return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
}
// Simulates elevation i.e. distance from the map
scale(n: number): number {
return (1 + n)/2;
}
// Calculates Perlin noise float value between 0 and 1 for x, y, z
noise = function(x: number, y: number, z: number): number {
// Find unit cube aka "region" that contains our sample point, int.
let xi = Math.floor(x) & 255;
let yi = Math.floor(y) & 255;
let zi = Math.floor(z) & 255;
// Find relative x,y,z of our sample point in cube between 0.0f and 1.0f
let xf = x-Math.floor(x);
let yf = y-Math.floor(y);
let zf = z-Math.floor(z);
// Compute fade curves for x,y,z floats.
let u = this.fade(xf);
let v = this.fade(yf);
let w = this.fade(zf);
// Hash coordinates or the 8 cube corners and add blended results from 8 corners of cube.
let A = this.p[xi ]+yi, AA = this.p[A]+zi, AB = this.p[A+1]+zi;
let B = this.p[xi+1]+yi, BA = this.p[B]+zi, BB = this.p[B+1]+zi;
// The gradient function calculates the dot product between a
// pseudorandom gradient vector and the vector from the input coordinate to
// the 8 surrounding points in its unit cube aka "region".
// All of this is then lerped together as a weighted average based on the faded u,v,w values.
return this.scale(this.lerp(w, this.lerp(v, this.lerp(u,
this.grad(this.p[AA ], xf , yf , zf ),
this.grad(this.p[BA ], xf-1, yf , zf )),
this.lerp(u, this.grad(this.p[AB ], xf , yf-1, zf ),
this.grad(this.p[BB ], xf-1, yf-1, zf ))),
this.lerp(v, this.lerp(u, this.grad(this.p[AA+1], xf , yf , zf-1 ),
this.grad(this.p[BA+1], xf-1, yf , zf-1 )),
this.lerp(u, this.grad(this.p[AB+1], xf , yf-1, zf-1 ),
this.grad(this.p[BB+1], xf-1, yf-1, zf-1 )))));
}
// Layers noise with multiple octaves. Octaves arg sets number of layers.
perlinOctaves(
x: number,
y: number,
z: number,
octaves: number,
persistence: number,
lacunarity: number,
octaveOffsets: Array<vector>)
{
let amplitude: number = 1; // higher the amplitude means range in height is greater
let frequency: number = 1; // higher frequency means height values change rapidly
let noiseHeight: number = 0; // value returned by this function
let perlinValue: number = 0; // perlin value modified by frequency and amplitude
let octaveX: number; // used to adjust for offset values
let octaveY: number;
let octaveZ: number;
// iterate over perlin values a number of times equal to octaves
for (let i = 0; i < octaves; i++) {
// apply frequency to x, y and z including offset values if any
octaveX = (x*frequency) + octaveOffsets[i].x;
octaveY = (y*frequency) + octaveOffsets[i].y;
octaveZ = (z*frequency) + octaveOffsets[i].z;
// noise returns a value between 0.0f and 1.0f
// noise * 2 - 1 returns perlin values between -1.0f and 1.0f
perlinValue = this.noise(octaveX,octaveY,octaveZ) * 2 - 1;
// increase noise height by the Perlin value of each octave
noiseHeight += perlinValue * amplitude;
// now at the end of our octave
// amplitude decreases every octave because persistence is 0.0f to 1.0f
amplitude *= persistence;
// frequency increases every octave because lacunarity is greater than 1
frequency *= lacunarity;
}
return noiseHeight; // return modified perlin noise value -1.0f to 1.0f
};
// Inverse linear interpolation.
// Returns a value between 0.0f through 1.0f for x relative to arguments a and b
inverseLerp = function(a: number, b: number, x: number) {
return ((x - a) / (b - a));
}
// seedable random offset
octaveOffsets(seed: number, octaves: number, offset: vector) {
let octaveOffsets = [];
let rand = new MersenneTwister(seed); // null argument returns a random number
let min = -100000;
let max = 100000;
let randNum: number;
let offsetX: number;
let offsetY: number;
let offsetZ: number;
for (let i = 0; i < octaves; i++) {
// random number between -100,000 and 100,000 inclusive
randNum = Math.floor(rand.random() * (max - min + 1)) + min;
offsetX = randNum + offset.x;
offsetY = randNum + offset.y;
octaveOffsets[i] = this.vector3d({x: offsetX, y: offsetY, z: offsetZ});
}
return octaveOffsets;
};
// Normalizes perlin noise octave values from -1.0f through 1.0f to 0.0f through 1.0f
normalizeNoise(heightMap: Array<number>) {
let normalized: Array<number> = [];
let noiseHeight: number = 0;
let maxNoiseHeight: number = -Number.MAX_VALUE; // lowest possible value
let minNoiseHeight: number = Number.MAX_VALUE; // highest possible value
// creates min and max range out of all values in perlin height map -1 through 1
for(let i = 0; i < heightMap.length; i++) {
noiseHeight = heightMap[i];
if (noiseHeight > maxNoiseHeight) {
maxNoiseHeight = noiseHeight;
} else if (noiseHeight < minNoiseHeight) {
minNoiseHeight = noiseHeight;
}
}
// normalizes perlin hight map values to 0.0 through 1.0 using inverse interpolation
for (let i = 0; i < heightMap.length; i++) {
// inverse interpolation turns minNoiseHeight to 0.0 and maxNoiseHeight to 1.0
normalized[i] = this.inverseLerp(minNoiseHeight,maxNoiseHeight,heightMap[i]);
}
return normalized;
};
// creates layered height map from Perlin noise functions above
create2dHeightMap(
mapWidth: number,
mapHeight: number,
seed: number,
scale: number,
octaves: number,
persistence: number,
lacunarity: number,
offset: vector)
{
let heightMap = [];
let normalizedHeightMap = [];
let mapSize = mapWidth*mapHeight;
let halfHeight = mapHeight / 2; // dividing by 2 centers noise
let halfWidth = mapWidth / 2; // dividing by 2 centers noise
let yi = 0;
let xi = 0;
let perlinValue = 0;
// calculate octave offsets if any random or otherwize
let offsets = this.octaveOffsets(seed,octaves,offset);
// scale aka elevation
if (scale <= 0) { scale = 0.0001; }
// fill height map array with Perlin values
for (let i = 0; i < mapSize; i++) {
yi = ((Math.floor(i/mapWidth)) - halfHeight) / scale;
xi = ((i%mapWidth) - halfWidth) / scale;
// call noise function
perlinValue = this.perlinOctaves(xi,yi,0,octaves,persistence,lacunarity,offsets);
heightMap[i] = perlinValue;
}
// normalize range of numbers from -1.0 through 1.0 to 0.0 through 1.0
normalizedHeightMap = this.normalizeNoise(heightMap);
return normalizedHeightMap;
};
} // PerlinNoise
export class MersenneTwister {
N: number;
M: number;
MATRIX_A: number;
UPPER_MASK: number;
LOWER_MASK: number;
mt: Array<number>;
mti: number;
constructor(seed: number){
if (seed == undefined) {
seed = new Date().getTime();
}
/* Period parameters */
this.N = 624;
this.M = 397;
this.MATRIX_A = 0x9908b0df; /* constant vector a */
this.UPPER_MASK = 0x80000000; /* most significant w-r bits */
this.LOWER_MASK = 0x7fffffff; /* least significant r bits */
this.mt = new Array(this.N); /* the array for the state vector */
this.mti=this.N+1; /* mti==N+1 means mt[N] is not initialized */
this.init_genrand(seed);
}
init_genrand(s: number) : void {
this.mt[0] = s >>> 0;
for (this.mti=1; this.mti<this.N; this.mti++) {
s = this.mt[this.mti-1] ^ (this.mt[this.mti-1] >>> 30);
this.mt[this.mti] = (((((s & 0xffff0000) >>> 16) * 1812433253) << 16) +
(s & 0x0000ffff) * 1812433253) + this.mti;
/* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
/* In the previous versions, MSBs of the seed affect */
/* only MSBs of the array mt[]. */
/* 2002/01/09 modified by Makoto Matsumoto */
this.mt[this.mti] >>>= 0;
/* for >32 bit machines */
}
}
genrand_int32(): number {
var y;
var mag01 = new Array(0x0, this.MATRIX_A);
/* mag01[x] = x * MATRIX_A for x=0,1 */
if (this.mti >= this.N) { /* generate N words at one time */
var kk;
if (this.mti == this.N+1) /* if init_genrand() has not been called, */
this.init_genrand(5489); /* a default initial seed is used */
for (kk=0;kk<this.N-this.M;kk++) {
y = (this.mt[kk]&this.UPPER_MASK)|(this.mt[kk+1]&this.LOWER_MASK);
this.mt[kk] = this.mt[kk+this.M] ^ (y >>> 1) ^ mag01[y & 0x1];
}
for (;kk<this.N-1;kk++) {
y = (this.mt[kk]&this.UPPER_MASK)|(this.mt[kk+1]&this.LOWER_MASK);
this.mt[kk] = this.mt[kk+(this.M-this.N)] ^ (y >>> 1) ^ mag01[y & 0x1];
}
y = (this.mt[this.N-1]&this.UPPER_MASK)|(this.mt[0]&this.LOWER_MASK);
this.mt[this.N-1] = this.mt[this.M-1] ^ (y >>> 1) ^ mag01[y & 0x1];
this.mti = 0;
}
y = this.mt[this.mti++];
/* Tempering */
y ^= (y >>> 11);
y ^= (y << 7) & 0x9d2c5680;
y ^= (y << 15) & 0xefc60000;
y ^= (y >>> 18);
return y >>> 0;
}
/* generates a random number on [0,1)-real-interval */
random() : number {
return this.genrand_int32()*(1.0/4294967296.0);
/* divided by 2^32 */
}
} // MersenneTwister
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment