Jump to content
  • Advertisement
Sign in to follow this  
mameman

Dynamic Objects in QuadTrees

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

I have a quad tree (level 3) and within each of the leaf nodes I have a linked list of static objects. Now I have other game entities that I want to move around the game world (and hence the quad tree). My question is what is the most efficient way of doing this?. I know that I have two choices (if there are more open to me please advise ;)). 1) Test all dynamic game entities that are within range of other dynamic objects. or 2) After dynamic game entities have been updated, check which leaf node(s) the objects are in and insert it into the list of objects that are at that node. Method (1) appears best because it doesn't involve inserting/removing nodes out of the tree. However if there are a large number of objects then this could effect performance. Method (2) looks best from a performance point of view as it is only checks objects that are within it's locality (in terms of collision). Also initially I will be using this for a limited number of objects (say a dozen) but I do want to expand on it so that it can handle a large number (pick one above 256). What would be best for me?. Advice/thoughts appreciated. MAMEman.

Share this post


Link to post
Share on other sites
Advertisement
why not a hybrid solution? Have the entities themselves store a "tag" (unsigned int) that says what node of the quadtree they are currently in. Then you can do your dynamic object check but do it based on this tag.

If two objects don't have the same tag, they can't be interacting. You may have instances where an object resides in multiple quads simultaneously in which case you may want to have a list of tags, but the idea is the same.

Good luck!

Share this post


Link to post
Share on other sites
DEhrman,

Actually that sounds pretty cool!. Since it doesn't involve having to insert and remove nodes at each frame. I can (like you say) "tag" the dynamic object(s). In my case it can only be 1, 2 or 4 nodes. Then compare the tags (the unsigned ints) before moving onto the more complex collision checks.

Great!. Thanks.

MAMEman.

[Edited by - mameman on May 15, 2007 10:04:45 AM]

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!