• Advertisement

Archived

This topic is now archived and is closed to further replies.

Moving objects and quadtrees

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

Ok, so I have set up a quadtree and I''m implementing it in my game. Here''s my problem: moving enemies don''t move from node to node, and I have no idea how to efficiently get them to. Right now, I''m taking all of my wall data, putting it in a linked list, and sending that list to a quadtree constructor, which breaks it down into units. I want to then be able to add various objects and quickly sort them into nodes, and to be able to keep track of moving objects, such as enemies. How can this be done?

Share this post


Link to post
Share on other sites
Advertisement
Well, I assume your quadtree leaves have some sort of boundary definition be it bounding boxes or spheres. The first step would be when an object is created and ''placed'', to run it through the quadtree as you might do anything else, until you actually place it in a leaf. I would keep a list in each leaf of the objects in it, and a pointer or some indicator on the object of what leaf it is in.

When an object moves, you can do a check to see if it''s still in the same leaf, and if not you could either just run it back down the tree or a better idea would be to start at the leaf and have some way of moving back up, since you would traverse less of the tree if you started at the leaf it was in and went up/around instead of starting at the top since in most cases, an object moving moves to a neighbor leaf, and even if it crosses over into another ''branch'', you still do not have to go up the tree very far to find out where it''s at.

That was the way I was planning on doing it, atm I use a variant of a quadtree and 2D bounding boxes to classify where objects are, and when they move, I check if they have moved from one subspace to another, and place them appropriately. The subspaces all keep a list pointing to the object, and each object keeps track of what subspace it is in.

Share this post


Link to post
Share on other sites
Quad tree operations on n objectrs are : n log4(n). So agorithmic complexity is not the issue. QT is a very good structure. The problem is the linear implementation factor. Decisive element for quadtree with dynamic operations in RT are :

a) a very fast allocator for nodes.
=> Use memory pools to store the nodes. (allco free is then less than 5 cycles)

b) be cache friendly.
=> pools are correct for that. Good idea : allocate 4 nodes at once to enhance continuity.

c) use a fast allocator for object lists in nodes.
Use a set of pools to allocate 1,2,4,8,16 pointer arrays quickly. It''s better than using intusive linked lists in your objects. To me objects should not know about the space partition implementation (Quad tree or Grid or BSP ...). You only have to store a pointer to the object reference in your object.

You''ll probably need, the operator
object -> node, position in the node list of objects.
This can be cached and be compacted in a customized 32 bits ID. For instance a 20(node index in the pool), 12(object index in the node list of objects) bitfield.


Share this post


Link to post
Share on other sites
Are those concerns really relavent on a 2+ gHz processor? And if so, can you give a threshold for number of objects were memory allocation times do become relavent from your experience? Like 1,000 objects, 10,000 objects ets... Thanks.

Share this post


Link to post
Share on other sites

  • Advertisement