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.

I would definitely recommend a quadtree. As you mention yourself, most grids would be empty most of the time. Managing linked lists is a lot of work considering the amount of bullets, that will travel several grids, before getting close to any enemy.

By using an algorithm with low tolerance for enemies in large areas, you should be able to create mostly enemy free regions where the bullets can travel without checking for collision.

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

As an alternative to a dynamic quadtree you could let several cells share a linked list. i.e. 5x5 cells share one linked list = 3600 in a 300x300 map. And no, a linked list with no elements uses very limited space.

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?

Assuming you don't like interpenetration, "sweep scan with AABB" tests are going to be very common: for circles (player, enemies, bullets) against solid tiles (walls).

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?

Sorry for the quite late reply. Even though you are using circles, you SHOULD still use AABB's to filter out all the circles you are definitely not hitting. That way you only need to calculate the much more expensive sphere collision on a few colliders, rather than every single one. This is common practice in most if not all physics engines.