Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Vector size limit?

This thread is locked; no one can reply to it. rss feed Print
Vector size limit?
kebapmanager
Member #14,863
January 2013
avatar

I am creating various objects and pushing them all in objects vector and iterating trough them to update, render and destroy them easier.
Problem occurs when I want to create more then 250 or so objects.
Game starts lagging and eventually if I doesn't stop creating new objects it freezes until program in the back doesn't destroy few objects(in my case it does it automatically since objects are snowflakes for example)
Where is the problem: - Iterating trough 250 objects 60 times in a second 2 or eventually 3 times? or vector cant hold that much memory or something?
and how to fix this?

std::vector<GameObject *> objects;
std::vector<GameObject *>::iterator iter;
std::vector<GameObject *>::iterator iter2;

// example of creating a snowflake:
Snow *snow = new Snow(player->GetX(), player->GetY());
object.push_back(snow);

// example of render:
for(iter = objects.begin(); iter != objects.end(); ++iter)
      (*iter)->Render();

Edgar Reynaldo
Member #8,592
May 2007
avatar

kebapmanager
Member #14,863
January 2013
avatar

Snow is actually al_draw_circle, so I think it has nothing to do with textures loading.
I have 4 iterations, render, destroy and this two down below, update and collisions.
Maybe vector just cant hold that much objects of this size?

#SelectExpand
1//Update 2 for(iter = objects.begin(); iter != objects.end(); ++iter) 3 (*iter)->Update(); 4 5//collisions 6int sz = (int)objects.size(); 7for (int i = 0 ; i < sz ; ++i) 8{ 9 GameObject* iter = objects[i]; 10 11 if( ! (iter)->Collidable() ) continue; 12 13 for (int i2 = i + 1 ; i2 < sz ; ++i2) 14 { 15 GameObject* iter2 = objects[i2]; 16 17 if( !(iter2)->Collidable() ) continue; 18 19 if( (iter)->CheckCollisions( (iter2))) 20 { 21 (iter)->Collided( (iter2)->GetID(), (iter2)); 22 (iter2)->Collided( (iter)->GetID(), (iter)); 23 } 24 } 25 }

Slartibartfast
Member #8,789
June 2007
avatar

I have 4 iterations, render, destroy and this two down below, update and collisions.

If by "destroy" you mean erase then don't, since it has linear time complexity. Instead you should swap the current element with the last element and pop_back, unless the order really matters.

There's also the fact that you check for collisions between all pairs of objects, so those are 250*250 = 62500 collision checks per frame, which could also be slowing you down.

Edgar Reynaldo
Member #8,592
May 2007
avatar

This has nothing to do with vectors. They are your best choice in this situation, since they have contiguous memory.

The problem is that you are doing (n^2 + n)/2 CheckCollisions calls where n is the number of objects in your vector.

I told you, profile your code. MinGW has gprof, MSVC probably has their own profiler.

Arthur Kalliokoski
Second in Command
February 2005
avatar

MSVC probably has their own profiler

The Express edition famously does not.

“Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”

― Robert A. Heinlein

kebapmanager
Member #14,863
January 2013
avatar

This is how it looks like, I will try your suggestion ! :)

//delete dead
    for(iter = objects.begin(); iter != objects.end(); )
    {
      if(! (*iter)->GetAlive())
      {
        delete (*iter);  
        iter = objects.erase(iter);
      }
      else
        iter++;
    }

I tryed to comment out collision checking and as it turns out thats what makes my game lagg. I was able to creat 2k objects without it( didint try more ;D). Should I set collision chechks only if objects are close to player?

Conclusion, I disabled collision but left in main to still iterate trough 62500 checks, and I got lagg back again, so the problem is in iterating trough 62500 objects basicly.I need to shrink that down.

Aikei_c
Member #14,871
January 2013
avatar

Should I set collision chechks only if objects are close to player

Depends on what your collision code looks like. If it's just meant to check for collision between circles, checking distance and checking for circles collision is pretty much the same thing.
Anyway, you don't need to check everything for collision every frame, like 60 times per second, right? You could only check some objects. Here is an idea: set a maximum time collision code can take per frame, and if it takes more, then stop it, remember the position, and then start from this position when you return to collision checking next frame.

taron 
Member #10,584
January 2009
avatar

Iterating through 62500 objects shouldn't be a problem.

Should I set collision chechks only if objects are close to player?

Only if you update objects close to the player, otherwise weird things might happen. Only check collisions with objects that are close to each other.
You could for example divide the board using an imaginary grid. Add objects to cells that they are inside of. Then while doing a collision check, only check collisions with objects in the same cell. Do keep your current vector as well, for keeping updating, rendering and deletion simple.

You can keep track of objects that can collide and objects that can't in 2 seperate vectors. You'll get rid of the if (foo->Collidable()) check completely or almost completely, which can improve performance a lot if your program is suffering from many branch mispredictions.

All those virtual calls and dereferencing pointers, pointing to objects made by new that might be located all over the place (causing cache misses), might be a problem.
Perhaps try a design like this, this is assuming snow is a very common object, expected to be on the screen in great quantities. If it isn't, don't bother with the following code, but do keep it in mind.

#SelectExpand
1struct SnowParticle 2{ 3 float x, y; 4}; 5 6class SnowParticleSystem : public GameObject 7{ 8 // std::array is C++11, if you're on an older compiler use an alternative 9 std::array<SnowParticle, 255> snowParticleArray; // 255 Snow particles max 10public: 11 // On older compilers, omit the override keyword 12 void Update() override 13 { 14 for (auto it : snowParticleArray) 15 { 16 // update snow 17 } 18 } 19 // Same for rendering 20};

Kris Asick
Member #1,424
July 2001

You know, collision checks shouldn't be all that time consuming... it's making me wonder if perhaps you're calling something like sqrt() for bounding circles, since sqrt() can cause huge performance hits if overused. (Typically, with bounding circles, you want to calculate based on the squared values of everything so you never have to call the square root function.)

It also helps to flag things appropriately. Not every kind of object needs to intersect every kind of object so you don't want to run collisions on two objects which will never interact with each other.

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

pkrcel
Member #14,001
February 2012

Maybe the performance hit is due to 250 calls to al_draw_circle?

I sort of remember that it winds up in al_draw_prim and 250 calls per frame may hit performance?

Not sure but still...

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

kebapmanager
Member #14,863
January 2013
avatar

pkrcel said:

Maybe the performance hit is due to 250 calls to al_draw_circle?

I sort of remember that it winds up in al_draw_prim and 250 calls per frame may hit performance?

Not sure but still...

Definitly not, I removed collision betwen blocks and now I can have 3000 al_draw_circles at the same time without seeing any lagg

You know, collision checks shouldn't be all that time consuming... it's making me wonder if perhaps you're calling something like sqrt() for bounding circles, since sqrt() can cause huge performance hits if overused. (Typically, with bounding circles, you want to calculate based on the squared values of everything so you never have to call the square root function.)

I dont use anything like that

It also helps to flag things appropriately. Not every kind of object needs to intersect every kind of object so you don't want to run collisions on two objects which will never interact with each other.

This is what acctualy helped me, I was runnig collision chechk betwen cubes, even though cubes never move...

Go to: