Creating a lot of objects in a tile-based game

Question

I am working on an SDL2 based isometric, tile-based engine for a SimCity 2000 Clone.

Basically I'd really appreciate if someone with experience could review my code and point out weak points since I'm not an experienced C++ dev.

Here is my repository.

But I do have a specific part I'd like you to review. In my Cell class, each object represents a map tile with informations like tileID (texture to render), and later attributes like "hasPower, water, ..."

It is quite complex and has a lot of member functions. My game is a SimCity 2000 clone and tiles can be elevated. so a cell must check its surrounding tiles if they're elevated, and if so draw a different texture (tileID) according to its neighbors elevation or even raise / lower itself.

The rendering is also done in the Cell class because the sprite object must know its ISO coordinates (including the height) which is known per cell object.

I could rewrite my code, so that the rendering is done in the vectorMatrix class (in a loop that iterates over all cells in the vector, gets the cell's height, sets the sprites isocoordinates, and then calls the sprites render() function), but I've tried that and it makes no performance difference.

Cell.hxx

#ifndef CELL_HXX_
#define CELL_HXX_

#include <vector>
#include <map>
#include <cmath>

#include "SDL2/SDL.h"


#include "sprite.hxx"
#include "basics/point.hxx"
#include "basics/resources.hxx"

/** @brief Class that holds map cells
 * Each tile is represented by the map cell class.   
 */
class Cell
{
public:
  Cell();
  explicit Cell(Point isoCoordinates);
  ~Cell();

  /** @brief get Sprite
    * get the Sprite* object for this cell
    * @see Sprite
    */
  Sprite* getSprite();

  /// get iso coordinates of this cell
  Point getCoordinates();

  /// Sets the neighbors of this cell for fast access
  void setNeighbors(std::vector<Cell*> neighbors);

  /** @brief Increase Height
    * Increases the height of this map cell and checks which
    * tileID must be drawn for each neighbor
    */
  void increaseHeight();
  /** @brief Decrease Height 
    * Decreases the height of this map cell and checks which 
    * tileID must be drawn for each neighbor
    */
  void decreaseHeight();

  /** @brief set Tile ID 
    * Change the texture of the map cell to a specific tile id
    * @see Resources#readTileListFile
    * @param tileID The tileID that should be rendered for this map cell
    */
  void setTileID(int tileID);
  /** @brief get Tile ID
    * Retrieves the current Tile ID of this map cell
    * @return Returns the current Tile ID as Integer
    */
  int getTileID();

private:
  Point _isoCoordinates;
  Sprite* _sprite;

  std::vector<Cell*> _neighbors;
  SDL_Renderer* _renderer;
  SDL_Window* _window;

  int _heightOffset = 20; // Offset for Y Coordinate between two height levels
  int _tileID;
  int _maxCellHeight = 32;

  /** \brief: determine which tile ID should be drawn for this cell
    * Checks all the neighbors and determines the tile ID of this mapcell according to it's
    * elevated / lowered neighbors.
    */
  void determineTile();

  /** \brief set tileID for each neighbor
    * After a cell is raised / lowered, each neighbor must check which tileID it should have
    * @see Cell#drawSurroundingTiles
  */
  void drawSurroundingTiles(Point isoCoordinates);

  /** Enum (bitmask) for mapping neighbor tile positions
    * [ T B L R TL TR BL BR ]
    * [ 0 0 0 0  0  0  0  0 ]

    * Our neighbor tiles look like this
    * 2 5 8  
    * 1 X 7
    * 0 3 6
    */

  enum elevatedTilePosition : unsigned int{
       NO_NEIGHBORS = 0x0,
       ELEVATED_TOP = 0x1,
       ELEVATED_BOTTOM = 0x2,
       ELEVATED_LEFT = 0x4,
       ELEVATED_RIGHT = 0x8,
       ELEVATED_TOP_LEFT = 0x10,
       ELEVATED_TOP_RIGHT = 0x20,
       ELEVATED_BOTTOM_LEFT = 0x40,
       ELEVATED_BOTTOM_RIGHT = 0x80,
  };

  /** UInt to elevate store tile position in */
  unsigned int _elevatedTilePosition;


  /** Map neighbor tile combinations to tile ID for terrain keytiles. */
  std::map<unsigned int, int> keyTileMap =
  {
    { NO_NEIGHBORS, 14 },
    { ELEVATED_TOP, 3 },
    { ELEVATED_BOTTOM, 5 },
    { ELEVATED_RIGHT, 1 },
    { ELEVATED_LEFT, 7 },
    { ELEVATED_BOTTOM_RIGHT, 2 },
    { ELEVATED_BOTTOM_LEFT, 8 },
    { ELEVATED_TOP_RIGHT, 0 },
    { ELEVATED_TOP_LEFT, 6 },

    { ELEVATED_TOP | ELEVATED_TOP_LEFT, 3 },
    { ELEVATED_TOP | ELEVATED_TOP_RIGHT, 3 },
    { ELEVATED_TOP | ELEVATED_TOP_RIGHT | ELEVATED_TOP_LEFT, 3 },
    { ELEVATED_TOP_LEFT | ELEVATED_TOP_RIGHT, 3 },

    { ELEVATED_BOTTOM | ELEVATED_BOTTOM_LEFT, 5 },
    { ELEVATED_BOTTOM | ELEVATED_BOTTOM_RIGHT, 5 },
    { ELEVATED_BOTTOM | ELEVATED_BOTTOM_RIGHT | ELEVATED_BOTTOM_LEFT, 5 },
    { ELEVATED_BOTTOM_LEFT | ELEVATED_BOTTOM_RIGHT, 5 },

    { ELEVATED_LEFT | ELEVATED_BOTTOM_LEFT, 7},
    { ELEVATED_LEFT | ELEVATED_TOP_LEFT, 7},
    { ELEVATED_LEFT | ELEVATED_TOP_LEFT | ELEVATED_BOTTOM_LEFT, 7},
    { ELEVATED_TOP_LEFT | ELEVATED_BOTTOM_LEFT, 7},

    { ELEVATED_RIGHT | ELEVATED_BOTTOM_RIGHT, 1 },
    { ELEVATED_RIGHT | ELEVATED_TOP_RIGHT, 1 },
    { ELEVATED_RIGHT | ELEVATED_TOP_RIGHT | ELEVATED_BOTTOM_RIGHT, 1 },
    { ELEVATED_BOTTOM_RIGHT | ELEVATED_TOP_RIGHT, 1 },

    { ELEVATED_TOP | ELEVATED_LEFT, 9 },
    { ELEVATED_TOP | ELEVATED_LEFT | ELEVATED_BOTTOM_LEFT, 9 }, 
    { ELEVATED_TOP | ELEVATED_LEFT | ELEVATED_TOP_RIGHT, 9 },
    { ELEVATED_TOP | ELEVATED_LEFT | ELEVATED_BOTTOM_LEFT | ELEVATED_TOP_RIGHT, 9 },
    { ELEVATED_TOP | ELEVATED_LEFT | ELEVATED_TOP_LEFT, 9 },
    { ELEVATED_TOP | ELEVATED_LEFT | ELEVATED_TOP_LEFT | ELEVATED_TOP_RIGHT, 9 },
    { ELEVATED_TOP | ELEVATED_LEFT | ELEVATED_TOP_LEFT | ELEVATED_BOTTOM_LEFT, 9 },
    { ELEVATED_TOP | ELEVATED_LEFT | ELEVATED_TOP_LEFT | ELEVATED_BOTTOM_LEFT | ELEVATED_TOP_RIGHT, 9 },
    { ELEVATED_TOP | ELEVATED_LEFT | ELEVATED_TOP_RIGHT | ELEVATED_TOP_RIGHT, 9 },

    { ELEVATED_TOP | ELEVATED_RIGHT, 10 },
    { ELEVATED_TOP | ELEVATED_RIGHT | ELEVATED_BOTTOM_RIGHT, 10 },
    { ELEVATED_TOP | ELEVATED_RIGHT | ELEVATED_TOP_LEFT, 10 },
    { ELEVATED_TOP | ELEVATED_RIGHT | ELEVATED_BOTTOM_RIGHT | ELEVATED_TOP_LEFT, 10 },
    { ELEVATED_TOP | ELEVATED_RIGHT | ELEVATED_TOP_RIGHT, 10 },
    { ELEVATED_TOP | ELEVATED_RIGHT | ELEVATED_TOP_RIGHT | ELEVATED_TOP_LEFT, 10 },
    { ELEVATED_TOP | ELEVATED_RIGHT | ELEVATED_TOP_RIGHT | ELEVATED_BOTTOM_RIGHT, 10 },
    { ELEVATED_TOP | ELEVATED_RIGHT | ELEVATED_TOP_RIGHT | ELEVATED_TOP_LEFT | ELEVATED_BOTTOM_RIGHT, 10 },
    { ELEVATED_TOP | ELEVATED_RIGHT | ELEVATED_TOP_LEFT | ELEVATED_BOTTOM_RIGHT, 10 },

    { ELEVATED_BOTTOM | ELEVATED_RIGHT, 13 },
    { ELEVATED_BOTTOM | ELEVATED_RIGHT | ELEVATED_TOP_RIGHT, 13 },
    { ELEVATED_BOTTOM | ELEVATED_RIGHT | ELEVATED_BOTTOM_LEFT, 13 },
    { ELEVATED_BOTTOM | ELEVATED_RIGHT | ELEVATED_BOTTOM_RIGHT, 13 },
    { ELEVATED_BOTTOM | ELEVATED_RIGHT | ELEVATED_BOTTOM_RIGHT | ELEVATED_BOTTOM_LEFT , 13 },
    { ELEVATED_BOTTOM | ELEVATED_RIGHT | ELEVATED_BOTTOM_RIGHT | ELEVATED_TOP_RIGHT , 13 },
    { ELEVATED_BOTTOM | ELEVATED_RIGHT | ELEVATED_BOTTOM_RIGHT | ELEVATED_BOTTOM_LEFT | ELEVATED_TOP_RIGHT , 13 },
    { ELEVATED_BOTTOM | ELEVATED_RIGHT | ELEVATED_BOTTOM_LEFT | ELEVATED_TOP_RIGHT, 13 }, 
    { ELEVATED_BOTTOM | ELEVATED_BOTTOM_LEFT | ELEVATED_TOP_RIGHT, 13 }, 

    { ELEVATED_BOTTOM | ELEVATED_LEFT, 11 },
    { ELEVATED_BOTTOM | ELEVATED_LEFT | ELEVATED_TOP_LEFT, 11 },
    { ELEVATED_BOTTOM | ELEVATED_LEFT | ELEVATED_BOTTOM_RIGHT, 11 },
    { ELEVATED_BOTTOM | ELEVATED_LEFT | ELEVATED_BOTTOM_LEFT, 11 },
    { ELEVATED_BOTTOM | ELEVATED_LEFT | ELEVATED_BOTTOM_LEFT | ELEVATED_TOP_LEFT, 11 },
    { ELEVATED_BOTTOM | ELEVATED_LEFT | ELEVATED_BOTTOM_LEFT | ELEVATED_BOTTOM_RIGHT, 11 },
    { ELEVATED_BOTTOM | ELEVATED_LEFT | ELEVATED_BOTTOM_LEFT | ELEVATED_TOP_LEFT | ELEVATED_BOTTOM_RIGHT, 11 },
    { ELEVATED_BOTTOM | ELEVATED_LEFT | ELEVATED_TOP_LEFT | ELEVATED_BOTTOM_RIGHT, 11},
    { ELEVATED_BOTTOM | ELEVATED_LEFT | ELEVATED_BOTTOM_RIGHT | ELEVATED_TOP_LEFT, 11 },

    //diagonal tiles - insert a block
    { ELEVATED_TOP_LEFT | ELEVATED_BOTTOM_RIGHT, 4},
    { ELEVATED_BOTTOM_LEFT | ELEVATED_TOP_RIGHT, 4},


    // special cases - elevate the tile
    { ELEVATED_RIGHT | ELEVATED_BOTTOM_LEFT, -1},
    { ELEVATED_RIGHT | ELEVATED_TOP_LEFT, -1},
    { ELEVATED_LEFT | ELEVATED_BOTTOM_RIGHT, -1},
    { ELEVATED_LEFT | ELEVATED_TOP_RIGHT, -1},
    { ELEVATED_TOP | ELEVATED_BOTTOM_LEFT, -1},
    { ELEVATED_TOP | ELEVATED_BOTTOM_RIGHT, -1},
    { ELEVATED_BOTTOM | ELEVATED_TOP_LEFT, -1},
    { ELEVATED_BOTTOM | ELEVATED_TOP_RIGHT, -1}

  };
};


#endif

Cell.cxx

#include "cell.hxx"

Cell::Cell()
{

}

Cell::Cell(Point isoCoordinates) : _isoCoordinates(isoCoordinates)
{
  _renderer = Resources::getRenderer();
  _window = Resources::getWindow();

  // Default Floor sprite has tileID 14
  _tileID = 14;

  _elevatedTilePosition = 0;
  _sprite = new Sprite(_tileID, _isoCoordinates);
}


Cell::~Cell()
{

}

Sprite* Cell::getSprite()
{
  return _sprite;
}

void Cell::setNeighbors(std::vector<Cell*> neighbors)
{
  _neighbors = std::move(neighbors);
}

void Cell::renderCell()
{
  if (_sprite != nullptr)
  {
    _sprite->setTileIsoCoordinates(_isoCoordinates);
    _sprite->render();
  }
}

Point Cell::getCoordinates()
{
  return _isoCoordinates;
}

void Cell::drawSurroundingTiles(Point isoCoordinates)
{
  int tileHeight = _isoCoordinates.getHeight();

  for (int i = 0; i < _neighbors.size(); i++)
  {
    if ( _neighbors[i] != nullptr )
    {
      _neighbors[i]->determineTile();

      // there can't be a height difference greater then 1 between two map cells.
      if ( tileHeight - _neighbors[i]->getCoordinates().getHeight() > 1 
      &&   Resources::getTerrainEditMode() == Resources::TERRAIN_RAISE
      &&   i % 2 )
      {
        _neighbors[i]->increaseHeight();
      }
      if (  tileHeight - _neighbors[i]->getCoordinates().getHeight() < -1 
      &&    Resources::getTerrainEditMode() == Resources::TERRAIN_LOWER
      &&    i % 2) 
      {
        _neighbors[i]->decreaseHeight();
      }
    }
  }
  // call for this tile too. 
  determineTile();
}

void Cell::increaseHeight()
{
  int height = _isoCoordinates.getHeight();

  if ( height < _maxCellHeight )
  {
    _isoCoordinates.setHeight(_isoCoordinates.getHeight() + 1);
    drawSurroundingTiles(_isoCoordinates);
  }
}

void Cell::decreaseHeight()
{
  int height = _isoCoordinates.getHeight();

  if ( height > 0 )
  {
    _isoCoordinates.setHeight(height - 1);
    drawSurroundingTiles(_isoCoordinates);
  }
}

void Cell::determineTile()
{
  _elevatedTilePosition = 0;
  int tileHeight = _isoCoordinates.getHeight();

  for (int i = 0; i < _neighbors.size(); i++) //determine TileID
  {
    if ( _neighbors[i] != nullptr )
    {
      if ( _neighbors[i]->getCoordinates().getHeight() > tileHeight )
      {
        switch (i)
        {
          case 0: _elevatedTilePosition |= ELEVATED_BOTTOM_LEFT; break;
          case 1: _elevatedTilePosition |= ELEVATED_LEFT; break;
          case 2: _elevatedTilePosition |= ELEVATED_TOP_LEFT; break;
          case 3: _elevatedTilePosition |= ELEVATED_BOTTOM; break;
          case 5: _elevatedTilePosition |= ELEVATED_TOP; break;
          case 6: _elevatedTilePosition |= ELEVATED_BOTTOM_RIGHT; break;
          case 7: _elevatedTilePosition |= ELEVATED_RIGHT; break;
          case 8: _elevatedTilePosition |= ELEVATED_TOP_RIGHT; break;
        }
      }
    }
  }

  auto keyTileID = keyTileMap.find(_elevatedTilePosition);

  if ( keyTileID != keyTileMap.end() )
  {
    _tileID = keyTileID->second;
  }

  // special case: if both opposite neighbors are elevated, the center tile also gets elevated
  if ((( (_elevatedTilePosition & ELEVATED_LEFT) && (_elevatedTilePosition & ELEVATED_RIGHT) )
  ||   ( (_elevatedTilePosition & ELEVATED_TOP) && (_elevatedTilePosition & ELEVATED_BOTTOM) )
  ||      _tileID == -1 )
  &&      Resources::getTerrainEditMode() == Resources::TERRAIN_RAISE)
  {
    increaseHeight();
    _tileID = 14;
  }

  if ((( (_elevatedTilePosition & ELEVATED_LEFT) && (_elevatedTilePosition & ELEVATED_RIGHT) )
  || (   (_elevatedTilePosition & ELEVATED_TOP)  && (_elevatedTilePosition & ELEVATED_BOTTOM) )
  ||      _tileID == -1 )
  &&      Resources::getTerrainEditMode() == Resources::TERRAIN_LOWER)
  {
    for (int i = 0; i < _neighbors.size(); i++)
    {
      if ( _neighbors[i] != nullptr )
      {
        if ( _neighbors[i]->getCoordinates().getHeight() > tileHeight )
        {
          _neighbors[i]->decreaseHeight();
        }
      }
    }
    _tileID = 14;
  }
  _sprite->changeTexture(_tileID);
}

void Cell::setTileID(int tileID)
{
  _sprite->changeTexture(_tileID);
  _tileID = tileID;
}

int Cell::getTileID()
{
  return _tileID;
}

I do have a vector matrix class for easy access of Cells at specific ISO coordinates.

When I start the game, the matrix is filled with Cell objects (they live throughout the game and are accessed often). The vectormatrix itself is quite fast, but this for loop takes quite some time. (In VS2017 debug mode on my laptop it's about 4,6 seconds for 128x128 tiles!) I've debugged the code and it's exactly this Line that takes so long.

  int z = 0;
  // initialize cell Matrix

  // DEBUG TIMER START
  for (int x = 0; x <= _map_size; x++)
  {
    for (int y = _map_size; y >= 0; y--)
    {
      z++;
      Cell* mapCell = new Cell(Point(x, y, z));
      _floorCellMatrix.addCell(x, y, mapCell);
    }
  // DEBUG TIMER END: ~4600 ms
  }

I found this article but I don't understand if this is applicable for my use-case or if that's a different story.

I've also read that the new operator should be avoided if possible, but I also don't really know how to implement this.

Answer 1

Sounds like quite an endeavor! I miss Sim City 2000. I even bought an Android version for $5 and then they took it away!

Good luck on this project.

---

Writing identifiers with a leading underscore is a bad idea, and is generally dissuaded as a style. Note that it is legal for member names if (and only if) the next character is not a capital letter or another underscore.

---

You have a default constructor for Cell which is empty! So what about all the raw pointer data members?

---

NL.9: Use ALL_CAPS for macro names only

---

You will need to define keyTileMap in one CPP file; you should move the huge initialization stuff to there, too.

---

In the constructor, use the member init list, not assignments in the body of the function. Some of those can be default initializers on the data members (tileID, elevatedTilePosition).

---

Don’t define an empty destructor. Let the compiler supply it; it will generate better code that way. If you must, just declare it as =default in the class.

---

Many of the simple functions should be inline in the class definition. e.g. { return sprite; }.

---

void Cell::setNeighbors(std::vector<Cell*> neighbors)
{
  _neighbors = std::move(neighbors);
}

OK, here is a tricky one! Do not treat this as a “sink” parameter! That is only for when you know a new object needs to be created (e.g. in constructors), not for when an existing object is reused.

You are forcing a full copy of neighbors complete with a block of memory, and deleting the memory block that _neighbors already held. Regular assignment would reuse this existing block of memory, if it fit.

I’ve seen a presentation with benchmarks, but I don’t recall who gave it now.

---

_sprite = new Sprite(_tileID, _isoCoordinates);

⧺C.149 — no naked new or delete.

You should probably make this a unique_ptr as a drop-in replacement without otherwise changing the architecture.

---

if (_sprite != nullptr)

Don’t write explicit tests against nullptr. Use the contextual conversion to bool, or in this case, the operator!.

if (!_sprite)

---

for (int i = 0; i < _neighbors.size(); i++)

Don’t go through the collection by index. Look how many times you use neighbors[i] in the block of code! Use the range-for construct to iterate directly over the vector!

for (auto n : _neighbors) {
  ⋮

(Note that if you change your vector to hold values rather than pointers, you will make that auto&)

---

Your ELEVATED constants are bitmapped, right? So you can combine them.

(_elevatedTilePosition & ELEVATED_LEFT) && (_elevatedTilePosition & ELEVATED_RIGHT)

 constexpr auto LEFT_and_RIGHT = ELEVATED_LEFT|ELEVATED_RIGHT;
 (_elevatedTilePosition & LEFT_and_RIGHT == LEFT_and_RIGHT)

The && is a short-circuit operation, so the code has to jump. Jumps are slow. Testing that both bits are set is the same speed as testing one!

---

std::vector<Cell*> _neighbors;

The set of neighbors is fixed, right? Like, 8 of them, not more?

The vector will allocate memory separately. Use a fixed-size array instead.

I don’t know what you are using for the matrix. It may, however, be overly complex. If you use a flattened linear vector instead of a 2D array (or vector of vectors) you can move around to neighbors quickly by using strides. So, you might not need to store this member at all, but will build it on the fly with simple arithmetic.

Answer 2

To address your concern about using new the answer is don't. Creating an object without new simply requires calling the constructor. You will then use RAII to manage the lifetime of your objects. There may come a day when you need objects to persist beyond their scope but you shouldn't today.

This:

Cell* mapCell = new Cell(Point(x, y, z));
_floorCellMatrix.addCell(x, y, mapCell);

Can be changed to:

_floorCellMatrix.addCell(x, y, Cell(Point(x, y, z)));

And any other new's can likely be similarly removed. The article you linked is about smart pointers which have mostly replaced the use of new and delete. It is an important subject. Read up on it.

Your performance problem is either in your Cell constructor or the vectormatrix addCell() method.

• Dont name anything with a leading underscore _. Many uses of the leading underscore are reserved and the rules are complicated. If you choose to use them anyway be thorough about how it works but it is common to simply avoid them and save the headache.

• Don't declare empty constructors and destructors. Especially since you don't want to create any Cells without the use of parameters.

• You are using pointers, not references, to your window and renderer, however that should not deliver a significant performance hit.

• I would still argue that the Cell class should know nothing about how it's drawn and that the renderer and window should iterate over the vectormatrix and handle that. The vectormatrix shouldnt do that either. There is a concept called SRP or Single Responsibility Principle that suggests these classes need to know about their jobs and thats it.

• Lastly you are creating your keyTileMap every single time you make Cell. That has to be your performance hit.