|Programming||By Shamus||May 7, 2012||61 comments|
Perlin Noise is a technique for quickly generating a metric crapload of really interesting pseudo-randomness. “Interesting” in that it forms nice organic patterns instead of pure random noise. “Pseudo Random” in that you can give it the same input and get the same output. “Crapload” means that you can make a final data set thousands of times larger than the noise you start with.
Note that in the context of this project I’m going to discuss Perlin in terms of 2D images, but I’m using it in 3D. It’s just easier to show you what we’re doing in 2D.
We begin with a basic image of really random noise, which I will depict as a 2D greyscale image. The more random the better. We want areas of light, dark, and medium brightness. We want it to be really diverse overall, but have small local clusters of bright or darkness. We don’t want large areas to be homogeneous, and we don’t want the small areas just just be a scatter of white and black pixels. We can accomplish this a lot of ways. I could churn out a bunch of values in a random number generator, for example. Or, we can just open up a new image in your Photoshop of choice, crank up the noise filter on a blank image, and hit save.
No. Obviously pure noise is boring.
To make Perlin noise…
Okay. According to Chris Serson below, this is not Perlin noise. This is… It’s complicated. The point is, when I Google’d for Perlin noise I ran into multiple pages that made the same error I made here. To avoid perpetuating this mis-naming of noise systems, I’m adding this note here.
I will say that it is hard to find a proper implementation of either Perlin Noise or the (sometimes preferred) Simplex noise. Most of the stuff I find is:
- Impenetrable jargon.
- Pages of indecipherable, Greek-laden maths.
- Example images of what the system can do, provided you can figure it out.
- A history of all the noise systems Ken Perlin has made, how he used them, and how people keep mis-attributing other noise systems to him.
So… not much in the way of code out there. In the end, what I have here works well enough for my purposes. If I need something more robust I can go on the quest for the One True Noise Algorithm at another time. Let’s just get on with this.
…we have to sample this image at different resolutions. Massive resolutions. Bigger than we would want to bother keeping in memory, really. What we do is take this noise and kind of zoom in on it. For example, here are the four pixels in the upper-left of our noise image.
Blending between these four values, we can come up with values in between. If it asks for the value 20% of the way across and 80% of the way down, we get this:
To be clear: We’re not calculating ALL of these values. It only creates the one pixel that was requested. I’m just showing you how it arrives at that value.
The neat thing is, I already had 90% of the code needed for Perlin Noise. For those of you reading through Project Frontier, check out
MathInterpolateQuad (). It has everything you need for doing the above.
The terrain generator is feeding us coordinates. We’re dividing those values by a thousand, so that it would require a thousand samples (a thousand meters of scenery) to cover the gradient from one edge of this four-pixel square to the other. Of course, if we stopped here we would have some really boring, super-flat scenery.
So we take another sample. Instead of 1/1,000, this one is taken at 1/500. Then we take another sample at 1/250, and another at 1/125. Each level of noise is at twice the frequency of the one before. Then we add all of these samples together, giving them all equal weight. We average them.
The upshot of all of this is that we get this large pattern of interesting noise.
This might not look terribly useful, but we can use this to generate interesting topography. Obviously we could use this to make hills where brighter = taller. But we can also use it to generate underground scenery. Let’s say we set a threshold. Everything above a certain brightness will be hollow, and everything below that threshold will be solid rock.
Which gives us a system of caves. If we set the threshold higher, then instead of large caves we’ll get little pockets, like Swiss Cheese.
If we take a narrow range of values above one point and below another, then we get a bunch of passages, all twisty-like.
So let’s take this noise and feed it into our cube-world and see how it looks:
This is just raw Perlin output. I’m not doing anything fancy with it at this point. Eventually it might be worthwhile to combine different sets of noise. (Perhaps one to make hills, and another to bore tunnels in the hills.) Or to set up different ways of deciding what’s solid and what’s empty. (Mess with the thresholds.) Maybe I’ll stretch noise along one axis to make tall or long caves. Or flatten out the bottoms to make Star-Trek style caves with lumpy walls and floors level enough for championship billiards. (A classic trope. Actually, is it a trope? I’ve never seen it officially listed.)
One of the things I wanted for this project was to experiment with noise like this, and see what other sorts of shapes and places one can make.
So now we have a foundation for making scenery. I’m sure we’ll come back to this when it’s time to work on the output.