Jump to content

How infinite terrain can be implemented in Leadwerks Engine 5

Josh

2,817 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


25 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

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

 

Share this comment


Link to comment

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

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.

  • Blog Entries

    • By Haydenmango in Snowboarding Development Blog 6
      So I've been researching snowboarding lately to get an idea of what animations and mechanics I need to create for my game.  I have learned lots of interesting things since I've only seen snow once or twice in my entire life and have never even tried snowboarding or any other board sports (skateboarding, surfing, etc.) for that matter.
       
      Snowboarding tricks are quite interesting as they are mostly derived from skateboarding.  Snowboarding tricks pay homage to their equivalent skating tricks by sharing many concepts and names.  For example basic grabs in snowboarding share the same concepts and names as skateboarding: indy, mute, method, stalefish, nosegrab, and tailgrab.  Something interesting to note is in snowboarding you can grab Tindy or Tailfish but this is considered poor form since these grabs can't be done on a skateboard (due to the board not being attached to the skaters feet) and grabbing these areas is generally something a novice snowboarder does when failing or "half-assing" a normal grab.  Check out this diagram to see how grabs work -
       
       
      So, after reading lots of text descriptions for tricks I was still confused by what all these terms meant and how they were actually applied.  So my next step was to look up these tricks actually being done and I found some really cool videos showing off how to do various tricks.  This video in particular is the best reference material I've found as it contains nearly every trick back to back with labeled names and some tweaks -
       
      Sadly my rigged model doesn't handle leg animations with the snowboard that well so I can't animate as many tricks as I want to.  Regardless there will still be around 15 total grab/air tricks in the game.  Now it's time for me to stop procrastinating and start animating!  
    • By jen in jen's Blog 3
      I thought I would share my experience on this; if you're working on Multiplayer, you will need to protect your packets. The solution is simple, let's go through how we can achieve this by implementing what Valve calls "challenge codes". (Some reading on the topic from Valve here: https://developer.valvesoftware.com/wiki/Master_Server_Query_Protocol#Challenge_response).
      Disclaimer: this doesn't cover other security techniques like authoritative server or encryption.
      So, I've worked on Border Recon last year (I think) and I needed a way to protect my server/client packets. There was no need for me to re-invent the wheel, I just had to copy what Valve has had for a  long time - challenge  codes.
      The idea behind challenge codes is similar to Captcha, but not exactly. Think of it like this: for every packet submitted to the server, it must be verified - how? By requiring the client to solve challenges our server provides.
      To implement this we need to have the following:
      A randomised formula in the server i.e.: a = b * c / d + e or a = b / c + d - e, be creative - it can be any combination of basic arithmetic or some fancy logic you like and can be however long as you want - do consider that the longer the formula, the more work your server has to do to make the computation.  Copy the same formula to the client. A random number generator.  So the idea here is:
      (Server) Generate a random number (see 3 above) of which the result would become the challenge code, (Server) run it through our formula and record the result. (Client) And then, we hand over the challenge code to the client to solve (an authentic client would have the same formula implemented in its program as we have on the server). For every packet received from the player, a new challenge code is created (and the player is notified of this change by the server in response). For every other packet, a new challenge code is created. (Client) Every packet sent to the server by the client must have a challenge code and its answer embedded.  (Server receives the packet) Run the challenge code again to our formula and compare the result to the answer embedded on the client's packet. (Server) If the answers are different, reject the packet, no changes to the player's state. The advantage(s) of this strategy in terms of achieving the protection we need to secure our server:
      - For every packet sent, new challenge code is created. Typically, game clients (especially FPS) will update its state in a matter of ms so even if a cheater is successful at sniffing the answer to a challenge code it would be invalidated almost instantaneously. 
      - Lightweight solution. No encryption needed. 
      Disadvantage(s):
      - The formula to answering the challenge code is embedded to the client, a cheater can de-compile the client and uncover the formula. Luckily, we have other anti-cheat solutions for that; you can implement another anti-cheat solution i.e. checking file checksums to verify the integrity of your game files and more (there are third-party anti cheat solutions out there that you can use to protect your game files).
       
       
       
    • By Josh in Josh's Dev Blog 4
      New commands in Turbo Engine will add better support for multiple monitors. The new Display class lets you iterate through all your monitors:
      for (int n = 0; n < CountDisplays(); ++n) { auto display = GetDisplay(n); Print(display->GetPosition()); //monitor XY coordinates Print(display->GetSize()); //monitor size Print(display->GetScale()); //DPI scaling } The CreateWindow() function now takes a parameter for the monitor to create the window on / relative to.
      auto display = GetDisplay(0); Vec2 scale = display->GetScale(); auto window = CreateWindow(display, "My Game", 0, 0, 1280.0 * scale.x, 720.0 * scale.y, WINDOW_TITLEBAR | WINDOW_RESIZABLE); The WINDOW_CENTER style can be used to center the window on one display.
      You can use GetDisplay(DISPLAY_PRIMARY) to retrieve the main display. This will be the same as GetDisplay(0) on systems with only one monitor.
×
×
  • Create New...