How do I efficiently manage a tile-based map with items and characters?

Question

I'm working on a simple C++ game to learn the language. It's ASCII, and features a tile-based map, enemies and items that spawn randomly. The player is, as usual, the '@' character. I'm trying to find the best way to handle the map and characters. I have the map in a 2D vector. Originally, it was a vector of characters, but then that became too hard to manage and too fixed, so the map is now a 2D vector of Tile objects. My enemies are contained in a vector called NPCs, and the items that get spawned are contained in a vector called Items.

My problem is in handling the relation between my map tiles and enemies/items. When an enemy stands on a tile, I have a pointer in the tile that points to that enemy, called npcPtr. Same goes for items, with another attribute of that object called itemPtr. This creates problems, because when an enemy dies and gets deleted from the NPCs vector, the pointers in the map don't dynamically update, and now point to the wrong enemies. The same happens for items. I partially solved this by updating the pointers in all the tiles after every move, but that does not seem like the best approach. How should I handle this tile/character relation?

I read this similar question, and that's pretty much how I handle things, but it doesn't seem to be an optimal approach. The advantage to having pointers in the tile is that I can check whether that tile is an enemy, an item or nothing; I don't want to lose that functionality. I can also obtain the NPC/item data right away, using the pointer, without having to parse through the NPCs vector.

---

My Code:

vector <vector <Tile>> _level //this is my level vector
vector <Character> _NPCs //this is my enemies vector

Making a new tile

Tile t //and then I set the tile parameters

Adding a tile to the level

levelLine.push_back(t)

Adding a whole line to the level

_level.push_back(levelLine)

Making an enemy

Character c //and then I set the parameters

Adding an enemy to the _NPCs vector

_NPCs.push_back(c)

Positioning the enemy objects in the level

//for j in level lines and k in level colums
if (j = _NPCs[i].getY() && k = NPCs[i].getX()){
    _level[j][k].setNPCptr(&_NPCs[i]); }

Handling enemy death

//re-initialize tile where enemy was to empty tile,
//_NPCptr gets set to nullptr
_NPCs.erase(_NPCs.begin() + npcPosition) //erase NPC from enemy vector

for (size_t i=0; i<_NPCs.size(); i++){
    _level[_NPCs[i].getY()][_NPCs[i].getX()].setNPCptr(&_NPCs[i]);
}

Answer 1

The way I handled entities as I call them in my game is to break the map into sectors (4^2 tiles per sector in my case). And further, a separate set of 'active' entities, those which are visible or marked 'always active'.

Each frame, I check to see if the camera has moved and figure out which entities should be moved from their sector to the active set and then which should be removed. Then, I only update/handle entities in the active set.

(This would detach entity position from sector directly, and cut down on the amount of copying things around).

This also helps with spawning, simply add the entity to the active set on spawn and it will be moved to the correct location during the next update cycle.

Using pointers for all entities (sectors and the active set could be vector), you can allocate a new entity when you spawn, and only delete it when the entity is removed completely from the map

One optimization to make (especially on the active set) when removing from a list is to swap the index of the entity you want to remove with the last one, and then decrease the size by one. This way you won't have to shift [potentially] an entire list every time you remove something. Note: this will possibly make things change their render order (this could be solved by some Z ordering if you want)

Answer 2

How do you manage the life cycle of your pointer? When an enemy dies, do you free it before reassigning it to another enemy or do you update the pointing directly?

This could help: https://stackoverflow.com/questions/2654415/proper-way-to-reassign-pointers-in-c