Data structures
Author
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.
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
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
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.
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.
Author
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.
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.
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; }}
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.
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.
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 ){ contained.erase( contained.begin( ) + i ); unit_found = true break; } } return unit_found;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
