Noise!
If you have any experience with procedural generation then you’ve probably at least heard of Perlin noise and/or Simplex noise. Both of these are examples of “coherent” noise (basically continuous noise that also always produces the same output for a given input). Noise can be defined for any number of dimensions (most commonly 2 and 3), and is used for procedurally generated textures and terrain (where the bright areas might become hills and the dark areas might become valleys).
The first of the two, Perlin noise, is an older algorithm developed by Ken Perlin in 1983. While it can definitely be used to create some great effects, it has the downside of having noticeable grid artifacts due to its underlying cubic lattice. These artifacts are seen as strong directional tendencies in 2D slices of noise, as well as visual differences between integer-valued and non-integer-valued slices of 3D+ noise. [Images generated using an implementation of Ken Perlin’s 2002 improvement upon the old algorithm]
Then Ken Perlin came out with Simplex Noise in 2001. Simplex Noise did a lot as far as resolving the directional artifacts goes, by switching to a different lattice structure. It was also faster, especially in higher dimensions. The downside is, of course, that the 3D-and-higher variants of Perlin’s Simplex noise are patent-encumbered, knocking their viability for independent developers down to basically zero. [Image: 2D slice of 3D Simplex noise, credit Stefan Gustavson]
Our game needs 3D noise for terrain generation, particularly cave generation and cliff/arch/overhang generation. That leaves us with two options: Take the easier and less-interesting route and deal with the artifacts of Perlin noise, or create something new. So I took the latter route, and developed a new noise algorithm for us to use called OpenSimplex noise.
The algorithm borrows the surflet summation idea from Simplex noise, but is based off of the lattice of a Simplectic Honeycomb instead of a skewed scissor-simplex lattice, and uses a slightly larger surflet radius. The result is a noise algorithm that, while isn’t as fast as Simplex noise, seems to beat Perlin noise in basically every speed-test I give it (Late edit: After further tests I retract this), and avoids significant cardinal-axis bias just like Simplex noise does. Below is a sample render (2D Slice of 3D).
If you’d like to try the algorithm out for yourself, or perhaps even use it in something, feel free. Here’s the code for a 3D implementation in Java, as well as a sample class you can use to test it quickly: https://gist.github.com/KdotJPG/b1270127455a94ac5d19
Play around with it and see what kind of effects you can create! Apply various functions to the output, do things with multiple differently-seeded instances, create animations by making the z value increment each frame, etc.
Stay tuned for the 4D implementation! I’ll be making another post on this blog once I get that ready.
