Generating Maps

It turns out that generating maps for a game like lwciv is not an easy problem to crack. The map is a critical component of game play and, therefore, must be generated in a way that is actually playable. For a Civilization type game, that means there must be land masses that are large enough to be playable before seafaring technologies are discovered. They must also be far enough apart to be difficult to reach with early seafaring technology, but the placement requirements must not be so strict that they limit the map variations. What follows is part one of my map generation odyssey.

The first problem I faced was finding a random number generator. I did a lot of searching around the interwebs but failed to discover anything I actually comprehended. It seems everyone likes to discuss random number generation, or more accurately, pseudorandom number generation, using advanced mathematics terms and notation. In other words, all the documentation is completely impenetrable unless you already understand the material being discussed. It’s no wonder people hate mathematics.

Eventually, my google-fu proved strong enough to uncover some references that were mostly comprehensible. I let what I almost learned percolate for time. Then I exercised my google-fu again and discovered some example random number generation code for the mc6809 (the CPU in the Coco3). This caused a blinding flash of understanding and I now had a random number generator I could use. Better yet, some additional research revealed exactly how it works if not why which means I can now generate arbitrary sequences of random numbers. I won’t go into the details of how the generator works, only that it does and it works in about a dozen instructions.

I tried out a simple random map generator and it became obvious that I needed something more sophisticated than simply rolling the dice for each map tile. So, I cranked up my google-fu again and wandered around through any number of map generation techniques from the “diamond-square algoirthm” to “perlin noise” to “fractal perlin noise”, and beyond. Just like for random number generation, nearly everything employed opaque mathematics jargon and notation, or worse yet, obscure pseudocode. Or it worked in Java or javascript or C++ or what have you but relying on obscure libraries or otherwise requiring a lot of knowledge beyond the algorithm being implemented. It also transpired that most methods were suitable for generating height maps but not so much for a civilization style map. There was a lot that suggested “just pick a cut-off and anything over that is land” and similar and it seemed reasonable.

Now it was obvious to me I wasn’t going to be testing algorithms by writing them in 6809 assembly language and running them on the Coco3. It was simply too much to do that. Instead, I decided to use C on my PC and have it display the test maps as a text dump. This proved to be a good choice.

First, I tried the diamond-square algorithm. I never did get it performing consistently though I did get some maps that were reasonably good. But with this algorithm, I could not reliably generate multiple land masses and what did get generated often showed “interesting” artifacts which would have required a smoothing pass to fix. To further complicate things, the diamond-square algorithm requires a map size that is exactly one bigger than a power of two, and also requires a square map. There are ways to work around those limitations but given the inconsistent results I was getting, I decided to look for another possibility.

I considered using Perlin noise or similar but that required too much brain work to understand and there was too much conflicting information, incomprehensible code, and so on, related to it so I binned the idea, at least temporarily.

The next thing I tried was picking a seed point for a land mass then plotting a land tile adjacent to it depending on the number of already adjacent land tiles with the requirement that the new land tile must not link up two separate masses. With this method and the introduction of some random perturbations, the results were better than with the diamond-square algorithm. However, they were also still too inconsistent and the land masses were to round with edges that were far too smooth.

I started looking around at existing open source projects for ideas. I looked into the freeciv map generation code and discovered that if it had been simple at some point, it was now far too complicated to figure out without a detailed understanding of the rest of the freeciv codebase. (Magic numbers for map types, anyone? Really?) Eventually, I decided to take a look at the map generator in freecol which seemed to generate decent maps. A quick review showed that the basic algorithm was split between generating land masses and setting the terrain on those land masses. The algorithm for generating land masses proved to be simple enough. However, it may be somewhat problematic for implementing on the Coco3 given that it uses a largely unbounded linked list to hold its state.

I cranked up my Mad C Skillz and implemented a simple version of the algorithm. The results were promising but not quite right. I spent some time tweaking and fiddling with it, adding a random perturbation here and adjusting land mass size parameters there until I finally got something plausible. Then I had to force the land masses to be further apart which required some more fiddling here and there, and more random perturbations to make it look less contrived. Finally, I started getting maps that look like the following:

     GGGGGGGG GGGGGGGGGGGG  GG           GGGGG  G                                               
   GGGGGGGGGGGGGGGGGGGGGGGGGGGG          GGGGGGG                                                
   GGGGGGGGGGGGGGGGGGGGGGGGGGGG          GGGGGG                                                 
   GGGGGGGG GGGGGGGGGGGGGGGGGGG G        GGGGGG                                                 
    GGGGGGGGGGGGGGGGGGGGGGGGGGGG          GGGGG                                                 
    GGGGGGGGGGGGGGGGGGGGGGGGGGGG          GGGG GG                                               
     GGGGGGGGGGGG GGGGGGGGGGGGGGG              G                         G                      
   GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG            G                         G                       
    GGGGGGGGGGGGGGGGGGGGGGGGGGGGG                                      G                        
     G GGGGGGGGG GGGGGGGGGGGGGG                                        G                        
     GG GGGGGGGGGGGGGGGGGGGGG                                                                   
     GGG GGGGGGGGGGGGGGGGGGGG G                                                                 
      GGGGGGGGGGGGGGGGGGGGGGGGGG G                                                              
     GGGGGGGGGGGGGGGGGG GGGGGGGGGG                                                              
     GGGGG GGGGGGGGGGGGGGGGGGGG GG G                                                            
     GG GG  GGGGGGGGGGGGGGGGGGGG GG G                                                           
     GGGG G  G G G  GGG GG  G                                                                   
     G  GG          GGGGGGG                                                                     
     G  GGG               G                                  GG                                 
                                                          G  GG                            GG   
                                                        G G GGGG                            G   
                                                       G GGGGGGGG                               
                  GG   G G                             GGGGGGGGGG                               
                   G   GGG   GG                        GGGGGGGGGGG                              
                    GG  GGG GGG                    G GGGGGGGGGGGGG GG                           
               G    GGGGGG G GGG                G  GGGGGGGGGGGGGGGGGG    GG  GGG                
       GG     GG    GGGGG GGGGGG   GGGG         G GGGGGGGGGGGGGGGGGGGGGGGG  G  G                
       GG     GGGGGGGGGGGGG GGGG    GGG           GGGGGGGGGGGGGGGGGGGGGGGG                      
           G GGGGGGGGGGGGGGGGGGGGG G G              G GGGGGGGGGGGGGGGGGGGG                      
         G  GGGGGGGGGGGGGGGGGGG                 GGGGGGGGGGGGGGGGGGGGGGGGG   G                   
      G G GGGGGG GGGGGGGGGGGGGG GG              GGGGGGGGGGGGGGGGGG G    GG G                    
      GGGGG GGGGGGGGGGGGGGGGGGGGGGG            G  GGGGGGGGGGGGGG    G    GG G                   
     G GGGGGGGGGGGGGGGGGGG GGGGGGGG           G   GGGGGGGGGGGGG G    GG   G                     
         GGGGGGGGGGGGGGGGGGGGGGGGGG               GGGGGGGGGGGGG     G G                         
  G   GGGGGGGGGGGGGGGGGGGGG GGGGGGGG               GGGGGGGGGGG         G                        
   GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG                  GGGGGGGGG                                  
   GGG GGGGGGGG G GGGGGGGGGGGGGGGGGG                 GG GGGGGGG                                 
  GGG GGGGGGG GGGG GGGGGGGGGGGGGGGGG                G  GG GGGGGG                                
   GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG                     GGGGGGG                                 
 G GGGGGGGG GG   GGGGGGGGGGGGGGGGGG                    GGGGG                                    
GGG GG  GGGG G   GGGGGGGG GGGGGGGGG G                  GGG                                      
 GGG      G G  GGGGGGGGGGG GGGGGGGGG                    GGG                                     
         GGGG  GGGGG GGGGGGGGGGGGG  G                   G                                       
         GGGGGGGGGG GGG   GGGGGGGGG GG                   G                                      
        GGGGG GGGGGGGGG     G  G GGGGG                                                          
         GGGG  GGGG G           GG GGG                                                          
         GG GGGGGG G           G   GG                                                           
          G    G  GGG             GG                                                            

And that starts to look like a reasonable map for lwciv. Note that “G” stands for “grassland”. Why I used G escapes me at the moment. It could just as easily stand for “ground” I suppose. Note that due to the text characteristics, the above is stretched vertically so in the actual game, the land masses would be less oblong.

It is clear to me that the results are still less than ideal but at least I have an algorithm that generates reasonable land masses. The next step will be putting some sort of terrain on them.


Leave a Reply

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