QuadTree Checking Collision With Different Levels of Nodes

I am making a QuadTree for a 2D Platformer. Researched on it and I managed to make a pretty good one where each node stores its 4 SubNode and there's a MAX_OBJECTS for each Node and MAX_LEVELS which represents the amount of Levels my Tree has, with 0 being the root.

So, I get my object and I try to store it into the Deepest Node possible. If I can't, then I'll store it in the Parent Node instead.

Then when I check for Collision, I'll see which Nodes have Possible Collisions with my Object, get the Objects in those Nodes and add it to a List of my Collision Checks.

My problem is this Checking for Collision. I am quite confused. For example, I have an ObjectA at Level 1 Node and it will collide with objects within its node. I have another ObjectB at Level 0 (Root Node) and it overlaps ObjectA's node so there is a possible Collision.

This is where it gets tricky, just from the paragraph above, I can see that Objects in the Parent Node have a chance to to collide with the Objects in the SubNode. So when I check for the Possible Collisions, do I check the Parent Nodes + SubNodes of my Object's Node...I'm not really sure as to how you choose which node to check.

There will be Nodes of Different Levels won't there? An Object of Level 1 can have Collision Checks with Level 0, Level 2, Level 5...etc(or is this wrong). It's hard to grasp what the criteria is of checking a specific node...To put it simply, a Tree has so many different Levels...

For all I know, there might be an ObjectA(x,y) at Level 0 and ObjectB(x,y) at Level5. Completely same coordinates, but different node levels. If I were to check Collisions for ObjectC(x,y) at Level 0, I'd put ObjectA in the List cause same Node, but what about ObjectB whose in a different Level, but same coords.

So just from the above theory/explanation or whatever you may call it. Can I conclude that the Nodes I check for Collisions should include Nodes from Root til the Node My Object is in + the SubNodes of Node my Object is in.

You might ask why not just store it in the same Level, well I heard from others that it's better if I store those overlapping ones at the parent node and it'd be good if I limit the amount of objects per node. So if the level is full, I need to send it up.

I'm sorry if this might be an easy question, it's just that I've pondered on this for 6 days now but I still can't figure it out. Please help! This is my last hope!

• Too Long To Read: How do I determine which Nodes to check Collisions for, there are the Parent Nodes, Sub Nodes and those Nodes that are the same Level as my Object's Node. I'm really confused on this. Aug 5, 2015 at 20:39

1 Answer

The answer is yes, of course.

You test object b against all L1 nodes in the root because that's where it is. If a node is hit, add it's objects to the short phase (object to object tests) list. Then recursively repeat the process against those child nodes which were hit. Do this until you determined to hit or miss all leaf nodes.

• There will be Nodes of Different Levels won't there? An Object of Level 1 can have Collision Checks with Level 0, Level 2, Level 5...etc(or is this wrong). It's just kind of hard for me to grasp what the criteria is of checking a specific node...To put it simply, a Tree has so many different Levels, if I were to find which Node are adjacent to me, it would be easy, but it's troubling me how I find what is the Levels of Node I check...I'm sorry if my English is bad or if I might have not got your point Aug 5, 2015 at 22:08
• Only if an L1 object has moved beyond the boundaries of it's node. Which should make it an L0 object anyway. Aug 5, 2015 at 22:14
• So say I have an ObjectA of L4 and my Tree's Leaf is at L8. I have an ObjectB same Coordinates as A but because the Node is full, it gets pushed to L3. Imagine this happens until Root Node, just from this, can I just conclude that I should check Collisions for all the Nodes from my Root to L4(the object I am checking collisions for). The SubNodes of L4(ObjectA node) will be Checked for Collisions as well? Sorry for the bother and thanks for the help! Aug 5, 2015 at 22:24