Optimizations?

[fatum]

I'm curious about any steps I could take to to increase the efficiency and speed of my game.

Currently I have a vector for each set of objects I'd like to draw on the screen.  For example, coins, enemies, blocks, etc.  Here's an example for how I have things setup:

Code: [Select]


void WorldLevel::draw()
{
for (int bi = 0; bi < blocks.size(); bi++)
{
if (InCameraView(blocks[bi]))
{
App.Draw(blocks[bi]);
}
}
for (int ei = 0; ei < enemies.size(); ei++)
{
if (InCameraView(enemies[ei]))
{
enemies[ei].draw();
}
}
}

void WorldLevel::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[ei].update();
enemies[ei].TouchGround(blocks[bi]);
}
}
}
}


I think the biggest sacrifice is looping through the blocks vector, because it's usually pretty large.  I also understand that it's probably bad practice to use nested for loops, but I'm not exactly sure how else to achieve what I'm trying to do.

I was thinking about making a second vector that contains all of the blocks that are on screen (blocks_drawable), and loop through that vector anytime I need the objects to interact with the blocks.  However, I assume I would still need to loop through the blocks to determine the blocks on screen, so I'm not too sure if there would be a noticeable difference in performance.

What could I do to make things run better?  The game feels very smooth whenever the blocks vector isn't too large, but things start to slow down whenever the vector becomes larger.
Thanks for any help!

[Laurent]

You could use a higher-level structure to sort your blocks, like a quad-tree (Google it!).

It will allow you to quickly find blocks of interest (for drawing or collision tests) without iterating on all of them.

[Groogy]

I wrote a little just about spatial partitioning here: http://www.sfml-dev.org/forum/viewtopic.php?p=35285#35285

(Where Quad-tree is an algorithm/data structure in)

Also found where I've discussed grid's which is a simpler and maybe more beginner friendly than Quadtrees. http://www.sfml-dev.org/forum/viewtopic.php?p=32767#32767

[slotdev]

I use a display list - simply, a list of things which I want displayed. Drawing my main game screen, which only has maybe 15 or 20 items at any one time, takes next to no time.

[fatum]

You could use a higher-level structure to sort your blocks, like a quad-tree (Google it!).

It will allow you to quickly find blocks of interest (for drawing or collision tests) without iterating on all of them.

I wrote a little just about spatial partitioning here: http://www.sfml-dev.org/forum/viewtopic.php?p=35285#35285

(Where Quad-tree is an algorithm/data structure in)

Also found where I've discussed grid's which is a simpler and maybe more beginner friendly than Quadtrees. http://www.sfml-dev.org/forum/viewtopic.php?p=32767#32767

I've been searching for QuadTree techniques, trying to create my own implementation.  It certainly feels foreign not needing to loop through each individual object, so I'm sure that everything I've tried so far isn't an actual implementation.

I use a display list - simply, a list of things which I want displayed. Drawing my main game screen, which only has maybe 15 or 20 items at any one time, takes next to no time.

How do you decide what to include and exclude from the display list?

[Tex Killer]

In case of tile based sprites printed from a matrix, if you have fixed size tiles, you can know exactly where to begin and where to end printing.
Take the left border X position of your camera and divide by the tile size to get the X index of the first tile to print on the matrix. Divide the X position of your right border by the tile size and add 1 to make sure it goes past the screen, and you have the last X index you are going to print.

Same goes for Y.

Then you have just to iterate on these positions and print them.

[fatum]

In case of tile based sprites printed from a matrix, if you have fixed size tiles, you can know exactly where to begin and where to end printing.
Take the left border X position of your camera and divide by the tile size to get the X index of the first tile to print on the matrix. Divide the X position of your right border by the tile size and add 1 to make sure it goes past the screen, and you have the last X index you are going to print.

Same goes for Y.

Then you have just to iterate on these positions and print them.

Thanks for the reply!  I organized my blocks into testBlocks

• [y] now, and I assumed that this loop would iterate through them:

Code: [Select]


std::map<int, std::map<int, sf::Sprite> > testBlocks;
...
for (int bx = CameraView.Left; bx < CameraView.Width; bx += 32)
{
for (int by = CameraView.Top; by < CameraView.Height; by += 36)
{
App.Draw(testBlocks[bx][by]);
}
}


The actual tile size is 16x18, however they're both scaled by a ratio of 2.  I've also tried

bx++;
by++;

As well as
bx += 16;
by += 18;

Initially I assumed the application would crash if I attempted to access a nonexistent index, but that doesn't seem to the the case.

I assume that I'm referring to nonexistent indexes in my std::map, but I'm not sure what I could do to refer to the appropriate ones.

[Tex Killer]

You are using pixel positions as matrix indexes...
Try it like this:

Code: [Select]

int left = CameraView.Left / 32;
int right = (CameraView.Left + CameraView.Width) / 32 + 1;
int top = CameraView.Top / 36;
int bottom = (CameraView.Top + CameraView.Height) / 36 + 1;
for (int bx = left; bx <= right; bx++)
{
   for (int by = top; by <= bottom; by++)
   {
      App.Draw(testBlocks[bx][by]);
   }
}

[fatum]

You are using pixel positions as matrix indexes...
Try it like this:

Thank you!  That's exactly what I was looking for, and it seems to be working well.  However, the framerate is significantly lower than it was before, but the newer method feels smoother than the previous method most of the time.

Should I go about my collision checking the same as I was before?  As in,

Code: [Select]


for (int bx1 = left; bx1 <= right; bx1++)
{
for (int by1 = top; by1 <= bottom; by1++)
{
player.TouchGround(blocks[bx1][by1]);
for (int ei = 0; ei < enemies.size(); ei++)
{
if (InCameraView(enemies[ei]))
{
enemies[ei].update();
enemies[ei].TouchGround(blocks[bx1][by1]);
}
}
}
}


It feels quite strange to be using two nested for loops.

[Groogy]

Well if you want to optimize, a good beginner thing to do is eliminate looping as much as possible.
For instance using a bit of math you can get the double loop down to a single loop but it probably is not worth it, destroys readability and not much gain.

But doing collision like that is really bad as it will scale up exponentially. I think the complexity is O(n^2) I think if I remember correctly. Here's where Grid's and Quadtree's come in. And if I remember correctly there the complexity for Quadtree's are O(log n). Which is significantly faster, just try out some numbers by replacing the N with whatever you want.

The big advantage here is that you can tell the Quadtree "I want objects within this circle" and it will give you those objects with little effort because it can cut away non-relevant objects very fast.