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:



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?

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 ?

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.

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 ! :)