How to iterate through specific elements in a vector C ?-CodePudding

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 :)

CodePudding user response：

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!

CodePudding user response：

I was wondering if there was a way to say "for each tile in vector of tiles that (fits a condition)

In general, no. The only way to know if an element fits a condition is to look at it and see if it fits the condition. You can't do that without iterating over all the elements and checking the condition for each.

The way to avoid this is to build some sort of index structure. For instance, if you have tiles with attributes that change rarely, you could pre-build vectors of pointers to all of your tiles with some attribute. That way you can check the condition only once (or rarely) instead of on each frame. For instance you could build separate vectors of all of your blue tiles, all of your red tiles, and all of your green tiles. Then if you want to iterate over all of the tiles of a certain color you could do "for each blue tile" directly instead of "for each tile, if it's blue". This generally trades storage/memory usage for execution speed.

The same concept applies to your specific situation, as you mentioned. You can pre-build caches of chunks, and quickly filter out whole chunks that aren't near your camera. This will prevent you from having to check every tile to see if it's in view.