9
\$\begingroup\$

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.
Improve this question
\$\endgroup\$

2 Answers 2

Reset to default
11
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • 5
    \$\begingroup\$ +1 I tend to agree with this, however @lezebulon, I suggest that you encapsulate any logic that needs to update both together, as early as possible. That is, when a player leaves a tile, there should be one atomic operation (function call) to remove both pointers, player-to-tile and tile-to-player, at the same time. And the same for when a player arrives on a tile, do the two pointer assignments together. This will save you some potential chaos where references don't agree with one another, i.e. one exists while the other does not. \$\endgroup\$
    – Engineer
    Nov 12, 2011 at 21:07
0
\$\begingroup\$

How do you handle collisions with the map? If you have a collision layer, a very easy way would be to first create a list of NPCs with coordinates indicating on which tile they are on and then iterating through that list and marking the collision layer tile under the NPC as a collision tile. That way, the collisions against NPCs would be handled at the same time as rest of the map. That is, of course, if the NPCs don't move...

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .