Perlin Noise

Welcome back! Last time we discussed the Diamond-Square algorithm. While that algorithm works great for certain cases, it had its drawbacks that we discussed last post. Instead of fixing those we're gonna just implement a different way to get similar results. That way is Perlin Noise!

So what is Perlin Noise? Well similarly to Diamond-Square, it's a way of generating random height-maps that can be used for a number of things. Games are generally a place they are used commonly to create random terrains. It is very simple to implement and produces much better looking results than Diamond-Square as it does not have the same artifacts. The biggest drawback to Perlin Noise is that it is slightly slower than Diamond Square and it can only generate squares. Both of these can be worked around though so lets dive into the code.

	PerlinNoise::PerlinNoise( int seed ) {
	m_seed = seed;
	m_gradient.resize( 256 );
	std::iota( m_gradient.begin(), m_gradient.end(), 0 );
	std::default_random_engine engine( m_seed );
	std::shuffle( m_gradient.begin(), m_gradient.end(), engine );
	m_gradient.insert( m_gradient.end(), m_gradient.begin(), m_gradient.end() );
	}

view raw PerlinNoise_Constructor.cpp hosted with ❤ by GitHub

Above we can see the constructor for our Perlin Noise class. We haven't looked at most of the constructors before but this one does more than most. In this one we fill a vector with random values. These random values are dependent on our seed and act as the "gradient" for the rest of the algorithm which will be talked about more later on.

	float PerlinNoise::perlin( float x, float y, float z ) {
	int x0 = ( int ) floor( x ) & 255;
	int y0 = ( int ) floor( y ) & 255;
	int z0 = ( int ) floor( z ) & 255;
	x -= floor( x );
	y -= floor( y );
	z -= floor( z );
	float u = fade( x );
	float v = fade( y );
	float w = fade( z );
	int a = m_gradient[ x0 ] + y0;
	int aa = m_gradient[ a ] + z0;
	int ab = m_gradient[ a + 1 ] + z0;
	int b = m_gradient[ x0 + 1 ] + y0;
	int ba = m_gradient[ b ] + z0;
	int bb = m_gradient[ b + 1 ] + z0;
	float g0 = grad( m_gradient[ bb + 1 ], x - 1, y - 1, z - 1 );
	float g1 = grad( m_gradient[ ab + 1 ], x, y - 1, z - 1 );
	float lerp0 = lerp( u, g1, g0 );
	g0 = grad( m_gradient[ ba + 1 ], x - 1, y, z - 1 );
	g1 = grad( m_gradient[ aa + 1], x, y, z - 1 );
	float lerp1 = lerp( u, g1, g0 );
	float lerp2 = lerp( v, lerp1, lerp0 );
	g0 = grad( m_gradient[ bb ], x - 1, y - 1, z );
	g1 = grad( m_gradient[ ab ], x, y - 1, z );
	lerp0 = lerp( u, g1, g0 );
	g0 = grad( m_gradient[ ba ], x - 1, y, z );
	g1 = grad( m_gradient[ aa ], x, y, z );
	lerp1 = lerp( u, g1, g0 );
	float lerp3 = lerp( v, lerp1, lerp0 );
	float res = lerp( w, lerp3, lerp2 );
	return ( res + 1.0 ) / 2.0;
	}

view raw PerlinNoise_Perlin.cpp hosted with ❤ by GitHub

