Generating "True" 2D Perlin Noise

Game Mechanics
#1

After reading material and trying out different examples for days I feel like I have hit a brick wall. Please note in advance I have read most posts and the wiki article on this topic, I’m just looking for some good advice.

I’ve been working on a 2D terrain generation system for a new game I’m working on, and after some reading decided to shoot for a Perlin noise powered implementation. After some reading, I found the following article:

How to Use Perlin Noise in Your Games: http://devmag.org.za/2009/04/25/perlin-noise/

I thought, “Brilliant! Finally an implementation I can seem to understand!” I put hands to keyboard and began writing an implementation based off the article. After running the code and finally getting some visual output I felt relief at first, and then slowly annoyance. Below are samples of my output.

512×512 122 KB

I’m annoyed because this “random” noise seems to generate features which appear as horizontal or vertical compostions of mountains or ponds. There are virtually no diagonal lines and very few circular formations. I went back to the original article to discover that the implementation was not Perlin noise, but instead a variation of value noise.

So I scrap my pervious implementation and start again. I begin by implementing the version of Perlin noise featured on Riven’s blog:

PerlinNoise :: smooth/turbulent : http://riven8192.blogspot.fr/2009/08/perlinnoise.html

Even though it seems to be in 3D space, I assume I can set Z to zero and all will be merry. Well so I thought, but once I test the code and find that for all possible inputs I was getting 0 from each call to the smoothNoise function.

Again, I feel like I have hit a brick wall, and I need to ask advice before I keep wasting any more of my time. Firstly, is the sort of horizontal/vertical features in value noise normal? And if they are, does Perlin noise not feature this? Lastly, if someone could point me in the direction of a functional Perlin noise implementation I would greatly appreciate it, as I am begining to think I am trying to understand something way out of my league :confused:

#2

No you shouldn’t have noticeable defects along the grid.

#3

Thanks for the confirmation Roquen :slight_smile:

Well since I put up my last post, I decided to take a stab at implementing Simplex Noise instead of Perlin based off the implementation by Stefan Gustavson, Simplex noise demystified: http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf

I used most of the 2D Simplex code he lists towards the end of the article, and then wrote the following function to stick it all in a 2D array that can be rendered in my game:

public static float[][] generateSimplexNoise(int width, int height){
		float[][] simplexnoise = new float[width][height];
		float frequency = 5.0f / (float) width;
		
		for(int x = 0; x < width; x++){
			for(int y = 0; y < height; y++){
				simplexnoise[x][y] = (float) noise(x * frequency,y * frequency);
				simplexnoise[x][y] = (simplexnoise[x][y] + 1) / 2;	//generate values between 0 and 1
			}
		}
		
		return simplexnoise;
	}

This generates the following map!

Thank god. Just may end up using Simplex Noise after all! My only remaining question is how do you randomise this? My original idea was to simply give a random offset for all the x and y values of my array, but is it that simple? Or should I be doing something else instead?

#4

That looks awesome!
I played around with that last night but couldn’t get a result nowhere near what you just got there. Been trying for an half hour to touch it up a bit to give presentable images.

Following this guys implementation of Gustavsons code on this page;

I recieve this; https://www.dropbox.com/s/r9rmsldozvnfnhz/simplex.png

I also tried a Diamond Square/Midpoint Displacement-thingie by dermetfan and was able to shoot out this;

Nowhere near as smoth as yours.

#5

Yes (in this instance) it’s that simple.

#6

@longshorts:

Looking at the code and image, it looks like you only utilize one layer of simplex noise. If you couple together a couple of layers with different frequencies and weights, you get a much nicer result.


public float noise(float x, float y, float frequency) {
    return simplexnoise(x / frequency, y / frequency);
}



// This is the basic idea:
public float octavedNoise(float x, float y) {
    return
        (noise(x, y, 1f) * 1 + // Each of this lines is called an "octave".
        noise(x, y, 2f) * 2 +  // The whole expression makes up a weighted average computation
        noise(x, y, 4f) * 4 +  // where the noise with the lowest frequencies have the least effect.
        noise(x, y, 8f) * 8 +
        noise(x, y, 16f) * 16) / (1 + 2 + 4 + 8 + 16);
}
// Of course this is not hardcoded in the end, I just made that for making it clear.
// In 'reality' it would be implemented with the parameters "octaves" and "roughness" and "scale":
public float octavedNoise(int octaves, float roughness, float scale) {
    float noiseSum = 0;
    float layerFrequency = scale;
    float layerWeight = 1;
    float weightSum = 0;

    for (int octave = 0; octave < octaves; octave++) {
        noiseSum += noise(x * layerFrequency, y * layerFrequency) * layerWeight;
        layerFrequency *= 2;
        weightSum += layerWeight;
        layerWeight *= roughness;
    }
    return noiseSum / weightSum;
}

