Data structures

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

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.

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.

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.

Thanks, I just dont understand how to do: remove u from contained;

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;}