Archive for August, 2009

Map Generator #2

Sunday, August 16th, 2009

Added from last time, I created a second layer of the map that marks which cells are part of which contiguous region. Currently the only regions recognized are land masses and bodies of water. In the future I will most likely also define rules to recognize hilly and mountainous regions. The regions themselves are discovered using a simple floodfill. The next step after this has me a little intimidated, as it will be to use spline curve approximations to vectorize the regions.

The code as it stands takes shortcuts – for example, the program will abort if more than 200 regions are discovered, as the region list is statically allocated. As things continue along rough edges like this will be dealt with.

Have a look:

Color terrain gen

Map Generator #1

Tuesday, August 4th, 2009

After not doing any free-time coding for quite some time, I’ve started a new project. I intend to make a program which can randomly produce a high quality hand-drawn looking fantasy world map. As an example, I’d like output that looks something like this map. I have chosen to develop this as a Mac OS X application that produces scalable PDF files as output. This will involve a number of things that I do not have any real previous experience with. In this post I will discuss the initial terrain generation aspects. I anticipate the next task after that will be dividing the map up into a number of regions based on geographic artifacts and then a vectorization process. Once that is done I will then want to add additional features such as rivers, forests, and towns.

The Code

The version of the code as of this writing is available for your perusal as you read this, as is the most recent version as I add more features. If you wish to follow along any, I will briefly discuss the main two files I created.

terrain.m

I had not previously had any experience with fractal terrain generation. A quick search revealed several useful sources. I created my algorithm from this description and images. I chose to not stitch the sides of the map together as most old-style maps are of a particular region of an entire world, so a loop would not make sense. The code difference is very small, though, so I may make it an option later.

The meat of this file is the function generateWithSmoothness. The basic terrain generation algorithm is the one described in the previously linked article. It’s fairly simple. Each step of the process is based on squares and diamonds formed by the points that have already been evaluated. The center points of these shapes are set to the average of the four corners, plus or minus a random offset. Adding points to the centers of squares in a grid creates a diamond pattern, and adding points to the centers of the diamonds creates a square pattern again. This is repeated until all points have been evaluated. In my implementation I perform this process iteratively instead of recursively as a depth-first solution will have problems with trying to use parent-level points that have not been evaluated yet.

I parameterized the smoothness of the terrain so that I could easily link it with a control in the UI. The smoothness factor controls the rate at which the random factor is decreased at each level of iteration. If the factor is rapidly reduced to near zero then all the points are just the averages of their corners, leading to a very smooth effect.

TerrainView.m

This class implements the component that owns the terrain class from above, tells it to generate, and displays the result. Most of the drawing code, in the drawRect function, was lifted from my earlier Demon project. It simply goes through the data returned by the terrain class, normalizes each point, and blacks out all points below a certain threshold in order to make a smooth surface for the “water”.

Screenshot

Terrain generator app