Jump to content

  • Log In with Google      Sign In   
  • Create Account


Finding neighbouring agents within interaction range efficiently


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
10 replies to this topic

#1 dangerdaveCS   Members   -  Reputation: 122

Like
0Likes
Like

Posted 28 October 2010 - 12:35 AM

Hello all. I have a bunch of critters that interact with each other only when nearby (i.e. they communicate by touch). So given an agent, I need to find all other agents within interaction range.

My first intuition is boids-style bin lattice spatial subdivision (i.e. divide all of space into a grid, each cell storing pointers to agents).

However, I've recently been playing around with Bullet physics library, and notice that uses a completely different method(s) for its broadphase stage of collision detection (which is basically what I'm trying to do).

I must not be understanding something right, because I can't think of a more efficient data structure than a grid, yet a popular physics library uses some mad hierarchical axis aligned something or other.

Can someone please enlighten me?

Sponsor:

#2 Zahlman   Moderators   -  Reputation: 1682

Like
0Likes
Like

Posted 28 October 2010 - 01:17 AM

Quote:
Original post by dangerdaveCS
some mad hierarchical axis aligned something or other.

Can someone please enlighten me?


I'd like to, but I can't tell exactly what the thing in question is :)

Could it be a quadtree (octree, for 3d)?

#3 dangerdaveCS   Members   -  Reputation: 122

Like
0Likes
Like

Posted 28 October 2010 - 01:24 AM

I believe Bullet has a choice of two broadphase methods:
  • btAxisSweep3 = "3D Sweep and Prune, based on axis aligned bounding boxes (AABB)" [from Bullet wiki]
  • btDbvtBroadphase = "a broadphase using two dynamic AABB bounding volume hierarchies/trees. One tree is used for static/non-moving objects, and another tree is used for dynamic objects.


So... why use these rather than just a grid?

#4 Littorio   Members   -  Reputation: 254

Like
0Likes
Like

Posted 28 October 2010 - 09:38 PM

With a grid you have to decide the size of the world and the resolution of the grid in advance. For example in a space shooter the grid is mostly empty except a few overcrowded cells.
The grid can be efficient in your particolar case if you know the size of the world and critters have uniform distribution.

#5 dangerdaveCS   Members   -  Reputation: 122

Like
0Likes
Like

Posted 29 October 2010 - 07:04 AM

Ahhh. OK that makes a bit of sense. So, let me make sure I understand.

Bounding volume hierarchies and the sweep and prune method are general purpose, but not necessarily optimal. If you have prior knowledge on the size and distribution of objects and the size of environment, then a simple grid structure is the most efficient...?

#6 WavyVirus   Members   -  Reputation: 735

Like
0Likes
Like

Posted 29 October 2010 - 07:56 AM

Quote:
Original post by dangerdaveCS
If you have prior knowledge on the size and distribution of objects and the size of environment, then a simple grid structure is the most efficient...?


Only if the prior knowledge indicates that this will be the case. If objects are clustered, for example, then a fixed grid provides no guarantee of the number of distance checks you will have to make - the worst case is that all objects lie in the same cell and you have to check them all. If they are rarely or never clustered then you can be more confident that a fixed grid will give you an acceptably small number of distance checks.

Something like a quadtree, on the other hand, can guarantee a maximum number of distance checks. Even with clustered objects, you can be confident that no more than X of them lie in any given cell. The downside is the overhead imposed by the maintenance of this structure. If an "educated guess" based on the behavior of objects in your game world, coupled with some testing, indicates that a fixed grid results in an acceptably small number of comparisons then it may be the best choice. You can experiment with grid sizes etc to find the optimal.

#7 TyrianFin   Members   -  Reputation: 122

Like
0Likes
Like

Posted 29 October 2010 - 08:40 AM

2d / 3d grid with good cell size is fastest.
And to make sure that grid size is right, you can create multible grids
with different sizeses. (ie. loose Octree with fixed depth. (all branches go to
max leaf depth))

Remove / insert to data structure = O(1)
Finding all cells inside volume = O(log(n))

/Tyrian

#8 shawnpresser   Members   -  Reputation: 100

Like
0Likes
Like

Posted 29 October 2010 - 03:46 PM

Hello!

Fortunately, this problem has been solved before. John Ratcliff implemented an extremely efficient algorithm for exactly what you describe (he calls it "spatial awareness"), then open sourced it. His C++ interface is extremely easy to use.

Step 1) go here: http://codesuppository.blogspot.com/2008/03/spatial-awareness-system.html

Step 2) click on the "Spatial Awareness System" link at the top (which currently links to http://www.amillionpixels.us/SAS_1.0.exe)

Step 3) run the program. It is an installer which will install the source code + demo app at "C:\Program Files\SAS". Sure, it might be a little annoying that it's not a ZIP file, but please disregard this; it will be totally worth it!

Step 4) Run "C:\Program Files\SAS\SphereTest\SphereTest.exe". When the program starts, press R. You'll be greeted with an awesome visual demo of the library's capabilities: http://dl.dropbox.com/u/315/random_pics/spatial_awareness_test_app.png ... the yellow spheres move around at different speeds. Each sphere is notified whenever it overlaps a new white point, and also when it no longer overlaps it. Which is exactly what you want.

Step 5) Open "C:\Program Files\SAS\SphereTest\SphereTest.sln" in Visual Studio (I use VS2005). It will ask to remove source control bindings; say permanently remove.

Step 6) Switch to Release build configuration, at the top.

Step 7) Unfortunately, the code contains a few minor compile errors. They are easily fixed. Here is what you'll see if you try to build the program right now:

http://dl.dropbox.com/u/315/random_pics/spatial_awareness_compile_error_vs2005.png

So, the include path is simply set up incorrectly. Change the highlighted line into this:

http://dl.dropbox.com/u/315/random_pics/spatial_awareness_compile_error_vs2005_fix1.png

That fixes one error. Now double-click on the other error, and change this....

http://dl.dropbox.com/u/315/random_pics/spatial_awareness_compile_error_vs2005_fix2_a.png

.... to this ....

http://dl.dropbox.com/u/315/random_pics/spatial_awareness_compile_error_vs2005_fix2_b.png

Presto! It builds and runs! Now you can mess with the settings to get a feel for how the library works.


At this point you should copy the Spatial Awareness code files into your own application and use it. Have fun!

The algorithm he provides is EXTREMELY efficient. I doubt it could be optimized without a lot of effort. Effort that you likely don't need to worry about doing. :)

#9 Martin Felis   Members   -  Reputation: 154

Like
0Likes
Like

Posted 01 November 2010 - 11:18 AM

Another nice way might be spatial hashing. There is a nice paper by Matthias Teschner, Bruno Heidelberger, Matthias Mueller, Danat Pomeranets, and Markus Gross called "Optimized Spatial Hashing for Collision Detection of Deformable Objects" which could also be used for your case. I hope this link works: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.4.5881&rep=rep1&type=pdf.

I think this is also used by the chipmunk 2d physics engine. Maybe you can get some code from there (they're using an MIT license).

Good luck!
-- blog: www.fysx.org

#10 dangerdaveCS   Members   -  Reputation: 122

Like
0Likes
Like

Posted 02 November 2010 - 02:28 AM

Thanks a lot for all the responses.

Spatial hashing sounds like it is more memory efficient, but not faster than a grid...?

Ratcliff's implementation uses either kd-tree or sweep-and-prune. I recognize sweep-and-prune as one of the methods Bullet uses. Would either of these be quicker than a grid? Even assuming I have reasonably guarantees on the distribution of agents?

#11 Adam_42   Crossbones+   -  Reputation: 2450

Like
0Likes
Like

Posted 02 November 2010 - 08:39 AM

Testing each algorithm is the only way to be certain which one is quickest for your use.

However A 2D grid is usually fast enough if the size of the grid cells is chosen well. In 3D however grids can be very wasteful of memory.




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