# Data structures

This topic is 4344 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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).

http://www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html

##### 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 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 on other sites
Quote:
 Original post by daniel_i_lnife: 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 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 on other sites
Thanks, I just dont understand how to do: remove u from contained;

##### 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 ){          contained.erase( contained.begin( ) + i );          unit_found = true          break;       }   }  return unit_found;}