darkpanda
Dark Prince
- Joined
- Oct 28, 2007
- Messages
- 843
This thread is meant to document the internal routines used by CivDOS to generate new, random maps.
To generate new maps, CivDOS uses a set of 4 input parameters, with value ranging from 0 to 2, included
When selecting "Start a New Game", the above parameters are set to [1,1,1,1] by default.
The map generation process goes through the following 7 steps:
The land mass generation uses 2 different map areas, each containing 80x50 squares:
A.1. Generate a random chunk
The random chunk algorithm is:
A.2. Merge the chunk to main geography
To merge the chunk into the main geography, for each square (x,y) from the chunk:
A.3. Check whether land mass is sufficient
There is a simple formula to verify whether the map contains enough squares compared to the land mass parameter:
Spawn/merge new random chunks while ( totalLandMass < ( ( landMassParam + 2 ) * 320 )
This land mass threshold has the following values for different values of the land mass parameter:
A.4. Correction of narrow passages ('X' shapes)
What I call a narrow passage is this famous 2x2 square configuration where ocean and land squares form an X:
Although there is some occurences of this configuration on the Earth map (MAP.PIC), this land configuration is never present in random CIV games precisely because CIV removes them at this step.
The correction is done as follows:
The temperature adjustment phase does the following:
The climate adjustment process war a real pleasure to decipher and understand: somehow it is mimicking the real-world water cycle, accumulating water from the ocean into clouds, which then pour down into rain while shrinking as they fly across land squares. Mountains play an especially strong role in shrinking clouds.
The exact routine is as follows, processing each map ROW (latitude) twice, from West to East (left ot right), then from East to West (right to left):
Next step, the erosion process will give the map touches of "real-world feeling" by basically roughing up everything that has been generated so far.
The algorithm is pretty simple, and does not really seem to follow any logic, more like "randomize" map squares a little bit:
Understanding the river process was a little more challenging, and there's part of it that is still a mystery to me - but it is not directly related to the generation of the map geography... Rather, it is the code that writes pixels with value '8' inside the 'improvement' layer. The purpose of this value has yet to be understood.
Anyways, for the generation of rivers themselves, here is how it goes:
Before going to generate the North and South poles squares, Civ computes the following the map-related data, most of which is eventually stored in the SVE gamesave:
The creation of North and South poles, otherwise mentioned in this thread from Gowron that provides a tool to stop generation of poles, uses the following, very basic algorithm:
To generate new maps, CivDOS uses a set of 4 input parameters, with value ranging from 0 to 2, included
- Land mass: controls the total land mass of the map, i.e. the total number of non-ocean squares (arctic/antarctic excluded)
- 0: Small - islandish world
- 1: Normal - balanced islands and continents
- 2: Large - pangeaish world
- Temperature: controls the spread ratio of arid areas (deserts) from the equator towards the poles
- 0: Cool - more tundra/artic
- 1: Temperate - balanced
- 2: Warm - more deserts
- Climate: controls the overall ratio of "wet lands" (jungle, swamp)
- 0: Arid - more deserts
- 1: Normal - balanced
- 2: Wet - more jungle/swamp
- Age: controls the erosion of the landscape (hills, mountains, inland seas & lakes)
- 0: 3 billion years - more mountains
- 1: 4 billion years - balanced
- 2: 5 billion years - more hills/lakes
When selecting "Start a New Game", the above parameters are set to [1,1,1,1] by default.
The map generation process goes through the following 7 steps:
- Land mass generation: continents are generated randomly, depending on the land mass parameter, with additional processing to refine their shapes
- Temperature adjustment: "dry" terrain types are assigned based on land mass and temperature parameter (desert, plains, arctic, tundra, hills, mountains, ocean)
- Climate adjustement: "wet" terrain types are re-assigned based on climate parameter (jungle, swamp, forests, arctic, plains)
- Age adjustment: terrain types are randomly eroded, based on age parameter (lakes, inland seas, mountains, hills, ...)
- River generation: rivers are added to the map
- Computation of map-related data: continents/seas segmentation, indexing, sizes computation, building sites, high-level pathfind...
- North and South poles generation: creation of poles (arctic/tundra)
A. Land mass generation
The land mass generation uses 2 different map areas, each containing 80x50 squares:
- the geography area is where the final land mass is progressively built; this is the "layer 0" of a MAP gamesave (see this post)
- the stencil area is where chunks of land mass are randomly spawned before being merged into the geography area; for this, CIV uses what is normally the "layer 8" of a MAP gamesave (see this post)
- Clear the stencil area, then generate a random chunk of land mass in the stencil area
- Merge the random chunk to the geography area
- If land mass is not sufficient, loop back to step 1.
- Fix narrow passages ('X' shapes)
A.1. Generate a random chunk
The random chunk algorithm is:
- Initialize:
- Initialize the whole stencil area to value 0 (empty / no land)
- Select a random starting position (x,y) in the range (4,8)-(71,33)
- Select a random path length L in the range [1-64]
- Set the 3 positions (x,y), (x+1,y) and (x,y+1) to value 15 (land); this is like painting position (x,y) with a 3-pixel-corner-shaped brush
- Randomly choose the next position to paint within the 4 direct neighbours of (x,y) at (0,-1)-North, (1,0)-East, (0,1)-South and (-1,0)-West
- Decrement path length L by 1
- Loop back to step 2. above until either path length L = 0 or (x,y) falls outside the bounded range [3,3]-[76,45]
A.2. Merge the chunk to main geography
To merge the chunk into the main geography, for each square (x,y) from the chunk:
- If the corresponding geography is empty (value 0), set its value to 1
- If the corresponding geography is not empty, increment its value by 1
A.3. Check whether land mass is sufficient
There is a simple formula to verify whether the map contains enough squares compared to the land mass parameter:
Spawn/merge new random chunks while ( totalLandMass < ( ( landMassParam + 2 ) * 320 )
This land mass threshold has the following values for different values of the land mass parameter:
land mass parameter | land mass threshold |
---|---|
0 | 640 squares |
1 | 960 squares |
2 | 1280 squares |
A.4. Correction of narrow passages ('X' shapes)
What I call a narrow passage is this famous 2x2 square configuration where ocean and land squares form an X:
Code:
####~~~~ ~~~~####
LAND~~~~ SEA~####
####~SEA ~~~~LAND
####~~~~ ~~~~####
~~~~#### ####~~~~
SEA~#### LAND~~~~
~~~~LAND ####~SEA
~~~~#### ####~~~~
Although there is some occurences of this configuration on the Earth map (MAP.PIC), this land configuration is never present in random CIV games precisely because CIV removes them at this step.
The correction is done as follows:
Code:
####~~~~ ########
LAND~~~~ LAND####
####~SEA ####LAND
####~~~~ ---\ ########
~~~~#### ---/ ########
SEA~#### LAND####
~~~~LAND ####LAND
~~~~#### ########
~~~~#### ~~~~####
SEA~#### SEA~####
~~~~LAND ~~~~LAND
~~~~#### ---\ ~~~~####
####~~~~ ---/ ########
LAND~~~~ LAND####
####~SEA ####LAND
####~~~~ ########
Land mass parameter | 0 | 1 | 2 |
---|---|---|---|
Demo |
|
B. Temperature adjustments
The temperature adjustment phase does the following:
- Define initial elevation terrain based on values coming from the land mass generation: ocean (value=0), flat land (value=1), mountains (value=2) and hills (value>=3)
- Set initial land types to desert, plains, tundra or arctic depending on the Temperature parameter, using the following logic, for each land map square (x,y):
- Compute the map square latitude with some randomness(vertical distance from the equator), and taking into account the temperature parameter, as follows:
- Substract 29 from y
- Add a random value in the range [0..7] to y
- Unsign y value
- Add ( 1 - temperatureParameter ) to y
- Rescale to [0..7] the value above, using the formula latitude = latitude / 6 + 1
- Assign the land typeas follows:
- if latitude = 0 or 1 -> DESERT
- if latitude = 2 or 3 -> PLAINS
- if latitude = 4 or 5 -> TUNDRA
- if latitude = 6 or 7 -> ARCTIC
- Compute the map square latitude with some randomness(vertical distance from the equator), and taking into account the temperature parameter, as follows:
Temperature parameter | 0 | 1 | 2 |
---|---|---|---|
Demo |
C. Climate adjustments
The climate adjustment process war a real pleasure to decipher and understand: somehow it is mimicking the real-world water cycle, accumulating water from the ocean into clouds, which then pour down into rain while shrinking as they fly across land squares. Mountains play an especially strong role in shrinking clouds.
The exact routine is as follows, processing each map ROW (latitude) twice, from West to East (left ot right), then from East to West (right to left):
- For each map row (y from 0 to 49):
- Initialize the row "wetness" to 0 (wetness can be seen as clouds accumulating humidity...)
- Initialize the row "latitude" to |25-y|, i.e. distance from the equator
- Firstly, process each row square from West to East (x from 0 to 79):
- If the square is OCEAN, accumulate clouds:
- compute the square "wetness yield" as |latitude-12|+climateParameter*4 - note: somehow, this yield is the highest for latitude 12, i.e. temperate regions between poles and equator; it is also boosted by the climate parameter, quite logically
- if the square wetness yield is higher than the current row wetness, then increase the row wetness by 1
- Else (if the square is not OCEAN), consume clouds:
- compute a random "rainfall" value between 0 and (7 - climateParameter*2); note: we see here that for wet climates (param = 2), the high random bound is lower (7-2*2 = 3), so the consumption of wetness to transform a square is lower as well, and more squares can be humidified...
- substract the rainfall value from the row wetness
- convert the land type as follows:
- PLAINS becomes GRASSLAND
- TUNDRA becomes ARCTIC
- HILLS becomes FOREST
- DESERT becomes PLAINS
- MOUNTAINS do not change, but additionally decrease the wetness by 3
- If the square is OCEAN, accumulate clouds:
- Reset the row "wetness" to 0
- Then, reprocess each row square from East to West(x from 79 to 0):
- If the square is OCEAN, accumulate clouds:
- compute the square "wetness yield" as latitude/2+climateParameter - note: this yield is different from the previous one, somehow it the highest at the poles...
- if the square wetness yield is higher than the current row wetness, then increase the row wetness by 1
- Else (if the square is not OCEAN), consume clouds:
- compute a random "rainfall" value between 0 and (7 - climateParameter*2); note: same as previously
- substract the rainfall value from the row wetness
- convert the land type as follows:
- SWAMP becomes FOREST - note: this cannot really happen, since the first pass does not create any swamp...
- PLAINS becomes GRASSLAND
- GRASSLAND becomes JUNGLE (for latitude<10) or SWAMP (for latitude>=10), and consumes an additional wetness of 2 (row wetness decreased by 2)
- HILLS becomes FOREST
- MOUNTAINS becomes FOREST, and consumes an additional wetness of 3 (row wetness decreased by 3)
- DESERT becomes PLAINS
- If the square is OCEAN, accumulate clouds:
Climate parameter | 0 | 1 | 2 |
---|---|---|---|
Demo |
D. Age/erosion adjustments
Next step, the erosion process will give the map touches of "real-world feeling" by basically roughing up everything that has been generated so far.
The algorithm is pretty simple, and does not really seem to follow any logic, more like "randomize" map squares a little bit:
- Compute the erosion loop count (amount of erosion) with the formula: loopcount = 800 * (1 + ageParameter); note: this makes between 800 and 2400 loops of erosion ; the older the world, the more erosion there is
- For loop from 0 to loopcount, do:
- If loop number is even (rightmost, least significant bit is 0), select a random map square to process
- Else, if loop number is odd (rightmost, LSB is 1), select a random neighbour from the previous square's inner circle (8 direct neighbours) to process
- Modify the selected square as follows:
- FOREST becomes JUNGLE
- SWAMP becomes GRASSLAND
- PLAINS becomes HILLS
- TUNDRA becomes HILLS
- RIVER becomes FOREST (cannot happen as no river has been created at this point)
- GRASSLAND becomes FOREST
- JUNGLE becomes SWAMP
- HILLS becomes MOUNTAINS
- MOUNTAINS becomes OCEAN (only if NW, NE, SW and SE squares are NOT ocean, to avoid 'X' shapes)
- DESERT becomes PLAINS
- ARCTIC becomes MOUNTAINS
Age parameter | 0 | 1 | 2 |
---|---|---|---|
Demo |
E. River generation
Understanding the river process was a little more challenging, and there's part of it that is still a mystery to me - but it is not directly related to the generation of the map geography... Rather, it is the code that writes pixels with value '8' inside the 'improvement' layer. The purpose of this value has yet to be understood.
Anyways, for the generation of rivers themselves, here is how it goes:
- Initialize the river count to 0; this is to count the number of rivers generated so far
- The routine below is repeated either for a maximum of 256 times or stops as soon as the number of generated rivers is above ((climateParam + landMassParam)*2 + 6):
- First create a backup copy of the whole map, which can be restored later if the river generation fails
- Initialize the river length to 0
- Initialize variable A to a random value in the range [0..3] then multiply it by 2; this makes the value of A taken randomly within {0,2,4,6}; thanks to Renergy for helping fix this
- Randomly select a HILLS square on the map
- Set the currently selected map square to RIVER type
- Check whether any of the 4 direct neighbour squares is of type OCEAN, that is N, E, S or W, and store this info as a flag 'ocean nearby'
- Initialize variable B to the same value as A
- Compute random variable C in the range [0..1]
- Update variable A as: A = ( ( (C - riverLength%2)*2 + A) & 0x7 ); as Renergy thoughfully put it, this is actually a "river downflow" heuristic for choosing the next river square, that can be expressed as: randomly choose to either go ahead or turn at a right-angle; if river length is even, the right-angle turn is to the right (clockwise), otherwise if the river length is odd, the right-angle turn is to the left (count-clockwise)
- The next step is the mystery one:
- Set B = 7-B
- If ( B <= A ) then set the Improvement layer square (x,y) to value '8' ; I can't exactly figure out the meaning of this yet... maybe used for debugging the river generation process ?
- Increment the riverLength by 1
- Select neighbour map square with id (A+1); as A is in the range [0..7], A+1 is in [1..8] and represents 1 of the 8 direct neighbours of the current square
- If the previous map square was NOT next to an OCEAN, and the currently selected map square is neither OCEAN, RIVER or MOUNTAINS, then loop back to step 5.
- Else if the (previous map square WAS next to an OCEAN, OR the selected map square is RIVER) AND the riverLength is equal to or above 5:
- Increase the River Count by 1
- Transform all FOREST squares into JUNGLE, within the 7x7-square area centered on the map square
- Else, discard the current river, and rollback the map geography to its previous state, using the backup made at the beginning
F. Computation of map-related data
Before going to generate the North and South poles squares, Civ computes the following the map-related data, most of which is eventually stored in the SVE gamesave:
- Continents and oceans sizes, in number of map squares: see the SVE data reference
- Continents path-finding data: see this post
- Oceans path-finding data: see this post
- Land values and per-continent build site count: see this thread and the SVE data reference too
G. North and South poles generation
The creation of North and South poles, otherwise mentioned in this thread from Gowron that provides a tool to stop generation of poles, uses the following, very basic algorithm:
- Set the full rows of map squares at latitude 0 (North) and 49 (South) to ARCTIC (value 15)
- Repeat the below routine 20 times:
- Set a random square in range [0..79] at latitude 0 to TUNDRA (value 7)
- Set a random square in range [0..79] at latitude 1 to TUNDRA (value 7)
- Set a random square in range [0..79] at latitude 48 to TUNDRA (value 7)
- Set a random square in range [0..79] at latitude 49 to TUNDRA (value 7)
Last edited: