Casus Belli - Article 1- The Map Generator
Empire type games (and CB is no exception) use a grid. Typical map size is 80 wide x 50 high. That is what we'll be using. Let me introduce you to my "progressive fast filled circle" algorithm.
Slice of Circle
This is a slice out of the full circle in the Text File.
............onmlkjihgfecbbaZXWVUTRQQPONMLKKJIIIIIIIJKKLMNOPQQRTUVWXZabbcefghijklmno. ............onmlkjihgfecbaZYWVVUTRQPONMLKKJIIHHHHHIIJKKLMNOPQRTUVVWYZabcefghijklmno. ............onmlkjihgfecbaZYWVUTSQQPONLKKJIHHGGGGGHHIJKKLNOPQQSTUVWYZabcefghijklmno. ............onmlkjihgfecbaZYWVUTSQPONMLKJIHGGFFFFFGGHIJKLMNOPQSTUVWYZabcefghijklmno. ...........onmlkjihgfedbaZYYWVUSSQPONMKJIIHGFEEEEEFGHIIJKMNOPQSSUVWYYZabdefghijklmno. ...........onmlkjihgfedbaZYXVUTSRPPONMKJIHGFEDDDDDEFGHIJKMNOPPRSTUVXYZabdefghijklmno. ...........onmlkjihgfedbaZYXVUTSRPONMLJIIHGEDDCCCDDEGHIIJLMNOPRSTUVXYZabdefghijklmno. ...........onmlkjihgfedbaZYXVUTSRPONMLJIHGFDDCBBBCDDFGHIJLMNOPRSTUVXYZabdefghijklmno. ...........onmlkjihgfedbaZYXVUTSRPONMLJIHGFDCBAAABCDFGHIJLMNOPRSTUVXYZabdefghijklmno. ...........onmlkjihgfedbaZYXVUTSRPONMLJIHGFDCBA*ABCDFGHIJLMNOPRSTUVXYZabdefghijklmno. ...........onmlkjihgfedbaZYXVUTSRPONMLJIHGFDCBAAABCDFGHIJLMNOPRSTUVXYZabdefghijklmno. ...........onmlkjihgfedbaZYXVUTSRPONMLJIHGFDDCBBBCDDFGHIJLMNOPRSTUVXYZabdefghijklmno. ...........onmlkjihgfedbaZYXVUTSRPONMLJIIHGEDDCCCDDEGHIIJLMNOPRSTUVXYZabdefghijklmno. ...........onmlkjihgfedbaZYXVUTSRPPONMKJIHGFEDDDDDEFGHIJKMNOPPRSTUVXYZabdefghijklmno.... ...........onmlkjihgfedbaZYYWVUSSQPONMKJIIHGFEEEEEFGHIIJKMNOPQSSUVWYYZabdefghijklmno.... ............onmlkjihgfecbaZYWVUTSQPONMLKJIHGGFFFFFGGHIJKLMNOPQSTUVWYZabcefghijklmno.... ............onmlkjihgfecbaZYWVUTSQQPONLKKJIHHGGGGGHHIJKKLNOPQQSTUVWYZabcefghijklmno....
If you view the full file (pretty!) you can see that is is 35 'concentric' circles around a point. I've transformed this text file into a set of offsets from the centre * point.
In c++ this is defined like this.
const MaxLayers=35;
const int NumPoints[MaxLayers]=
{8,12,16,32,18,28,40,44,60,52,54,56,72,80,76,100,86,92,96,96,128,128,106,
120,136,140,140,168,126,160,168,164,172,180,156};
const int Offset[MaxLayers]=
{0,16,40,72,136,172,228,308,396,516,620,728,840,984,1144,1296,1496,1668,
1852,2044,2236,2492,2748,2960,3200,3472,3752,4032,4368,4620,4940,5276,5604,
5948,6308};
const int C[6620]={
-1,-1,0,-1,1,-1,-1,0,1,0,-1,1,0,1,1,1, ... lots and lots more
NumPoints says how many points there are in each layer. The first layer is the A's - there are 8 of those. Offset is how far into the data each layer starts. c is 3310 pairs of offsets (horizontal and vertical) so starting at the * -1, -1 is the offset of the A in the N.W corner. Moving clockwise through the A's is 0,-1 then 1,1, down a row to 1,0 and so on.
So how is this used to generate maps? Its quite simple. The Map grid holds three values- 0 = empty, 1= land, 2 = sea. 1. Generate 40 or 50 random land points then 30 or 40 sea points. Store the coordinates of all the land and sea points in two arrays. 2. Loop through 35 generations and for each generation we loop through all land and sea points. Look at all the points (for that generation) around each land or sea point. If the examined location is empty we set it to be the same as the centre point. If there is something there already, we ignore it and move on.
Its a bit like pearls growing in an oyster. We expand each point with extra layers but add an extra layer to all points at the same time. Inevitably land points coalesce into bigger continents and islands while the increasisng sea points bump against them to give interesting coast lines and lakes.
This is followed up by a quality check. As map generation is a stochastic process (that's posh for random) we only want to accept the map if it falls within certain limits.
The limits I set are
- All islands must be 300 squares minimum size. If any are smaller they get sunk.
- Any lakes below 10 in size are filled in.
- There must be 3 or 4 islands/continents. 2 is too little 5 or more too many.
- Land must be around 1800-2100 squares.
If we were going for ultra realistic map generation, you'd expect 30% of the map to be land - around 1,200 squares. But that makes things too spread out- so 50% more land makes for more interesting maps.
How do we count the size of islands?
And Lakes as well. We use a recursive fill algorithm. First we loop through the map squares and set all empty squares to sea as "nature abhors a vacuum". Next we define an extra byte (signed -127..127) for each map location and we'll call it the continent number. It's +ve for land, -ve for sea. This is preset to 0. We now loop through the map looking for any location with a zero continent. We now call a function to count land (or one to count seas). I found it easier to have two functions, each has the coordinates of the square as its parameters.
After checking that the coordinates are on the map, if the continent number is 0 it sets the continent number to the current value then calls itself 8 times, passing in the coordinates of the 8 locations around itself. Eventaully this finishes, having 'explored' all adjacent locations of the same type. Be careful with large map sizes as the recursive painting algorithm can eat up the stack very quickly.
When the fill's are being done, count how many times each continent location is set and record the continents (and lakes/seas) sizes. This is needed for pruning out unsuitable maps according to the limits set earlier.
Now Just add cities, terrain and voila
Terrain is forests and Mountains. Mountain are impassable so we don't want too many of those- say 200. Forests we add 500. You can try different values. However we want to add cities first and there is one major constraint. Spacing. We don't want to add a city if its next door to another. We need at least 4 squares separation. For a map this size we are adding 50 cities which means 1800/50 = 36 squares each. Think of each city in an 6 x6 block.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 * 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
This gives approx 4 to 5 squares of separation so long as all cities can be fitted in. If we use Pythagoras and when pick random locations then it's possible when we add a new city to scan the list and see if (xc-xn)^2 + (yc=yn)^2 is > 16. If its not we try again. keep track of how many times this is retried and if it reaches say 1,000 then this map is a dead loss and best to regenerate another.
Typical Game Map
24 ~~...~^^..~~~~~~~~~~~~.........~~~~~?^^^^.O?~~~~~~~~~~~~.......~~~~~~~~~~~~~~~~~24 25 ~~.........~~~#.~~~~~~?.......?~~~~~.^..^...~~~~~~~~~~~~...^..~~~~~~~~~~~~~~~~~~25 26 ~~~O....?#.~~~O.~~~~~.....^~~~~~~~~~....##..~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~26 27 ~~~.^..###.~~~?.##~~~~O.^..^.~~~...##..###..~~~~~~~~~~~~~~^^.~~~~~~~~~~~~~~~~~~~27 28 ~~~.?.^^#O.~~~....~~~~~~..^O...~.O##?^.^?#..~~~#~~....~~~~.?...?~~~~~~~~~~~~~~~~28 29 ~~~......#......##.~~~~~~.?.......###..^.##O?#.#.....?~~~~......~~~~~~~~~~~~~~~~29 30 ~~~.......#....#...~~~~~~~...~?......^^...#~~~#.......~~~~.....#..~~~~~~~~~~~~~~30 31 ~~~.O.#..##.........~~~~~~~~~~.#......#.###~~~......~~~~~~~~~#.###~~~~~~~~~~~~~~31 32 ~~~~~..###..#..#....##~~~~~~~~#....~~##.###~~~##.....#~~~~~~~###.?.~~~~~~~~~~~~~32 33 ~~~~~###?###.#?##..?##...~~~~~..i^#~~.^#?#.######..?###..~~~~~#..^#~~~~~~~~~~~~~33 34 ~~~~~....O...#.##..###.....~~~?....~#...####.####..###.....~~~....#~~~~~~~~~~~~~34 35 ~..?..........O.......O.?..~~~~..^O..#...^.....?..#.##.?...~~~~..~~~~~~~~~~~~~~~35 36 ~....................~~....~~~~~~.?.###O..^.....###..~~~~..~~~~~~~~~~~~~~~~~~~~~36 37 ~...O......?.....~..~~~~...~~~~~~~..###?..^.....#.#.~~~~~..~~~~~~~~~~~~~~~~~~~~~37 38 ~~~~~............~~~~~~~~~~~~~~~~~~~.........O.....~~~~~.~~~~~~~~~~~~~~~~~~~~~~~38
Map Legend
- ~ Sea
- . Land
- ^ Mountain
- # Forest
- O City
- ? Unknown Resource
A full map is here
This isn't what will be displayed on screen, just what is actuially there.
