World Generation

Okay this post, let's think ahead a bit. World generation!

I went around to various places that have world generation code and have determined the ultimate algorithm for Cultura. So ultimate, it might get changed in the future as I discover other ways of world generation.

We start with outlining the steps of my world generation. To the user, during the loading screen, it may say things like reticulating splines or recalcumalating solar flux but behind the scenes the actual rough steps would be something like:

• Generate a random set of points based on a seed
• Soften random nature of points through Lloyd's algorithm to get a more uniform distribution
• Use Perlin noise to generate a height map for the different points
• Select continent locations and then artificially bump up height in those areas
• Mark everything below a particular height threshold as ocean
• Mark everything above a particular height threshold as mountain. (Probably do it in the same loop as the step above)
• Form rivers. Likely run them from the ocean coastline inland, moving along increasing height.
• Rainfall and temperature gradient. Temperature increases as you move southward, the north is the arctic. Rainfall is more complicated but I may do a east to west calculation and have mountains "block" rainfall.
• Biome selection per region.
• For each type of resource (grass, bush, tree, animal, metal, stone etc) select a subset of points as super points. Each super region has a mutually exclusive selection of a specific version of the resource.
• Figure out which region each tile is in
• Spawn resources, animals into each region
• Spawn starting factions into starting location regions

It's quite a list! And each one is a lot of work to implement. I won't be doing this until basically all the RTS features are good to go because it's both a heck of a lot to do and test (and a lot of small tweaking to get nice looking maps) but I really need everything else to be functioning to really try it out. That is, I need to be able to claim ownership of regions, abandon areas, build structures, harvest goods, store stuff, build units, fight enemies, hunt animals and so on. So this is just purely thinking ahead for now.

In order to generate a random set of points I'm not going to choose anything far more complicated than the c++ provided rand function. It allows me to use a seed which guarantees the same set of points. However, once I have a random set of points there is likely to be significant clustering. So I'd use Lloyd's algorithm to get a more uniform distribution which is more expected from a game perspective. Overly random leads to games with players are clear and significant disadvantages.

This creates a nice polygonal map for us to use as the basis on which we make all decisions in how the terrain looks in the end. We assign each point a height via some calculation using Perlin noise. But we want continents not a random spray of land. Why? Well my game is heavily dependent on the concept of diplomacy and trade and I think it heavily restricting should there be no oceans to create ocean-going trade (a mainstay of mercantile Europe for instance). Also I think ship-going trade is cool. So after Perlin noise gets us a random height assigned to each point, I wanted to select a subset of points (we could run our rand again and then pick existing points closest to those points). Those ones cause points around them to increase height by a set offset (say points below a certain distance and it probably shouldn't be cumulative, you can only apply the offset once). Then we apply the water/mountain threshold. We should be left with continents.

Next, we can easily assign a temperature to points. Based on it's northerly location, it gets colder. There's only a northern arctic in this game (which more or less reflects Eurasia versus the Americas). Then we assign rainfall. My idea for now is to have rain come in from the east and move westward, increasing with water underneath, dropping over land (increasing the rainfall of those squares), dropping more quickly as you move up in elevation, dropping more slowly as you move down elevation. But given that at this point, all you have is the list of points, it might be a tad hard to figure out how rainfall shifts as you move westward so it might be significantly simplified.

The temperature and rainfall determines biome (affecting the look of the region) and shifts the weighting of the random choice of plants, animals and resources that might occur in it. For each resource type we repeat the steps:

• Generate a subset of random points and relax them to be more uniformly distributed.
• Form super regions (points belong to the closest super point)
• Select one type of the resource per region. No repeats. (This implies that the number of super regions is equal to the number of types possible)
• Adjust resource information per point

This will create varying super regions of each resource, and then as you apply other categories there can be different overlaps allow areas which had zebras to have different vegetation and not the same combo throughout. We can also do less super regions and do the same calculation twice per resource type (such as animal) in order to have two different animals per point.

Now we get to the slow part. The points are meant to create a polygonal map via a Voronoi diagram. Then each tile needs to figure out to which Voronoi region it is in. Then we create region objects that understand what tiles it owns. For each region object it is associated with a single point and the point has the information regarding biome and resources. Thus now we are drawing out the terrain which will be saved in the TerrainManager object. Inside the TerrainManager object we have the super efficient storage of giant ass integer arrays.

Each tile gets set to a particular terrain. Then we run through each region object and populate it with a set number of grass nodes, bush nodes, tree nodes, resource nodes and animal herds. We may additionally set migration routes for each animal herd.

Bam! Now you have a procedurally generated world.

Okay so I've left the description on how to figure out which point (therefore which Voronoi region) a tile belongs to because it's a bit wordy. I'm concentrating on speed so I'm going to take a super dump on memory complexity. What we'll do is pathfind outward from each point to each tile, marking tiles based on the lowest distance to each point and truncating the pathfinding tree where we meet areas that are already marked and we are not closer. This process will self-terminate once all nodes are marked and best-path is found from each tile to each point.

for int i to number_of_points
    create pathFindTree
    add to array
end loop

bool hasUnmarkedTiles = true

while (hasUnmarkedTiles)
    for int i to number of pathFindTrees
     do one level of pathfind
    end loop
end loop

//pathfinding function
PathFindTree
{
    Node root
    Queue nodes
    int distance
    int pointIndex

    pathFindOneLevel
    {
     Queue newNodes
     node = nodes.popFront()
     while (node is not null)
     {
      //if the distance isn't better, we should terminate this branch
      if (distance < lowestDistance[x][y])
      {
       lowestDistance[x][y] = distance
       mark tile with pointIndex
       addChildren to queue
      }
     }

     distance++
     nodes = newNodes
    }
}

We'll just assume that I didn't make mistakes there. This gives us a linear time calculation for what each tile should be like. Then we can run through all tiles, set their terrain type and then also build the region objects. Then we run through each region object to populate resources and animals. Then finally we pick starting points for each faction and spawn their units.