Jump to content
  • Advertisement
Sign in to follow this  
syph

Using an stl::Multimap with collision detection

This topic is 4667 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
Advertisement
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
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!