data structure - In a 2D tile-based game, how should NPCs and tiles reference each other?

I'm making a tile engine for top-down 2D games. 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?

I think

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.

Answer

Why not both? There are times when you'll want to look to see if there's any NPC on a specific tile (such as for collision detection, as you mentioned), and other times when you'll want to iterate over all the NPCs in the world (such as for running their AI methods every frame).

A pointer per tile is not that much memory unless you're working on a memory-constrained platform or you have a really huge map.