Sign in to follow this  
satanir

Representing open-world scene with many dynamic objects

Recommended Posts

satanir    1452

AC/GTA like game - many static and dynamic objects.

BSP seems like the obvious choice. The main drawback is the cost of updating the tree in case I have a lot of dynamic objects.

 

One solution I have, it to manage the dynamic objects using a different data structure. Since for every object I have a zone in which it can move, I was thinking BVH-like structure, where I use the zone as the bounding-rect.This solves the problem of having to dynamically update the data structure, while still allowing efficient culling and collision-detection of the dynamic objects. This only works if the zones are not big enough, so not a scalable solution.

 

Ideas will be appreciated.

 

 

Share this post


Link to post
Share on other sites
cr88192    1570

A BSP is not an obvious choice—it is useful for indoor scenes and not much else, especially not for dynamic scenes.

 

An octree is more intuitive.  A series of octrees can be used depending on how expansive your game world needs to be vs. fine node coverage.  Updating an octree is nearly instantaneous if implemented correctly.

 

 

L. Spiro

 

 

yeah.

 

a downside about BSPs/etc is that they don't scale "upwards" particularly great.

like, great for minimizing checks if you have a lot of stuff in a small space, not so great if things are more sparsely distributed.

 

 

my personal experience is that for larger worlds, it makes sense to divide things into a regular grid, mostly because a grid can easily extend easily in any direction, and you usually only really need to keep a small number of these grid-blocks loaded at once.

 

say, a person can use grid-blocks of 256x256x256 meters or similar, with more precise structures within each grid-block;

slight special cases may be involved in the case of objects that protrude from the grid-block (checking for object interactions across adjacent grid-blocks).

 

 

then, within each large block, a more precise subdivision can be used (BSP or BVH or octree or whatever else).

 

 

personally, I have had some success with dynamic BSP-like trees, but mostly via tricks (figuring out an O(n log n) rebuild algorithm, and separating up various types of objects according to their behavior and whether or not they are currently actively moving). technically, they are hybridized with a BVH though (usually object-based and having bounding volumes, in addition to a division plane), and in some cases incorporate tricks from AVL trees (such as node rotations), and may do partial (localized) rebuilds, so are by no means "traditional" BSP trees (nor even necessarily binary, they may use a "center" branch for things which cross the plane, or for objects which have left their node of origin and can't be "pushed down" to a lower node, ...).

 

an octree may or may not be simpler or faster, but admittedly I haven't really used them personally.

Share this post


Link to post
Share on other sites
Krohm    5030

According to this benchmark (Bullet broadphase collision) a simple tree of AABB (light yellow bars) appears to be the most promising method.

Don't even think at BSP. Don't. I learnt about its drawbacks when I was a Quake1-2-3 mapper. They are natively static, non-scalable and non-trivial (ID Software needed three iterations to get them half correct).

Share this post


Link to post
Share on other sites
serumas    796

Quadtree is some kind of layered grid too.

Talking about AABB tree... Box2d has it... but that not means that is faster than enything, maybe that means its safe for everithing.

For example I have changed box2d algorithm to my own. And for 5000 moving objects on area from ~6 ms broadphase droped to ~1 ms, becouse algorithm was extremaly optimized for my game mechanics (lots of moving objects, wraped world, small compared to area objects).  After that I have dicided to write whole simplified physic my self. 

And one physic loop for 5000 objects from 50ms (best box2d case) droped to 12ms(own worst case). My algorithm on testing program with 10000 circle objects takes ~0,5 ms, but its very dependant on data structure...

 

I just want to say that there is no best algorithm for everything. It very dependant on data structure, world size, object size, speed of moving, mechanics and etc...

Edited by serumas

Share this post


Link to post
Share on other sites
Krohm    5030


I just want to say that there is no best algorithm for everything. It very dependant on data structure, world size, object size, speed of moving, mechanics and etc...
Quoted for emphasis, this is something we should truly stress.

 

If memory serves, my realistic cases are about 600 static rigid bodies, large majority being boxes and a few (probably less than 100) are simple hulls. There can be up to 20 moving objects (kinematic). There are currently no dynamic objects in my tests.

All broadphases, when properly set up, gave me more or less the same performance.

As I support some pretty extensive scripting I preferred AABB tree due to the promised flexibility. I just don't have to worry.

Share this post


Link to post
Share on other sites
satanir    1452




I just want to say that there is no best algorithm for everything. It very dependant on data structure, world size, object size, speed of moving, mechanics and etc...

I agree. I specifically wanted to target something like AC 2+, where you have a large bustling city. Assuming you have 1000+ objects, but can see only 20 at a time, regular octree doesn't make sense. Sure, it's easy to manage, but updating this tree for all the dynamic objects in not necessary.

I guess the simplest solution is octree, while updating only objcets in a certain radius around the camera position.

 

BTW, most resource I looked at advocate BSP.

Share this post


Link to post
Share on other sites
satanir    1452

I use a 'loose uniform grid' for my openworld game, it is very simple, every object has to connect only to one cell, and adding/removing objects is basicly free.

How do you avoid objects popping into the scene? If an object is only connected to a single cell, you don't get a smooth transition between cells, so potentially an object can connect to a visible cell, and it will pop into the scene.

Edited by N.I.B.

Share this post


Link to post
Share on other sites
cr88192    1570

 

I use a 'loose uniform grid' for my openworld game, it is very simple, every object has to connect only to one cell, and adding/removing objects is basicly free.

How do you avoid objects popping into the scene? If an object is only connected to a single cell, you don't get a smooth transition between cells, so potentially an object can connect to a visible cell, and it will pop into the scene.

 

 

 

would guess:

presumably a player can see multiple grid cells, like pretty much everything within a certain radius of the camera.

 

if most of the pop up is a fair distance away (such as 500m or 1km), it is less obvious.

potentially, this could be combined with a 2-stage drawing strategy or "3D skyboxes" or similar to further hide pop-up.

 

for example, distant large-scale features (buildings, etc) could be periodically drawn into a 3D skybox, and then when approached, the "real" version mostly appears in front of the skybox version (in a hopefully not-too-obvious transition), with possibly a few translation and/or warping tricks involved to help hide the fact that it is drawn as part of the skybox.

 

 

ADD: or, if you mean for determining object visibility, yes. this is possibly a separate issue though, and is a little more involved.

Edited by BGB

Share this post


Link to post
Share on other sites

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