Posts Tagged ‘graphics’

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

Demon

Wednesday, March 26th, 2008

I’ve been meaning to make a “pretty” implementation of an Xscreensaver hack for ages. It’s called “demon”, and it features a random grid of colored cells that end up in swirling color patterns. I finally got around to trying it out, and used it as an opportunity to play with Mac OS X’s graphics APIs.

Code!

Without any particular context, here is how I iterate. Note that I make the edges wrap around. If the syntax is slightly wacky-looking that’s because it’s Objective C.

Iteration

The logic itself is fairly simple; at each iteration, one particular color of cell gets to “eat” any neighbors of the previous color. To wit: First the red pixels gets to eat their purple neighbors, then the orange pixels get to eat their red neighbors, then the yellow the orange, and so on, until red comes around again. Stable arrangements come up when you have cyclical patterns where the colors can chase one another forever without getting consumed or any one color is entirely eliminated, at which point a cycle can never emerge.

- iterate{
    static int c = 0;
    char **newgrid;
    int x, y;
 
    if(grid == grid1){
        newgrid = grid2;
    }else{
        newgrid = grid1;
    }
 
    int C = (c + 1) % ncolors;
    for(x = 0; x < width; x++){
        for(y = 0; y < height; y++){
            if((grid[x][y] == c) && (
               (x > 0 && grid[x-1][y] == C) ||
               (x == 0 && grid[width-1][y] == C) ||
               (x < width - 1 && grid[x+1][y] == C) ||
               (x == width - 1 && grid[0][y] == C) ||
               (y > 0 && grid[x][y-1] == C) ||
               (y == 0 && grid[x][height - 1] == C) ||
               (y < height - 1 && grid[x][y+1] == C) ||
               (y == height - 1 && grid[x][0] == C))){
                    newgrid[x][y] = C;
            }else{
                newgrid[x][y] = grid[x][y];
            }
        }
    }
    c = (c + 1) % ncolors;
 
    grid = newgrid;
 
    [self redraw];
 
    return 0;
}

Drawing

Unfortunately, the means of drawing I used is rather slow. This is actually my second attempt, as the first was even slower. For reference, the first attempt drew using NSRectFill and associates.

- (void)drawRect:(NSRect)rect{
    if(grid){
        int x, y;
        CGRect pixel;
        CGContextRef context = [[NSGraphicsContext currentContext] graphicsPort];
 
        pixel.size.height = size;
        pixel.size.width = size;
 
        for(x = 0; x < width; x++){
            pixel.origin.x = x * size;
            for(y = 0; y < height; y++){
                pixel.origin.y = y * size;
                Color c = colors[grid[x][y]];
                CGContextSetRGBFillColor(context, c.r, c.g, c.b, 1);
                CGContextFillRect(context, pixel);
            }
        }
    }else{
        [[NSColor blackColor] set];
        NSRectFill ([self bounds]);
    }
}

Future

I will next try and draw to a bitmap and see if that’s any faster. I also suspect that I may want to iterate with a second thread rather than having a callback timer go off every quarter-second. When I’m satisfied with the performance, I’ll post an app on here.