Date: 1997-03-31
From: Paul
Subject: RE: Tape & Alexander

I had a minor sinking feeling when I first saw your message and realized I wasn't sure how to consolidate countries into continents. Then I thought "Hah! Here's a good use for a stack. I'll just go methodically around the world, and whenever I find a land cell without a parent continent I'll assign it to a new continent and push its land neighbors onto the stack for subsequent assignment." Just like the initial land growth phase, only a little different. For one thing, there's no need for the random element - so a stack should work fine. But when I started the coding, I realized there's a simpler solution yet - recursion.

Here's the modified algorithm:

Walk the entire array of cells. Each time you find a land cell that isn't assigned a continent, bump up the continent count and assign that cell. Also check its eight nearest neighbors. Any that are land are guaranteed to be continent-unassigned, so assign them to the continent just identified, and call the eight-nearest-neighbors-check routine recursively on each of the land neighbors in turn.

Note: the algorithm happens in a pass after all land generation has occurred. The former "continent" identification is now renamed "country," and is otherwise unchanged.

OK, I know this algorithm is doubly inefficient:

  1. Recursion overhead.
  2. Most land cells will be visited multiple times. Once, guaranteed, walking the entire array of cells in the outer loop. One or more additional times as neighbors of other land cells.
The good news is that empirically this doesn't matter. On a 200 x 200 world, the additional wall-clock time is undetectable on my Pentium Pro.

Here are the first two 75 x 75 worlds with continent assignments.

It looks like I have the land probability factor set a little high for ordinary worlds, but the results are pretty interesting nonetheless.

We did have mountains implemented at one point. All sparks were considered mountains, and I think there was a special "mountain probability" variable that decided if more mountains were generated, possibly much as you broadly outline below. I don't remember the details any more.

I was considering implementing your suggestion of recent weeks to use country boundaries to identify streams. Now, though, I wonder if we shouldn't use the boundaries for roads or ridge tops or something else. Most of your proposed enhancements (rivers, river widths, elevations) will be kind of tough for me to deal with until I improve the resolution and actually display world maps. Of course this will likely cut you out of the loop unless you get a PC, or I figure out how to generate .bmp files. Maybe it's time to worry about cities now. Any thoughts on how we should place them? And what else can we focus on before I need to worry about actual display code?