1000+ Game-Objects in Vector too slow? What is my mistake?

Question

I am currently working on a game, where there is a need for keeping track of lot of objects.

I have a game object class, which holds all the necessary information of the object and handles AI() on update();

I decided, that only objects with a brain, will need an update every frame. So I have separated vectors to save time. However, I cannot seem to find a similar solution when drawing objects. So I got

std::vector<cOBJECT*> LivingObjects;

and

std::vector<cOBJECT*> WorldObjects;

When drawing all objects, I first put all of the objects in a RenderList:

//Add World and Living Objects into one list of RenderObjects
RenderObjects = WorldObjects;
RenderObjects.insert(RenderObjects.end(), LivingObjects.begin(), LivingObjects.end());

Then I sort them by Y:

//Sort all Objects by Y (bottom) Coordiante
sort(RenderObjects.begin(), RenderObjects.end(), cmd);

Here is the code for that (maybe this is slow too?:

//Sorts by Y-Coordinaté
bool cmd(cOBJECT* obj1, cOBJECT* obj2)
{
    return obj1->getrect().y + obj1->getrect().h < obj2->getrect().y + obj2->getrect().h;
}

Then I draw them. The drawing function will check if they are on screen on or not! So I only draw visible objects:

//DRAW OBJECTS and 
for (std::vector<cOBJECT*>::size_type i = 0; i != RenderObjects.size(); i++)
{
    RenderObjects[i]->render(Renderer, CameraX, CameraY, SCREEN_WIDTH, SCREEN_HEIGHT);
}

Here is the actual draw function´:

int cTEXTURES::renderAnimation(int targetX, int targetY, double angle, SDL_Point* center, SDL_RendererFlip flip, SDL_Renderer* Renderer, int row, int speed, int offX, int offY, int SCREEN_HEIGHT, int SCREEN_WIDTH)
{
    //Draw if part of it shown on screen
    if (targetX - offX >= -FrameWidth && targetX - offX <= SCREEN_WIDTH + FrameWidth && targetY - offY >= -FrameHeight && targetY - offY <= SCREEN_HEIGHT + FrameHeight)
    {
        SDL_Rect SourceRect;
        SDL_Rect TargetRect;

        TargetRect = { targetX - offX, targetY - offY, FrameWidth, FrameHeight };

        SourceRect.x = (CurrentFrame - 1) * FrameWidth;
        SourceRect.y = (row - 1) * FrameHeight;
        SourceRect.w = FrameWidth;
        SourceRect.h = FrameHeight;

        if (OldTime + speed > SDL_GetTicks()) { SDL_RenderCopyEx(Renderer, TheTextureManager::Instance()->TextureList[TexturePath], &SourceRect, &TargetRect, angle, center, flip); return 0; }

        OldTime = SDL_GetTicks();

        //SDL_RenderCopyEx(Renderer, TheTextureManager::Instance()->TextureList[TexturePath], &SourceRect, &TargetRect, angle, center, flip);
        TheTextureManager::Instance()->draw(TexturePath, Renderer, &SourceRect, &TargetRect, angle, center, flip);
        CurrentFrame++;

        if (CurrentFrame == (Frames + 1))
        {
            CurrentFrame = 1;
            return 1; // returns 1 if one row is finished
        }

        return 0; // returns 0 if animation is not finished
    }
    return 0;
}

Now I got 1000+ objects, probably even 2000+ later on. Just running through the for-loop to check if the objects need to be drawn is very time-intensive, right?

What am I missing? How can I keep track of 1000s of objects and know whether to draw them without such extensive amount of work for the CPU? Especially because I will need a lot of room for a lot of AI

Thanks, this is driving me nuts.

Answer 1

For speeding up iterators of stl containers in debug builds (and compile times due to header parsing) include the following lines in the first header (or precompiled header) before anything else is included (such as the "windows.h" header):

#ifdef _WIN32
#   define _CRT_SECURE_NO_WARNINGS  // disable the Microsoft specific warnings about _s buffer underrun security issues for ISO methods (fopen, strcpy etc..)
#   define VC_EXTRALEAN             // cut down includes
#   define WIN32_LEAN_AND_MEAN      // cut down includes
#   undef _SECURE_SCL               // iterators generate less overhead code in debug
#   if _ITERATOR_DEBUG_LEVEL > 0
#       define _SECURE_SCL 1
#   else
#       define _SECURE_SCL 0
#   endif
#endif

The _iterator_debug_level setting can be a bit tricky if you link to other libraries that have different iterator_debug_levels.

This will make your debug builds run a lot faster, but if performance is required, it is often the usage of the containers that needs a second look, and finally rolling your own containers is the last resort if your operations are complex or specific.