I'm making a tile engine for 2D games (seen from the top). Basically the world is composed of a grid of tiles. Now I want to put for instance NPCs that can move on the map.
What do you think is best: 1) each tile has a pointer to the NPC that is on its tile, or a NULL pointer 2) having a list of NPCs, and they have the coordinates of the tile they are on. 3) something else?
1) is faster for collision detection but it would use much more memory space and it is slower to find all NPCs in a map. 2) is the opposite.