Allegro.cc - Online Community

Allegro.cc Forums » Game Design & Concepts » collision handling

This thread is locked; no one can reply to it. rss feed Print
 1   2 
collision handling
imaxcs
Member #4,036
November 2003

Hi Allegators!

I have a problem on how to implement the collision handling in my game in a good style. Let's say I have a class CObject, a class CCollidingObject and furthermore the classes CShip, CPowerup, and CBullet. I think the names are pretty self-explanatory. Anyway the class hierarchy is like this:

CObject
|
CCollidingObject
|
CBullet, CShip, CPowerup

Now, I have a singleton-class which stores a list to all CCollidingObjects. The collision-detection is not the problem. What I need help with is where to respond on a collision. I have thought up two different approaches:

1.) Every CCollidingObject has a virtual method called "collided_with(CCollidingObject* object)" where the collision is handled. My problem with this is, that I will probably need to make downcasts to the specific classes. For example, if the player's ship collides with a power-up, the method needs to downcast to see if the object is a CPowerup and if it is, do the correct thing (gain hull energy or health, give more ammo, ...) I really don't like this approach because of the downcasts and I will most probably run into include-loops. :(

2.) The collisions are handled somewhere global in one place. The downside with this is, that I will also need downcasts to call the specific methods (like decrease_health(), destroy() or the like) and I would also need to make all these methods public. :(

I would like you to give me advice on how to resolve this. Is there a cleaner way (without downcasts at best) to do this? How would you do this?

Thank you for your time!

Kris Asick
Member #1,424
July 2001

I'm not an expert in OOP... yet... but I think if you want to stay fully OOP compliant, you may be stuck with having to downcast.

Though my approach with my game engine was to reduce collision detection to a process only some objects can initiate and which only the base class information is distributed in the process. The base class objects store enough basic information that knowing specifics about any particular derived class would be unnecessary. When the two objects collide, each object should primarily affect its OWN status, not each other's, beyond the basics.

Thus the level within the class hierarchy that the collision takes place at should not have anything critical to the collision further derived. IE: If two objects distribute kinetic energy by mass on an impact with each other, you wouldn't store the mass of the object in a derived class above the collision object, you would store it below or in the collision object itself.

So if you need to know whether something which hits a ship is a powerup or not and what kind of powerup it is, that information needs to be stored at the collision level, or closer to the base level, and then the ship, not the powerup, would process it.

...If that makes any sense at all. I'm still figuring all this OOP stuff out so I could be way off my rocker there... ???

--- Kris Asick (Gemini)
--- http://www.pixelships.com

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Audric
Member #907
January 2001

Collision is probably irrelevent for :
CBullet - CBullet
CBullet - CBonus
CBonus - CBonus

Which leaves you CShip - everything else (including CShip)
Now you only need to derive thevirtual CollidingObject::handle_collision_with (CShip & ship)
for all 3 classes.
Does it suit your needs?

edit: after further research, in the general case what you need is multiple polymorphism, which doesn't seem to be available in C++.
It would consist of a "method"

virtual collision(CollidingObject &a,CollidingObject &b)

that you would derive for all 3x3 combinations, and at run-time it would select which one to use depending on a and b.

Fladimir da Gorf
Member #1,565
October 2001
avatar

One way would be to have a map from two type IDs to a function pointer.

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

imaxcs
Member #4,036
November 2003

Thanks for your suggestions so far but I am not satisfied.

Kris Asick: If I would put all the necessary informations that I need to fully handle every collision into the CCollidingObject-class or even higher in the tree, it would defeat one of the most basic OOP-features. Why should a CCollidingObject have a member which stores the shield energy, as a ship would have? I really don't like that!

Audric: well, if for example a bullet collides with a ship, who would then destroy the bullet? Should the ship destroy the bullet? IMHO, when they collide the ship AND the bullet should both handle the collision, the ship should decrease it's health/shield energy, and the bullet should set some flag, so that it gets destroyed in the next frame. (I already figured out that having objects being destroyed at a global place is by far the best method)
Furthermore, consider I only have a linked list of all CCollidingObjects, so even calling your function would require me to do a down-cast. Apart from that, it would work for your scenario, but I also want objects like asteroids and other stuff which should also collide with ships and bullets. So, all in all it doesn't suit my needs! :(

edit:

Audric: that's a feature I miss in C++ since I have started using it! :-/

Flad: care to elaborate a bit more? I am not quite sure I did understand.

Tobias Dammers
Member #2,604
August 2002
avatar

First of all, divide the collision problem into two sub-problems: collision DETECTION and collision RESPONSE.
Only objects that MOVE require collision detection, all other objects are static and should only be a "passive" partner in any collision. This alone can drastically reduce the amount of computing needed for collision detection (e.g. by maintaining two separate lists for dynamic and static objects, or by sorting your list so that dynamic objects come first, allowing you to stop iterating when you hit a static object). Objects that trigger no collision response at all (backgrounds and decorative sprites, as well as particle effects and scores popping up when you kill an enemy) can be skipped for both the "active" (outer loop) and the "passive" (inner loop) iteration, so putting them at the very end of the list makes sense too.
Abstract collision detection behavior into a class hierarchy of its own:

cBoundingObject (pure virtual)
|
+- cBoundingSphere
|
+- cBoundingBox
|
+- cBoundingPoint
|
+- cBoundingLine
|
+- cWhateverBoundingThingy

Whether the actual collision check should be a member function or a global function is a matter of taste. If all your objects use the same bounding type, there is no need for an entire class hierarchy and virtual functions, but it's still a good idea to encapsulate the collision detection.

When it comes to collision response, you should group all possible sorts of collision responses into groups, such as:
- bounce
- deal damage
- explode
- be picked up and apply powerup
- ...
The class should have a set of member functions or variables to indicate the desired collision response. Since many of the responses require access to 2 objects, as well as object insertion / deletion, it is a good idea to keep the actual response code in the main game class (I usually call it cScene); it is not very OOP to have objects manipulate the main object list. Also, this is far more flexible, and usually faster, than the downcasting approach, since you can re-use the collision response code for totally unrelated types of objects, provided it is handled in the main game class. For example, a generic bullet could use linear non-accelerated movement, and no bouncing, while a missile class derived from it might use the same damage dealing, but "inherit" its bouncing code from the ship class.

--- EDIT ---
Your examples:
- not every class needs a shield, but the cCollisionObject should have a member function get_shield(), returning either cShield* (defaulting to NULL), or a number indicating the current shield load. I recommend encapsulating the shield code into its own dedicated structure, this allows you to put a shield on anything you want quite easily. This does NOT mean that cCollisionObject should have a member van cShield* shield; only classes where this makes sense should. Conversely, cCollisionObject() should have a member function take_damage(float), which will reduce shield / hull / ... or whatever is available, and marking the object as "dead" if necessary. For an indestructible object, this obviously does nothing.
- "dead" flags are a good idea, since they allow you to remove all dead objects in one go, and clear all references to dead objects before removing them. It is not a good idea to have individual objects messing around with the global list.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

Audric
Member #907
January 2001

edit: I didn't precise below, this is about collision RESPONSE

Personnally, I use a very Actor-oriented model:

What does a bonus do when it touches something ?
It informs it that a bonus wants to hug him - if the target acknowledges, the bonus dies.

What does a enemy bullet do when it touches something ?
It informs it that it has come in contact. If target acknowledges a positive hit, the missile becomes a hit flash, then later dies.

etc.

The messaging is simply done by calling for example: bool actor::hit_by_missile(missile * this)
Each class derives its own, the default code for all interaction is simply
{ return FALSE; } // I don't care
Also, to reduce the number of checks, at the base class level I do a simpleif (active_actor->active_flags & passive_actor->passive_flags)

Tobias Dammers
Member #2,604
August 2002
avatar

I prefer having the scene inform the objects involved that they are touching, and decide what to do with them according to their stats.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

ImLeftFooted
Member #3,935
October 2003
avatar

The common practice is for CCollidingObject to handle it on movement. If any sub-class of CCollidingObject ever wants to move it must call a movement function implemented by CCollidingObject. That function checks if the new position collides with any other CCollidingObjects.

Pretty simple really.

No down-up or any casting at all.

Audric
Member #907
January 2001

You assume that only movement can cause a collision.
Don't forget "growing" and "state changing" (ie: from invis/invulnerable to vulnerable)
I'm thinking of growing especially for (dangerous/damaging) explosions.

Well, anyway, do what's most suited for the game at hand. A classic shoot'em up will typically have 70% objects on screen as player projectiles, so better "optimize" for this situation.

ImLeftFooted
Member #3,935
October 2003
avatar

All the events that can trigger a collision must be implemented in CCollideObject. It is the OOP way.

Kris Asick
Member #1,424
July 2001

Quote:

If I would put all the necessary informations that I need to fully handle every collision into the CCollidingObject-class or even higher in the tree, it would defeat one of the most basic OOP-features. Why should a CCollidingObject have a member which stores the shield energy, as a ship would have? I really don't like that!

Why do you need that much information to be accessible?

In the case of a weapon hitting a ship, the weapon has a damage value, the ship has its shields. A collision is detected by the system and both objects run their collision routines.

Ship Collision:
Is target object a weapon? Yes
Call target object function GetDamageVal().
Decrease shields by damage value retrieved from target object.

Weapon Collision:
Is target object a weapon? No
Is target object a ship? Yes
Queue self to be destroyed after collision detection is over.

You never have to send the damage or shield data through the collision class since the ship class has its own method of handling collisions and so does the weapon class.

Does that make more sense?

--- Kris Asick (Gemini)
--- http://www.pixelships.com

--- Kris Asick (Gemini)
--- http://www.pixelships.com

ImLeftFooted
Member #3,935
October 2003
avatar

class Collidable {
 void moveTo(int x, int y)
 {
  if(.. collision ..)
   this->onCollision(otherCollidablePointer);
 }
 virtual void onCollision(Collidable*) {}
};

class Ship : public Collidable {
 ...
};
class Missle : public Collidable {
 virtual void onCollision(Collidable *c)
 {
  Ship *s = dynamic_cast<Ship*>(c);

  if(s)
   s->inflictDamage();

  dienow();
 }
};

This is the proper OOP style. If you're going to do differen't go for it but know that you are not doing OOP style.

Audric
Member #907
January 2001

Quote:

This is the proper OOP style. If you're going to do differen't go for it but know that you are not doing OOP style.

no comments...

axilmar
Member #1,204
April 2001

Here is a perhaps easier way to handle the problem (If only C++ had multimethods!): have a base class CCollision with a virtual method 'execute':

class CCollision {
public:
    virtual void execute() = 0;
};

Then have a template subclass with two types, one for each type of object; this class acts as a container of the two types:

1template < class T1, class T2 > class CBinaryCollision {
2public:
3 CBinaryCollision(T1 *firstObject, T2 *secondObject) : m_firstObject(firstObject), m_secondObject(secondObject) {
4 }
5 
6 T1 *getFirstObject() const {
7 return m_firstObject;
8 }
9 
10 T2 *getSecondObject() const {
11 return m_secondObject;
12 }
13 
14private:
15 T1 *m_firstObject;
16 T2 *m_secondObject;
17};

Then have a specific subclass which handles specific types. For example, to manage the collision between the ship and the powerup, you can do the following:

class CShipPowerUpCollision : public CBinaryCollision<CShip, CPowerUp> {
public:
    CShipPowerUpCollision(CShip *ship, CPowerUp *powerUp) : CBinaryCollision<CShip, CPowerUp>(ship, powerUp) {
    }

    virtual void execute() {
        CShip *ship = getFirstObject();
        CPowerUp *powerUp = getSecondObject();
        if (ship->collidesWith(powerUp)) {
            ship->power++;
        }
    }
};

Then place all collision objects in a list which you frequently scan, invoking the 'execute' method:

std::list<CCollision *> collisions;
collisions.push_back(new CShipPowerUpCollision(myShip, myPowerUp));
while (gameLoop) {
    ...
    for(std::list<CCollision *>::iterator it = collisions.begin(); it != collisions.end(); ++it) {
        CCollision *collision = *it;
        collision->execute();
    }
}

EDIT:

If there are not many collisions to test, perhaps the procedural approach is best:

while (gameLoop) {
    ...
    testCollision(myShip, powerUps);
    testCollision(myShip, bullets);
    ...
}

imaxcs
Member #4,036
November 2003

Thank you again for your help!

It seems there is no 100 percent clean method to do this. But you all gave quite some cool stuff to make it at least come close. I especially like axilmar's idea! Thank you! :)

edit: ok, axilmar, I really like your approach but there is one thing I am still not fond of.
In your code:

std::list<CCollision *> collisions;
collisions.push_back(new CShipPowerUpCollision(myShip, myPowerUp));
while (gameLoop) {
    ...
    for(std::list<CCollision *>::iterator it = collisions.begin(); it != collisions.end(); ++it) {
        CCollision *collision = *it;
        collision->execute();
    }
}

How do I check, which collision has occured? How do I know it's a CShipPowerUpCollision and not something else?

Tobias Dammers
Member #2,604
August 2002
avatar

Quote:

How do I check, which collision has occured? How do I know it's a CShipPowerUpCollision and not something else?

By checking the types of the colliding objects, duh.
Either dynamic_cast the objects (which is ugly), or give them virtual member functions that return some value with which you can recognize them.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

axilmar
Member #1,204
April 2001

Quote:

How do I check, which collision has occured? How do I know it's a CShipPowerUpCollision and not something else?

You shouldn't do that! the whole point of putting the collision code into objects is that you don't have to do that. Put all the code that must be executed in a collision inside the CCollision subclass.

Here is a wikipedia article about multimethods:

multimethods

ImLeftFooted
Member #3,935
October 2003
avatar

You can use the "CShipPowerUpCollision" system if you want, but your project wont last more then a week when you realize how many utterly useless objects you've created and what a pain in the ass it is. Then your code will turn so ugly you'll give up on the project and start over :'(

But, some lessons have to be learned the hard way.

piccolo
Member #3,163
January 2003
avatar

this works nice the script pointer hard coded id based.

1 
2 
3void UnitList::setup_collision(DATAFILE *music)
4{
5
6 textout(screen,font,"setup_collision called ",100,320,makecol(6,255,255));
7 
8
9 int i,j;
10
11 for( i = 0; i < numItems; i++ )
12 {
13
14 for( j = 0; j < numItems; j++ )
15 {
16 if(listofUnits<i>->get_UnitObject()->Get_inarea()==listofUnits[j]->get_UnitObject()->Get_inarea())
17 {
18 if(listofUnits<i>->get_UnitObject()->is_collision(listofUnits[j]->get_UnitObject()) )
19 {
20 if(listofUnits<i>->get_UnitObject()->Get_id() != listofUnits[j]->get_UnitObject()->Get_id())
21 {
22 textout(screen,font," collision detected ",400,320,makecol(6,255,255));
23 
24 listofUnits<i>->get_UnitObject()->Set_collision(true);
25 listofUnits[j]->get_UnitObject()->Set_collision(true);/// this has the sam bug from project 3 setting point useable
26 
27
28if(listofUnits[j]->get_UnitObject()->Get_id()!=computerId)
29{
30 targget=listofUnits[j]->get_UnitObject()->Get_id();
31}
32else
33{
34 targget=listofUnits<i>->get_UnitObject()->Get_id();
35}
36
37 
38 if(listofUnits<i>->get_UnitObject()->type ==2)
39 {
40 listofUnits<i>->get_UnitObject()->triggered=true;
41 
42((TriggerConfig*)listofUnits<i>)->TriggerObject.runScript(((CharacterConfig*)listofUnits[j])->get_UnitObject(),music);
43 //listofUnits<i>->get_UnitObject()->set_onewhotiggeredme(*(listofUnits[j]->get_UnitObject()));
44/*
45if(listofUnits<i>->get_UnitObject()->scriptId==1)
46{
47 listofUnits[j]->get_UnitObject()->Set_inarea(1);//rig
48 if(computerId==listofUnits[j]->get_UnitObject()->Get_id())
49 {
50 ch_current_area = 1;//rig
51 }
52}
53else if(listofUnits<i>->get_UnitObject()->scriptId==2)
54{
55 listofUnits[j]->get_UnitObject()->Set_inarea(2);//rig
56 if(computerId==listofUnits[j]->get_UnitObject()->Get_id())
57 {
58 ch_current_area = 2;//rig
59 }
60}
61else if(listofUnits<i>->get_UnitObject()->scriptId==3)
62{
63 listofUnits[j]->get_UnitObject()->Set_inarea(3);//rig
64 if(computerId==listofUnits[j]->get_UnitObject()->Get_id())
65 {
66 ch_current_area = 3;//rig
67 }
68}
69
70else if(listofUnits<i>->get_UnitObject()->scriptId==4)
71{
72 listofUnits[j]->get_UnitObject()->Set_inarea(4);//rig
73 if(computerId==listofUnits[j]->get_UnitObject()->Get_id())
74 {
75 ch_current_area = 4;//rig
76 }
77}
78*/
79 
80
81// listofUnits<i>->get_UnitObject()->runScript();
82 listofUnits<i>->get_UnitObject()->triggered=false;
83 
84 // listofUnits<i>->get_UnitObject()->set_onewhotiggeredme(NULL);
85 }
86 break;//list of ele
87 }
88 else
89 {
90 listofUnits<i>->get_UnitObject()->Set_collision(false);
91
92 }
93 }
94 else
95 {
96 listofUnits<i>->get_UnitObject()->Set_collision(false);
97 
98 }
99 }
100
101 }
102
103 }
104 textout(screen,font,"setup_collision done ",100,350,makecol(255,6,255));
105}

one of the objects

1 
2 
3void Trigger::runScript(Unit *onewhotiggeredme,DATAFILE *music)
4{
5 if(triggered== true)
6 {
7 
8//if(attributess.attackstamana >= 50) //each telaport takes 50
9//{
10//attributess.attackstamana = attributess.attackstamana - 50; //attack take 50 stamana points to do
11//onewhotiggeredme->Set_inarea(2);
12//if(attributess.attackstamana < 0)
13//{
14//attributess.attackstamana=0;
15//}
16 
17 switch(scriptId)
18 {
19 case 1:
20 //do this
21 onewhotiggeredme->Set_inarea(1);
22if(computerId==onewhotiggeredme->Get_id())
23 {
24 play_sound(SAMPLE_MAGIC,music);
25 ch_current_area = 1;//rig
26 stop_song();
27 play_song(MIDI_SPIKKO,music);
28 
29 }
30 break;
31 case 2:
32 //do this
33 onewhotiggeredme->Set_inarea(2);
34if(computerId==onewhotiggeredme->Get_id())
35 {
36play_sound(SAMPLE_MAGIC,music);
37 ch_current_area = 2;//rig
38 stop_song();
39 play_song(MIDI_BATTLE,music);
40 }
41 break;
42 case 3:
43 //do this
44 onewhotiggeredme->Set_inarea(3);
45if(computerId==onewhotiggeredme->Get_id())
46 {
47play_sound(SAMPLE_MAGIC,music);
48 ch_current_area = 3;//rig
49 stop_song();
50 play_song(MIDI_FROG,music);
51 }
52 
53 break;
54 case 4:
55 //do this
56 onewhotiggeredme->Set_inarea(4);
57if(computerId==onewhotiggeredme->Get_id())
58 {
59play_sound(SAMPLE_MAGIC,music);
60 ch_current_area = 4;//rig
61 stop_song();
62 play_song(MIDI_GOTA,music);
63 }
64 break;
65 }
66 
67 
68 
69 
70 
71 
72 }
73 
74// }
75
76 
77}

wow
-------------------------------
i am who you are not am i

axilmar
Member #1,204
April 2001

Quote:

You can use the "CShipPowerUpCollision" system if you want, but your project wont last more then a week when you realize how many utterly useless objects you've created and what a pain in the ass it is. Then your code will turn so ugly you'll give up on the project and start over :'(

But, some lessons have to be learned the hard way.

Hey, I couldn't agree more. That's why I wrote that if his collision detection needs are simple, the best approach is the procedural one.

imaxcs
Member #4,036
November 2003

Thanks for all your thoughts! Although I hope that your assumptions concerning my project failing are wrong. ;)

