Sign in to follow this  

Using an stl::Multimap with collision detection

This topic is 4305 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'm making a platformer using directX 9.0c / C++ and have been able to get the map working and scrolling properly. Neat stuff. My collision detection uses a brute force "loop through every tile and see if it collides with the hero" method, which was fine ... until my hero started shooting. ;) I've looked at quadtrees, but that seems overly complicated for what I'm doing. I can add a little inefficiency to my system since I have something like 300 fps (when not shooting). My first though was to use an STL multiset and save the hassle of creating all the quadtree stuff. Simply associate every object with its section of the fixed grid and its 8 neighbors. Then check collision just with other objects within these same sets. Thing is, I haven't seen _anyone_ mention this method, so I figure it must be horribly flawed in some way. This is my first game, and I'm trying to reduce the number of false steps (there have been many!) I take as I develop it. I'm just looking for a little advice that could save several nights of coding. Thanks all!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
What you're proposing is an implementation of spatial hashing. A quadtree or octtree has the advantage of being more adaptive to objects of widely varying sizes (and being more applicable to the problem of finding all the objects within a certain region, for purposes such as drawing all the objects in the currently visible region). For collision detection, spatial hashing can be very effective.

Using a multimap is an implementation detail. I think a more common implementation is to simply use a vector (containing lists of objects) and use the world coordinates to calculate the index into the vector. Using a multimap instead of a vector is a time/space tradeoff. In a sparsely populated region, the multimap will use less space, but locating objects in it will be slower than using a vector. Using a hash table is another possibility.

Share this post


Link to post
Share on other sites

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