I have an NxM grid in this scenario:

• Blue blocks are the map
• Red circles are enemies
• Green circle is the player
• Little magenta dots are bullets, both from the player and enemies.

Collision tests I would like to make are (if relevant):

• Player vs enemies
• Enemies vs enemies
• Player bullets vs enemies
• Enemy bullets vs player

I currently perform map physics by using the tilemap directly, but now I have to implement physics for entities, and thinking about options is getting me a bit mad. Current options for spatial indexing are a grid, with each cell being the same size as the current map or any other size, and a quadtree, for adaptative cell size.

The simplest option would be use a grid, so that's the one I would like to do in first place, but anyway, a few problems arise:

• Since bullets are smaller than entities, cells may be a lot populated of bullets
• The idea of having NxM linked lists overwhelms me. If the map were 300x300, 90000 linked lists.... anyway, a way to solve this could be to increase the cell size, but then, the previous point gains weight.

I guess the way to solve these two issues is to use a quadtree. I would go with the cell approach to see what happens, but still thinking that those are so much linked lists (one for each cell). I just wanted to have a little feedback on my concrete scenario, and let more experienced people tell how they would approach this. Maybe I'm overrating the cost of having so much linked lists and I should just go with it and try.

Another sub-question here is that if I want to handle collision tests separately, I think I should be using multiple data structures. Let's say, as player bullets won't collide with the player, I just don't need to check it, so I could make several data structures with proper entities on each, but if 1 grid with 90000 linked lists overwhelms me, I don't know how it would be with 90000 x 3 or 4.

Thanks in advance.

EDIT: re-thinking about it, the linked list thing is not as memory costly as I thought, since almost all of cells would be empty.

That being said, you need a big game before performance should be an issue. Assuming you are using sweep scan with aabb.

This is not a big game, but anyway this is another point I want to focus on. I want to use circle shapes, and not AABB's, so my final collision check will be a distance calculation. I didn't get the sweep scan with aabb, I mean, if I'm not doing it that way, could I have any performance issue?