Jump to content
  • entries
    940
  • comments
    5,894
  • views
    863,972

How infinite terrain can be implemented in Leadwerks Engine 5


Josh

8,416 views

 Share

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 7
 Share

26 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

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
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.
 

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
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)

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
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).

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
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
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
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: 

 

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
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.)

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.

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

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
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.

Link to comment
On 12/5/2017 at 2:36 PM, 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

User driven content is the answer and it's what more and more games are moving to. Let your users create the content. Just provide them with terrain and veg. The ability for users to build in game has really taken off and it's only getting stronger.

 

I always thought it was odd how physics is always taking up cycles on objects that can't possibly be hit by anything just by existing. Seems you'd only want a small moving section around something that is moving to check things directly around it. If you gridded out the terrain, a player walking around would only need to check collisions with a 3x3 grid around it with it in the center grid at all times. Dynamically load the 3 grids and unload the other 3 grids as the player moves around. I would think the same ideas of a 3x3 gird could be done for actual terrain chunks. Loading/unloading as they player moves around.

There is no need for things to happen in unloaded terrain chunks in real-time. When one gets loaded it just may needs to know about some state variables so things inside of it can adjust accordingly. Push a button in 1 grid that should cause x to happen in an unloaded grid? That state variable is set (and stays with the player) and when grid x is loaded whatever entity is on it checks that state variable and puts itself in whatever state it needs to show the effect. So terrain state variables become special and whenever a terrain chunk is loaded all entities on it have a method called which has all state variables available to it so they can do what they need to do based on the value of the state variable.

 

Link to comment

Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...