Jump to content
  • Advertisement
Sign in to follow this  
CelticSir

Problem with my quad tree think i might be using them wrong

This topic is 422 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

Hi

 

I have a quad tree to make finding object collisions easier since my objects vary in sizes on my tiled map and the map is reasonably large. My problem is i think i might either have misunderstood quad trees, or, its not suitable for my needs.

 

So here is a visual demonstration of the issue i have:

FJ5mc1p.png

So the red square is some object in my quad tree, the blue dot represents its position. 
The green shape is the area i am searching, since this is where i want to place my next object. 

The problem is the area i search is just the green rectangle. And it won't detect the red object since it's position (the blue dot) is outside the range, even though visually we can see it is clearly colliding. But my quad tree search won't find any objects in the way and thus i  get no collision detection.

So, am i misunderstanding how to use a quad tree, or am i using the wrong thing for what i am trying to do here?

Edited by thefollower

Share this post


Link to post
Share on other sites
Advertisement
A loose quaftree helps with some of that, but crossing boundaries will always happen.

The key feature is the dramatic reduction in search space. Instead of testing against everything in the world, you test against the few objects in a few nodes. If something spans a boundary then it happens and you have a few more tests it is still better than testing against the entire world.

Share this post


Link to post
Share on other sites

A loose quaftree helps with some of that, but crossing boundaries will always happen.

The key feature is the dramatic reduction in search space. Instead of testing against everything in the world, you test against the few objects in a few nodes. If something spans a boundary then it happens and you have a few more tests it is still better than testing against the entire world.

 

Right, but then how do you search for such an object since as far as the search is concerned it doesn't find the object since its position is out of the boundary that i searched for. Either that or maybe my code is wrong ?

Share this post


Link to post
Share on other sites

Don't search for a point, search for an area.

Also, you can use each layer of the hierarchy for objects that are larger than their boundaries.  In your image that means testing the full-screen level which contains zero objects, move down the hierarchy and test the southeast quadrant which has zero objects, and then because your zone spans two areas you would test against both the southeast and southwest quadrants.
You would also want to test a layer below that, so your green box would search for any children in the main box that contains it because it fits inside each, plus test both northeast and southeast on the grid containing the pink box.

Or in other words:

Quadtree root overlaps, but the collection is empty.
Quadtree [ SE ] overlaps, but the collection is empty.
Quadtree [ SE ] [ SE ] overlaps, and has one item in the collection for testing.
Quadtree [ SE ] [ SE ] [ SE ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SE ] [ SW ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SE ] [ NE ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SE ] [ NW ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SW ] overlaps, and has one item in the collection for testing
Quadtree [ SE ] [ SW ] [ NE ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SW ] [ SE ] overlaps, but node is null so cannot descend

Again, the goal of a quadtree for spatial operations is to reduce the number of tests. A level might have thousands or tens of thousands of objects, but with careful level design you can reduce any spatial query to a single-digit number of items.

If you have a strict quadtree the pink object should not exist across the boundaries, but should be placed in the layer above.  That is, instead of existing in both [SE][SW] and [SE][SE], it should only exist in [SE] since that fully contains it. A loose quadtree allows objects to overlap somewhat, often by 25% (half of a child node). It requires more tests across neighbors, but means fewer graph changes when objects move.

Share this post


Link to post
Share on other sites

Don't search for a point, search for an area.

Also, you can use each layer of the hierarchy for objects that are larger than their boundaries.  In your image that means testing the full-screen level which contains zero objects, move down the hierarchy and test the southeast quadrant which has zero objects, and then because your zone spans two areas you would test against both the southeast and southwest quadrants.
You would also want to test a layer below that, so your green box would search for any children in the main box that contains it because it fits inside each, plus test both northeast and southeast on the grid containing the pink box.

Or in other words:

Quadtree root overlaps, but the collection is empty.
Quadtree [ SE ] overlaps, but the collection is empty.
Quadtree [ SE ] [ SE ] overlaps, and has one item in the collection for testing.
Quadtree [ SE ] [ SE ] [ SE ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SE ] [ SW ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SE ] [ NE ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SE ] [ NW ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SW ] overlaps, and has one item in the collection for testing
Quadtree [ SE ] [ SW ] [ NE ] overlaps, but node is null so cannot descend
Quadtree [ SE ] [ SW ] [ SE ] overlaps, but node is null so cannot descend

Again, the goal of a quadtree for spatial operations is to reduce the number of tests. A level might have thousands or tens of thousands of objects, but with careful level design you can reduce any spatial query to a single-digit number of items.

If you have a strict quadtree the pink object should not exist across the boundaries, but should be placed in the layer above.  That is, instead of existing in both [SE][SW] and [SE][SE], it should only exist in [SE] since that fully contains it. A loose quadtree allows objects to overlap somewhat, often by 25% (half of a child node). It requires more tests across neighbors, but means fewer graph changes when objects move.

 

Oh so i test from the higher leaf downwards rather than the specific ones the area covers, that makes much more sense albeit slightly slower but it solves the issue! I'll work on it tomorrow! Thanks ! :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!