Sign in to follow this  

data structure for moving objects

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

basicly i have a 2d game where there is some people and bullets and tiles. my tiles are unmoveable so they can be sorted when i load the map and the collision is really fast. but with my bullets in a std::list and my dudes in a std::vector to check collision i have to iterate thought all bullets and all dudes and check each bullet for each dude for collision. i dont wana sort the list or the vector based off of the x or y because its slower. is there a way to sort a data structure of anykind at run time every frame to reduce my number of collision tests or will it hurt me more. right now if i make a few more dudes then they make a few more bullets and all of a sudden i get exponential speed loss for adding the dudes. :( THX

Share this post


Link to post
Share on other sites
Divide your space. You can try a grid-like approach, subdividing your level in many "nodes", and placing your entities doing simple bounds chekcing. Then you just test an entity with the ones in the same node. When an entity move, check if it goes over the node bounds, and if it does, assign it to another node.
Take care with this: each entity could need to be in up to four nodes at the same time.

Or you can try looking into quadtrees. It is a recursive data structure: you basically divide the entire level space in four nodes, then every node is divided in other four nodes and so on. You stop when you get to a certain level. By the way, it could end up being too much for your 2d game.

Share this post


Link to post
Share on other sites
I wrote a demo that had 4000 fish all schooling at 70 fps, each one doing a proximity check every frame and moving based on near-by fish. To partition, I used a structure like:

struct Fish_id
{
unsigned int fish_idx : 16;
unsigned int x : 16;
unsigned int y : 16;
unsigned int z : 16;
};

Then each frame, each Fish_id was calculated based on the fish's position in space and the desired grid cell size, and the list was sorted x, y, z. Then for each Fish_id, a proximity check was done based on the surrounding 27 cell cube. This check is very fast because you just binary search until you find one value in the range, then iterate forward and backward until the next/previous Fish_id is outside the query range, and just keep fish that satisfy your specific query. If several fish had the same Fish_id, the proximity check only needed to be done once and the same result_set could be used for all fish that had == Fish_id.

The cool thing about this method is that you're not sorting the Fish themselves, just this 8-byte structure, so it's much faster and not 'obtrusive'. You could easily shave it down to 4 bytes by eliminating z, and making x and y both 8 bits.

Share this post


Link to post
Share on other sites

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