🔒 Locked

QuadTree questions

Started by Toolmaker Jul 1, 2006 at 12:58 PM 0 replies 600+ views

Original Post

216

Jul 1, 2006 at 12:58 PM

I'm currently attempting to implement a quadtree using this article here on GDNet. I intend to use it to store units in my 2D RTS game, written in C#. However, I do have a few questions: 1) Is it necessary to store my tree in an array? Or can I use a standard tree layout where each node contains 4 child nodes? 2) From what I can tell, the QT splits up the map in zones(obviously, since it's the purpose of it), but how do I handle if the current camera is in 2 leafs on the tree? Traverse both leafs and draw the units in the leafs that are in the actual bounds of the camera? 3) Currently, I use a Point to determine the bounds of each zone. First point is the top left, and the second one is bottom right. I want to store units by position, so this means, each cell is 16x16. How do I go on with this when creating the QT? Give total size of the zone, and a minimum size of w/h and then keep iterating until I reach 16x16? Toolmaker

Evil Steve

382

Evil Steve

Jul 1, 2006 at 1:42 PM

Quote:
Original post by Toolmaker
1) Is it necessary to store my tree in an array? Or can I use a standard tree layout where each node contains 4 child nodes?

You can use a tree container, yes. But usually it's more efficient to store 4 pointers in the node, each pointing to a child node.

Quote:
Original post by Toolmaker
2) From what I can tell, the QT splits up the map in zones(obviously, since it's the purpose of it), but how do I handle if the current camera is in 2 leafs on the tree? Traverse both leafs and draw the units in the leafs that are in the actual bounds of the camera?

You traverse the entire tree, checking if the current node is in the bounds of the camera. If it is, then your recurse (or itterate) to the 4 child nodes. If this is a leaf node, then you render the contens of it. If this node isn't in the bounds of the camera, then you don't render it at all.

Quote:
Original post by Toolmaker
3) Currently, I use a Point to determine the bounds of each zone. First point is the top left, and the second one is bottom right. I want to store units by position, so this means, each cell is 16x16. How do I go on with this when creating the QT? Give total size of the zone, and a minimum size of w/h and then keep iterating until I reach 16x16?

If you store the position (in map-space) of the top-left corner of the node, then you can determine the position of each unit in the node by offsetting it's position by the position of the node itself.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.