Archive for the ‘Coding’ Category

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

Ants Intro

Friday, October 10th, 2008

Inspired by the brave explorers that found their way into my kitchen via means unknown, I’ve been working on a simulation of ants with their actions being based on the pheremone trails they leave behind. Given that I could represent their decision making process with a simple table of values, I decided to use a genetic algorithm to refine the values over successive generations and attempt to breed better and better ants. I wrote up an initial design before I began coding, although I found some issues with it and have strayed somewhat as time has gone by.

As of writing this, I have covered most of the basic functionality necessary to prove the function of the simulator to myself. I have ants that run around and bring food back home, I use a version of a genetic algorithm to make future generations better than prior ones, and I have a visualizer that lets me see how the ants move and how the pheremones are distributed.

Speed is an issue, and it is a limiting factor in running larger simulations and having multiple teams of ants fight one another. In the name of making things run faster, I’m probably going to have to greatly simplify or entirely remove the code for diffusing pheremones across the map. More on this once I come up with a solution, but my initial method required touching every cell on the map 9 times, which just won’t do when I’m trying to run hundreds of thousands of iterations in a timely manner.

So as to provide historical context, I will link to the current revision of the repository. Several aspects of the code have grown beyond my original plans for them and everything needs a bit of a cleanup. As I address the deficiencies of various features I plan to write up the changes I made here.

ICFP 2008 Final

Friday, September 26th, 2008

Well, the final results are up. We were disqualified in the 10th of 11 rounds. Judging by the results (but not looking at the actual map they used, even though they link to it), this one tested whether or not people’s entries correctly tracked and dodged martians. Ours ignored them entirely, of course. Counting places from the top, we came in 29th. Not bad for our first try at a time-limited team contest where we had terrible organization. We’re all excited for next year and hope to do even better, whatever the task is.

ICFP Scoring

Friday, August 15th, 2008

So far we’ve passed the 8th round of testing, as listed on the official scoreboard. So far we’re tending to be in the middle-ish of the pack of entries that survived each round. I’m actually impressed at how well we’re doing. Certain kinds of maps would completely destroy us, given the way we find paths. We could never navigate a maze, for example, nor could we evade martians if they put them directly in our path.

Here’s to victory!