Sign in to follow this  
daniel_i_l

Data structures

Recommended Posts

I want to speed up collision detection between units so I've divided my map into squares and want each square to hold information about all of the units in the square, then each unit checks collision only with the units in his square. Also, the units should be able to put themselves into the square's memory and then remove itself. I though about having each square hold a stl vector of pointers to the units in it's square, but then how would a unit be able to remove himself from one square and put himself in another (if it's moveing for example) ? Thanks.

Share this post


Link to post
Share on other sites
You could use a quadtree/octree (2d vs. 3d), a kd-tree or a combination of both or another kind. There's lots of spatial dividing/separation (it's called someting else but cannot quite remember the last word) methods like the one you've made available around the net.

But a simple solution for your problem would probably be to let the objects register themselves in a manager, and let that manager decide when and where they should go (eg. in what the squares they should be placed).
That's the solution I've made for my quadtree and it works like a charm (and the whole thing is lighting fast too, for my needs at least :D).

Here's a link for how to build a quadtree:
http://www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html

Share this post


Link to post
Share on other sites
By letting the unit have a pointer back to the "square" (and hence indirectly to the vector) being in. Moreover, by granting access to the square, the unit is able to get pointers to the surrounding squares.

However, please notice that collisions between units in neighboured squares may occur. So either you have to overlap the squares by an amount of maximal unit extent, or else check collision also with the units of the neighboured squares if the unit is close enough to te squares border.

Share this post


Link to post
Share on other sites
nife: that sounds like a good idea, but how is the manager built, and how does it place and remove the units?

haegarr: I don't understand how a pointer to the square would help?

I'm rather new to data structures so any clarification would be appreciated.
Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by daniel_i_l
nife: that sounds like a good idea, but how is the manager built, and how does it place and remove the units?

haegarr: I don't understand how a pointer to the square would help?

I'm rather new to data structures so any clarification would be appreciated.
Thanks.


You use the pointer in order to "know about" the containing Square, so that the unit can communicate with that square. It looks something like:


class Unit {
Square* holder;
// other stuff
public:
void move(int dx, int dy) {
x += dx; y += dy;
// other checking logic
holder = holder->notifyMoved(this, dx, dy);
}
};

class Square {
vector<Unit> contained;
Square* left, right, up, down;
// other stuff
public:
Square* notifyMoved(Unit* u, int dx, int dy) {
if (u is no longer within my bounds) {
remove u from contained;
Square* target = (left/right/up/down, as appropriate);
target->add(u);
return target;
}
return this; // otherwise
}
void add(Unit* u) {
add u to contained;
}
}

Share this post


Link to post
Share on other sites
A nice overview of a common grid-based method for broad phase collision detection is at:

http://www.harveycartel.org/metanet/tutorials/tutorialB.html

We did something similar in a commercial game currently under development. It works pretty well.

If you really want to delve into the nitty gritty details, have a look at "Real-Time Collision Detection" by Christer Ericson. His section on Uniform Grids is really good.

Share this post


Link to post
Share on other sites
Zahlman's pseudocode really shows you how to accomplish that. However, if you explicitly want to know how to remove something from a std::vector it is very easy.

// lets say this is in Zahlman's Square class...
bool removeUnit( Unit* unit ){
size_t const unit_count = contained.size( );
bool unit_found = false;
for( size_t i=0; i < unit_count; ++i ){
if( unit == contained[i] ){
contained.erase( contained.begin( ) + i );
unit_found = true
break;
}
}
return unit_found;
}

Share this post


Link to post
Share on other sites

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