Try it out :slight_smile:

#7

Try increasing decreasing the frequency of your output. I get much larger features and smoothing maps with a smaller frequency.

Thanks, I did wonder about how to implement different octaves. I’ll give it a shot then repost my results, thanks!

#8

[quote=“longshorts,post:7,topic:45880”]
I have tried lots of things, but when i used the method you posted instead of the one from the page i was able to create a better looking map, but, the problem is that is it generating way too much 0’s and 1’s. See this result; https://www.dropbox.com/s/z8bpolrdihegcqq/savedColor.png

Upping or lowering the frequency doesn’t change the total amount of them.
I am just copy and pasteing the code since i am not a brainiac for algorithms and math.

#9

matheus, I could kiss your genious face, your code worked brilliantly!

I have altered your code to the following so it outputs a two dimensional array that can be used for image processing, I’ll post it here in case someone else wants to refer to it.

public float[][] generateOctavedSimplexNoise(int width, int height, int octaves, float roughness, float scale){
		float[][] totalNoise = new float[width][height];
	    float layerFrequency = scale;
	    float layerWeight = 1;
	    float weightSum = 0;

	    for (int octave = 0; octave < octaves; octave++) {
	    	//Calculate single layer/octave of simplex noise, then add it to total noise
	    	for(int x = 0; x < width; x++){
	    		for(int y = 0; y < height; y++){
	    			totalNoise[x][y] += (float) noise(x * layerFrequency,y * layerFrequency) * layerWeight;
	    		}
	    	}
	    	
	    	//Increase variables with each incrementing octave
	        layerFrequency *= 2;
	        weightSum += layerWeight;
	        layerWeight *= roughness;
	        
	    }
	    return totalNoise;
	}

I ran a few tests and everything works great. A nice map is generated with the following:

SimplexNoiseGen sng = new SimplexNoiseGen();
float[][] osn = sng.generateOctavedSimplexNoise(512, 512, 3, 0.4f, 0.005f);

And the output! Note, there is a large mass of water because the output is between -1 and 1 for this map, and my program is currently set to make anything less than 0.1 deep water.

Sabomoth, give it a shot with the method I just posted, and drop down the roughness parameter, that should give you the result you are looking for. If it still aint right, just play around with the last three parameters so you get a good feel of what they do :slight_smile:

#10

Wohoo ;D Glad to be helpful :slight_smile:

#11

I am afraid our implementations of Gustavson’s original code is mismatched for me to be able to easily patch them together, for example, the one i copied already had octaves and that running before, and the get noise method seems to differ a bit as well. The result i get from your newest method is just even more zeroes and ones, and it only gives between numbers 0-1. No matter how low/high/many octaves, roughness or scale i got. I guess i’ll try to build everything from scratch and not follow that guide of there, might even learn something.

Did you have a look at the Diamond/midpoint-displacement stuff? Of what i have seen from perplex noise it is a lot more smooth, while the other one feels more ‘natural’.

https://bitbucket.org/dermetfan/libgdx-utils/src/b220ba67bf5c2e7f9c3cfd77cfea5d9add542a8d/libgdx-utils/src/net/dermetfan/utils/math/Noise.java?at=default
That algorithm isn’t as fast as perplex, a 512x512 grid can take 3-4 seconds to fill. Might be some faster implementations out there though.

#12

What do you mean by ‘perplex’ noise? Google couldn’t help me :confused:
Are you maybe talking about simplex noise?
Simplex noise isn’t much different from Perlin Noise (or, better: Gradient Noise), it is just slightly modified to use simplex shapes as cells instead of squares, which minimizes the number of interpolation points and finally makes the algorithm faster.

Ken Perlin developed both algorithms and his aim with Simplex Noise was to make a faster version of Gradient Noise.

I wouldn’t suggest the Diamond-Square algorithm. It’s not a function that you could call on an arbitrary position, you need to have a grid for that, which is why it’s more limited in usecase (only limited maps, something like the infinity of minecraft would be impossible/hard).

#13

Yeah, i ment Simplex, i was a little perplexed(har har har…)

One game i am thinking of having a go at this winter is a age of empires/anno style game, which has a set boundary, so its not infinite but quite large. While another is a more ‘unlimited’ role playing game. Havent decided which to go with yet, but whichevers mapgeneration comes out the best has an edge over the other. I am aware of the history, i have spent a few days reading up on the few different noises and such, just havent tried them myself till now.

