Code Optimizations

Hey there /prog/, let's talk about optimization or different things we can do to speed up our applications.

Currently I'm writing a game, and it usually takes up around ~50% of my CPU usage on the bigger maps.  I have a vector that contains all of my blocks, enemies, and other things that should be drawn on the screen.

In my draw thread, it could look like this:
player.draw();
for (int bi = 0; bi < blocks.size(); bi++)
{
    if (InCameraView(blocks[bi]))
    {
        draw(blocks[bi]);
    }
}

In my update thread, it looks like:
player.update();
for (int bi = 0; bi < blocks.size(); bi++)
{
    if (InCameraView(blocks[bi]))
    {
        player.TouchGround(blocks[bi]);
        for (int ei = 0; ei < enemies.size(); ei++)
        {
            enemies.update();
            enemies[ei].TouchGround(blocks[bi]);
        }
    }
}

Obviously only an example, and I typically have lots of more objects that are currently being drawn on the screen.  I also understand that it's usually very bad to have nested for loops, but I'm not exactly sure how else I could handle this.

Also, for rendering I have a lot of "switch" blocks to determine what I should render or update.

switch (CurrentWorld)
{
    case Worlds::MainMenu:
        worldMainMenu.draw();
    break
    case Worlds::Level:
        worldLevel.draw();
    break;
}

Also, for updating thread:
while (true)
{
    while (resetTime >= gameTime)
    {
        resetTime -= gameTime;
    switch (CurrentWorld)
    {
            case Worlds::MainMenu:
                mainMenu.update();
            break;
        case Worlds::Level:
            worldLevel.update();
        break;
    }
    }
}

How do you guys like to optimize your applications to run better and use less processing power?

To improve readability, I'll package the above pieces into code tags.

Drawing method inside of a class:

player.draw();
for (int bi = 0; bi < blocks.size(); bi++)
{
    if (InCameraView(blocks[bi]))
    {
        draw(blocks[bi]);
    }
}

Update method inside of a class:

player.update();
for (int bi = 0; bi < blocks.size(); bi++)
{
    if (InCameraView(blocks[bi]))
    {
        player.TouchGround(blocks[bi]);
        for (int ei = 0; ei < enemies.size(); ei++)
        {
            enemies.update();
            enemies[ei].TouchGround(blocks[bi]);
        }
    }
}

Inside of the draw thread:

switch (CurrentWorld)
{
    case Worlds::MainMenu:
        worldMainMenu.draw();
    break
    case Worlds::Level:
        worldLevel.draw();
    break;
}

Inside of the update thread:

while (true)
{
    while (resetTime >= gameTime)
    {
        resetTime -= gameTime;
    switch (CurrentWorld)
    {
            case Worlds::MainMenu:
                mainMenu.update();
            break;
        case Worlds::Level:
            worldLevel.update();
        break;
    }
    }
}

I think that is a good use for a nested loop in the update function. You are filtering out unneeded blocks and avoiding updating the entities in them. Right now, you are determining which blocks need processing by looping over all of them and then testing them with the InCameraView function. So the routine will always run in time that is at least proportional to the number of blocks. You may be able to speed things up by using a method that takes less work to find out which blocks need processing and which ones don't. If you can get this procedure to take time proportional to only the number of active blocks, then you'd probably get a good boost. You would need to take advantage of the type of environment your game has though.

Why not keep a second list of objects that are in view and add/remove objects from that as the player moves, that way you aren't checking everything each time.

Next optimization would be to create zones for your map and sort objects into those zones, so you don't even have to check objects unless they're in the current zone when the player moves.

>>3
I'd like to speed up the InCameraView method.  Currently the Camera View is an invisible rectangle, and I check if objects x and y coordinates are inside.  If so, return true, else return false.

>>4
I was actually wanting to do something like this, but I wasn't actually sure how to set it up.  It seems that I would still need to loop through the vector to see which objects are in range, for example:

for (oi = 0; oi < objects.size(); oi++)
{
    if (InCameraView(objects[oi]))
    {
        objects_drawable.push_back(objects[oi]);
    }
    else
    {
        objects_drawable.erase(objects_drawable.begin() + oi);
    }
}

So obviously I'd still be looping through the vector, which would be consuming my CPU!

Bump for interest.

>>5

It sounds like your game is a 2D environment. What you can do is keep your blocks stored in a way such that you can efficiently access only the ones that are possibly visible from the user's view. If the blocks are discrete tiles, then this is pretty trivial, it just comes down to rounding the x y coordinate of the corners of the screen to discrete values and then translating the tile offsets to array indecies.

>>5
get your player's coordinates
only scan an area of 10x10 blocks around your current coordinates

>>8
To do that he'll need to partition his map somehow like mentioned in >>4

But yes it's a cpu/memory tradeoff situation.
Spend more memory to avoid wasting cycles.

>>2
You could set up an array of pointers like blocks[X][Y] and then make all objects at the same screen position into a vector or linked list at that array index.
player.draw();
for (int bix = CameraView.Xmin; bix < CameraView.Xmax; bix++)
for (int biy = CameraView.Ymin; biy < CameraView.Ymax; biy++)
{
    if (blocks[bix][biy]) drawall(blocks[bix][biy]);
}

void drawall(Block *b) {
    while (b) {
        draw(b);
        b = b->next;
    }
}

>if (InCameraView(blocks[bi]))
Why don't have Z-index for objects and draw objects which have the Z-index priority first and everything else as low-priority background
Now changing Z-index is like adding substracting Ints and thats cheap for 3d
player.TouchGround(blocks[bi]);
I would use event system per block, block() function
block(block_id)-> calls function when touched: e.g. DumpMushroom(block_id) or SelfDestroyAs(block_id,BRICK_TEXTURE)

What do you mean by block? is that another minecraft clone?

>>10
I've been trying to setup something like this recently, and I think I'm making progress.  Instead of looping through the blocks vector each iteration and referring to the block's index, I should loop through the points inside of the Camera's view range and display the blocks that match.

>>11
It almost does feel like I'm using an event driven system currently, but I'm sure that TouchGround(); gets called way too frequently.

>>12
I'm working on a 2D side scrolling game.  In fact, I'd prefer to have it so that the blocks are just one object, I certainly think that would speed things up.