Managing lots of game entities
Author
I have a bit of a problem, I am coding an asteroids clone and I have lists of objects (asteroids, player bullets, enemies, enemy bullets, etc) that I wan't to check collisions for. My collision checking routine has already gotten kind of messy.
Does anyone know of an elegant and efficient way to handle interactions between large amounts of different types of objects in a scene?
for large amount you need to look into spatial partitioning like a Quadtree or similar.
For some technique on sorting different types, you can check these two threads:
http://www.gamedev.net/community/forums/topic.asp?topic_id=265392
http://www.gamedev.net/community/forums/topic.asp?topic_id=215247
For some technique on sorting different types, you can check these two threads:
http://www.gamedev.net/community/forums/topic.asp?topic_id=265392
http://www.gamedev.net/community/forums/topic.asp?topic_id=215247
For Asteroids, the easiest is just to do the n-squared test of everything against everything. You probably won't have more than 30 object on screen, and doing circle-circle collision testing (which is what you should use for Asteroids) is very, very quick. 1000 tests per frame won't even make a modern computer wake up.
If all of your Asteroid, Bullet, Ship, etc objects derive from TestablePosition, and update x/y each frame, then you can do something like this:
Note that this can be made much smarter, by stopping when you find a single hit per object, or trying to find more than one hit, or putting objects in a quad tree or a hash grid to accelerate queries, etc. But this initial solution should get you going. If C++ is not your bag, then use whatever primitives allow easy insert, delete and iteration (like, a Perl hash would be fine).
If all of your Asteroid, Bullet, Ship, etc objects derive from TestablePosition, and update x/y each frame, then you can do something like this:
struct TestablePosition;std::set< TestablePosition * > gAllTestables;struct TestablePosition { TestablePosition() { gAllTestables.insert( this ); } ~TestablePosition() { gAllTestables.erase( this ); } float x, y, radius; TestablePosition * hitThisFrame;};struct HitTester { HitTester( TestablePosition * tp ) : tp_( tp ) { } void operator()( TestablePosition * o ) { if( o == tp_ ) return; float dx = (o->x - tp_->x); float dy = (o->y - tp_->y); float dr = (o->radius + tp_->radius); if( dx*dx+dy*dy <= dr*dr ) { tp_->hitThisFrame = o; } }};void FindHit( TestablePosition * tp ) { std::for_each( gAllTestables.begin(), gAllTestables.end(), HitTester( tp ) );}void FindAllCollisions() { std::for_each( gAllTestables.begin(), gAllTestables.end(), FindHit );}Note that this can be made much smarter, by stopping when you find a single hit per object, or trying to find more than one hit, or putting objects in a quad tree or a hash grid to accelerate queries, etc. But this initial solution should get you going. If C++ is not your bag, then use whatever primitives allow easy insert, delete and iteration (like, a Perl hash would be fine).
i just recently learned this, and i found it very very usefull. make all of your objects of the same base type (make sure all the functions your derived objects will call are virtual) then create a container class and create an instance of an object by using new and then store the refrence to this in a vector.
something like this (sort of pseudo) ...
snk_kid i think it was showed me how to do this without having add a template function, it was called "virtual constructor idiom?" i think, im still not sure how it works though. making add template is technically un-needed since the only objects you can add are derived type objects from a base type, but making it a template is no serious problem.
hope this helps.
EDIT: i forgot to put a destructor in the container class ... this is needed. just run through the vector and delete each element.
something like this (sort of pseudo) ...
class base{ // ... virtual void something ();};class asteroid{ // ... void something ();};class bullet{ // ... void something ();};class container{ std::vector < base * > refrences;public: template <class T> void add (T object) { T *p = new T (object); refrences.push_back (p); } void execute () { for (int n = 0; n < refrences.size (); n ++) refrences[n] -> something (); }};// where ever you want to do this ...container scene;scene.add <asteroid> (asteroid (// ... constructor ...));scene.add <bullet> (bullet (// ...));// thene you can run execute and every object will do]// collision detection, or whatever ...scene.execute ();snk_kid i think it was showed me how to do this without having add a template function, it was called "virtual constructor idiom?" i think, im still not sure how it works though. making add template is technically un-needed since the only objects you can add are derived type objects from a base type, but making it a template is no serious problem.
hope this helps.
EDIT: i forgot to put a destructor in the container class ... this is needed. just run through the vector and delete each element.
Quote:Original post by ekrax
i just recently learned this, and i found it very very usefull. make all of your objects of the same base type (make sure all the functions your derived objects will call are virtual) then create a container class and create an instance of an object by using new and then store the refrence to this in a vector.
I think he already had his entity system sorted and he had problems with his collision detection/response system. anyways if your gonna do it this:
Quote:Original post by ekraxtemplate <class T> void add (T object) { T *p = new T (object); refrences.push_back (p);}
your making redundant copies so make the parameter a constant reference e.g.
template <class T> void add (const T& object) { T* p = new T(object); refrences.push_back (p);}and as the template type parameter is used in the function arguements you don't need to explicitly state the type it can deduce the type from the instance passed to the function so this:
scene.add <bullet>(bullet());can just be this:
scene.add(bullet());Quote:Original post by ekrax
snk_kid i think it was showed me how to do this without having add a template function, it was called "virtual constructor idiom?" i think, im still not sure how it works though
not diffcult, just need a simplified example:
struct base { virtual base* clone() const = 0; virtual ~base() {}};struct derived1 : base { base* clone() const { return new derived1(*this); }};struct derived2 : base { base* clone() const { return new derived2(*this); }};int main() { base* ptr1 = new derived1; base* ptr2 = new derived2; base* ptr3 = ptr1->clone(); base* ptr4 = ptr2->clone(); base* ptr5 = ptr3->clone(); base* ptr6 = ptr1->clone(); delete ptr1, delete ptr2, delete ptr3, delete ptr4, delete ptr5, delete ptr6; return 0;}other alternatives are factory/abstract factory design patterns, sorry to sckoobs for making a detour from your problem.
Yes, basically the theme here is to work with an abstract bounding volume objects that each game object has. I used rectangles and left per-pixel tests for another day. You could even shrink your rect bounds so if a ship left a spray wake as part of its gfx then a bullet would pass thru the wake and not hit the ship. You could even make bunch of collision rects and slap them onto a sprite instead of doing per pixel tests. So if your asteroid sprite is irregular this could help. Just thought of these things. Kind of reminds me of multiple object aligned bounding boxes in 3D world.
I'd recommend Recursive Dimensional Clustering (RDC), this was a chapter in Game Programming Gems 2. It is pretty simple yet very effective.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