Here we have our perlin method. This is where the majority of our calculations and code is. There is a lot of stuff going on here so I will cover the basics. If you are very interested in each low level idea, Ken Perlin wrote an entire paper about Perlin Noise you can read. So, carrying on. First we take the floor of our values and bitwise and them with 255 ( Read here if you don't know what bitwise operations are ). We then subtract these values from the floor of themselves. Then we see another method we haven't seen yet, fade. Let's look at fade.

	float PerlinNoise::lerp( float t, float a, float b ) {
	return ( b - a ) * t + a;
	}
	float PerlinNoise::grad( int hash, float x, float y, float z ) {
	int h = hash & 15;
	double u = h < 8 ? x : y;
	double v = h < 4 ? y : ( h == 12 || h == 14 ) ? x : z;
	return ( float ) ( ( ( h & 1 ) == 0 ? u : -u ) + ( ( h & 2 ) == 0 ? v : -v ) );
	}
	float PerlinNoise::fade( double t ) {
	return t * t * t * ( t * ( t * 6 - 15 ) + 10 );
	}

view raw PerlinNoise_helpers.cpp hosted with ❤ by GitHub

Here we can see all of the methods we haven't seen yet. Fade and grad are actually unique in that every implementation of Perlin Noise is supposed to/should use the same equation made by Ken. You can see it is just a simple math equation where we multiply and add some values. So carrying on, we can next see where our gradient values come on. These are chosen based from our x, y, and z, and the subsequent variables that came from them. We then see the grad method actually used. Here a series of bitwise operations change the values. These help insure randomness. They are then linear interpreted ( lerp ) with each other in our lerp method. This is just a stand linear interpolation, nothing fancy. This is done multiple times over every point. So how do we actually use this?

	void PerlinNoise::to_png( const std::string &file, int width, int height ) {
	pngwriter png( width, height, 0, file.c_str() );
	for ( unsigned int i = 0; i < height; i++ ) {
	for ( unsigned int j = 0; j < width; j++ ) {
	float x = ( float ) j / ( float ) width;
	float y = ( float ) i / ( float ) height;
	float n = perlin( x * 10, y * 10, 0.8 );
	// n = 20 * noise.perlin(x, y, 0.8);
	// n = n - floor(n);
	png.plot( i, j, n, n, n );
	}
	}
	png.close();
	}

view raw PerlinNoise_topng.cpp hosted with ❤ by GitHub

Above is our to_png method. We need some visual representation to output this to to see our results and that is how we do it. So lets run it and see what it looks like.

Wow, look at that! It looks random! And every time we run it it will be random. But wait... What is the commented code? Well with Perlin Noise we can easily modify the produced values to create something... different. Let's uncomment that code and run it and see what happens!

Wow! Look at that! That commented code works well for producing a wood-like texture. Pretty nifty. Playing around more can create different effects but I will let you explore them yourselves. Hope you enjoyed this and learned something new. As usual, see the full code here.

Diamond Square

Last time we talked about the Midpoint Displacement algorithm in preparation for the Diamond Square algorithm. Dimond Square is basically a 2D version of Midpoint Displacement. It has lots of use in modern video games due to its speed and ease of implementation. So let's get started to see how it actually works.

Source

Wikipedia has a helpful image to help easily understand the algorithm. First four corners are selected and their height values are remembered. Those values are averaged and given a random offset value. The center of those four is now the new corner. This is the diamond step. The square step is next. The middle is used as a reference and each point out from it is set to a random value and the average of the four corners. This is repeated multiple times. 

In the code below we can see the implementation of the "generate" method. This method is where the bulk of the work for Diamond Square is done. It loops over the grid a certain number of times, each time doing a "diamond' step and a "square" step as discussed above.

	DiamondSquare::DiamondSquare( unsigned int width, unsigned int height, int featureSize ) {
	m_width = width;
	m_height = height;
	for ( unsigned int i = 0; i < width * height; i++ ) {
	m_map.push_back( 0.0f );
	}
	for ( unsigned int y = 0; y < width; y += featureSize ) {
	for ( unsigned int x = 0; x < width; x += featureSize ) {
	setSample( x, y, Utility::random_in_range( -1.0f, 1.0f ) );
	}
	}
	int stepSize = featureSize;
	float scale = 1.0f / width;
	float scaleMod = 1.0f;
	do {
	diamond_square( stepSize, scale );
	stepSize /= 2;
	scale *= ( scaleMod + 0.8f );
	scaleMod *= 0.3;
	} while ( stepSize > 1 );
	}
	void DiamondSquare::diamond_square( int stepSize, float scale ) {
	int halfStep = stepSize / 2;
	for ( unsigned int y = halfStep; y < m_width + halfStep; y += stepSize ) {
	for ( unsigned int x = halfStep; x < m_width + halfStep; x += stepSize ) {
	square_step( x, y, stepSize, Utility::random_in_range( -1.0f, 1.0f ) * scale );
	}
	}
	for ( unsigned int y = 0; y < m_width; y += stepSize ) {
	for ( unsigned int x = 0; x < m_width; x += stepSize ) {
	diamond_step( x + halfStep, y, stepSize, Utility::random_in_range( -1.0f, 1.0f ) * scale );
	diamond_step( x, y + halfStep, stepSize, Utility::random_in_range( -1.0f, 1.0f ) * scale );
	}
	}
	}

view raw DiamondSquare_diamond_square.cpp hosted with ❤ by GitHub

Then below we can see the implementation of the actual diamond_step and square_step methods. These do as discussed in the description above.

	void DiamondSquare::square_step( int x, int y, int size, float value ) {
	int hs = size / 2;
	float a = sample( x - hs, y - hs );
	float b = sample( x + hs, y - hs );
	float c = sample( x - hs, y + hs );
	float d = sample( x + hs, y + hs );
	setSample( x, y, ( ( a + b + c + d ) / 4.0f ) + value );
	}
	void DiamondSquare::diamond_step( int x, int y, int size, float value ) {
	int hs = size / 2;
	float a = sample( x - hs, y );
	float b = sample( x + hs, y );
	float c = sample( x, y - hs );
	float d = sample( x, y + hs );
	setSample( x, y, ( ( a + b + c + d ) / 4.0f ) + value );
	}

view raw DiamondSquare_diamond_step_square_step.cpp hosted with ❤ by GitHub

The last bit we have to talk about is the sample method. This is a clever method that uses bit operations to get locations on the map. Because of how it works it allows the map to wrap around itself and generate maps that have borders that will be seamless. We can see the actual implementation below.

	float DiamondSquare::sample( int x, int y ) {
	return m_map[ ( x & ( m_width - 1 ) ) + ( y & ( m_height - 1 ) ) * m_width ];
	}
	void DiamondSquare::setSample( int x, int y, float value ) {
	m_map[ ( x & ( m_width - 1 ) ) + ( y & ( m_height - 1 ) ) * m_width ] = value;
	}

view raw DiamondSquare_sample.cpp hosted with ❤ by GitHub

Now that we see how it works, we can see the result!

This is an example output. We can see the high areas are lighter than low areas. This has a fault though which is discussed below.

While this algorithm has advantages, it also comes with some downfalls. One of the notable downfalls that affects many when using this algorithm is that it has a tendency to generate ridges in lines. So many times there will be a set of ridge peaks or valleys at very similar locations. There are ways around this but those are out of the scope of this post. Another downfall is that the map has to be a size of 2^n + 1. This is rarely a problem but can be if you need a certain sized map. The simplicity of this algorithm is what makes it so powerful and why these downfalls are rarely an actual problem.

Thats the basics with Diamond Square. It's a simple implementation and generates random results. As usual hope you learned something and heres the full code.

Midpoint Displacement

Up until now all of our programs have been printing grids to console. These were cool to look at but were often only useful for a very specialized purpose. Because of this were are going to do something very different. We are going to write our own Midpoint Displacement algorithm. Midpoint Displacement is a form of the Diamond-Square algorithm ( another algorithm we will be covering later on ). These two algorithms are very similar the main difference being Midpoint-Displacement outputs a line while Diamond-Square outputs a grid. However, to better understand Diamond-Square we later on we are starting simple with Midpoint-Displacement. So let's get started!

Midpoint-Displacement is an extremely simple algorithm ( I wrote a Java version back in high school its so simple ) but it creates unique and interesting outputs every time we run it. The algorithm works as follows. First, two endpoints are created. These will be used as anchors. A midpoint is then found between the two points and it offset by a random number based on a "roughness" value. The algorithm is then run again doing the same thing. Finding the middle between each point and raising or lowering the point based on the "roughness." The idea is simple so let's see what it looks like in code.

	void MidpointDisplacement::generate( std::vector<Point> &points, int roughness, int npoints ) {
	if ( npoints < 0 )
	return;
	for ( unsigned int i = 1; i < points.size(); i += 2 ) {
	Point pMid = middle( points.at( i ), points.at( i - 1 ) );
	Point pDis = displace( pMid, roughness );
	points.insert( points.begin() + i, pDis );
	npoints--;
	}
	generate( points, roughness / 2, npoints );
	}

view raw MidpointDisplacementGenerate.cpp hosted with ❤ by GitHub

Extremely straightforward. The method calls itself each loop around and makes sure that it is only doing the number of points that there should be. We can see there are two methods that we use that are not in the code so we can look at those briefly below.

	Point MidpointDisplacement::middle( const Point &p1, const Point &p2 ) const {
	return Point( ( p1.m_x + p2.m_x ) / 2, ( p1.m_y + p2.m_y ) / 2 );
	}
	Point MidpointDisplacement::displace( const Point &p, int roughness ) const {
	return Point( p.m_x, Utility::random_in_range( p.m_y - roughness, p.m_y + roughness ) );
	}

view raw MidpointDisplacementMiddle_Displace.cpp hosted with ❤ by GitHub

The "middle" method is just your run of the mill midpoint formula that you learned in elementary school. Then with the "displace" method we can see that we keep the x-value the same and modify the y-value based on it's current value plus a random number in between the negative roughness and positive roughness.

In order to see how what this outputs, I wrote a small method that plots the x and y values on a black image. So when we run the program, we might expect to see something like this.

Or something like this.

We can see that the Midpoint-Displacement algorithm generates ridges and valleys. This has some practical use in real games too! 

Source

I lot of people probably remember playing that game ( or something similar ). It used an algorithm similar to Midpoint-Displacement to create its random and interesting terrains. 

We've got a basic understanding of Midpoint-Displacement now so we can next talk about the Diamond-Square algorithm! This algorithm also has a lot of use in real life games. As usual, hope you learned something and you can see the source code here.