Sign in to follow this  

Unity Handling collision data in a (very large) node-based open world

This topic is 816 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What I'm trying to achieve with this thread is a discussion regarding managing collision data in an "unbounded" dynamically loaded (and/or generated) world (that is, the game world is not really intended to be "unbounded", but can be much much larger than either single or double precision floating point would allow). I have currently no intention of taking advantage of an unbounded world, but I like the concept and frankly this is a pretty neat little general design problem. Since information on this topic is scant, I'd like to share what I've thought of so far and hope that people can point out issues with my reasoning and offer other ideas, or perhaps provide links to prior R'n'D that I may have missed.

 

Some background: I had to rehash my scene graph code recently, so naturally I went a wee bit too far for what I presently need and implemented a hashed node system. Despite added complexity, what I have in place now is far more extensible and more easily maintained than the messy linear solution I had before. I'd like to point out that I've added an aside at the very end of this post, in which I'm pointing out that I'm aware of the fact that I'm completely overthinking here. However, as noted above, that doesn't stop this from being a fun little exercise.

 

Some specifics: each location transform in world space stores a hashed node ID and corresponding node space coordinates as an offset from the node's origin. I chose not to normalize the node space coordinates. GetNodeIDFromCoordinates() and GetNodeCoordinatesFromID() convert between the node index/ID and xy/xyz coordinates in whatever spatial domain the game happens to need. Since currently NODEID is a simple int32 value, this can neatly store something like a 65000x1x65000 node world where each node can have a size of whatever floating point precision IVector3D happens to be using.

struct IWorldTransform {
  NODEID iNodeID;
  IVector3D vPosition;
  };

In addition, each player (or rather, each human controllable character) implements what I'm calling its own "view", which extends from -n to +n nodes in each direction around the screen space portion of the world that is centered on it. The center of the screen determines the center node of the view. The required n depends on various factors, such as screen resolution and camera zoom.

 

A view is kind of an extended view frustum, for lack of a better term (as described in this fairly old document: The Continous World Of Dungeon Siege (link to a PDF file)), which completely encapsulates what's currently visible on screen and is always aligned to node boundaries. For instance, in my current single player game the player's view corresponds to the entire simulated game world.

 

Rendering stuff like this is trivial since the transformation (what ever space it is being done in) is calculated once every time a view is updated and actual vertex transformation is performed on the GPU anyway, after setting up the model view matrix using a generic TransformWorld(currentView) call. However, when it comes to managing collision data, there are several solutions I've thought of. And none are really perfect.

 

My ideas on collision so far:

 

Actually all of these are viable for what I need at the moment, but since my head is already in this, I'd like to take the discussion a bit further. You know, for fun.

 

Method 1: store no transformed collision data at all, only extents of bounding volumes for each object/mesh in view space (as explained above). No distinction is made between static and dynamic objects. Whenever collision needs to be tested, all collision hulls belonging to objects whose bounding volumes intersect the sweep are translated into view space and collision is performed as usual. This is the simplest method, yet allows for both temporal and spatial coherence optimizations. The thing about it is that it would work wonders for player-only scenarios, but as soon as there is a remotely significant number of projectiles or some such random crap added to the game world, the computational cost has the potential to skyrocket. Things get even more complicated when multiple disjoint emitters of dynamic objects (urr, players and mobs for the most part, that is) are involved.

 

Method 2: store continuously updated collision data for static objects in view space, maintain dynamic objects on an as-needed basis, as in Method 1. While this takes care of static collision data most of the part, it still means that essentially all collision data for the entire loaded world needs to be updated every time the player crosses a node boundary. Some prediction can be made to precache this data when the player approaches the edge of a node, but node corners still present a problem, since a total of three additional copies of the precached world need to be created, leading to potential gameplay lag or load peaks. In particular, fast-moving objects can really screw up performance when emitted near a node boundary. It also reeks of the likelihood that after multiple back-and-forth adjustments, floating point precision issues start to kick in and stuff like cracks start appearing between adjacent objects.

 