I use a CCollisionHandler which's process-method currently looks like this:

1void CCollisionHandler::process(float delta_time)
2{
3 list<CCollision*> collisions;
4 
5 // check for collisions
6 for (list<CCollidingObject*>::iterator it_outer = CObjectList::o().begin_colliding();it_outer != CObjectList::o().end_colliding();it_outer++)
7 for (list<CCollidingObject*>::iterator it_inner = it_outer;it_inner != CObjectList::o().end_colliding();it_inner++)
8 if (it_inner != it_outer && (*it_outer)->get_attitude() != (*it_inner)->get_attitude())
9 {
10 // first make a bounding-box-collision-detection
11 float outer_center_x = (*it_outer)->get_x() + (*it_outer)->get_w() / 2;
12 float outer_center_y = (*it_outer)->get_y() + (*it_outer)->get_h() / 2;
13 float outer_w = (*it_outer)->get_w();
14 float outer_h = (*it_outer)->get_h();
15 
16 float inner_center_x = (*it_inner)->get_x() + (*it_inner)->get_w() / 2;
17 float inner_center_y = (*it_inner)->get_y() + (*it_inner)->get_h() / 2;
18 float inner_w = (*it_inner)->get_w();
19 float inner_h = (*it_inner)->get_h();
20 
21 if (fabs(outer_center_x - inner_center_x) < (outer_w + inner_w) / 2.0f
22 && fabs(outer_center_y - inner_center_y) < (outer_h + inner_h) / 2.0f)
23 { // bounding-box hit detected
24 Collision collision = (*it_outer)->get_poly()->GetCollision(*((*it_inner)->get_poly()), Placement(Vec2D((*it_outer)->get_x(), (*it_outer)->get_x())), Placement(Vec2D((*it_inner)->get_x(), (*it_inner)->get_x())));
25 if (collision.IsCollision())
26 { // pixel-perfect hit detected
27 CCollision* collision = 0;
28 try
29 {
30 collision = new CCollision(*it_inner, *it_outer);
31 }
32 catch (CInvalidParameterException& e)
33 {
34 CLog::write("Could not create collision: " + e.get_message(), CLog::ERROR_);
35 continue;
36 }
37 
38 collisions.push_front(collision);
39 }
40 }
41 }
42 
43 //CLog::write(collisions.size());
44 
45 // process the collisions
46 for (list<CCollision*>::iterator it = collisions.begin();it != collisions.end();it++)
47 {
48 if ((*it)->get_type() == CCollision::ENEMYSHIP_WITH_PLAYERBULLET)
49 {
50 CShip* ship = dynamic_cast<CShip*>((*it)->get_o1());
51 CBullet* bullet = dynamic_cast<CBullet*>((*it)->get_o2());
52 
53 ship->CHurtable::hurt(bullet->get_damage());
54 bullet->CDestroyable::set();
55 
56 // explosion
57 CExplosion* explosion = 0;
58 try
59 {
60 explosion = new CExplosion(bullet->get_explosion(), bullet->get_x(), bullet->get_y());
61 }
62 catch (CInvalidParameterException& e)
63 {
64 CLog::write("Failed to create new explosion: " + e.get_message());
65 }
66 CObjectList::o().add(explosion);
67 }
68 else if ((*it)->get_type() == CCollision::PLAYERSHIP_WITH_ENEMYBULLET)
69 {
70 CShip* ship = dynamic_cast<CShip*>((*it)->get_o1());
71 CBullet* bullet = dynamic_cast<CBullet*>((*it)->get_o2());
72 
73 ship->CHurtable::hurt(bullet->get_damage());
74 bullet->CDestroyable::set();
75 
76 // explosion
77 CExplosion* explosion = 0;
78 try
79 {
80 explosion = new CExplosion(bullet->get_explosion(), bullet->get_x(), bullet->get_y());
81 }
82 catch (CInvalidParameterException& e)
83 {
84 CLog::write("Failed to create new explosion: " + e.get_message());
85 }
86 CObjectList::o().add(explosion);
87 }
88 delete (*it);
89 }
90 
91 collisions.clear();
92}

In the first part, I check all objects for collisions and create CCollision-objects which are saved in a temporary list. In the second part, I handle all the collisions based on it's type.

Works quite nice, so I am pleased. ;)

edit: damn, piccolo you are random!

ImLeftFooted
Member #3,935
October 2003
avatar

I suppose that could work, assuming all projectiles are implemented as 'bullets'. You've sorted created your own OOP paradigm without using C++ syntax.

std::lists are quite bloated by the way, using them might hurt your fps.

Tobias Dammers
Member #2,604
August 2002
avatar

Quote:

std::lists are quite bloated by the way, using them might hurt your fps.

How so? A list uses some extra memory for the list structure (3 pointers per node plus 2 for the head and tail nodes IIRC, so 12n + 8 bytes of overhead for n objects on a typical 32 bit system), true. But it all depends on what you are doing.

Lots of random insertions / deletions? Lists are your friend. The time you save in memory reallocation due to vector resizing should easily compensate for the memory overhead, unless we're talking thousands and thousands of objects.
OTOH, if you can live without random insertion, and use "dead" flags for an en-bloq deletion (by copying the live objects to a new vector), a vector or some other type of dynamic array may be faster. A custom dynamic array can sometimes exploit some special properties of your objects, which allows for certain optimizations (e.g. short-circuiting some loops); this may or may not increase your performance. (If your custom dynamic array is badly sub-optimal, it might actually be slower than any STL container...)
I suggest you code in a way that allows for easy switching between the two container types, and let the profiler decide.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

