# Section IVGetting Noisy in Here

Finally the part I have been wanting to get to! One of the power players in the procedural world are methods called noise. Noise is a random (in our case pseudorandom) distribution of values over a range. Normally these values range from -1 to 1, but can have other values. We use these predictably random functions to control our methods. The simplest, yet least useful to use will be a white noise function, which some of you should be familiar with. Picture your old analog TV set to a blank channel or the scene from the movie Poltergeist.

Example

There has been quite a bit of advancement in the generation of random values, with the works of Steven Worley and Ken Perlin. We can use a combination of their methods, to achieve some really interesting results. The are two main types of noise that we will be covering are lattice and gradient based noise methods.

#### Lattice Noise/Value Noise

There is a little bit of confusion in the procedural world with what is a value based noise and what is gradient. This is demonstrated by the article we will be referencing calls the process we will be reviewing [1] Perlin when it is actually Value Noise.

Value Noise is a series of nDimensional points at a set frequency that have a value, we then interpolate between the points which then gives us our values. There are multiple ways to interpolate the values and most do it smoothly but to help you understand the concept lets temporarily do a linear interpolation.

Take for example if we had a 1D noise with our lattice set at every integer value and a linear interpolation we get a graph similar to this:

If we were to sample any point now between any of the lattice points we would get a value between the values of the closets points. In this 1d grid it would be the two closest points, in a 2d grid it would be 4 and in a 3d grid it would be 6 (for 2d/3d you can sample more but these are the minimum neighborhoods). So if we were to sample from this 1d Noise at the coordinate x=1.5 we would end up with a value of 0.55 (unless my math sucks).

If we use this process and mix together value noises of increasing frequency and decreasing amplitude we can make some interesting results. Another parameter we can introduce for control is persistence, which has some confusion as well as to its “official” definition. The term was first used by Mandelbrot while developing fractal systems. The simplest way to describe it would be the weighted effect of the values on the sum of the noise functions.

### Random Function

In order to get our noise functions rolling we first need to create a random number generation method. Here is a section of pseudo-code presented in [1]:

```function IntNoise(32-bit integer: x)
x = (x<<13) ^ x;
return ( 1.0 - ( (x * (x * x * 15731 + 789221) + 1376312589) &#038; 7fffffff) / 1073741824.0);
end IntNoise function
```

Right away one should notice that this is very close to the code that we used for the white noise generator above. There are many ways to generate a random number but we will convert this one initially and then test other methods to see which are more effective.
The GLSL version of this code would be:

```float rValueInt(int x){
x = (x >> 13) ^ x;
int xx = (x * (x * x * 60493 + 19990303) + 1376312589) & 0x7fffffff;
return 1.0 - (float(xx) / 1073741824.0);
}```

This function requires our input value to be an integer (hence making it a lattice), we then use bit-wise operators as explained in GLSL specs[2]. I have no clue what is really happening with the bit-wise stuff other then we are shifting the number around… sorry I dont know more. The numbers that we used are right from Hugos example [1] and are prime numbers. You can change these numbers all you want, just make sure you keep them as prime in order to prevent as noticeable of graphic artifacts. From here we just need to decide how we want to interpolate the values between points.

### Its all up to Interpolation…

The simplest way to interpolate is linearly like what we used above is represented by this equation:

Mock CodeGLSL Code

```
function Linear_Interpolate(a, b, x)
return  a*(1-x) + b*x
end of function
```
```
float linearInterp(float a, float b, float x){
return a*(1.-x) + b*x;
}```

This is ok if we want sharp elements, but if we want smoother transitions we can use a cosine interpolation.

```function Cosine_Interpolate(a, b, x)
ft = x * 3.1415927
f = (1 - cos(ft)) * .5
return  a*(1-f) + b*f
end of function
```
```float cosInterp(float a, float b, float x){
float ft = x*3.12159276;
float f = (1.0 - cos(ft)) * .5;
return a*(1.-f) + b*f;
}```

