Continent Generation and Detection for Computer Generated Worlds

Recently[1,2,3] I've been experimenting with algorithms to create random landmasses. Once I'm given this random land I want to run some functions on it that will give me extra data.

I want to know:

• How many landmasses are there (those areas of land bordered by sea)?


• Which tiles make up these landmasses?

World Generation Output

X  = Earth
O = Water

OOOOOXXXOOOO
XXXOOOOXOOOO
OOXXXOOOOOOO
OOOOOOXXXOOO
OOOOOOXXXOOO
OOOOOOXXXOOO

In the above I would say there are 2 landmasses. Because the landmass at the bottom and top wraps around (I don't want my world to be flat, if not round I want it to be at least donut shaped). I had some trouble imagining an algorithm that would go through this and give me a Continent Array, each array entry containing a reference to those tiles in each continent. So for the above the output would be.

ContinentArray.Count = 1

ContinentArray[0] = [0,1],[1,1],[2,1][2,2][3,2][4,2]
ContinentArray[1] = lots of tiles

This is the kind of problem that must be handled by Adobe Photoshop when you use the magic wand tool. Anyway the solution I came up with was to use a recursive algorithm. It's probably a reinvention but I called it the "Explorer Algorithm".

The Explorer Algorithm

I'll write this in some C# flavoured psuedo code.

Explore(ref array AContinent, int x, int y)
{
   if(map[x,y] == Water)
   return;

   //It's an earth tile in our continent so let's add it
   AContinent.Add(map[x,y]);

   // now we set it to water so we don't add it again
   map[x,y] <- Water;     
   //Explore surrounding tiles     
   Explore(AContinent, x, North(y));     
   Explore(AContinent, x, South(y));     
   Explore(AContinent, East(x), y);       
   Explore(AContinent, West(x), y);    

   //Also explore diagonal tiles - depends on   
   //what you define landmass as I guess

   Explore(AContinent, West(x), North(y));
   Explore(AContinent, West(y), South(y));
   Explore(AContinent, East(x), North(y));
   Explore(AContinent, East(x), South(y));      
   
    //*
 
} 

* I think I might be able to return the tile to Earth here without problem but I haven't checked so I don't know.

The minor problem with this is that it sets your continents to water. But you merely iterate through your new continent array and set all the tiles back to Earth and eveything it fine.

So to use the explorer algorithm you would do the following:

forall the tile [x,y]  in map
{
   Array c = new Array;
   Explore[c, x,y]

   if(c != null)
       BigContinentList.Add(c)
}

Then you would take every continent in the big continent list and iterate through it's tiles setting them to Earth.



So I expanded my earlier program and it now can count the continents and allow me to cycle through the highlighting each one. As you can see the 10th continent is currently highlighted.

This Weekend's Code

Well I did the above. Then I fixed up my game code so it doesn't crash and does streaming a lot more efficently. Then I made the fullscreen switch work pleasently. When switching from fullscreen to a window the window looks nice and actually has it's frame and all the window stuff one would expect. Then I kind of ran out of steam but what I should have done was if the resolution is higher then show more of the map but that's a lot of work! In fact I've been avoiding it but it's something I need to get done so I can get on with the GUI.