Sign in to follow this  

Action / RTS quad tree algorithm needed

This topic is 3727 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 need for a bunch of units that move around to quickly find all the other units within N distance of itself. This is a 2D space game and the units may 'stack'. These units will also frequently move around. I have been told what I need is a quad tree which is very good at space searches, but mostly they are poor handling objects that move around within them. I was also told that there are some implementations of quad trees that do a decent job of handling objects that move around. Is there any example of this someone can point me to?

Share this post


Link to post
Share on other sites
Meh. I would use a simple "bin" approach. Divide your map into square sections (the bins) slightly larger than the distance you want to check. When you update a unit's position, set it up in the correct bin using the integer quotient of its x and y position.

Then when you want to find all units within N distance of a given unit, you only need to search its bin and the 8 bins around it.

Cache the distances you calculate if there is a good chance the other units will perform the same check on you.

Share this post


Link to post
Share on other sites

This topic is 3727 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this