1. Computing

How to Generate a Map for Empire using SDL

Tutorial One of Two

By

Screenshot of Empire Mapgen

There were a couple of entries in Programming Challenge 18 which was about generating maps but I've written this one from scratch based on an algorithm that I developed years ago. The generator code will be incorporated into the Empire game but is worthy of a tutorial in itself.

This is the first of two tutorials on the Empire Map Generator. The second one will be published shortly.

Note, if you are creating your own SDL project (for these sources in Visual Studio 2010 or Visual C++ Express 2010), then you should see How to setup Visual Studio 2010/Visual C++ 2010 Express with SDL.

The generator uses a text file of concentric circles (approximately 40 layers) that are converted into coordinates around a point. A number of land and sea points are "grown" by adding circles of points, except where there is already a sea or land point and the collison of land and sea points builds up an interesting looking map. Not all 40 layers are used, I've used a #define NUMLAYERS of 19. Larger maps would need bigger layers.

The circles.txt file has a * at the centre (x=48,y=44) and that's surrounded by As then Bs etc like this all the way to Z then a-o.

CBBBC
BAAAB
BA*AB
BAAAB
CBBBC

The conversion stage looks for each character A, B etc and generates an offset relative to the * , so the first A is at (-1,-1) the next one at (0,-1), then (1,-1) and so on. There's an array of points for each letter in the 8 points for A, 12 for B and so on.

The converter is a small standalone program that takes the circles.txt file and generates the data.h source code file used by the map generator. In this case I've not published that (written long ago in Turbo Pascal), just the data.h file (in the mapgen sources zip file) that was output and limited to the first 35 rings.

It has MaxLayers = 35 (number of layers). NumLayerPoints[35] holds the number of points in each ring. 8 for 'A', 12 for 'B' etc. Then the offsets[35] into the large circlepoints[] array where the offset coordinates start. This consists of 3,310 pairs of x and y values. The first 8 have the 'A' offset relative to the point.

The first 8 'A' offset is -1,-1 (top left corner) then 0,-1 (middle top) etc. The B's' start at an offset of 16 because the 'A's have 8 x 2 ints and so on. AddaLayertoAllPoints uses the global variable gennum to add a given layer. Note that after adding the xo and yo (offsets), a sanity check is done on x and y to make sure it doesn't go outside the map bounds. The points are done in the order land points then sea points so this simplifies the check to see if the layer is going around a land or sea point. The macro onMap(X,Y) makes this code check inline as it's used in several places

void AddaLayertoAllPoints() {
    int i,x,y,xo,yo,cindex,pindex;
    pindex = Offset[gennum];
    for (i=0;i< NumLayerPoints[gennum];i++) {
        xo= circlepoints[pindex++];
        yo= circlepoints[pindex++];
        for (cindex=0;cindex < numlandpoints + numseapoints;cindex++) {
            x= genpointsx[cindex];
            y= genpointsy[cindex];
            x+= xo;
            y+= yo;
            if (onMap(x,y) && notAtEdge(x,y)) {
                if (map[x][y].locis == ltnull) {
                   map[x][y].locis = (cindex < numlandpoints) ? ltopen : ltsea;
                }
            }
        }
    }
}

The array genpointsx[] and genpointsy[] hold the randomly placed points. The first numlandpoints values are land (ltopen) the rest are sea (ltsea).

I've used SDL to show map generation in action. If you want to see point by point call RenderScreen() after the map[x][y].locis = but make sure you add a SDL_Delay(20) call or the points will appear too fast. The aim of the map generator is to produce a playable map for the two player game Empire that is used in the tutorials.

These are the various stages in map production in the function BuildMap()

  1. Generate a number of random Land and Sea Points on an empty map.
  2. Grow these points adding a layer round every point then another, but only adding the land or sea point if there isn't anything there already.
  3. After all points have been grown, fill in all empty points with sea.
  4. Recursively count the size of every sea. If it's below 75 fill it in.
  5. Recursively count the size of every island. If it's below 100 sink it.
  6. Recount the sizes again after filling in so there are fewer but larger continents.
  7. If the number of continents isn't between 3 and 4, and land count between 1300 and 1700 restart the process.
  8. Add Mountains.

In the 2nd part of this tutorial. This covers adding cities plus a discussion of some of the C code used.

©2014 About.com. All rights reserved.