Procedural World Generation

 

My biggest role on my most recent game project - 'Greatest City' - was setting up a system of procedural generation for the world.  It needed to be infinitely scalable, easily saved and loaded, and able to generate new area at runtime.  This is, of course, in addition to being interesting, well laid-out, and ultimately visually appealing.  The timeframe for this game was only one semester, so the system had to be concise and a lion's share of attention had to be paid to optimization, but I'm confident that this system is easily expandable should the game continue on

Mapping

The terrain generation system is broken up into tiles, with each tile having its own heightmap, splatmap, and densitymaps.  All of these tiles need to, of course, tile, and they all need to be procedurally generated with multiple different controls available to edit them.

 

The goal of this project was always to get an interesting world that users can remember and navigate around.  To do that, the game needed to have defined biomes - things that the player can easily see, identify, and recollect in order to keep their bearings.  The game takes place in a wooded area, so our 3 primary biomes are grasslands, forests, and lakes.  The system only has three right now, but if we get the chance to continue developing, we plan to have different tiles that each contain new biomes, like deserts, mountains, and tundra.

A lion's share of the terrain gen is happening in Substance Designer, where the actual maps are created.  An initial heightmap is created from some basic noise, and then the biomes are derived from that and placed on top of it.  The grasslands blur the area where they are to give flatter areas, whereas the lake subtracts from the heightmap to form a deep pit.  

The four outputs from this graph are the heightmap, the splatmap, the image for the mini-map (that was easy enough to build alongside the rest of the terrain), and the density maps.  There are four density maps; trees, rocks, grass-patches, and buildings.  It was pretty convenient to encode these into the different RGBA channels to save on texture memory.  These maps just tell objects where they can and can't be, with a value of 1 being abundant with that object and 0 being devoid.  

Each biome also generates its own noise for its splatmap, and four textures are used; red is mud, blue is leafy grass, green is sand, and black is regular grass.  For the current number of biomes, these are all the textures we really need, though we could easily create another splatmap and blend between the two using the unused alpha channel on the splatmap.  

These graphics show each of the channels as the seed is randomized.  None of the parameters are being edited here, which is why the lake is largely staying in one place.

 

Asset Placement

Asset placement consists of three steps; randomizing the substance, generating the ground, and then placing the environment pieces on the surface of the ground.  

The first step is pretty simple - we just take an instance of our heightmapping material, pass it a random seed, and then iterate through all of its exposed parameters, randomizing them with a predetermined range.  These alter things such as the lake's size, shape, and location, as well as the size of grasslands and the falloff between biomes.  Once the substance has been rebuilt, the ground is generated.

The ground mesh is just a simple 100x100 grid.  This process iterates through all of those verts, samples the heightmap at a position relative to the vertex' position, and then raises that vertex by that amount.  At runtime, the ground is rotated to make sure that generation starts closer to the player and then works its way outwards.  After this is all done, the mesh collider for the ground is updated, normals are recalculated, and the environment spawning is initiated.

The final step iterates through an array of an environment spawner class that places a specific number of assets on the ground's surface, then move on to the next spawner in the list.  Each asset is run through three tests to make sure that it can exist in the spot where it is randomly placed.

The first is a proximity test, where it verifies to make sure that it isn't too close to any asset of the same type.  if it is, it fails, and the spawner function recurs.  The second is a density test, which exists to make sure that objects are being placed according to their density map.  This function generates a random number between 0 and 1 and then samples the density map in the spot where the object is being placed.  if the sampled value is less than the number generated, the test fails and the function recurs.  The final test is the surface-normal test, and it doesn't run for all objects.  This just makes sure that the surface normals are facing roughly straight-up.  If they aren't, the test fails and the function recurs.  This function runs for things like grass patches, trees, and buildings that can't really exist if the ground is too uneven.

Objects like resources and buildings are spawned last, and they run a function to delete any objects within a certain radius of them to create a nice clearing and to make sure that important pathways aren't blocked by trees and rocks.

 

Generation

The procedural generation system supports building at runtime and at the start of gameplay.  It also supports generating new terrain as well as saving/loading old terrain.  With the different permutations of these, that means there are four different types of generation functions for every piece of the system; loading at runtime, loading at compile-time, generating at runtime, and generating at compile-time.

