New Noise Algorithms

[prestidigitator]

I am messing around with different noise algorithms including Improved Perlin Noise and Simplex Noise, and looking at what it would take to switch base noise algorithms in the server configuration settings and when requesting noise values from the Lua API.

I was wondering if there are any existing tools to test the speed of map generation, so that I can easily compare how the selection of noise algorithms affect it. Is there anything in the GUI, or are there test scripts, or should I just test the functions and classes out separately in standalone code?

Thanks!

[prestidigitator]

Well, I wasn't able to really find anything, so I'm testing straight noise performance using stand-alone test programs.

The first change I made was to go to an object-oriented interface. The old "Noise" class was a step in this direction, but I have made it an interface instead, with virtual methods. Then I implemented LegacyNoise (the current Minetest noise algorithm), PerlinNoise (Improved Perlin Noise), and SimplexNoise.

The result of OO-ifying the API was that individual calls for single noise values slowed down by a factor of 10, but calls that generate whole blocks of data sped up by about 50%. After that, the PerlinNoise and SimplexNoise perform worse than LegacyNoise (about half as fast), but generate much smoother patterns. I'll post a visual comparison at some point.

This is just for a very simple base noise function. I have implemented, but not yet tested, transformed noise (with offsets, smoothing, and input spreading) and fractal noise (multiple octaves). So testing and comparing those will be next.

I'd like to eventually provide an option of switching noise functions, with the default remaining LegacyNoise. I'm not sure whether to stick that in the NoiseParams or just put it in minetest.conf. I'll have to take a look at the parsing and see what is simpler and makes the most sense.

[prestidigitator]

Here is the visual comparison. This is just basic noise, not fractal noise (i.e. one octave worth of noise). I used the straight noise function to create 512x512 grayscale images. Each one is for a 40x40 grid of lattice points. For reference, pretend you are seeing an elevation map, looking down at a 10km x 10km area of Minetest map (since the default noise parameters for terrain use a lattice grid spacing of 250m x 250m).

LegacyNoise


PerlinNoise


SimplexNoise

[Mito551]