Method 3: store static collision data in node space (eg relative to an anchor in each node, which in my case is the origin at the top left corner). This allows easy caching, since no collision data need to be updated after its initial load. However it still incurs a penalty similar to Method 1 when the player or another dynamic object crosses a node boundary. For most cases this will be trivial, but doing a sweep test (even if it's just raycasting) for a projectile that travels very fast or instantaneously requires all collision data that is not stored in the node the object originates from to be dynamically transformed. With this method, handling dynamic objects in general is complicated, since as they cross from one node to another, their transform resets, making spatial and temporal coherence schemes more difficult to implement.

 

Of course these are all just ideas. I don't have an up and running game world to test them on, so whatever performance issues and optimizations I'm desperately trying to think of, may well be moot with real data.

 

That being said, that's not the end of the story, though.

 

 

 

Where it gets complicated is when dealing with multiple "views" - eg multiple players or several human-controllable entities that can separate from one another. The biggest impact is the memory footprint: Method 1 would scale linearly, since only one copy of the collision data exists for each static and dynamic object; Method 2 would be the worst, since in a naive approach (n * 2 + 1) x (n * 2 + 1) nodes worth of data need to be maintained P times, for each human-controllable entity; Method 3 would, again, be the most practical, since with some caching it would be fairly memory efficient and would require infrequent collision volume adjustment (although when the need arises, it needs to be performed in real time and cannot really be precalculated).

 

To me Method 3 is the clear winner here, but I find myself reluctant to actually implement it before doing some more digging. Maybe there's a Method 4 that I haven't thought of. In any case, I'd like to learn more about how collision is handled (that is, how collision data is stored and handled) in open world games. I've never traversed far enough, but for instance 7 Days To Die is a Unity-based dynamically generated open world game, which should eventually start to suffer from precision issues. Minecraft needs to handle a similar case, although its data set is far more simple. World Of Warcraft at least feels like it's either running on double precision or uses some kind of spatial partitioning similar to this, although my research turned up nothing. The same goes for Skyrim and Just Cause, or the estimated 39000 km2 world size of Guild Wars. Not to mention space sims that need to handle stuff on interplanetary or intergalactic scales (although I have no experience with any of those offering continuous collision detection, much less on a detailed scale). So yeah - weight in! :)

 

An aside: for all intents and purposes most collision in general is performed on unoriented volumes - either static meshes or simple generic volumes, such as AABBs and spheres that never rotate. For all these, adjustment from the origin to the object space that needs testing is nothing more than a bunch of floating point additions, which at the end of the day is not all that expensive. Conversely, dynamic objects that can rotate, need to be updated in real time anyway, which makes any spatial hashing of those largely moot. I have currently rolled my own collision code, but since it's fairly outdated, I want to leave room for a hopefully painless transition to Bullet at some point. However, I have no experience with Bullet, so with that particular API in mind, perhaps one of the above methods is better suited for real time performance than another. Some feedback on this would be nice as well.

Share this post


Link to post
Share on other sites

This topic is 816 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Forum Statistics

    • Total Topics
      628726
    • Total Posts
      2984411
  • Similar Content

    • By INTwindwolf
      THE PROJECT

      INT is a 3D Sci-fi RPG with a strong emphasis on story, role playing, and innovative RPG features such as randomized companions. The focus is on the journey through a war-torn world with fast-paced combat against hordes of enemies. The player must accomplish quests like a traditional RPG, complete objectives, and meet lively crew members who will aid in the player's survival. Throughout the game you can side and complete missions through criminal cartels, and the two major combatants, the UCE and ACP, of the Interstellar Civil War.
      Please note that all of our current positions are remote work. You will not be required to travel.
      Talent Needed
       
      Unity Engine Programmer
      Website Administrator
      3D Animator
      We have made great strides in the year 2017! INT has received a comprehensive face-lift compared to the start of the year. We look forward to a productive, fruitful year 2018!
      Revenue-Share
      This is the perfect opportunity to get into the game development industry. Being an Indie team we do not have the creative restrictions often imposed by publishers or other third parties. We are extremely conscientious of our work and continuously uphold a high level of quality throughout our project.
      We are unable to offer wages or per-item payments at this time. However revenue-sharing from crowd-funding is offered to team members who contribute 15-20 hours per week to company projects, as well as maintain constant communication and adhere to deadlines. Currently the crowd-funding campaign is scheduled for the year 2018. Your understanding is dearly appreciated.
       
      Thank you for your time! We look forward to hearing from you!
       
      John Shen
      HR Lead
      Starboard Games LLC
    • By Apollo Cabrera
      Energy particles being harnessed by collection multi-hedron energy matrix. Whuuuttt?
      Love it :)
    • By AndySv
        Total Music Collection (http://u3d.as/Pxo)   THE COLLECTION CONTAINS:   Mega Game Music Collection   Universal Music Collection   Huge library of high quality music for any project! All at an incredibly low price!   - 2,5GB of high quality audio - 100+ different music tracks - Loop and short versions   Action, fantasy, casual, horror, puzzle, epic, dramatic, romantic, positive, inspiring, motivational and more!
    • By Dafu
      FES Retro Game Framework is now available on the Unity Asset Store for your kind consideration!
      FES was born when I set out to start a retro pixel game project. I was looking around for an engine to try next. I tried a number of things, from GameMaker, to Fantasy Consoles, to MonoGame and Godot and then ended up back at Unity. Unity is just unbeatable in it's cross-platform support, and ease of deployment, but it sure as heck gets in the way of proper retro pixel games!
      So I poured over the Unity pipeline and found the lowest levels I could tie into and bring up a new retro game engine inside of Unity, but with a completely different source-code-only, classic game-loop retro blitting and bleeping API. Months of polishing and tweaking later I ended up with FES.
      Some FES features:
      Pixel perfect rendering RGB and Indexed color mode, with palette swapping support Primitive shape rendering, lines, rectangles, ellipses, pixels Multi-layered tilemaps with TMX file support Offscreen rendering Text rendering, with text alignment, overflow settings, and custom pixel font support Clipping Sound and Music APIs Simplified Input handling Wide pixel support (think Atari 2600) Post processing and transition effects, such as scanlines, screen wipes, screen shake, fade, pixelate and more Deploy to all Unity supported platforms I've put in lots of hours into a very detail documentation, you can flip through it here to get an better glimpse at the features and general overview: http://www.pixeltrollgames.com/fes/docs/index.html
      FES is carefully designed and well optimized (see live stress test demo below). Internally it uses batching, it chunks tilemaps, is careful about memory allocations, and tries to be smart about any heavy operations.
      Please have a quick look at the screenshots and live demos below and let me know what you think! I'd love to hear some opinions, feedback and questions!
      I hope I've tickled your retro feels!



      More images at: https://imgur.com/a/LFMAc
      Live demo feature reel: https://simmer.io/@Dafu/fes
      Live blitting stress test: https://simmer.io/@Dafu/fes-drawstress
      Unity Asset Store: https://www.assetstore.unity3d.com/#!/content/102064

      View full story
    • By Dafu
      FES Retro Game Framework is now available on the Unity Asset Store for your kind consideration!
      FES was born when I set out to start a retro pixel game project. I was looking around for an engine to try next. I tried a number of things, from GameMaker, to Fantasy Consoles, to MonoGame and Godot and then ended up back at Unity. Unity is just unbeatable in it's cross-platform support, and ease of deployment, but it sure as heck gets in the way of proper retro pixel games!
      So I poured over the Unity pipeline and found the lowest levels I could tie into and bring up a new retro game engine inside of Unity, but with a completely different source-code-only, classic game-loop retro blitting and bleeping API. Months of polishing and tweaking later I ended up with FES.
      Some FES features:
      Pixel perfect rendering RGB and Indexed color mode, with palette swapping support Primitive shape rendering, lines, rectangles, ellipses, pixels Multi-layered tilemaps with TMX file support Offscreen rendering Text rendering, with text alignment, overflow settings, and custom pixel font support Clipping Sound and Music APIs Simplified Input handling Wide pixel support (think Atari 2600) Post processing and transition effects, such as scanlines, screen wipes, screen shake, fade, pixelate and more Deploy to all Unity supported platforms I've put in lots of hours into a very detail documentation, you can flip through it here to get an better glimpse at the features and general overview: http://www.pixeltrollgames.com/fes/docs/index.html
      FES is carefully designed and well optimized (see live stress test demo below). Internally it uses batching, it chunks tilemaps, is careful about memory allocations, and tries to be smart about any heavy operations.
      Please have a quick look at the screenshots and live demos below and let me know what you think! I'd love to hear some opinions, feedback and questions!
      I hope I've tickled your retro feels!



      More images at: https://imgur.com/a/LFMAc
      Live demo feature reel: https://simmer.io/@Dafu/fes
      Live blitting stress test: https://simmer.io/@Dafu/fes-drawstress
      Unity Asset Store: https://www.assetstore.unity3d.com/#!/content/102064
  • Popular Now