3
\$\begingroup\$

I am working on a game with a lot of bullets, currently every second it loops through a vector of bullet objects and checks if its marked for erasure or not.

if (timer2>=120){

    auto it = Bulletlist.begin();
    while (it != Bulletlist.end())
    {
    if ((it->del)) {
             it = Bulletlist.erase(it);
         }  
         else {
             ++it;
         }
    }
    timer2=0;
    }else{
    timer2++;
    }

This works fine for around 0-200 bullets, however when I try to scale it larger the delay becomes very noticeable. I am still very new to C++, And was curious if there is a better way of doing this. The bullet class automatically marks itself for deletion when it goes out of bounds.

    int update(){
    if (acceleration!=0){
    if (speed < acceleration){
    speed+=increment;
    }
    }
    x=(speed*cos(angle)) + x;
    y=(speed*sin(angle)) + y;

    if (x<0) del=true;
        if (x>1000) del=true;
        if (y<0) del=true;
        if (y>750) del=true;
    circ.setPosition(x,y);
    window.draw(circ);
};

Edit: Bullets are generated right now on a loop within a enemy class

void shoot(int which){
    Bullet B1;
    B1.setsprite();
    currentangle+=(6.2832/bnum)+0.05;
        B1.setvars(x,y,currentangle*which,1.f,2.f,0.01f);
    Bulletlist.push_back(B1);
    }
    void update(){
     movtimer+=0.01f;
     //x += sin(movtimer);
     //std::cout<<x;
     //printf("\n");
     sprite.setPosition(x,y);
      if (timer>=10){
      for (int i=0; i<bnum; ++i) {
      shoot(1);   
      }
      timer=0;
      }else{
      timer++;
      }
      window.draw(sprite);
      for (std::vector<Bullet>::iterator it = Bulletlist.begin() ; it !=    Bulletlist.end(); ++it){
       it->update();
      }
```
\$\endgroup\$
  • \$\begingroup\$ You might want to add how you generate your bullets too. You would not need to delete your bullets. \$\endgroup\$ – Vaillancourt Sep 20 at 17:31
  • \$\begingroup\$ @AlexandreVaillancourt Added how they are generated. \$\endgroup\$ – Sam Boman Sep 20 at 17:38
  • \$\begingroup\$ eeek! Change your vector for a std::list! That's not the solution to your issue, but that's a quick fix. \$\endgroup\$ – Vaillancourt Sep 20 at 17:42
  • 2
    \$\begingroup\$ If performance is an issue, you might wanna use a design method called object pooling. What you do is that you, at the start-up of the game/level/scene, fill a container with a fixed number of objects (bullets in this case). When a bullet is supposed to be shot in the game, the code retrieves a bullet from the container, marks it as used, moves it across the screen, renders it and whenever it should be destroyed, stop rendering it and finally mark it as free so the code knows it's ok to pick that bullet from the container later. Destroy the objects at game shutdown. \$\endgroup\$ – Daniel_1985 Sep 20 at 19:57
  • 2
    \$\begingroup\$ @Daniel_1985 This looks a bit like what I hinted! You might want to turn that into an actual answer so that people can vote :) \$\endgroup\$ – Vaillancourt Sep 20 at 23:15
5
\$\begingroup\$

You're using a std::vector<Bullet>. This has the advantage of keeping data contiguous in memory, so iterating over it is fast (it has something to do with cache efficiency vs cache misses).

The way you're using it is slow.

auto it = Bulletlist.begin();
while (it != Bulletlist.end())
{
  if ((it->del)) {
    it = Bulletlist.erase(it);
  }  
  else {
    ++it;
  }
}

When you erase an item, it has to make sure that the order is preserved, and that the data is still contiguous in memory. To do so, it will move (or copy) all the items that come after the erased one so that it "fills the hole" left. This is very long.

There are a couple of "cheap" alternatives:

  • Use a std::list instead of a std::vector. The list will preserve the order, but does not have the constraint of keeping the items contiguous in memory (at the cost of a little speed).
  • Use a smart pointer such as std::unique_ptr to store your objects. You'll also lose a bit of speed during the iteration because the code will jump all over in memory too, but your removal of the bullets will be much faster because copying/moving a smaller object is faster.

More complex alternative involve to copy (or move, if your Bullet is move-able) a bullet from the end of your vector to the "slot" where the to-be-deleted Bullet is.

It goes a bit like this (pseudo-code):

int index = 0
while index < vectorSize
  if vector[index] is to be deleted
    vector[index] = vector.lastElement
    vector.popLastElement
  else
    index ++

You could also evaluate the cost of having dead bullets in your collection: if it's not that high, keep them there, then when you need to add a new one, instead of creating one, resurrect one that is dead (and keep an index to it to go from there when you'll be seeking a new bullet spot). That's a bit like object pooling. I haven't tried that personally.

I'm sure that if you wait a bit, some other users will post more smart(er) answers :)

\$\endgroup\$
2
\$\begingroup\$

After advice from Alexandre Vaillancourt, my earlier comment is now turned into an answer.

If performance is an issue, you might wanna use a design method/pattern called Object pooling. What this method/pattern actually means is that you, at the start-up of the game/level/scene, fill a container (an std::vector, an std::list etc) with a fixed number of objects, bullets in your case. When a bullet is supposed to be shot in the game, the code retrieves a bullet from the container, marks it as used, moves it across the screen, renders it and whenever it should be destroyed (at collision with ground, walls, characters etc), stop rendering it and then finally mark it as free so the code knows it's ok to pick that bullet from the container later, for later usage. At the game/level/scene shutdown, the bullets are destroyed. By using this method/pattern, no bullets are created and/or destroyed during run-time, which is always a good thing. I have added some example code below.

#include <vector>

// Bullet object
struct SBullet
{
    Vector2D    Position;
    float       Speed;
    float       Damage;
    bool        InUse;
};

typedef std::vector<SBullet*> BulletVector;

// Will be filled at the startup of the game/level/scene and destroyed/cleared at game/level/scene shutdown
BulletVector Bullets;
Bullets.clear();

// Will be filled with bullet pointers during run-time
BulletVector ActiveBullets;
ActiveBullets.clear();

int main()
{
    // Fill the bullet vector with bullets
    for(unsigned int i = 0; i < 128; ++i)
    {
        SBullet* pBullet = new SBullet;

        pBullet->Position   = Vector2D(0.0f, 0.0f);
        pBullet->Speed      = 16.0f;
        pBullet->Damage     = 2.0f;
        pBullet->InUse      = false;

        Bullets.push_back(pBullet);
    }

    While(Running)
    {
        Update();
        Render();
    }

    // Destroy the bullet vector
    BulletVector::const_iterator ItBeg = Bullets.begin();
    BulletVector::const_iterator ItEnd = Bullets.end();

    for(; ItBeg != ItEnd; ++ItBeg)
    {
        delete (*ItBeg);
    }

    Bullets.clear();
}

void Update()
{
    // Mouse button has been pressed so it's time to add a free bullet into the active bullets vector
    if(InputHandler.MouseButtonClicked)
    {
        SBullet* pBullet = RetrieveFreeBullet();

        if(pBullet)
        {
            pBullet->Position   = pPlayer->GetPosition(); 
            pBullet->InUse      = true;

            ActiveBullets.push_back(pBullet);
        }
    }

    unsigned int NumBullets = ActiveBullets.size();
    unsigned int Index      = 0;

    while(Index < NumBullets)
    {
        SBullet* pBullet = ActiveBullets[Index];

        MoveBulletAcrossScreen(pBullet);

        /*
        The bullet has collided with an enemy, mark it as free, remove it from the active bullets vector and maybe render some explosion/particles etc
        Removing the bullet from the active bullets vector wont destroy the actual bullet, only remove the actual pointer from the vector
        */
        if(CollisionCheck(pBullet, pEnemy))
        {
            pEnemy.ReduceHealth(pBullet->Damage);

            pBullet->Position   = Vector2D(0.0f, 0.0f);
            pBullet->InUse      = false;

            SBullet* pTemp = ActiveBullets[Index];

            /*
            Swap the current bullet's and the last bullet's container position
            It's better to remove an object in the end of the vector since the rest of the objects after won't have to be moved back in the vector to fill up the empty space (which is costly)
            */
            ActiveBullets[Index] = ActiveBullets[NumBullets - 1];
            ActiveBullets[NumBullets - 1] = pTemp;

            ActiveBullets.pop_back();

            --NumBullets;
        }

        // The bullet has collided with some ground - the same procedure as above to remove the bullet
        else if(CollisionCheck(pBullet, pGround))
        {
            pBullet->Position   = Vector2D(0.0f, 0.0f);
            pBullet->InUse      = false;

            SBullet* pTemp = ActiveBullets[Index];

            ActiveBullets[Index] = ActiveBullets[NumBullets - 1];
            ActiveBullets[NumBullets - 1] = pTemp;

            ActiveBullets.pop_back();

            --NumBullets;
        }

        else
            ++Index;
    }
}

void Render()
{
    BulletVector::const_iterator ItBeg = ActiveBullets.begin();
    BulletVector::const_iterator ItEnd = ActiveBullets.end();

    for(; ItBeg != ItEnd; ++ItBeg)
    {
        RenderSprite((*ItBeg), pBulletSprite);
    }
}

SBullet* RetrieveFreeBullet()
{
    // Might wanna have a variable containing the last used index into the bullet vector for faster returning of a bullet

    BulletVector::const_iterator ItBeg = Bullets.begin();
    BulletVector::const_iterator ItEnd = Bullets.end();

    for(; ItBeg != ItEnd; ++ItBeg)
    {
        if((*ItBeg)->InUse)
            continue;

        return (*ItBeg);
    }

    // No free bullet available, might wanna return the bullet at the start of the vector instead of nullptr so that nullptr is never returned
    return nullptr;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.