Continent Generation 3-Algorithm
This is the third post of N describing the continent generation system I’ve been working on for the last few years.
A recent video from a world created by this algorithm is HERE.
The algorithm is carried out in a few dozen steps, each of which are encapsulated in a zone generation class. Some of the steps are combined or split in the descriptions below. The steps are dependent on previous steps, and all data is passed forward, and the overall algorithm starts by creating a list of zone generation steps, then iterating through them to create the world.
It begins by downloading metadata from the server, and then clearing any old data and setting up the big data grids that will be needed for the generation process.
- The generation begins by creating coarse-grained Perlin noise over the entire continent to give some features that will cross zones. Then, it gives the overall continent a slight “cone” or “pyramid” shape by raising the level of the terrain slightly as it moves from the edges to the center.
- The edges are then sunk below what will be the water line surrounding the continent.
- After that, the zone partitioning begins. The world will have two main numbers: BlockSize (such as 48) and ZoneSize (such as 5) which specifies how big each zone is expected to be.
- It then creates a grid of points in a grid that has ZoneSize granularity (every ZoneSizeUnits place another). These positions are then perturbed.
- Then, the Voronoi diagram for this set of points is calculated. The zones will be the regions in the Voronoi diagram, and the edges become the mountain ranges separating the zones.
- The centers are connected with roads, following a subset of the Delaunay (dual) graph of the Voronoi diagram.
- The roads are created using an extension of Bressenham’s line drawing algorithm that has features such as varying widths, random perturbations that offset from the “correct” path, and also Perlin noise to allow for curvier lines. Some of the data passed into the line generation algorithm looks like this:
- I think this is an important point. Bressenham’s algorithm with randomization and Perlin noise are two things I use over and over to create interesting patterns.
- Roads are created first, because a lot of the other steps in the algorithm have checks that don’t let them happen near roads, or they are mitigated near roads. This leads to roads that are devoid of vegetation, and which aren’t affected by the various terrain modifying code that will happen later.
- Then, the code generates mountains along the Voronoi edgesm, and the ridgelines are marked as the zone boundaries. Some mountain ranges are drawn along the “lines to infinity” in the Voronoi diagram. The mountains use the same line drawing algorithm as the roads use, so they can curve rather than following an exact straight line.
- Zones are then created by starting at each zone center and performing a breadth-first search that adds cells to the zone until they reach the cells marked as mountain ridgelines. Sometimes there are imperfections that cause a zone to bleed out into two Voronoi cells, but it feels like it’s more interesting than annoying so I haven’t chased that down completely.
- The bounds of each zone are then calculated, and will be used later on to generate more detailed features in each zone.
- The edge mountains are then given shape by using some different Perlin noise. Some of them are even made very very short so the transitions between zones happen at ground level. Then these height adjustments are added to the overall heightmap.
- “Locations” are then added to each zone. The center of each zone is created into a Location that will end up being a small village, or in a few cases a larger city. Then, other Locations are randomly placed in the world where there will be roughly one other Location for each two 128x128 blocks in the world. These will be used for smaller camps or questgivers. Locations will be avoided by the tree and grass placement process for the rest of the game. After other heightmap modifications are performed, the locations will be flattened.
- Crevices are added. These are created using Bressenham’s algorithm which creates a fat, meandering line across the zone that then gets sunk into the ground a bit. At intervals, smaller side crevices are added to the main crevice. This is just a detail that I think looks interesting and breaks up basic Perlin noise. I recommend coming up with things like this to have distinct features in worlds that you generate.
- Each terrain then gets “detail heights” added. Each ZoneType has rules for how “bumpy” or “hilly” it is, and those rules are used here to create zones that range from really flat to very bumpy. A few Perlin noises with different paramters are used here. These changes are dampened near roads, but each ZoneType can specify how much roads are affected by this. So, a desert might have rolling hills and really affect the road, while zone with spikier terrain might be set to leave the roads alone.
- Roads are then given a “dip” so that if they exist inside of a flat piece of terrain, they are a bit lower than the terrain so it looks like they’ve been worn down over the years.
- The “Locations” created above are then turned into flattened disks, and then the terrain around them is smoothed so that eventually it merges back with what was there originally (So that the disks don’t lead to vertical drops where the disk stops and the regular terrain begins again.)
- Then, real Unity Terrains are created for the entire world to take advantage of their steepness calculations.
- Bridges are then added along roads. These are created by gouging out the ground, then placing the bridge over the gap. There is a complicated way the code removes the ground to try to make it look interesting each time. This could use more work.
- The terrain is then given another smoothing pass by convolving with a kernel that has exponential dropoff (currently 0.20) proportional to the abs(dx)+abs(dy) of the point from the center within a certain radius (currently 3).
- I do some special smoothing near zone boundaries. Because each zone has its own heightmap code to create its specific shape, this can lead to ugliness at the boundaries. So, as the smoothing code approaches the boundaries, the smoothing kernel turns more into the average of all the cells within radius 3. So, at the actual border of the zone, the new smoothed heightmap is just the average of all cells within radius 3. Of course, I use a second heightmap grid to calculate all of this, then use the new heightmap as the heightmap going forward.
- Once the heightmaps are finalized, other objects and terrain texture blending are added. The bridges were done first because they were dependent upon road heights and other things and they needed to be done before the heightmaps were finalized.
- Grass is added first. Each zone has a set of valid grass types, and a couple are picked for each instantiation. They are then placed using Perlin noise for each type. I limit this to 2 plant types because I am using the Unity terrain code for the final gameplay, and it seems to chug quite a bit. In terrain patches with multiple zones, grass from different zones becomes necessary.
- It then adds rocks and potentially some other things like statues that might get randomly placed throughout the zones. This also uses Perlin noise, but it needs some work.
- Then, trees are added. Zones either use Perlin noise per tree type or they are expected to use uniform placement in areas such a a forest. In either case the code loops over the grid cells within the zone bounds, skipping 3 at a time, I believe. At each cell, the trees are either given a uniform chance of being placed or the chance is pulled from Perlin noise created for that tree type. At each cell, the chances are added up, and one is picked if their chances sum to more than 1. Otherwise, no trees will be placed. Only one tree is picked for each cell.
- Bushes are similar, but they always use Perlin noise, and their noise function has a higher frequency and amplitude to make for more clusters. Every 2 grid cells, bush placement is checked. At the waterline, special bush placement is used to place things like cattails.
- Then, fences are added along roads at intervals. I hope to add more things like lamps for special areas later on.
- Each zone has four texture channels: Base Terrain, Road, Dirt and Steep/Rock. The road areas have Road terrain, and the rest is Base for now.
- Terrain texture blending begins now by adding dirt borders to roads.
- Roads are then dirtied a bit by adding some random dirt patches.
- Now, steep terrains are given Rock or Dirt textures depending on how steep they are.
- The edge mountains are then given another pass where their rules might change to allow for some variation in their appearances. For example, they might use the dirt terrain or the base terrain for the zone in their steep portions, instead of the rock terrain.
- Some other work is done to make the terrain below the level of the ocean a mix of dirt and rock.
- Then, since the game needs to take a picture of the entire continent to create the minimap, all of the textures are loaded into all of the terrain chunks and the alphamaps are set.
- The way I deal with multiple zone types within a single 128x128 grid is by adding a set of textures and alpha splatmap channels per zone type. So for example, if a 128 block had 3 zones in it, and each zone has 4 texture channels, I would make that block have 12 texture channels, and then loop through the grid of cells and set the Base/Road/Dirt/Rock splatmap percentages into either the first, second or third block of 4 numbers depending on whether that grid cell was from the first, second or third zone found within that terrain block. It’s not efficient but I am not a shader programmer so I never figured out how to make this better.
- After all of the terrain textures are set up, an ortho camera is placed far above the continent, and renders into a texture that is then modified by adding blue or white for areas below the waterline and it’s saved out.
- Then the world data is saved out in chunks. The world data contains the zone id (1 byte), height (2 bytes), texture blending (4 bytes) and object at that location (2 bytes) into a file.
At that point the generation is done, and the files could be uploaded to the server so multiple people could see the same world.
Playing in the world requires loading in a bubble of data around the user in such a way that it doesn’t cause too many chugs. Currently this consists of the following:
- A terrain chunk manager that keeps track of what terrain is loaded, and every several frames updates a list of blocks to load and unload. This is based on keeping a “bubble” of loaded terrain blocks around the user. It’s currently 4 blocks out from the player’s position.
- The manager then every several frames will start to load or unload a block. It loads until no more loads are pending, then unloads.
- The loading process reads the bytes in from the proper file, then over several frames sets the heightmap, the textures, the alphamaps, the grass, then it loads in trees and other props and also links the terrain blocks together using the Terrain’s SetNeighbors method.
- This setup isn’t terribly efficient, and it ends up using about 1.5gigs of RAM in the editor once everything is up and running. The trees and other objects are downloaded from asset bundles and cached, and there is a list of objects that removes things slowly as they are no longer needed in the world.
So that’s the idea behind the world generation and then what happens when you play in the world. There’s a lot more work to be done, but I am happy with where this is right now, since I can see how to start layering creatures and quests and so forth on top of this. It will just take time.