There is also cubic iterp, but we will skip that for now and focus on linear and cosine. The last thing we will want to do, in order to make our noises smoother on their transitions is introduce a you guessed it smoothing function. This function can optionally be used and can be expanded to how ever many dimensions you would need. The smoothing helps reduce the appearance of block artifacts when rendering out to 2+ dimensions. Here is a snip-it of pseudo-code from [1].

```
//1-dimensional Smooth Noise
function Noise(x)
...    .
end function

function SmoothNoise_1D(x)
return Noise(x)/2  +  Noise(x-1)/4  +  Noise(x+1)/4
end function
```
```
//2-dimensional Smooth Noise
function Noise(x, y)
...
end function

function SmoothNoise_2D(x>, y)

corners = ( Noise(x-1, y-1)+Noise(x+1, y-1)+Noise(x-1, y+1)+Noise(x+1, y+1) ) / 16
sides   = ( Noise(x-1, y)  +Noise(x+1, y)  +Noise(x, y-1)  +Noise(x, y+1) ) /  8
center  =  Noise(x, y) / 4

return corners + sides + center

end function
```

Later in this section we will look at the differences between smoothed and non-smoothed noise. Now we need to start taking all these elements and put them together. Here is the pseudo code as exampled by [1]

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

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

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

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

end function
```

I decided to make a few structural changes to this for the GLSL conversion. In the above example they use four functions to make it happen, we are going to do it with three. I think it will also be relevant to add uniforms (or defines depends on your preference) to control things like octaves, persistence and a smoothness toggle. I will also be using strictly the cos interpolation, this is by personal choice any method can be used though. So following the structure of our SM object, we set up the shader argument as follows:

```
sm = new SM(
{
size : new BABYLON.Vector2(512, 512),
hasTime : false,
//timeFactor : 0.1,
uniforms:{
octaves:{
type : 'float',
value : 4,
min : 0,
max : 124,
step: 1,
hasControl : true
},
persistence:{
type : 'float',
value : 0.5,
min : 0.001,
max : 1.0,
step: 0.001,
hasControl : true
},
smoothed:{
type : 'float',
value : 1.0,
min : 0,
max : 1.0,
step: 1,
hasControl : true
},
zoom:{
type : 'float',
value : 1,
min : 0.001,
step: 0.1,
hasControl : true
},
offset:{
type : 'vec2',
value : new BABYLON.Vector2(0, 0),
step: new BABYLON.Vector2(1, 1),
hasControl : true
},
},
fx :
`precision highp float;
//Varyings
varying vec2 vUV;
varying vec2 tUV;
/*----- UNIFORMS ------*/
uniform float time;
uniform vec2 tSize;
uniform float octaves;
uniform float persistence;
uniform float smoothed;
uniform float zoom;
uniform vec2 offset;
```

This will set up all of our uniforms and the defaults for them. You can do these as defines, but if having the ability to manipulate it on the fly they should be uniforms. I also added a uniform that we will not be manipulating directly ever but letting the size of the canvas/texture set this value when the shader is compiled. With this we need to make some changes to our SM object to accommodate this new uniform.

```SM = function(args, scene){
...
this.buildGUI();

this.setSize(args.size);

return this;
}

SM.prototype = {
...
setSize : function(size){
var canvas = this.scene._engine._gl.canvas;
size = size || new BABYLON.Vector2(canvas.width, canvas.height);
this._size = size;
var pNode = canvas.parentNode;
pNode.style.width = size.x+'px';
pNode.style.height = size.y+'px';
this.scene._engine.resize();
this.buildOutput();
}
...
```

Now the shader will always know what the size of the texture is, because we have made this a inherent feature of the SM object we need to add the uniform for tSize to the default fragment that the shader has built in. This is in the situation that the default shader get bound that it will validate and compile. From here we need to include our random number function, our interpolation function and the noise function itself. I am going to include a lerp function as well in case you want to use this and the interpolation vs cos.

```//Methods
//1D Random Value from INT;
float rValueInt(int x){
x = (x >> 13) ^ x;
int xx = (x * (x * x * 60493 + 19990303) + 1376312589) & 0x7fffffff;
return 1. - (float(xx) / 1073741824.0);
}
//float Lerp
float linearInterp(float a, float b, float x){
return a*(1.-x) + b*x;
}
//float Cosine_Interp
float cosInterp(float a, float b, float x){
float ft = x*3.12159276;
float f = (1.0 - cos(ft)) * .5;
return a*(1.-f) + b*f;
}
//1d Lattice Noise
float valueNoise1D(float x, float persistence, float octaves, float smoothed){
float t = 0.0;
float p = persistence;
float frequency, amplitude, tt, v1, v2, fx;
int ix;
for(float i=1.0; i<=octaves; i++){
frequency = i*2.0;
amplitude = p*i;

ix = int(x*frequency);
fx = fract(x*frequency);

if(smoothed > 0.0){
v1 = rValueInt(ix)/2.0 + rValueInt(ix-1)/4.0 + rValueInt(ix+1)/4.0;
v2 = rValueInt(ix+1)/2.0 + rValueInt(ix)/4.0 + rValueInt(ix+2)/4.0;
tt = cosInterp(v1, v2, fx);
}else{
tt = cosInterp(rValueInt(ix), rValueInt(ix+1), fx);
}

t+= tt*amplitude;
}
t/=octaves;
return t;
}
```

So now we have a GLSL function to generate some 1D noise! It has four arguments, the last one of smoothed can be omitted if you please but I like having it so…. It a fairly simple function and most of our noise functions will have a similar structure. We could also put a #define in that would control the interpolation, but for simplicity I am just using the cosine method. From here it is as simple as setting up the main function of our shader program to use this noise. To do this we decide our sampling space and pass that to the x value of the noise function along with our other uniforms that we have already set up.

```void main(void) {
vec2 tPos = ((vUV*tSize)+offset)/zoom;
float v = valueNoise1D(tPos.x, persistence, octaves, smoothed)+1.0/2.0;
vec3 color = vec3(mix(vec3(0.0), vec3(1.0), v));
gl_FragColor = vec4(color, 1.0);
}
```

Super easy right!? Our sampling space that we use is the 0-1 uv multiplied by the size of the texture, which effectively shifts us to texel space. The choice to use to vUV instead of the tUV was because for some reason the negative value was creating an artifact as seen here:

I could try to trouble shoot that, but instead its just easier to use the 0-1 uv range and move on.

Next add an offset which is also in texel space, you could do it as a percentage of the texture’s size but that is user preference. We then divide the whole thing by a zoom value. That gives us a nice sampling space, which we then pass to our noise function with our other arguments. Because the noise function returns a number between negative 1 and positive 1, we shift it to a 0-1 range by simply adding one then dividing the sum by two.

### A New Dimension

One dimensional noise is cool and has its uses, but we need more room for activities. Before we develop more noises and look at different methods for generation having an understanding of how to extend the noise to n-dimensions is pretty important. For all general purposes all calculations stay the same, you just have to make a couple more of them. It would probably be smart to add a support function for smoothing the values of the interpolation now that we are working with larger dimensions. The main modifications to the function will be changing some of the variables from floats and integers to vectors of the same type. The last function to add is a random number generator that takes into consideration the 2 dimensions.

```//2D Random Value from INT vec2;
float rValueInt(ivec2 p){
int x = p.x, y=p.y;
int n = x+y*57;
n = (n >> 13) ^ n;
int nn = (n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff;
return 1. - (float(nn) / 1073741824.0);
}

float smoothed2dVN(ivec2 pos){
return (( rValueInt(pos+ivec2(-1))+ rValueInt(pos+ivec2(1, -1))+rValueInt(pos+ivec2(-1, 1))+rValueInt(pos+ivec2(1, 1)) ) / 16.) + //corners
(( rValueInt(pos+ivec2(-1, 0)) + rValueInt(pos+ivec2(1, 0)) + rValueInt(pos+ivec2(0, -1)) + rValueInt(pos+ivec2(0,1)) ) / 8.) + //sides
(rValueInt(pos) / 4.);
}

//2d Lattice Noise
float valueNoise(vec2 pos, float persistence, float octaves, float smoothed){
float t = 0.0;
float p = persistence;
float frequency, amplitude, tt, v1, v2, v3, v4;
vec2 fpos;
ivec2 ipos;
for(float i=1.0; i<=octaves; i++){
frequency = i*2.0;
amplitude = p*i;

ipos = ivec2(int(pos.x*frequency), int(pos.y*frequency));
fpos =  vec2(fract(pos.x*frequency), fract(pos.y*frequency));

if(smoothed > 0.0){
ivec2 oPos = ipos;
v1 = smoothed2dVN(oPos);
oPos = ipos+ivec2(1, 0);
v2 = smoothed2dVN(oPos);
oPos = ipos+ivec2(0, 1);
v3 = smoothed2dVN(oPos);
oPos = ipos+ivec2(1, 1);
v4 = smoothed2dVN(oPos);

float i1 = cosInterp(v1, v2, fpos.x);
float i2 = cosInterp(v3, v4, fpos.x);
tt = cosInterp(i1, i2, fpos.y);

}else{
float i1 = cosInterp(rValueInt(ipos), rValueInt(ipos+ivec2(1,0)), fpos.x);
float i2 = cosInterp(rValueInt(ipos+ivec2(0,1)), rValueInt(ipos+ivec2(1,1)), fpos.x);

tt = cosInterp(i1, i2, fpos.y);
}

t+= tt*amplitude;
}
t/=octaves;
return t;
}
```

There we have it, there are definitely some problems with this method that if we took some time and refined this could be fixed. These problems are things like artifacts as the noise transfers from a positive to a negative coordinate range which is apparent the more you zoom in and noticeable circular patterns the closer to 0,0 we get. In order to fix this quickly and essentially ‘ignore’ that problem we just add a large offset to the noise initially and screw our coordinates to be far away from the artifacts.

As a challenge see if you can change the interpolation function to be cubic. Read the section on it here [3].

You can also see a live example of the 2d Lattice Noise here.

# Experiments in Procedural Level Creation

## Introduction

After working on doing some texture synthesis, a method for creating dungeons and other content kinda just smacked me in the face. I have been itching for about two days now to get a chance to do this. The night I thought it up the write up went as follows:

A Zone (Z) is defined as a area of set units that is divided into a set amount of Cells (C). For this deployment I will be dividing the
Z into a 3 by 3 grid with the labeling of each cell as follows starting from the top left; n10, n00, n01, m10, m00, m01, s10, s00, s01. Because I am spliting it into thirds to keep things simple I will define the size of the zone always to something divisible by 3, for general purposes I will always use a Z size of 60 by 60 making each cell 20^2 pxls. Because we will be averaging the black and white value of the cells we limit the size of the zones to be as small as possible but still large enough to have defined details. The larger our Zones the larger the calculation overhead.

Once my Zone method and size is established and I have defined the cells for it, I have to calculate every possible state of the Zone and output that to a human readable jpg. This is achieved by looping through combination sets of the cells, and creating a single array of all states, then use that information to generate a canvas with the correct cells displayed as black and white on or off state.

After the human readable jpg is produced, reload our now created Zone map into the program and associate each zone’s location information on the map and cell state information into a referenceable and searchable array or object.
At this point I can start choosing my method for a base noise, because each Zone will only be 60 by 60 I believe my Worley2D noise from my Das_Noise library will work just fine, if there is a calculation lag on the generation of the zones due to the noise, I will see about moving to a modified SimpleX. Starting from the top left of the visible stage, we calculate the values for the base noise by passing it to our zone object and averaging the values of each cells black white ratio due to the noise, and round to 0 or 1 effectively converting the noise to a Zone similar to the ones I generated earlier. Loop through the map object,
and find out which zone matches the closest to the new noise zone.

The point of first creating a human readable image instead of just having the noise be manipulated is that after we get a look for the base layout that we want, an artist can use the human readable image as a template to draw a secondary reference image that has the same dimensions as our reference map. I could then load image data into the map object from the secondary reference image and output the fancy tiles instead of just black and white. This process could also be extended to use secondary noise calculations to establish and simulate different biomes and altitudes, changing what tile map is referenced.

This is all theory but it sounds about right so I’m gonna give it a shot.

## The Reference Map

Diving right in I think the smartest thing to do will be to create my first reference map, or the human readable map I described earlier. The first day I thought of this I tried to make it by hand in illustrator and got about 32 combinations in before I realized that was dumb, and it was time to make canvas go to work.

First we need to calculate the combinations of the cells and make something that we can use to output a physical reference map. What I mean by combinations is if we had an input of [1, 2, 3] the output would look like =>123,213,132,232,312,321…. There are lots of ways to do this, but I will try to keep it simple. Because order does not matter, we do not have to worry about permutations (the same combination in a different order).

This script to make it happen is as follows:

```dungeon = function(args){
args = args || {};
args.zSize = args.zSize || 60;
args.zDiv = args.zDiv || 3;
this.zSize= args.zSize;
this.zDiv = args.zDiv;
};

dungeon.prototype._createRefMap = function(){
var cells = [];
var pCount = this.zDiv * this.zDiv;

function perm(s,c){
if (c == 0) {
cells.push(s);
return;
}
perm(s+'0', c-1);
perm(s+'1', c-1);
}

perm('',pCount);

var last = cells.splice(cells.length-1,1);
cells.unshift(last+'');
console.log(cells);
};
```

Just creating a new dungeon and then calling the prototype now outputs all of the permutations for a total of 512, on a side interesting note, is it also the could be looked at as every possible combination of a binary set of 9. Looking at the structure I already know that my two most common ones I am shooting for will be all states on and all states off, so I think it would be best to take the first record and move it to the front of the array to save on calculation time once we start looping through our state array.

## Zone Object

Now it is time to make a Zone Object, this will be the basis for our mapping of the noise, this makes a object that we can put in an array, and compile the states of the cell as a searchable string. After that we will look at making a readable image.

```dungeon.Zone = function(size, div, state){
this.size = size;
this.div = div;
this.searchString = state;
this.state = state.split('');
this.cells = [];
for(var i=0; i < div*div; i++){
this.cells.push(0);
}
for(var i=0; i < state.length; i++){
var sID = parseInt(state[i],10);
this.cells[sID] = 1;
}
return this;
};
```

I then modified my pre-existing script to the following:

```...
var map = [];
for(var i = 0; i < cells.length; i++){
map.push(new dungeon.Zone(this.zSize, this.zDiv, cells[i]));
}
this.map = map;
console.log(map);
```

This gives us an array on the main dungeon object that contains set of Zones with a searchable string for referencing later. I now need to create a new function to compile the physical map and set values for where the zone object is on the output map. This step is only necessary so that at a later time an artist can create a secondary reference map at a later time, if I just wanted black and white pxls to display I could effectively skip this step but that is not the final product I want.

I also went ahead and allocated the memory for each of the zone objects to have image data as well, even though I’m just using the map image and not an artistic tile image do to the fact of 512 tiles is quite a bit of content to come up with, just for an example. Using this function I generate my reference map that I will use as both a way to look up / store tiles and their properties; it also creates the ability for me to output a canvas with the tiles on it to make a human readable map.

```dungeon.prototype._calculateMap = function(){
var map = this.map;
var cvas = document.createElement('canvas');
var ctx = cvas.getContext('2d');

var X = 0, Y = 0;
var cellSize = this.zSize/this.zDiv;

cvas.width = 20*this.zSize;
cvas.height = Math.ceil(map.length/20)*this.zSize;

for(var i = 0; i < map.length; i++){
var x = 0, y = 0;
for(var j = 0; j < map[i].cells.length; j++){ if(map[i].cells[j] == 1){ ctx.fillStyle = "#FFF"; }else{ ctx.fillStyle = "#000"; } ctx.fillRect(x+X,y+Y,cellSize,cellSize); x+=cellSize; if(x > this.zSize-cellSize){
y+=cellSize;
x=0;
}
};

ctx.strokeStyle = "rgba(255,0,0,0.2)";
ctx.strokeRect(X,Y,this.zSize,this.zSize);

var imgData = ctx.getImageData(X,Y,this.zSize,this.zSize);

map[i].imgData = imgData;
map[i].x = X;
map[i].y = Y;

X+=this.zSize;
if(X > cvas.width-this.zSize){
Y+=this.zSize;
X=0;
}
};
};
```

Now it’s time to start generating a noise, and see if we can kick this thing into gear and output a dungeon like structure. Later I will research into making the ability for you to draw on the base noise and see the overlay tiles update accordingly, this would be cool for later development I think, but is something that is down the road a little bit.

Also CLICK HERE for an Example of the Reference Map

## Enter Das_Noise

Ok so now the next step will be to generate a base noise map to start sampling, and outputting out maps imageData in the correct areas and see what kind of output I can get. I’m assuming this should go without much hitch and with a well set up noise will structure itself to resemble a dungeon right of the bat (I hope).

I want to use a good sized chebyshev style Worley Noise to start because I believe this will have a good look to it once overlaid, and will guarantee that most if not all the rooms connect. If you are not familiar with my Das_Noise library you can check it out here: http://pryme8.github.io/Das_Noise

To test the noise I am going to output on a 600 by 600 pxl canvas the noise till I get something acceptable. When I go to use it, i will not have to create the noise to any sort of output, but rather just check its values at certain locations then parse that how ever is needed to see what cells are active or not in that zone.
Already looking at this noise, we can visualize what the dungeon will look like if the calculations have been set up correctly. The next step is to identify the what each zone on the noise matches up to on our reference map, to see this in action click the link below to do one zone at a time on our canvas to the left.

Generate Zone

*UPDATE – I went ahead and added a basic tile map to reference, to show how that would work… you can look at the code to see how I did that, but after seeing it deployed I have three options, rework the tilemap to be cleaner and work a little better, make some sort of comparison script to see what the other tiles next to it are, and if there is a flat edge, have caped variations to use, or make everything procedrual… I think given the fact it took me two and a half hours to make 512 tiles im going to go with the last option here at some point.

Ohhh yeah, that works! Ok so I think I will wrap it up on this, but first here is a look at how I ID the zone of the noise.

Here is and example of the same process, with the noise of the same seed, but set to Simple2 and a scale of 100.

```dungeon.prototype._idNoise = function(x,y,noise){
if(typeof noise ==='undefined'){
noise = this.noise;
}
var cellSize = this.zSize/this.zDiv;

var string = '';
var self = this;
var ctx = (document.getElementById('noise-canvas')).getContext('2d');
ctx.fillStyle = "red";

var cX = 0;
var cY = 0;

for(var i=0; i<this.zDiv*this.zDiv; i++){
var t = 0;

for(var pY = 0; pY < cellSize; pY++){
for(var pX = 0; pX < cellSize; pX++){
t+=noise.getValue({x:(pX+(this.zSize*x)+(cellSize*cX)),
y:(pY+(this.zSize*y)+(cellSize*cY))});

}
}

t/=(cellSize*cellSize);
if(t<0.45){ string+=0+""; }else{ string+=1+""; } cX++; if(cX>this.zDiv-1){
cX=0;
cY++;
}
}

for(var i=0; i<this.map.length; i++){
if(this.map[i].searchString == string){
return this.map[i];
}
};
};
```

## Conclusion…

This was all literally done in one day intermittently while I cleaned the house… so yeah I think this is a valid and good approach for what I want to achieve. I will have to experiment with different noise types styles and scales and then come up with a nice tileset for it (I will prolly jack RPG maker resources for now). I think once this is deployed a little more the possibilities will be extensive.

I will be posting a simple Canvas Game based on this principle at some point!

Resources and References : None… I just made this crap up… if you have any questions Pryme8@gmail.com.