Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (530)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Generating "True" 2D Perlin Noise  (Read 4770 times)
0 Members and 2 Guests are viewing this topic.
Offline longshorts

Senior Newbie


Medals: 1



« Posted 2013-12-30 18:47:35 »

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.



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 :/
Offline Roquen
« Reply #1 - Posted 2013-12-30 19:43:52 »

No you shouldn't have noticeable defects along the grid.
Offline longshorts

Senior Newbie


Medals: 1



« Reply #2 - Posted 2013-12-30 20:08:47 »

Thanks for the confirmation Roquen Smiley

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:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
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?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Sabomoth

Junior Member


Medals: 1
Exp: 2 years



« Reply #3 - Posted 2013-12-30 20:40:34 »

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;
http://stackoverflow.com/questions/18279456/any-simplex-noise-tutorials-or-resources

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;
https://www.dropbox.com/s/cfrc6pr71n8njcn/diamond.png

Nowhere near as smoth as yours.
Offline Roquen
« Reply #4 - Posted 2013-12-30 21:04:56 »

Quote
but is it that simple?
Yes (in this instance) it's that simple.
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #5 - Posted 2013-12-30 21:29:00 »

@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.

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

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
// 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 Smiley

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline longshorts

Senior Newbie


Medals: 1



« Reply #6 - Posted 2013-12-30 21:45:37 »

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.

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

@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.

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

Junior Member


Medals: 1
Exp: 2 years



« Reply #7 - Posted 2013-12-30 21:57:44 »

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

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.


Offline longshorts

Senior Newbie


Medals: 1



« Reply #8 - Posted 2013-12-30 22:39:12 »

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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
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:

1  
2  
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 Smiley
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #9 - Posted 2013-12-30 23:15:42 »

Wohoo Grin Glad to be helpful Smiley

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Sabomoth

Junior Member


Medals: 1
Exp: 2 years



« Reply #10 - Posted 2013-12-30 23:29:51 »

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.

Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #11 - Posted 2013-12-30 23:37:32 »

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'.

What do you mean by 'perplex' noise? Google couldn't help me :/
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).

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Sabomoth

Junior Member


Medals: 1
Exp: 2 years



« Reply #12 - Posted 2013-12-30 23:45:01 »

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'.

What do you mean by 'perplex' noise? Google couldn't help me :/
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).

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.
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #13 - Posted 2013-12-30 23:51:31 »

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.

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

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline longshorts

Senior Newbie


Medals: 1



« Reply #14 - Posted 2013-12-31 00:01:18 »

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.

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.
Offline philfrei
« Reply #15 - Posted 2013-12-31 01:26:17 »

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?

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.
http://www.java-gaming.org/topics/sivi-2d-simplex-noise-visualizer-tool/30187/view.html
SiVi - Simplex noise Visualizer tool.


This shows a color mapping function I used.




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.


"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline SimonH
« Reply #16 - Posted 2013-12-31 02:18:01 »

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!

People make games and games make people
Offline Roquen
« Reply #17 - Posted 2013-12-31 07:48:27 »

I always call value or simplex noise 'Perlin noise'.
And I always say "right" instead of "left" because it sounds cooler to me.  Screw people that follow my directions.

But, always keep in mind, it's a fractal, not a noise function Wink
The classic octave construction with noise is a fractal.
Offline matheus23

JGO Kernel


Medals: 106
Projects: 3


You think about my Avatar right now!


« Reply #18 - Posted 2013-12-31 11:14:02 »

The classic octave construction with noise is a fractal.

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

Smiley

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Sabomoth

Junior Member


Medals: 1
Exp: 2 years



« Reply #19 - Posted 2013-12-31 14:32:14 »

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.

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.
http://stackoverflow.com/questions/18279456/any-simplex-noise-tutorials-or-resources
Offline Roquen
« Reply #20 - Posted 2013-12-31 16:49:22 »

What do you mean by 'classic octave construction with noise'?
Informally the doubling/halving scheme...it's self similar at all zoom levels.
Offline philfrei
« Reply #21 - Posted 2013-12-31 16:57:23 »

@Sabomoth -

Stefan Gustavson's implementation does NOT require a seed. I'm guessing the seed that is in Richard Stengle's reply must be of his own creation, part of the class "SimplexNoise_Octave" which he wrote.

I imported Stefan Gustavson's improved implementation (referenced in the article we linked earlier) and use that directly. I can't really comment on Stengle's code because I've never used it. There are various steps he could be "helpfully" handling in that code, but it is hard to say exactly what without more code-reading than I want to take time to do.

I think the safest thing is to call Gustavson's static SimplexNoise.noise() directly. You can call it from within two nested loops (height and width) and fill the data array directly, yourself, from the  results of the calls. If you wish to combine octaves, then a third nested loop would also be used, and the results summed via weighting as described earlier.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline Roquen
« Reply #22 - Posted 2013-12-31 16:58:58 »

And there's no need to cut-and-paste from the PDF...there's source on his site (which might include changes made since the paper was written).
Offline philfrei
« Reply #23 - Posted 2013-12-31 17:04:03 »

What do you mean by 'classic octave construction with noise'?
Informally the doubling/halving scheme...it's self similar at all zoom levels.

Exactly.
Ken Perlin himself describes it here:
http://www.noisemachine.com/talk1/21.html

Quote
And there's no need to cut-and-paste from the PDF...there's source on his site (which might include changes made since the paper was written).

Yes! The link is on the paper, and it does include improvements over the implementation code in the paper itself.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

ctomni231 (34 views)
2014-07-18 06:55:21

Zero Volt (30 views)
2014-07-17 23:47:54

danieldean (25 views)
2014-07-17 23:41:23

MustardPeter (27 views)
2014-07-16 23:30:00

Cero (42 views)
2014-07-16 00:42:17

Riven (44 views)
2014-07-14 18:02:53

OpenGLShaders (33 views)
2014-07-14 16:23:47

Riven (34 views)
2014-07-14 11:51:35

quew8 (30 views)
2014-07-13 13:57:52

SHC (66 views)
2014-07-12 17:50:04
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!