Generating Maps II

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.

Leave a Reply

Your email address will not be published. Required fields are marked *