Jump to content
  • Advertisement
Sign in to follow this  

QuadTree traversal

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

Let me preface this by saying that I have never used data trees before so everything I'm saying here is all self taught and google researched over the last week.

Ok with that out of the way:

I have a quad tree set up for my side scrolling game. Each node has two array lists (they are array lists for convenience, they never get to have more than four members), one for data and one for children nodes.

I pass the root node entities (the data) and based on their x and y positions, it passes it to it's children, who pass it to their children and so on, until it is at a leaf node where it is either placed into the nodes data list, or, if the list is full (4 entities), the node is given four children and all 5 entities (original 4 plus the new one) are passed to its children.

My problem now is how do I go through and get them back when I want to use them?
All the traversal algorithms I've seen have given me all the nodes, but I only need the leaf nodes.
In addition, I really only need certain nodes based on which node the player is in.

Any help on this would be very welcome,

Share this post

Link to post
Share on other sites
If you have an algorithm that returns all nodes in the quadtree using recursion, all you have to do is check if a child node is contained in/intersected by the area you want to retrieve entities from. If it is not, you can ignore that entire branch of the tree. Something along the lines of this should work.

getEntitiesInRectangle(Node node, Rectangle rect, List output)
if node is leaf:
for every entity e in node:
if rect contains/intersects e: add e to output;
for every child n in node:
if rect contains/intersects n:
call getEntitiesInRectangle(n, rect, output)
Edited by lwm

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!