Because of the impact that the world has on gameplay (and the sheer amount of times that the generation function is being run), we had to work crazy hard to optimize all of the runtime functions.  Almost everything in the system happens in a coroutine, with the number of operations per frame to be determined by the quality settings.  The ground generation only messes with a few verts each frame, and then starts the environment spawning when it's all done.  The environment spawning also only handles a few assets at a time.  This system generally works very well, but there are still some operations that just inherently take some time, such as rebuilding the substance (this really depends on the texture resolution of the substance material), rebuilding the mesh collider for the ground, and recalculting the normals/tangents for the mesh.  Fortunately, loading during runtime is much faster and cleaner than generating from scratch, since all of the previously mentioned tests that need to be run simply don't happen, the save file is just read and assets are placed exactly where they belong according to that.

 

Saving/Loading

One of the system programmers on my team wrote up a great saving/loading system that I implemented for the world generation.  Every time a tile is generated from scratch, it writes the data, and whenever a load-file already exists, it reads it back.  

Saving ground generation was simple.  The vertices in the mesh only ever have vertical movement, so I just saved the y position of all the vertices, and this value is applied to the ground tiles whenever they are loaded.  This conveniently eliminates the need to rebuild substance files or sample textures in any way.  

The environment spawning is a little bit more complicated, in that I have to save a transform as well as a type.  Luckily, because of the order that everything is being saved and written in, the code can differentiate between rocks and trees, but it needs to have an additional type integer that tells it exactly which tree exists at that spot.  

The buildings were similarly difficult, but also had a lot of other variables associated with them, such as who their occupant was, whether their occupant still lived there, whether the building had been discovered yet, etc.  Fortunately, these tasks are easy when you have good tools.

Speaking of tools, I wrote up a pretty simple "Save Manager" tool to help members of the project delete any save files that they had without having to navigate to the directory where they were being saved.  This is important because if, at any time during development, the number of a certain asset is changed or new objects are introduced into the system, old save files become unusable and begin to throw errors while reading back.  Being able to click a button and delete any save files that are causing problems is handy for members of the team that aren't totally familiar with how the save manager works.

 

Reallocation

One obvious problem with having vast game worlds is the strain that tracking all of that data puts on the CPU.  So, we implemented a system to destroy old tiles as you get too far away from them.  Because all of the data is saved after a tile is created, we can safely do this knowing that the tiles can be rebuilt exactly as they were.

Each tile has 8 reference points on it (one for each corner) that track the player's distance from them.  If the player gets close enough, the reference spawns a tile opposite the player and then turns itself off (assuming no tile has already been created there).  This prevents the per-frame operations from stacking exponentially and still generates the terrain intelligently. 

 

A terrain-manager class tracks the player's position periodically and also keeps track of all the tiles that have been created.  It then calculates the distance from the tile the player is on and each tile in the list.  If the tiles are a certain distance apart, the tile is destroyed.  All of the references for each tile are then turned on again, just to make sure that the tile can be rebuilt if the player gets close enough.  

 

Shading

Although it's not technically a part of the procedural generation, shaders played a big part in making sure that the environment really came to life.  The splatmapped ground was one of the most important of these, because without it, the environment would have looked painfully monotonous.

It has 4 diffferent textures that can be used, which we are using for mud, grass, leafy-grass, and sand.  Each texture has a diffuse, normal-map, metallic-roughness map, and a height-map used for parallax.  It also supports distance-blending which works really nicely since the tree cover usually prevents the player from seeing any tiling off in the distance.  

The environment also includes a custom water shader, the procedural skybox that I built (more on that here), vegetation shaders for motion/sub-surface-scattering for the trees and leaves, and the standard shader that I made for all of the other environment assets.  The standard shader excludes any roughness/specularity in the attempt to make things cartoonish without being cell-shaded.  I also built in some fake ambient occlusion, since light-mapping is not an option for a procedurally generated game.  It just grabs the normal direction of the object and darkens any faces that are pointing down.  This works great on rocks and trees, but for more complex, geometric shapes like buildings it can be toggled off.  

 

We also opted to go for what a lot of stylized games are going for these days (namely Legend of Zelda: Breath of the Wild and The Last Guardian) and decided to use cell-shaded characters to make them pop more from the background.  The character actually consists of three different shaders - a cell-shader for his clothing, a cell-shader with simulated SSS for his skin, and a more complex hair shader.  

 

This system is a pretty simplified version of what a lot of AAA games are doing, but considering that it was the work of one technical artist over the course of 12 weeks, I'm pretty happy with where its at.  The systems are cleanly built, fully functional, and quite expandable.  Hopefully, I will get the chance to work on 'Greatest City' more in the future, and there are a lot of things I would love to do to make the world generation system even better.

© 2017 by Evan Edwards

  • LinkedIn Social Icon
  • Twitter Classic
  • Facebook Classic