How infinite terrain can be implemented in Leadwerks Engine 5

Entry posted by Josh · December 5, 2017

9,682 views

Gamers have always been fascinated with the idea of endless areas to roam. It seems we are always artificially constrained within a small area to play in, and the possibility of an entire world outside those bounds is tantalizing. The game FUEL captured this idea by presenting the player with an enormous world that took hours to drive across:

In the past, I always implemented terrain with one big heightmap texture, which had a fixed size like 1024x1024, 2048x2048, etc. However, our vegetation system, featured in the book Game Engine Gems 3, required a different approach. There was far too many instances of grass, trees, and rocks to store them all in memory, and I wanted to do something really radical. The solution was to create an algorithm that could instantly calculate all the vegetation instances in a given area. The algorithm would always produce the same result, but the actual data would never be saved, it was just retrieved in the area where you needed it, when you needed it. So with a few modifications, our vegetation system is already set up to generate infinite instances far into the distance.

However, terrain is problematic. Just because an area is too far away to see doesn't mean it should stop existing. If we don't store the terrain in memory then how do we prevent far away objects from falling into the ground? I don't like the idea of disabling far away physics because it makes things very complex for the end user. There are definitely some tricks we can add like not updating far away AI agents, but I want everything to just work by default, to the best of my ability.

It was during the development of the vegetation system that I realized the MISSING PIECE to this puzzle. The secret is in the way collision works with vegetation. When any object moves all the collidable vegetation instances around it are retrieved and collision is performed on this fetched data. We can do the exact same thing with terrain Imagine a log rolling across the terrain. We could use an algorithm to generate all the triangles it potentially could collide with, like in the image below.

You can probably imagine how it would be easy to lay out an infinite grid of flat squares around the player, wherever he is standing in the world.

What if we only save heightmap data for the squares the user modifies in the editor? They can't possibly modify the entire universe, so let's just save their changes and make the default terrain flat. It won't be very interesting, but it will work, right?

What if instead of being flat by default, there was a function we had that would procedurally calculate the terrain height at any point? The input would be the XZ position in the world and the output would be a heightmap value.

If we used this, then we would have an entire procedurally generated terrain combined with parts that the developer modifies by hand with the terrain tools. Only the hand-modified parts would have to be saved to a series of files that could be named "mapname_x_x.patch", i.e. "magickingdom_54_72.patch". These patches could be loaded from disk as needed, and deleted from memory when no longer in use.

The real magic would be in developing an algorithm that could quickly generate a height value given an XZ position. A random seed could be introduced to allow us to create an endless variety of procedural landscapes to explore. Perhaps a large brush could even be used to assign characteristics to an entire region like "mountainy", "plains", etc.

The possibilities of what we can do in Leadwerks Engine 5 are intriguing. Granted I don't have all the answers right now, but implementing a system like this would be a major step forward that unlocks an enormous world to explore. What do you think?