Jump to content

How infinite terrain can be implemented in Leadwerks Engine 5

Josh

2,037 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.

blogentry-652-12746406290766.thumb.jpg.89e358c7cb0b35eff0f0ab2f6042b3ae.jpg

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.

Image1.jpg.4d2a3ec26a8aee5b5345884327aa7706.jpg

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.

3.jpg.94d1a9006513d292eb923751fee23f90.jpg

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.

func.jpg.22a8720c464111c0982989a929e24a42.jpg

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?

5289431185_999629e855_b.jpg.09a5923c412a6027525620715ed6c093.jpg

  • Like 6


23 Comments


Recommended Comments

Infinite terrain would be really cool, but how do you add infinite content to infinite terrain?

It would be wonderful for a sandbox type of game

Share this comment


Link to comment
2 minutes ago, martyj said:

Infinite terrain would be really cool, but how do you add infinite content to infinite terrain?

It would be wonderful for a sandbox type of game

The vegetation can easily be infinite.  Of course you will only have cities and towns here and there, and not everywhere.

So I am pretty sure we can either have infinite or very very large terrains.

  • Like 1

Share this comment


Link to comment
4 minutes ago, Josh said:

The vegetation can easily be infinite.  Of course you will only have cities and towns here and there, and not everywhere.

So I am pretty sure we can either have infinite or very very large terrains.

So one thing I would like, if not impossible, is the ability to hide a specific item in the vegetation layer.

For example:

A player walks up and cuts down a tree.

We could hide that instance of the tree and replace it with an instanced object to perform, say a dropping animation.

Is this currently possible? Would be really useful for infinite based content to have all the vegetation intractable.
 

Share this comment


Link to comment
2 minutes ago, martyj said:

So one thing I would like, if not impossible, is the ability to hide a specific item in the vegetation layer.

For example:

A player walks up and cuts down a tree.

We could hide that instance of the tree and replace it with an instanced object to perform, say a dropping animation.

Is this currently possible? Would be really useful for infinite based content to have all the vegetation intractable.
 

Good idea!  Not exactly supported right now but it could be implemented by modifying the layer mask.

What would even be better is the ability to convert a vegetation instance back into a full entity.  Timber!

  • Like 1

Share this comment


Link to comment

Would that be modifying VegiationLayer::filtermap?

I assume vegetation is defined by an image with the same size as the Terrain's height map. If colored it would show that vegetation. 0 = no possible vegetation?

