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

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]);
}

• What's the problem you want to solve here? You mention the linked answer - storing this information reciprocally (tile knows what's on it, NPC/item knows where it is) - doesn't seem optimal. Are you just worried about the memory overhead of storing a map coordinate with each character? This is tiny compared to typical game data like textures/sounds, so you may be in micro-optimization territory here. Also consider that it helps you do other things more efficiently, like answering "where is the nearest key?" by iterating over each key (likely few), instead of searching each map tile (hundreds!) – DMGregory Oct 5 '16 at 22:13
• I don't iterate through the tiles, I do iterate through the NPCs/items to find the nearest. I use the pointer in the tile just to know what's inside a tile. Let's say I want to move the character or an NPC, instead of having to check if any of the NPCs or any of the items are positioned in that X,Y, I just have to check if the NPCpointer and Itempointer of the tile are nullptr to see if it's empty, and if it's not I can use that same pointer to access them. I think that's pretty handy and slims the code down. What do you think? – RedKnight91 Oct 7 '16 at 1:06
• I'm pretty sure Vector isn't designed for auto memory management in this way. I had a similar problem once, and I think I just used a fixed array buffer, and tracked everything myself. Another possible solution is using the boost library, I believe. Though I strongly recommend using a buffer or memory pool as auto allocation/deallocation is not going to be efficient for game programming, in my experience. – bigcodeszzer May 15 '17 at 17:43

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)

• This technique is usually called "Spatial Hashing". – Philipp Oct 20 '17 at 8:39

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?

• my enemy kill cycle is the following: 1. Clear tile where enemy was, 2. remove enemy from NPC vector, 3. reassign pointers to tiles, 4. move player. To reassign the pointers what I do is i cycle through the NPC vector and assign their pointer to the tiles in the NPC x,y coordinates. Not totally sure how your link applies in my case, I am saving everything on the stack, so not sure how this works. Again, I am doing this game while learning C++, so while I am familiar with stack/heap I haven't fully mastered that aspect yet. : ) – RedKnight91 Oct 6 '16 at 1:34
• I don't know if this helps you understand but my NPCs vector is created vector <Character> _NPCs and then I do 'Character c', set all the attributes and .push_back on the vector. later on I assign his pointer (&npc) to a Tile, as an attribute (Character* npcPtr). – RedKnight91 Oct 6 '16 at 7:49
• What do you do for reassigning the pointer? npcPtr = &npc or *npcPtr = npc ? Also I am not a pro of C++, if you can edit your first post with your code it will help other guy here to guide you on the right fix. – Matteo Oct 6 '16 at 8:36
• I do npcPtr = &npc. Ok I'll update the question, thank you. Btw I'm Italian, and I think you are too given your name : D – RedKnight91 Oct 6 '16 at 9:02