Anyone who has delved into procedural generation, or procgen, for land creation knows there are a variety of methods and algorithms out there to accomplish the task. Each of these algorithms have their own strengths and weaknesses, which may or may not be acceptable to any given developer for any given project. Allow me a moment to outline a few of the more common methods of land generation.
Polygonal Map Generation
Most land generation algorithms revolve around some type of procedural generation technique designed to create lands made up of polygons. Polygons in 3D graphics are the same thing you remember from basic geometry class: three or more points connected by lines to form a shape, only for 3D graphics those points exist in three dimensions instead of the flat 2D surface you learned in geometry. The most basic and commonly used of these shapes is the triangle.
Most polygonal procedural generators follow four basic steps: 1) Create a series of elevations, 2) create points in space based off those elevations, 3) connect points to form polygons and 4) set the land to be displayed (biome) for each polygon based on the elevation. The two most often used methods to start this process are noise generated height mapping and two-dimensional array mapping. Both are almost identical in nature, the difference being how the elevation data is thought of by the programmer (an image vs an array). Nearly all polygon procedural land generators have the advantage of running very fast but the disadvantage of a lack of vertical (or obtuse) land faces. Additionally, modern graphics cards are designed to display polygons, making rendering very fast as well.
Noise Height Maps
As the name implies, this method uses one of a variety of algorithms to create a set of elevations based off pseudo-random noise. A few of the more often used noise generation algorithms are the Perlin, Simplex and Wavelet functions. A quick search of the Internet will produce plenty of tutorials for those interested. There is a good scholarly article by Lagae et al entitled “A Survey of Procedural Noise Functions” which outlines many of these methods.
In a nutshell, a noise function is used to effectively create a grayscale image. The color value of each pixel of the image corresponds to a specified elevation, for instance a noise value of 0.0 (black) might be -100.0m while a value of 1.0 (white) equates to 100.0m as given in the equation below.
elevation = (noise – 0.5) * 20.0
Not a very large min/max of elevations, but you get the picture.
The primary advantage of using noise height maps for land generation is the speed at which these functions operate. Any of the height map methods are fast enough to create lands in near real-time to be displayed one area after the next seamlessly. The disadvantages are a lack of granular control over how the land is formed and reliance on the elevation to create the biomes.
2D Array Maps
Array mapping is like noise height maps in that an X by Y grid is filled with pseudo random elevations (a height map is just an X by Y grid as well). The difference comes from the structure, whereas a height map is generally thought of as a grid of values ranging from 0.0 to 1.0, an array map can consist of anything the programmer desires. Utilizing class objects or structures as the base type for the 2D array allows the savvy programmer a bit more granular control over the land, but comes at the cost of a slight decrease in speed and increase in memory requirements.
The Omega Connection land generation engine began with a 2D array map, except instead of creating an elevation first, a biome is chosen for each grid. Each biome has a minimum and maximum elevation change assigned. These two distinctions allow for an averaging of both the surrounding land biomes and elevations to be used during computation. With this combination, we could generate steep rock faces that plateau to a smoother rolling desert. While slower in generation than a noise function, creation time remained fast enough to display the land in near real-time seamlessly.
As previously mentioned, one of the disadvantages for nearly all polygonal procedural generators is the lack of vertical or obtuse land faces. This disadvantage also includes the creation of caves and other underground passageways as part of the standard procedures. The creation of each polygon is a matter of the computer playing connect the dots from one elevation grid to the next, meaning that to go from an elevation of 50.0m up to 150.0m creates a slope which can neither be truly vertical nor create an overhang or cavern. Enter voxels.
Voxel Map Generation
Thanks in part to the success of Minecraft, procedural generation of voxel lands has gained in interest among the game development community and computer science scholars. Also thanks to Minecraft, most people think of voxels as cubes stacked up or floating in space. This, unfortunately, is not a good representation of what a voxel is.
A more accurate depiction of voxels is a 3D collection of points. If you think of a computer image as a 2D collection of points (because that is what it is), then a voxel is a collection of computer images stacked one on top of the other. Just as a single pixel in an image corresponds to some color, a single pixel of a voxel corresponds to SOMETHING. What that something is is entirely up to the developer, but usually represents a specific biome for land generation purposes.
Where do the cubes come into play? From one of the biggest disadvantages of voxels: the memory requirements. An example will help make sense of this all. If we were to create a noise height map for a land that is 100m X 100m in size and an elevation range from 0.0m to 100.0m using standard 32bit floats to store the elevation numbers, excluding overhead, it would require 320,000 bits of data. This gives us 100,000 points that we play connect the dots with to form polygons which the graphics card displays at varying resolutions by automatically filling in the surface of every polygon. Not too bad for memory size.
Now take the example of a voxel. At first glance you might think the total memory requirements for the same size grid would be 100 X 100 X 100 X 32bits = 32,000,000 bits, but you would be wrong. Remember, a voxel is only a single point, or pixel, and a graphics card will not fill in the gaps between each point like it does for polygons.
For the sake of simplicity, let’s say your computer monitor only had a resolution of 100 X 100 pixels and the closest you could get to a surface in your video game was to display a square meter of landscape on screen. Each square meter of surface would have to consist of 10,000 points, but that is only a single 2D surface and voxels are collections of 3D points. This means that a cubic meter would consist of 1,000,000 points with a total memory requirement for our voxel map of 32,000,000,000,000 bits of data. That’s 100,000,000 (100 MILLION) times the memory requirements of our polygon noise map!
To combat this huge memory overhead, most voxel maps use a 1m (or similar) polygonal cube to represent a single point of a voxel. This reduces the memory requirement back down to our original guess of 32,000,000 bits, or 100 times that of our noise map example. And thus, we have people thinking of voxels as stacked cubes.
The second disadvantage of procedural generation of voxel maps should be obvious by now: speed. Each of those points in space require some sort of computational time to create and there are 100 times more points in our comparison example. While it might not take 100X longer to generate these points, it is certainly much slower than polygonal generation.
Although there have been some advances through academic and real-world research to not only speed up voxel creation but also to compress the data requirements down significantly, the data size gap remains an issue with pure voxel map generation. The stacked cube solution currently remains one of the most widely used approaches with a major focus turning towards updating the marching cubes algorithm commonly used to generate smoother voxel surfaces. I won’t get into detail on this algorithm as there are plenty of resources available online. I will, however, suggest a read of Eric Lengyel’s dissertation “Voxel-Based Terrain for Real-Time Virtual Simulations” as it provides a good foundation that developers can use for rendering voxel maps.
The disadvantages out of the way, let’s look at some of the advantages of using voxel lands. The first of these I harp on all the time, vertical walls and overhangs. Included in here is also the creation of caverns and underground tunnels, but more on that in a moment. The second advantage is going to seem a bit counterintuitive because it is speed.
The creation of a surface map using voxels will always be slower than any of the polygonal methods. It is just a matter of data quantities and cannot be changed. The speed of voxels comes from creating multilayered 3D surfaces and in these instances, can be much faster to compute and generally faster to render. Allow me to explain with a couple examples.
In your videogame world, you have decided to include dry river beds as part of the land terrain. Using a polygonal map, you would generate your rivers using some path finding algorithm, recreate the polygon mesh where the river runs and then remove the river leaving only the new mesh. Easy enough, except a dry river bed looks differently than the land it is replacing. It is effectively a different biome and thus that new polygonal mesh must be set accordingly.
A second and much more pronounced example comes from caves. There is no way to create any underground artifice using a standard procgen polygonal map. You might be displaying three dimensions on screen, but the reality is your map is stored in a 2D grid of some type (image or array). To compensate for this a separate map must be created for each cave with the entrance polygons shifted around to look correct and marked with a different biome. During actual game play this cave must then be loaded separately from your main land and it takes some major computational effort to match up the polygons for your land with the polygons for the first few steps inside the cave (many videogames just load the cave once you “enter” it and unload the main land to avoid these computations).
The world of voxel maps is much more efficient for these “erosion type” actions. You just remove the points you do not need. Want a dry river bed? Remove all the points X deep along your path finding algorithm; the points representing the new land biome are already there waiting underneath. Want a cave? Just start stripping points out of a rock wall and never have to load the cave separately again.
While the basic voxel land creation functions remaining slower, these types of advanced land generation procedures are much faster using a voxel map. If you are like me, the problem is you want your cake and to eat it too. This is where Poly-Voxels come into play.
Poly-Voxels
Now that you have a basic understanding of the ins-and-outs of polygonal and voxel procedural land generation, poly-voxel generation is relatively easy. It is a hybrid of the two styles developed for the Omega Connection land engine that combines the best of both worlds into one relatively uncomplicated system. At the most basic level, Poly-Voxel generation simply bounces back and forth between polygonal and voxel.
In the first stage, a small polygonal land array is generated. The map starts very small in design with the biome set first before the elevation to achieve the aforementioned deserts atop rock walls effect. This small map is then scaled progressively upward to a medium map using algorithms akin to a standard image bicubic resampling algorithm. The reason for the scaling is simple, creating a small polygon map is incredibly fast, as is a scaling algorithm, and when combined produce a larger map with “clumps” of biome together. The algorithms required to produce a larger map with the same level of biome consistency uses far more processor time, only to produce the same effect.
Starting Map – 20px X 20px |
First Up-Scaled Map – 100px X 100px |
Pre-Voxel Up-Scaled Map – 400px X 400px |
The second stage converts the land array into a 3D voxel array using the minimum and maximum elevations as the baseline for the third dimension. Utilizing the voxel map, rivers and caves are carved out of the land with the biome automatically set accordingly just by removing the required points. You can even use the existing polygon map for the river pathfinding algorithms and remove the corresponding points from the voxel.
The last stage consists of two components occurring simultaneously. A small section of the voxel is extracted and scaled upward to the final map scale using a pseudo smoothing algorithm. The sectional break down allows grids of map to be saved in smallish chunks (100m X 100m) for faster save and load times. During the scaling process, each voxel surface that is exposed to air (or water) is converted back to a polygonal surface map and recorded (saved or passed to OC Game itself) leaving only the outer shell of the voxel as a series of points for a polygon mesh. Caves and vertical walls intact.
Utilizing the hybrid method of Poly-Voxels, the Omega Connection land generation engine can create a 2000m X 2000m map using a single thread in an average of five (5) seconds. To be completely fair, a little over half the land generation time is devoted to the erosion method Omega Connection uses to create water bodies and caverns. The five seconds may seem a little high, but if you compare to the continuous land generation typically seen in procgen examples where a grid of 100 X 100 is constantly being generated as the camera flies over the land, we are effectively creating one such grid every 0.0125 seconds. Fast with the icing and decorations intact and ready to be eaten. That’s how I like my cake.