Updating the vegetation texture would update the vegetation on the GPU? (Haven't looked at any shaders yet)

Share this comment


Link to comment
6 minutes ago, martyj said:

Would that be modifying VegiationLayer::filtermap?

I assume vegetation is defined by an image with the same size as the Terrain's height map. If colored it would show that vegetation. 0 = no possible vegetation?

Updating the vegetation texture would update the vegetation on the GPU? (Haven't looked at any shaders yet)

Yes, I think so.  However, there is not a 1:1 ratio of instances and pixels on the filter texture.  You could have multiple trees that are covered by the same filter pixel, so you would have to actually get all instances that pixel effects and convert them all into entities before masking that pixel out.

  • Like 2

Share this comment


Link to comment

You didn't mention it but your post makes it seem like it'll cover it: multiplayer.  Two players can be in two different parts of the map at the same time.  If you ever want to implement automatic multiplayer synchronization as I think you mentioned a while back, this is something else to keep in mind (and make you scratch your head even more).

Share this comment


Link to comment
19 minutes ago, gamecreator said:

You didn't mention it but your post makes it seem like it'll cover it: multiplayer.  Two players can be in two different parts of the map at the same time.  If you ever want to implement automatic multiplayer synchronization as I think you mentioned a while back, this is something else to keep in mind (and make you scratch your head even more).

Ah, but my proposed design for the physics easily handles this.  Wherever a moving object exists, that heightmap data is loaded, or it is generated procedurally if it does not exist.

  • Like 2

Share this comment


Link to comment

Yay Josh is showing interest in procedural stuff. 

This would be amazing if it comes with an LOD system for normal entities.  Limiting LOD to vegetation makes open world design extra complicated and is one of the main reasons I put hunt for food on hold. 

 

As martyj said:

2 hours ago, martyj said:

Infinite terrain would be really cool, but how do you add infinite content to infinite terrain?

with the current system only your vegetation could be infinite; you will quickly run out of space for real entities on the scene tree and eventually render your project unusable by adding too many entities.

  • Thanks 1

Share this comment


Link to comment
2 minutes ago, Haydenmango said:

Yay Josh is showing interest in procedural stuff. 

This would be amazing if it comes with an LOD system for normal entities.  Limiting LOD to vegetation makes open world design extra complicated and is one of the main reasons I put hunt for food on hold. 

 

As martyj said:

with the current system only your vegetation could be infinite; you will quickly run out of space for real entities on the scene tree and eventually render your project unusable by adding too many entities.

The scene management system is very good at handling large numbers of objects that are outside the visible range.  The Zone was specifically created to test this system, as it has a huge number of objects but many items are very small and have a short view range.

So it's not purely number of objects that will slow the engine down, although Leadwerks 5 in general will give your game loop more time to run before you see a hit in performance.

In any case I am very interested in pushing our limits forward in version 5 and would love to hear any ideas you have.

  • Like 1

Share this comment


Link to comment
5 minutes ago, Josh said:

The scene management system is very good at handling large numbers of objects that are outside the visible range.  The Zone was specifically created to test this system, as it has a huge number of objects but many items are very small and have a short view range.

So it's not purely number of objects that will slow the engine down, although Leadwerks 5 in general will give your game loop more time to run before you see a hit in performance.

I was unaware The Zone was infinite. :P

 

As for suggestions I have this: 

 

Share this comment


Link to comment
3 minutes ago, Haydenmango said:

I was unaware The Zone was infinite. :P

That's what I am saying, it could be.  There can be 100,000 entities outside of the camera range at rest and they will have no impact on performance.

  • Like 1

Share this comment


Link to comment

Very excited that you're considering large-scale terrain for Leadwerks 5, that topic's been an interest of mine for ages. I particularly find the algorithm for "Real-Time Deformable Terrain Rendering with DirectX 11" by Egor Yusov in GPU Pro 3 interesting. They basically observe that terrain at any point on the grid usually only deviates slightly from a value linearly interpolated from its neighbors. They use that to only store the delta from that interpolation and get a data set that can be very efficiently compressed. The terrain is then reconstructed at run time from those delta sets according to the required LOD level. There might be some interesting ideas for you in there (and by now OpenGL also provides the relevant features like texture arrays etc.)

Share this comment


Link to comment
8 hours ago, Rastar said:

Very excited that you're considering large-scale terrain for Leadwerks 5, that topic's been an interest of mine for ages. I particularly find the algorithm for "Real-Time Deformable Terrain Rendering with DirectX 11" by Egor Yusov in GPU Pro 3 interesting. They basically observe that terrain at any point on the grid usually only deviates slightly from a value linearly interpolated from its neighbors. They use that to only store the delta from that interpolation and get a data set that can be very efficiently compressed. The terrain is then reconstructed at run time from those delta sets according to the required LOD level. There might be some interesting ideas for you in there (and by now OpenGL also provides the relevant features like texture arrays etc.)

The same thought has occurred to me.  I will check the book out!  We are moving into an exciting phase of new research and development, and the sky is the limit for Leadwerks 5.  I want your biggest ideas.

Share this comment


Link to comment

Actually, with double-precision floating points the sky is no longer a limit at all.

Share this comment


Link to comment

Here's another idea I've had on how to get more detail out of the terrain with less points.  If just one point is interpolated then the memory consumption goes down to 25% what it would be otherwise.

Image1.jpg.7272df63684de72a130e725ab0205311.jpg

Share this comment


Link to comment

Hi, for generating terrain, I would not use randomized data. You could use function like voronoi noise that is based on fractals. Then the user data would be a modifier over that generated noise. I think they use an approach similar to this in No Man's sky to generate the planets and the terrain. So if you would be doing a multiplayer game over that terrain, everybody would see the same thing.

  • Like 2

Share this comment


Link to comment

How did you make the roads in this (I found it hard to replicate on the terrain editor in LE):

blogentry-652-12746406290766.jpg.44a3329844844b343c7d1df3a3c6cd02.jpg

Share this comment


Link to comment
20 minutes ago, jen said:

How did you make the roads in this (I found it hard to replicate on the terrain editor in LE):

blogentry-652-12746406290766.jpg.44a3329844844b343c7d1df3a3c6cd02.jpg

I believe that shot is from LE2 from Dave Lee's blog.  I just googled a random image and posted the first one with a lot of trees.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Create Your Account

Sign in

Already have an account? Sign in here.

Sign In Now
×