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.