Perlin Noise Island Generator source code by Chris Breinholt.
One of the big things with the new game I'm making is I want it to have replayability. I want people to keep coming back to the game, playing it over and over again, having a unique experience every time they play it. It just makes the game that much better. This is a hard thing to do with 2D rogue-like RPG's though, so one of the ways I thought would help with replayability, would be implementing random world generation. Meaning, every faeture in the world (forrests, mountains, beaches, dungeons, caves, etc), would be completely randomly generated. That way the player is pretty much in a whole new world each time he plays the game. So after many hours of research on the topic, one algorithm really stood out to me, and could help generate the exact kind of terrain I was wanting. It's called Perlin Noise.
I'm not going to explain the algorithm a whole lot, but if you want more information on Perlin Noise, I strongly suggest reading this article. After writing my own python implementation, I had a program that would generate terrain like these:
And if I color the map, like these (Tan=Beach, Light Green=Plain, Dark Green=Forrest, Blue=Water, and Grey=Mountains/Caves):
This produced some pretty good looking random terrains. But the were a little too jagged for what I'm looking for. So I wrote another function that helped to smooth everything out. Here are the results:
The results are pretty amazing, but if this was going to be the world for my game, what is going to stop the player from walking off the edge? The terrain is great, but still isn't quite what I'm looking for. So then the thought of a large island popped into my head. If I could tell the program to generate an island surrounded with water instead of a plain with bodies of water, there would be reasonable limit as to where the player could actually travel. After some reading on theories of how to do this, I basically just used the same program I wrote for my dungeon generator for finding the rooms furthest away from the path from the staircases. The program generates map the same size as our noise map filled with 0's, then it picks a random spot, adds 1 to the value of that spot, then travels across the map in random directions adding 1 to each new spot IF the new spot has a value that is less than or equal to the current spot, then repeat those steps a bunch of times. This created maps that higher areas in the center part, and lower areas in the outer parts, just like an island! The next step would be to normalize this new map so it had values from -1 to 1 instead of 0 and up. Then we multiply the Perlin Noise map that makes up our current plain map (before my smoothing and coloring functions), by the corresponding values of our new island style map. This gave me the results that look something like this:
Then once we add the coloring function...
Then finally use the smoothing function to make the map a little cleaner.
Perfect! That's exactly what I wanted for the game. The steps for the whole program are something like this:
1. Generate Perlin Noise map.
2. Generate a "Island" mask map.
3. Multiply each value of the Perlin map by the corresponding value in the Island map.
4. Color the map, then smooth it to clean up the picture a little bit.
I can write a MUCH more in depth guide on how Perlin Noise works and how to implement it, as well as more explanation on the Island mask algorithm and how to combine the two, but it would take quite some time. So if anyone is actually interested in that let me know and I will do it. :)
I uploaded the Python source code for this program, here is the link to the google code project page.
You can download the source under the downloads tab: