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 GGGGGGGGGGGGGGGGGGGGGGGG GG GGGGGGGGGGGGGGGGGGGGG GGG GGGGGGGGGGGGGGGGGGGG G GGGGGGGGGGGGGGGGGGGGGGGGGG G GGGGGGGGGGGGGGGGGG GGGGGGGGGG GGGGGGGGGGGGGGGGGGGGGGGGGGGG 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 GGGGGGGGGGGG GG G G GGGGGGGGGG G GGG GG GGGGGGGGGGG GG GGG GGG G GGGGGGGGGGGGG GG G GGGGGG G GGG G GGGGGGGGGGGGGGGGGG GG GGG GGG GGGGG GGG GG GGG G GGG GGGGGGGGGGGGGGGGGGGGGGGGGGGGG GG GG GGGGG GGGGGG GGGG G GGGGGGGGGGGGGGGGGGGGGGGG G G GG GGGGGGGGGGGGG GGGG GGG GGGGGGGGGGGGGGGGGGGGGGGG GGG GGGGGGGGGGGGGGGGGGGGGGG GG GGGGGGGGGGGGGGGGGGGGGGGGG GG GGGGG GGGGGGGGGG GGGGGGGG GGGGGGGGGGGGGGGGGGGGGGGGG GGGGGGGG GGGGGGGGGGGGGGGGGGG G GGGGGGGGGGGGGGG GGGGG G G GGGGGGGG GGGGGGG GGGGGGGGGGGG GGGGGGGGGGGGGGGGGGGGGG GG G GGGGGGGGGGGGGGGGGGGGG G G G GGGGGGGGGGGGGGGGGGGG GGGGGGGGGGGGGGGGGGGGGGGGGGGG GGGGGGGGGGGGGGGGGGGGGGGGG GGGGGGGGGGGGGGGGGGGGGG GG G GGGGGGGGGGGGGGGGGGGGGG GG G GGGGGGGGGGGGGGGGGGG GG GGGGGGGGGGGGGGGGGGGGGGGGGGG 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 G
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.