Random and Procedural Map Generation Part 1: Noise and Maps
Since a young age I’ve always been interested in creating and drawing maps, whether it be political maps of fictional worlds or trail maps of ski resorts drawn on the back of the cardboard that comes with those velvet coloring kits (remember these?). However, I’m terrible at drawing. (like, REALLY terrible)
So, I decided to combine my passion for programming with map making! I wanted to be able to create maps like these with the click of a button:
So I decided to start the project in Java (mainly because I’m familiar with the language) and got to work!
Random Noise
At its basic core, a map can be viewed as a two dimensional grid. Assign some numeric values to each coordinate, and you have elevation. With elevation, we can determine some very basic features crucial to every map:
- Low elevation can be drawn as water
- Medium elevation can be drawn as land
- High elevation can be drawn as mountains
With these three simple rules, we can draw a map; assuming we have a grid with elevation for each coordinate defined. Since we’re going to be generating these maps programmatically we have to figure out a way to randomly generate a map every time we run our program.
I first started by creating a two dimensional grid, and then ran through it assigning random elevation to each point, and whipped up a quick little GUI to display it. (Low elevation is colored as white, high elevation as black)
Looks great! …if we we’re trying to show what channel 97 looked like on decade old television sets.
The problem with this approach is that we have very high elevations next to very low elevations. We need to try and smooth these elevations to prevent these drastic jumps from coordinates next to one another, so we can get rolling hills that lead to coasts that eventually lead to seas.
Smooth Noise
So let’s do just that! Let’s start with the same implementation above, but smooth out all the elevations by averaging each point’s elevation with its neighbors. With that in mind, we get something a little like this:
Well, not much of an improvement, but at least it looks a TINY bit less jumbled. If we imagine hard enough we can see millions of tiny islands; although that takes quite a bit of imagination!
Perhaps our approach was correct, but we just need to smooth out our noise even more! Instead of averaging each point’s elevation with its immediate neighbors, let’s try averaging each point with all of its neighbors within a five point radius:
Okay. So it is a hell of a lot less jumbled than our previous noise graphs. But it still looks nothing like a map! Not to mention how terribly inefficient it is to generate noise this way; for every point we have to average its value with its 24 neighbors (in the case of five degrees). Multiply that by the amount of coordinates in the grid (which is 1,000 * 1,000 = 1,000,000 in the above example) and we have 24,000,000 comparisons being made! Averaging each point’s elevation with even MORE neighbors makes this operation exponentially more expensive, and the result looks more and more like gray paint was smothered across the screen.
But, let’s still see how it looks! Let’s see what smooth noise with ten degrees looks like when we apply the below rules:
- Low elevations are colored blue
- High elevations are colored green
Not too shabby, eh? Perhaps if we were to increase the number of degrees we’d get closer to having continents and oceans, however increasing the degrees as mentioned above is becoming way too expensive. Generating the above graphs took almost ten seconds on my machine! We cannot continue with this approach
Perlin Noise
Perlin noise is a very popular way of generating random, yet smooth noise. The algorithm for generating it is fairly complex, so I won’t go into detail on its implementation here. However, should you be interested in implementing the algorithm yourself (like I did), here are some helpful references to get you started:
After a lot of hard work, and a bit of magic, we get some noise looking like this:
Looks a lot like those “difference clouds” tools in Photoshop and Gimp, huh? That’s because they use this same algorithm, or very similar ones, to generate noise graphs as well! Perlin noise is a very powerful and versatile algorithm that can be used to mimic many real world phenomena, feel free to research more about it on the web. (It is very interesting stuff!)
Getting back to our map generation, we now have a noise grid that isn’t jumbled with drastic elevation changes between neighbors, and still looks different every time we run our program, since we are still using a random seed to jump-start our noise grid. Let’s go ahead and see what this looks like when colored using our two simple rules:
As you can tell, Perlin noise is excellent for randomly generating maps! All we did was generate Perlin noise of a certain size (1000 by 1000 in this case) and then color elevations less than 0 as blue, and elevations greater than 0 as green. And that’s it, we now have a realistic, albeit very basic, map!
Stay tuned for future articles where I dive in to adding additional terrain to our map generator, talk about procedurally generating realistic lakes and rivers, as well as coming up with an algorithm to place cities!