A Guide to Procedural World Generation
Generating game content using procedural generation methods is becoming more and more popular as our games become larger and more detailed. To start with lets try to define and understand what procedural generation actually is. Essentially it is the method of creating something by writing an algorithm to create it instead of actually hand-crafting it. This technique is often used in high budget animations because they don't have time to hand design the entire scene all the time. For example they might use an algorithm to determine where each blade of grass is located instead of placing each blade themselves. Now obviously the algorithm used must not be extremely predictable because then it might just place all the grass blades into a predictable pattern and it will look very fake. Basically what we need is a deterministic pseudo-random algorithm.
It needs to be deterministic because it needs to produce the same output every time when given the same input. In a video game we don't want the level to look different each time we load the game, which means the output needs to be deterministic. The input (aka the seed value) is what will really determine the output. So if the player starts a new game the world is generated using a new seed value. Or in the case of No Mans Sky, a seed value determines the layout of galaxies, the solar systems in a galaxy, and the planets in the solar systems. Procedurally generated worlds means we can explore entire worlds that no one has ever seen before, not even the people who created the game. On top of that, it saves a lot of time and energy because artists no longer need to hand craft everything. This may seem like a pipe dream but let me now convince you it's very possible.
Lets begin with terrain generation because that's really the starting point for everything else. The simplest approach to this problem is to simply start with a flat surface and then apply different types of noise to distort the surface until you have something that roughly looks like terrain. If done well this method can produce good results but there are more robust approaches which will produce more realistic results. We can use real models of the way water flows and erodes the land in our algorithms to produce better results. By making use of principles in hydrology and similar fields it's possible to create very realistic terrain, even more so than what artists could make by hand, because they simply don't have time to focus on all the little details, whereas procedural algorithms can recreate those small details if they are based on realistic models.
The following video demonstrates the use of such techniques to create quite a nice looking landscape with rivers running through it. Another important aspect of terrain generation is the terrain texturing. The DirectX 11 Terrain Tutorial Series has some great information on this subject. Since we don't know how the landscape is going to be shaped we cannot apply textures before hand. A simple approach to this problem is to use the slope and height at any given point to determine the type of terrain at that point. For example a point which is very high will be cold so it will probably have snow on it, but if it's on a steep slope then snow may not be able to accumulate and the rock face may be exposed. The slope value has many other uses, especially when calculating soil deposits and deciding where to place vegetation.
Once you have your landscape with your rivers running through it, you can then start to think about vegetation. For example many plants and trees like to grow close to a water source but others might prefer drier conditions, some like to be close to sea level while others prefer higher altitudes, etc. So you can start to create models of where different types of vegetation should occur and you can use those models to underpin the behavior of your procedural generation algorithm. A lot of great terrain generation engine exist and there are even popular video games which make use of advanced terrain generation engines. For example Rust has an extremely impressive terrain generation engine and it only continues to improve with updates.
Procedurally choosing the location of trees and plants is good, but there's a lot more we can do. Have you ever played a game and been annoyed how every single tree looks the same? That is the main problem with hand-crafted vegetation, the artists can only create a limited number of objects due to storage and time constraints. But if we were to model the way trees grow, we could create a procedural algorithm for generating trees which look different every time. The following video demonstrates exactly that. They are even able to simulate different species, so you can have a wide variety of trees all of the same species, meaning they look similar but they have differences like real trees of the same species. To be honest this is probably the most impressive procedural algorithm I've ever seen, it's a shame research like this often fails to be utilized.
Then once we have our terrain with our water and vegetation we can begin to think about the wildlife. Different types of wildlife prefer different types of environments. Certain types of vegetation attract different types of animals. The density and layout of the vegetation also effects where animals live. The altitude, the temperature, all these things and many more can be taken into consideration to create a realistic wildlife model. Humans are also animals when you get down to it and we have certain preferences about where we choose to live. What is more complicated is the structures we build, but even that can be procedurally modeled. Entire cities can be procedurally generated by modeling the way cities are built.
We start by choosing a few points which will be the densest points in our city, then generate a road network which emphasizes a connection between these core points, which is much how real road networks are structured. We can then divide the road layout into different zones: residential, commercial, industrial, etc. That will allow us to decide which types of buildings should go where. If you've played SimCity then you know it's a bad idea having industrial zones right near residential zones, so we try to avoid things like that, but make sure all buildings are close enough to water and power plants, etc. Essentially, the goal is to just keep adding ideas like that to your model until it looks real enough. The following video demonstrates some of these ideas to procedurally generate an entire city (keep in mind this was made back in 2008):
One of the downfalls you may notice about that demo is that the buildings it generates are rather simple and they all look very similar. Just like trees though, it is possible to procedurally generate a wide range of different buildings. You could start by defining some basic building shapes, square, rectangular, triangular, round, oval, etc. You can then get a lot of variation just by changing things like paint style, window style, roof style, number of floors, etc. You can even get tricky and combine different smaller buildings to create larger ones. The following video demonstrates some of these techniques and although it seems to use only square and rectangular shapes, the amount of variation it achieves is still very impressive. There are other interesting videos on procedural building generation if you search for it on YouTube.
If we wanted to go all out we could even fill our procedurally generated buildings with procedurally generated furniture, so that every chair looks a bit different, every table a bit different, every lamp a bit different, etc. How on Earth could furniture be procedurally generated you ask? Well we must take a slightly different approach in this case because you cannot really generate furniture from scratch like other things. The solution is to blend together existing hand-crafted models to create entirely new models which contain aspects from all the models which were blended together. This can provide a huge amount of variation with only a few models but on rare occasions is could produce unrealistic objects. If all this sounds too complicated, even simple tricks like having a few different textures for the same mesh can be quite effective.
Having said all that, many video games would still need to have their own hand-crafted buildings, which is totally fine. The beauty of procedurally generated worlds is that you can tweak them after they have been generated. If something looks a bit funny you can adjust it to your liking. Of course this means the game would have to use a single seed value which never changes so adjusting stuff by hand does have that downside. You could have hand-designed buildings with procedurally chosen locations, that is definitely a good option if you don't need every building to look different. However it's still a good idea to create large buildings out of smaller buildings or even more basic building components because it can reduce memory usage substantially while still providing a great deal of variation.
Another related problem is how to procedurally generate animals and other creatures. The best way to approach this problem is to view it as modular character creation but for animals instead of people. The same sort of concept can also be extended to other things like the generation of trees and plants. Using the same basic components, then changing their color or shape, and then connecting them together in different ways can provide a huge amount of variation. This is the approach taken by No Mans Sky for the generation of animals and vegetation on planets. Keep in mind this is not the same approach as modeling the way trees grow, every tree of the same species on a planet will look the same, but different planets will have different trees. The following lecture by an artist on the NMS team explains in more detail how they went about it.
A key thing to remember when designing a procedurally generated world is that you want things to load only as they are required, for example you don't want some distant planet to be generated if the player is no where near it. This way this can be solved is by using an infinite "layer-based" approach which loads a high level of detail in the environment close to the player and less detail the further away from the player/camera. The different levels of detail are layered on top of each other so that when a "cell" in the grid gets closer to the player more detail can be layered on top of it. This solution means that the game world can be virtually infinite in size because you will always find new stuff if you keep moving in the same direction. The following video describes the layer-based procedural algorithm in more detail:
Another thing to keep in mind is that once we have a well designed procedural world engine, it then becomes possible to create a truly awesome procedural universe engine. Every planet you visit can be truly unique because they would all be procedurally generated using different parameters and different seed values. The universe its self would be procedurally generated so it could be virtually infinite in every direction, meaning it would be impossible for one person to explore every planet. Games such as No Mans Sky have already attempted this and they made a really good effort considering the size of their development team, but there's clearly a lot of untapped potential with these types of games. Developers will learn from the model variation techniques used by No Mans Sky and our future games will build upon those concepts and refine them.
Imagine how much easier it would be for indie game developers to create awesome games if they had tools which could automatically generate a game world for them according to their specification. They would have far more time to focus on game mechanics and other important things which often don't get enough attention. Obviously this approach will not work for many types of games, but even games that don't require procedural generation can still benefit from basic variation techniques and modularity principles. There are some issues such as long loading screens while you wait for the world to be generated, but the size of the game will be very small when most of the content is procedurally generated. One guy generated an entire 3D city with animations and all of that was contained in a 180KB file. That is smaller than a single texture from a modern game.
Advertisements