SimplexNoise looks cool. is there a way to implement them all at once so that they intersect or something? (i'm not that good with programming and stuff)

[jojoa1997]

They should all be used differently because you have height, humidity,and other stuff I don't remember

[Mito551]

or some kind of fractal stuff: a set of regions is generated with one type of noise, then environment inside the region is generated with another one. something like that

[prestidigitator]

Yeah. I've implemented FractalNoise so its octaves can be built with any of those basic noise algorithms. It would be easy enough to create another variant that could use an arbitrary Noise of any type for each different octave. That'll probably be an exercise for the future though.

Note that I'm going to try to expose this to Lua, too, so when you ask the engine for a noise object you can specify which kind you want. If you use the existing API you'll get LegacyNoise (exactly what you get now). If you add maybe a "type" attribute when you request it, you'll be able to get one of the other types.

[prestidigitator]

Okay. So for PerinNoise and SimplexNoise I simplified the lattice point hash function, which was a little heavy for gradient based noise. These noise functions are now a little slower than LegacyNoise for single octaves, but faster for multiple octaves (implemented by wrapping each object with a FractalNoise object)?! Strange, but anyway they seem to be somewhat competative in terms of performance, being a bit faster or a bit slower depending on the amount of data being produced.

But here's a neat outcome: the quality of PerlinNoise and SimplexNoise is better, meaning that it is likely you could get away with fewer octaves than when using LegacyNoise. So this might easily make up for any straight one-for-one performance comparison.

Here is a texture generated from each of the different base noise functions wrapped by a FractalNoise. Each one uses 3 octaves of noise (and persistence of 0.5 with automatic normalization back to the [-1, 1] output range), and I have reduced the size to 4 lattice cell lengths on a side to "zoom in" and show the fractal noise details better. So instead of imagining this as a 10km x 10km patch of terrain, imagine instead that it is 1km x 1km.

LegacyNoise


PerlinNoise


SimplexNoise

[prestidigitator]

Unfortunately I've been told in no uncertain terms that the existing NoiseParams is "set in stone" so there's no room for adding some kind of "type" parameter to it. This is from a source who apparently thinks I want to reinvent Mapgen when I really just want to provide each Mapgen an alternate source of noise (polymorphism through composition, not inheritance) to use for its source of pseudo-random numbers.

That brick wall will probably make it tough to mix noise types. I think the only real tenable solution left is to change the base noise algorithm used by all parameterized noise (terrain, trees, beach, biome, heat, humidity, etc.).

(Unfortunately there may be some resistance to this change because someone else has recently revamped the noise and mapgen code and may not like it being changed again. I hope that doesn't show up when and if this is ready for a pull request, but even if it does it's still a fun exercise.)

[prestidigitator]

I just spoke to celeron55, who seems interested in this change for the fact that the generalized API will make dynamic modification of fractal noise parameters (scale, persistence, etc.) very easy to change. This would result in the ability to create smoother terrain in some places and more jagged terrain in others. So it looks like this may be a valued enough contribution that small extra requirements like optional settings format changes may be acceptable even if they might touch on some pieces of logic, ah, folks touchy about code they may have changed in the recent past.

(For further info, see the IRC log: http://irc.minetest.ru/minetest/2013-03-23#i_2949428)

[prestidigitator]

I'm going to rename "LegacyNoise" to "ValueNoise" because it's a bit presumptuous, and the goal isn't really to replace or obsolete it but to provide additional options to anyone who likes to tweak their settings.

[proller]

how you draw this noise images?
its possible for custom noise and noiseparams?
i want to play with farscale and farspread params from here https://github.com/minetest/minetest/pull/559

[prestidigitator]

It's not fully integrated yet. I've got some test programs that use the new Noise classes to generate noise values and spit out raw image data that I import into the GIMP (I have to specify height and width when importing) so that I can export them again as PNGs. In fact, all I do is write 512x512 RGB triplets where R=G=B (grayscale) to std::cout, and pipe the program's output to a file. However, soon I should be able to show screenshots of actual generated terrain, and hopefully not long after that I'll have a pull request ready.

I'm paused briefly with the actual noise work so that I can enhance the NoiseParams parsing from the server config file. Currently it assumes that the struct (or any struct you are going to read) is 100% static and will be for all time. I'm working on instead allowing Lua table syntax, so that new name/value pairs can be used but the existing syntax and current behavior will continue to function correctly.

[proller]

you can try use json parser for one config string with noiseparams, its easiest way.
find deSerializeJson in serverlist.cpp

[rubenwardy]

(translated)

It is not fully integrated yet. I have some test programs using the new noise classes to generate noise and spit raw image that I. Import into the GIMP (I have to specify the height and width, the import), so that I can export it again as PNGs In fact, everything I do write to 512x512 RGB triplets, where R = G = B (grayscale) to std :: cout and Pipe. The program's output to a file But soon I should be able to show screenshots of the current generated terrain, and hopefully not long after that I will provide a pull request.

I just stopped using the actual noise work, so I can improve the NoiseParams parsing the server configuration file. Currently it is believed that the structure (or struct you'll read) 100% is static and will remain for all time. I'm at work so instead of Lua syntax table so that new name / value pairs can be used, but the existing syntax and current behavior will continue to function correctly.

please write in English.

[prestidigitator]

please write in English.

From the round-trip, I'd say Google Translate did a pretty good job. ;-)

[prestidigitator]

you can try use json parser for one config string with noiseparams, its easiest way.
find deSerializeJson in serverlist.cpp

Now you tell me! I've actually utilized the Lua parser to do this already, but I set that aside for the moment and will integrate it later. For now I'm going to create a pull request that JUST changes the noise interface, and doesn't provide a way to get to it from the settings file or Lua. The second pull request will have the settings/Lua interface. That way even if people have a problem with the parsing, the noise will at least get in.

[prestidigitator]

Performance test results are in! And they're pretty incredible.

Celeron55 pointed me at F6 (twice) to get the time it takes the game to generate map chunks. So after creating a branch on which I made a rather exhaustive replacement of all calls to noise{23}d_perlin(), NoisePerlin{23}D(), etc., I switched to the branch with the old code, then to the branch with the new code and each of LegacyNoise (soon to be renamed ValueNoise), PerlinNoise, and SimplexNoise selected as the base noise algorithm.

With the old, mostly functional noise calls, generating a map chunk took on average about 120-130ms (this includes lighting calculations of around 50ms).

With ANY of the object oriented calls (LegacyNoise, PerlinNoise, SimplexNoise), generating a map chunk is taking on average about 120-140ms.

So, ah, yeah, it seems to work pretty damn well. (This is on an AMD Athlon(tm) II X4 630 with 8GB of RAM running (K)Ubuntu 12.10, just FYI.)

[prestidigitator]

And now some Simplex Noise terrain screenshots, for your pleasure:









These just look nice, and show it is working. The speed was the exiting part for now. I'll try to get some good tangible comparisons of the actual noise up soon.

[Calinou]

Looks good, why not put that as default if it is faster than the current map generation? We could still keep the old noise in a different mapgen, since we can have several mapgens now.

[jojoa1997]

Yeah maps could be configurable with different map gens.

[prestidigitator]

Well, what I was thinking is that the NoiseParams could select the noise type. That way any type of noise could be used with any mapgen, just by changing the config file. I expect that for the most part different mapgens will differ by a lot more than just which noise algorithm they choose.

But certainly different mapgens COULD select different noise algorithms, both before and after the noise type is added to NoiseParams. I've changed all allocation of noise to call a factory method (createDefaultBaseNoise()), so anywhere you explicitly wanted a particular type of noise, you could create your own factory method or just call "new" with the concrete type you wanted.

It's not faster, but it is about the same, though it might allow for speedups if the noise quality is better enough that fewer octaves of noise can be used. I'll leave it up to others to make it the default if they like; myself I'm a little afraid of messing up existing configurations or worlds (generate new chunks with a different noise functions and you'll get pieces that don't fit at all, like a mixed up jigsaw puzzle.

[prestidigitator]

Okay. Here are some comparisons. I have generated 3 worlds with different noise algorithms but the same parameters (including seed, though that's a little irrelevant when using different noise algorithms). In each I flew around the square (x,z)={(-250,-250), (250,-250), (250,250), (-250,250)} to generate the map and then went to two specific points and took screenshots with roughly the same camera angles. These three shots are from the first point (x,y,z)=(0,250,0):

ValueNoise (called "LegacyNoise" above)


PerlinNoise


SimplexNoise


(Sorry for the clouds. Forgot to turn them off in time.)

[prestidigitator]

Here is the same region of the same three worlds, viewed straight down from (x,y,z)=(0,500,0):

ValueNoise


PerlinNoise


SimplexNoise

[prestidigitator]

You'll notice that you can see somewhat correlating features between the Perlin Noise and Simplex Noise terrain. This is because they use the same gradients to produce the outputs, but the Simplex Noise uses skewed coordinates for the lattice points and does the interpolation a little differently. That's why there are similar major features, but their shapes and locations are distorted a little and the details are different. Value noise, on the other hand, uses the hashes of the lattice coordinates in a fundamentally different way, so there isn't going to be much similar in its features.