A while back, I talked about generating maps for a civilization type game for the coco3. I left it last time with generation of land mass blobs but no actual terrain. So how does one turn a land mass blob into something with forests and plains and deserts?
It turns out that there are a lot of ways of generating terrain. However, most of them involved complex algorithms that require heavy computation and/or a great deal of code. There are two problems with those algorithms. The first is that the documentation on those algorithms is completely opaque to anyone who doesn’t already understand them, dripping in mathematical jargon, incomplete examples, poor or inconsistent use of terminology, and so on. In other words, I couldn’t figure most of them out. But that was not the biggest problem as it could “easily” be solved by some additional research.
Instead, the real problem is that the coco3 has limited resources. For technical reasons, this entire operation is going to be done at the assembly language level. That means I have to provide all my own routines to do everything. I also have limited memory available for the code, which makes things even more difficult. I can’t even throw a C compiler at the problem because the resulting code for the game will be larger than the addressable memory space of the machine. That means that in order to get a functional result, I need a relatively simple algorithm. That means I cannot use any algorithm that needs huge intermediate data sets due to lack of memory, nor can I use an algorithm that needs complex spatial analysis due to both lack of memory and processing power.
Fortunately, there are relatively simple solutions to generating a mostly adequate map. First, however, I needed to define what characteristics make up a decent map.
The most important characteristic is that the poles need to have colder terrain types and the equator needs to have hotter terrain types. Across the rest of the area, the terrain types should gradually fade between the extremes. That means one should not find a hot desert tile beside a polar glacier, for instance.
There are other factors, too. The most significant one is humidity which determines whether the terrain is wet or dry. Too dry and you can’t have a forest. Too wet and you get a swamp. That sort of thing.
So how do we handle this simply? Let’s examine the temperature problem first. It’s relatively easy to decide that the average temperature of the poles should be, say, -20. And let’s say the average temperature at the equator is 40. These numbers are arbitrary. Changing them will change the resulting terrain distribution. Raising the polar temperature would give a warmer world while lowering the equatorial temperature would give a cooler world. Moving the temperature extremes closer together yields a smaller variation in terrain types by latitude while moving them apart makes the transition more extreme.
The problem is now determining how to interpolate the temperature at intervening latitudes. This interpolation function can be as complicated or as simple as desired. For simplicity, I chose a linear function which has a slope determined by the temperature differential between the poles and the equator. To avoid having even thermal bands across the map like stripes, I added a random fudge factor to the temperature determination for each tile. To avoid range errors, the resulting temperature is coerced into a fixed range.
Now that I have a way to set the temperature of each tile, I then needed to set a temperature range for each terrain type. This is another factor that can be tweaked to change the map results. Changing the minimum and maximum temperatures for the various terrain types will affect their relative placement on the map. Of course, it is important that there is always at least one available terrain type for any valid tile temperature.
Now comes the fun part – setting the terrain. For each map tile that has been marked as land, the temperature of the tile is calculated. Then a list of terrain types that are valid for that temperature is created. One entry in that list is chosen at random and the tile is set to that terrain type. By adding the same terrain type to the master list multiple times, the relative frequencies of each terrain type can be controlled. For instance, plains could be made more likely than grassland at one latitude but the opposite at another latitude by strategically filling the master list of terrain temperatures with extra entries.
Here is an example of a map generated using the above method:
FFFTI F I IIITT
FITFFIIFF I I F IIII
FTFIIFIIFF TIFF IFIF
FF GFIITTF TITTIGFFI
TGFFFFTTFFF FFTFFFFF
FTTTGTIFGT T G GTIG FFF
TGGTFFGIGT T TF FGIF FIFFGGFT
FTTFFTFGGF FFG G FFGG TGFGFGGT
GFFTGTGFG FGG FGF FGGGFGF GJFTGGG
GGGFFPFFFFFG F F F FPTGFG FJFFGFF
FFGPGGFFFGGGGFJF FGFGPFF GFFGF GFF
GFPFFGPGPFGFPFJF FPJJF JFGFGGPP
GPGPFFFPGPPFGJJ P PGJFJJF
GGPFFPGFJGFGFGFFF FFFGFFF
GJGGJPJPFGGFJFGGGJ PJFPF
JJJJPPPGJJPPJPJGJF J PPPPP
DFFGPJJFFJJJPJFJPPGP JPJJ
DFPJFGJPJJJDJFJPPFPP JJ PP
JDPJJPGGJPPGPPPJDJJF GP JJPJP
JJJJPJPJPF PPJJPPPD D DJ JJJ FD F
PJPJPJPPJJP PJPDJJJ JJDJ DP PDJ JDJP
JPPPJDPJ PDJPJDJP J DDPDPPPDJJJJP DP JJD
DD JPPDDP JPDDD P D D JJPDDDPDPJJJDJJJ PDJDJJ
PD PJ JDJ JDDD D D D JJDDDJJDPPPPDDJPPJ DJJ P D
PJD PDJJ PDDJJ D D DDPDDJJPDDJPDPPDJDPD J J J
DD JD J PD JPD DD J JJJDJDDPDPJJDJDPJDD D
DD JPJ JDDD DDDJ PD PDDJJDDJ DJDPDPDDDPDD
D J JDDDJ PDDDDDJDDDDJJDJDJDPJP
DDDDDDDD D JDJDDDDDJJDDDJDDJDDDDDD
DDDJDJD DDJDJ JJDDJDDDDDDDD JDDD
DDDDDDD JDDDDDDDDDDDDDDD DDDD
D DDDDDD DDDDDDDDDDDDDDDDDDD DD
D DDDD D DDDDDDDDDDDDDDDDDDDDDDD
DDDDD DDDDDDDDDDDDDDDDDDDD
DDD DDDJDDDDDDDDJDDDJDDD
DD DDDDDDDDDD DJDDDDDD
DD D JDDJD JDD JD
D DJP D
JJD
P JP
D P D DJDJ
D P J J DDPPDP J DD
D PP DJ D JPDPPP PJPPPP D
J PJ GD JPP PPPJP DPPPPPD JPPPP P
J JPJPF JPJD PJ PPFPJJ JJPPGJDJJJJGD JJGPF
PGPPGJ D JPFPJPPJ D JPJJJGJ FDDF JJJGJGPFJFJJFF
DPJPJPFJPPPJPPDP P PJGGPJPDG FDJPPJJPJPDJFDJJJ
FFPPFJJJPFJPPPPJJG PF FPPJFJGJGJF FGFPPGPPPGPJJFPPFFF
PFGPGPGPPPJPJPPPJ F GPFPFPFJFJPPPFPGGFGGFJFGPGFPGP GGJ
FJ GJGJFJF PJPPFJPJ JFFFFGJGP GG GGGFJPFFGGJPFGGP JF
G JGFPFFFGFGJFPF GPGGGGFFGGFPGFJFFGGFPGFGFJJJGP
GPFFF FGGGFFPFPJG J FGGGFPGGFPFFGFFGFPGFFJFFFGGGPFJ
FFGFFFGGFFFFG JGGGJ G FJFGGGPGPGFJGGPFPFJGFGJPGGFJGGGF
GFFGGJGGFGFPFFGFFFF FTGFFFFFGGTFJFFGG GFGGGFJFFFGGTT
GFGGF FFFFGFFPFF J TGFGFJFGGGFGFPGGFFGFFGGGGT
FGFGT GTTFFGTG FFGFFFFGTFGGGFFGFFTGTGTG FFFGF
ITTT GFF IFTGIF FIFTGFFGGGTITFGTFFTF GFFGFGT
FTF F FFTFTTGFF G FITFFTTGTGFGGTFTIGTGFTFTFTFTIF FF
GFIIIFF FTFIFTIFF FF GGFF TGTIFFFFFTFFFFF FFFFGI I FIT
TFTIFGI FTTTFGFIT F FFIF FTFFIIFIFFFFFIIFIFIFFGFGIGFIIT
FI IFTFT IIIIT TFI FFFFIFFIITTIFIFFFF FFFIFTI
FFTFF I FFFI IFFFFTFFITTFFIFITF FFF F
Each letter above represents a terrain type. “I” stands for “ice”. The rest should be relatively guessable.
The above does not have any consideration for humidity levels or for determining forest coverage. Instead, it treats forest and jungle as separate terrain types. However, the same method used to filter terrain for temperature can be used to filter for humidity; it just requires another set of parameters for the master terrain characteristics list. It also needs some means to determine humidity. It is probably sufficient to handle humidity in a somewhat random manner though proximity of ocean tiles might be worth considering at some point. Again, adding complexity may make the process too slow on the limited platform this exercise is targeting.
It’s also clear that there is far too much ice deployed and forests appear to be a bit too common. These are easily adjusted by tuning the master terrain list and the temperature calculator. Also, adding humidity to the calculations will make a difference as well. With a general algorithm now worked out, the rest is merely tuning.
Next time around, I will discuss exactly how this might be implemented on the target machine. To now, I have been testing code using C on a modern computer. Converting the algorithm to assembly language on a coco3 will likely prove as challenging as working out a map generator in the first place.