ImLeftFooted
Member #3,935
October 2003
avatar

std::list goes out of the way to support a large number of features. This bloat has a high cost. If you can manage to make your list simpler and not require these advanced features you will be saving a lot of overhead.

Quote:

How so? A list uses some extra memory for the list structure (3 pointers per node plus 2 for the head and tail nodes IIRC, so 12n + 8 bytes of overhead for n objects on a typical 32 bit system), true. But it all depends on what you are doing.

Yes there is some memory overhead and something tells me its larger then this (maybe some test-cast programs are in order?) but memory is not my main concern.

iterating a list is costly, with at the very least a pointer lookup per iteration. A pointer lookup typically will cost you a whole cycle. So the overhead is in actually iterating the list, not insertion and deletion.

If you must insert randomly and require deletes to happen instantly, then you will be forced to use std::list. But an experienced coder will realize that most list uses can be achieved without these two requirements.

Lets take an example. Say you had a particle engine. Particle engines are always trying to cram more particles and more effects into the game without hurting the frame rate. Every little bit of optimization counts.

In order to avoid having to resize your list, you can employ a simple trick of adding a flag to each particle object specifying if its alive or not. Instead of actually removing the element and reallocating the whole array, you can simply flag the element as dead and re-use it when you have to create new particles later on.

This technique is used in a project I'm working on currently. I'm going to report the FPS for level 1 during normal place as well as the particle count. I'm then going to switch over to a std::list type and report the same results. (I'll put them in my next post / edit).

[edit]
Alright, using the as-is vector style:
58 particles on screen = 95 fps
Using list:
51 particles on screen = 91 fps

So the difference isn't amazingly large in this case, but the more particles the more dramatic the effect.

 1   2 


Go to: