This project has moved and is read-only. For the latest updates, please go here.

[Solved] QuadTree usage

Topics: User Forum
Nov 8, 2012 at 9:17 AM
Edited Nov 8, 2012 at 11:46 AM

Hi guys, I was wondering if someone could explain me or provide an example on how to use the QuadTree classes included in FarseerPhysics


I will try to be more specific.

The fact is that both QuadTreeBroadphase and DynamicTreeBroadphase implements the interface IBroadphase.

This interface has three main methods (I think) which are void UpdatePairs(BroadphaseDelegate callback); void MoveProxy(int proxyId, ref AABB aabb, Vector2 displacement); void Query(Func<int, bool> callback, ref AABB aabb);

What I'd like to know from you is what these methods actually do, what I've understood is that UpdatePairs perform some collision detection among objects and for each collision detected it calls the callback, instead Query just check for collision between the aabb and the other objects.

The move method moves the aabb and its proxyfixture to displacement and should adjust my aabb to fit the new location.

Is it correct ?

Thanks a lot for the help and sorry for my bad English, regards.

Nov 9, 2012 at 1:20 AM

Would you like to use the Quadtree as the broad phase in FPE, or as a separate data structure for your own needs?

QuadTreeBroadphase and DynamicTreeBroadphase are actually the Farseer Physics specific implementations of the broadphase algorithms. I separated the algorithms by design, so that you are able to use the algorithms in your own game. The algorithms themselves are inside QuadTree.cs and DynamicTree.cs.

To answer your question:

UpdatePairs does the actual movement of proxies and calls a callback whenever a pair of AABBs touch each other.

MoveProxy moves the proxies in the data structure to a new position, corresponding to the position of the fixtures.

Query 'ask' the data structure what is touching the AABB that is provided.

Essentially the same thing you already wrote, so I think you have the right idea. Normally you would not use the UpdatePairs or MoveProxy methods outside the engine, but I encourage people to use Query.

Nov 9, 2012 at 9:49 AM

Thanks for the answer ! 

I was trying to use the Farseer implementation of the QuadTree, but I'm still having some troubles: If I want to use your implementation outside the Engine (so I won't use any bodies and so on) can I still use the QuadTreeBroadphase class or I must create bodies for every object of my game and then set the bodies as sensors and try to compute the collision with the QuadTreeBraodphase ?

Because right now I just use the FixtureProxy with just the AABB is it correct ?

Thanks a lot and, again, sorry for my English


Nov 9, 2012 at 2:09 PM

You don't need to use the QuadTreeBroadphase, you just need the QuadTree. The QuadTree is more generic and works with any object you like.

Do something like this:

QuadTree<YourObject> quadTree = new QuadTree<YourObject>(span, 5, 10);

Where span is the AABB that contains the world. 5 are the maximum number of buckets and 10 is the maximum depth. To add an element to the Quadtree, you call quadTree.AddNode(yourObjectInstance). Then you can at any point in time query (using quadTree.Query()) the quadtree to 'ask' if it is in a certain area.

Nov 10, 2012 at 5:03 PM

Thanks for the help !

Please answer my last question when I use quadTree.Query the searchR AABB is the region where I want to look for collisions, so this AABB can be, for example, the player bounding box ?

If so the Elements passed to the callback are the one lying in the region where is the player's bounding box ?

Thanks a lot for the patience and the answers !

Nov 11, 2012 at 9:39 PM

Yes, the AABB you pass to Query() is the area you would like to check for object containment. The objects passed to the callback are the ones that intersect with the AABB.

If you are using the QuadTree for AABB testing against collision objects, then you can use the Fixture.BeforeCollision delegate. It gets fired when AABBs touch, and before the real collision gets computed. Return false inside the delegate method to cancel the collision, or true to process the collision.

Nov 12, 2012 at 8:54 AM

Alright ! Thanks for the help !