Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Representing open-world scene with many dynamic objects


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 N.I.B.   Members   -  Reputation: 1195

Like
0Likes
Like

Posted 11 November 2013 - 12:02 PM

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.

 

 



Sponsor:

#2 L. Spiro   Crossbones+   -  Reputation: 14026

Like
5Likes
Like

Posted 11 November 2013 - 01:04 PM

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


It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#3 BGB   Crossbones+   -  Reputation: 1554

Like
0Likes
Like

Posted 13 November 2013 - 11:15 AM

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.



#4 Krohm   Crossbones+   -  Reputation: 3183

Like
1Likes
Like

Posted 14 November 2013 - 01:34 AM

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



#5 serumas   Members   -  Reputation: 724

Like
2Likes
Like

Posted 14 November 2013 - 04:01 AM

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, 14 November 2013 - 04:12 AM.


#6 Krohm   Crossbones+   -  Reputation: 3183

Like
0Likes
Like

Posted 14 November 2013 - 12:25 PM


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.



#7 N.I.B.   Members   -  Reputation: 1195

Like
0Likes
Like

Posted 14 November 2013 - 01:00 PM




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.



#8 hunpro   Members   -  Reputation: 878

Like
0Likes
Like

Posted 14 November 2013 - 02:32 PM

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.



#9 N.I.B.   Members   -  Reputation: 1195

Like
0Likes
Like

Posted 14 November 2013 - 02:47 PM

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., 14 November 2013 - 02:47 PM.


#10 BGB   Crossbones+   -  Reputation: 1554

Like
0Likes
Like

Posted 14 November 2013 - 08:19 PM

 

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, 14 November 2013 - 08:34 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS