How to iterate through specific elements in a vector C++?

Question

I'm making a game with C++ and SFML and was wondering if there's a way to iterate through specific elements in a vector. I have a vector of tiles which makes up the game world, but depending on the game map's size, (1000 x 1000 tiles) iterating through all of them seems very inefficient. I was wondering if there was a way to say "for each tile in vector of tiles that (fits a condition)". Right now, my code for drawing these tiles looks like this:

void Tile::draw()
{
    for (const auto& TILE : tiles)
    {
        if (TILE.sprite.getGlobalBounds().intersects(Game::drawCuller.getGlobalBounds()))
        {
            Game::window.draw(TILE.sprite);
        }
    }
}

As you can see, I'm only drawing the tiles in the view (or drawculler). If the vector is too large, it will take a really long time to iterate through it. This greatly impacts my fps. When I have a 100 x 100 tile map, I get around 800 fps, but when I use a 1000 x 1000 tile map, I get roughly 25 fps due to the lengthy iteration. I know that I could separate my tiles into chunks and only iterate through the ones in the current chunk, but I wanted something a little easier to implement. Any help would be appreciated :)

Answer 1

Given the following assumptions:

• Your tiles are likely arranged on a regular grid with a (column, row) index.
• Your tiles are likely inserted into your vector in row-major order, and is also likely fully-populated. So the index of a tile in your vector is likely (row * numColumns + column).
• Your view is likely axis-aligned to the grid (where you can't rotate your view - as is the case with many 2d tile-based games)

If those assumptions hold true, then you can easily iterate through the appropriate range of tiles with a nested loop.

for (int row = minRow; row <= maxRow; ++row) {
   for( int column = numColumn; column <= maxColumn; ++column) {
      int index = row * numColumns + column;

      // Here you can...
      doSomethingWith(tiles[index]);
   }
}

This just requires that you can compute the minRow, maxRow, minColumn, and maxColumn from your Game::drawCuller.getGlobalBounds(). You haven't disclosed the details, but it's likely something like a rectangle in world coordinates (which might be in some units like meters). It's likely either a left, top, width, height style rectangle or a min, max style bounds rectangle. Assuming the latter:

minViewColumn = floor((bounds.minInMeters.x - originOfGridInMeters.x) / gridTileSizeInMeters);
maxViewColumn = ceil((bounds.maxInMeters.x - originOfGridInMeters.x) / gridTileSizeInMeters);
// similarly for rows
minViewRow = floor((bounds.minInMeters.y - originOfGridInMeters.y) / gridTileSizeInMeters);
maxViewRow = ceil((bounds.maxInMeters.y - originOfGridInMeters.y) / gridTileSizeInMeters);

The originOfGridInMeters is the global coordinates of top-left corner of the tile at (row=0, column=0), which may very well be (0, 0), conveniently, if you set up your world like that. And gridTileSizeInMeters is, well, just that; presumably your tiles have a square aspect ratio in world space.

If the view is permitted to go outside the extents of the tile array, minViewColumn, (and the other iterator ranges) may now be less than 0 or greater than or equal to the number of columns in your tile array. So, it would then be necessary to compute minColumn from minViewColumn by clipping it to the range of tiles stored in your grid. (Same goes for the other iteration extents.)

// Clip to the range of valid rows and columns.
minColumn = min(max(minViewColumn, 0), numColumns - 1);
maxColumn = min(max(maxViewColumn, 0), numColumns - 1);
minRow = min(max(minViewRow, 0), numRows - 1);
maxRow = min(max(maxViewRow, 0), numRows - 1);

Now do that loop I showed you above, and you're good to go!