#14

If you want to implement the Diamond Square algorithm, I can give you this good source of information: http://www.gameprogrammer.com/fractal.html

But, always keep in mind, it’s a fractal, not a noise function :wink:

#15

My implementation is pretty much taken directly from the link I posted above earlier:

Stefan Gustavson, Simplex noise demystified: http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf

Scroll down to page 11, and you will find the 2D simplex noise method. You will need that and any other methods which are referenced by it (also listed in the same article). After that, the generateOctavedSimplexNoise method I posted earlier should link in with it just fine.

#16

[quote]My only remaining question is how do you randomise this? My original idea was to simply give a random offset for all the x and y values of my array, but is it that simple? Or should I be doing something else instead?
[/quote]
If you are using 2D noise, you can randomize by putting a random “translation” offset for every X and/or Y that is used for every invocation of the noise function. It is that simple. In fact, you can add the translation (a single addition op) to just the X or just the Y. The main thing is to be consistent, to do this for every invocation.

Another way to “seed” the function is to go 3D, and put in the same Z value throughout. Each Z “slice” will return its own unique values for given X & Y combos. I don’t recommend this though, because the 3D function takes longer to execute than the 2D function, even with the “translation” included.

Every value returned by the Simplex or Perlin or improved Perlin, for a given X & Y will always be the same (for that particular algorithm) and will lie between -1 and 1. At the other end, you have some sort of mapping to a range of your own, be it an index into a color map or maybe the range 0 to 255 for a 16-bit RGB color channel, or a “height” for your terrain. Part of your coding will of necessity handle the scaling and translation from the noise output to the mapping input.

If you add multiple function calls (presumably to combine different frequencies), the output range becomes the largest and smallest possible values. So, with two invocations to the noise function, the range becomes -2 to 2, with 3 it becomes -3 to 3, etc. This will probably throw off the mapping to your output unless you compensate. One way to deal with this, is to multiply each of the noise calls by a weight. Very common (and convenient) is to make the weight equal to half the frequency, in a sort of fractal progression.

So, with four noise calls, each at a higher octave, you have four results. The first octave result gets multiplied by 1/2, the second octave (where the X & Y inputs are multiplied by 2) result is multiplied by 1/4, the third by 1/8, the fourth by 1/16. The result (1/2 + 1/4 + 1/8 + 1/16) will equal 15/16ths of the range -1 to 1. Thus you don’t have to worry about messing up the mapping.

But all this is totally arbitrary. There are countless ways to get from the noise output to the mapping input. You can make your own weighting function with more “high frequency” components and less “low” if you like, or have the results modulate another function (e.g., sin function) that in turn produces a result that gets mapped. Have you seen, for example, the use of the ABS function for mapping, as a means of getting “turbulent” noise?

I will plug my Java Simplex Visualizer application once again. It has a mixer where you can plug in your own weights and as well a places where you can set frequencies of multiple channels, including a place to try various “translations” to see what that does. There is a commented code sample under “Help” tab, but only for a single channel. (Multiple channels would require another inner loop.) The applet may not run due to new signing requirements, but the jar can be downloaded and run.


SiVi - Simplex noise Visualizer tool.

This shows a color mapping function I used.

http://hexara.com/Images/EarthMap.JPG

This graphic shows the tool with some settings for a Terra-Map where I tried “doubling” the octaves for grins rather than hitting every octave. It uses a slightly different color mapping.

http://hexara.com/Images/TerraMapSiVi.JPG

#17

It’s really good fun isn’t it!

I always call value or simplex noise ‘Perlin noise’. I know it’s not strictly accurate but I love Ken Perlin’s attitude and sheer class. I reckon calling all PRNG noise techniques after him will add to his fame. A great man - cheers Ken!

#18

And I always say “right” instead of “left” because it sounds cooler to me. Screw people that follow my directions.

The classic octave construction with noise is a fractal.

#19

What do you mean by ‘classic octave construction with noise’?
So constructing nosie with multiple octaves of simplex noise is a fractal?

Then I’d rethink my statement:
Diamond Square is not a noise function
Simplex/Gradient/Perlin noise is a noise function

:slight_smile:

#20

I copied everything from the pdf this time instead of the so called quotes the other guy offered and it seems to work as you said. Though i have found that the reason i receive so many 0’s is that the negative numbers returns as 0’s when i receive the array back from the method., so that’s something I’ll have to work with next year.

As for making it random, go check the guy i was following at the beginning, the code that he quotes includes a seed and a random number in that version of Gustavsons code.