Members - Reputation: 205
Posted 08 August 2012 - 09:01 AM
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,
"Other than that, I have no opinion."
My Blog - Check it Out
Members - Reputation: 2105
Posted 08 August 2012 - 12:05 PM
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; else for every child n in node: if rect contains/intersects n: call getEntitiesInRectangle(n, rect, output)
Edited by lwm, 08 August 2012 - 12:06 PM.
current project: Roa