Hello, I would like to know if there is a really very fast technique to detect collisions for a "big" number of sprites. Currently, I'm using the grid method, but it is not accurate.
For example, to get the sprite position on the grid, I use binary offsets to save CPU load. The problem is that to check if the sprite is on several boxes of the grid, it requires to do 4 operations by adding the width and the height of the hitbox, which kneels the CPU.
I work on a very weak system compared to current computers. Is there a method to manage a lot collisions without killing the CPU?
Kenshoryu said: The problem is that to check if the sprite is on several boxes of the grid, it requires to do 4 operations by adding the width and the height of the hitbox
You can insert sprites to only one cell which contains its center. But then while checking for collisions you need to iterate 4 cells instead one. For me this always was much faster because there is no need for dynamically sized cell lists. Instead each cell has only a pointer to first object, and objects have a next pointer to build a linked list. It's possible to compact the objects so they are sorted by cell and no list is necessary, just a first object index and object count per cell.
(Same concepts apply to loose octrees, and if you have sprites larger than a grid cell you need a multi level grid.)
Kenshoryu said: 1) Establish a grid of cell larger than the sprites
If all sprites had the same size, the ideal grid size would be the sprite size. (Grid could be a bit larger, but not smaller)
Kenshoryu said: In this way, if a sprite is on a cell containing targets, it is enough to read the list corresponding to its cell.
No, for the loos method i have described (putting objects only into one cell), you always need to iterate multiple neighbor cells to find all collisions.
Here an image of a multi level grid (parent grid is always double the size of child grid):
You see, Pacman is in the dark grey cell. To detect collisions for Pacman it is necessary to iterate over a 2x2 range of cells (light gray), depending on if its center is on the left / right, or bot / bottom from its grid center. Initially and to be sure, you can start using the full neighborhood of a 3x3 range. But later you can verify only 2x2 is actually necessary. It is necessary to check multiple cells because objects overlap and are rarely fully bounded by a single cell.
Important: The overlap is guaranteed to be equal or smaller than the grid size. To guarantee this is true, a sprite that is only a bit larger than a red grid cell, has to go into the parent green grid.
To detect collisions between multiple levels, 2 options exist:
1. Pacman would not detect collision with the Ghost. Instead the larger ghost has to iterate over all child cells it intersects. (green range) But the ghosts bounding rectangle needs to be extended by half of a child levels grid size, to ensure we do not miss overlaps. This is the faster method if you have a small number of large sprites.
2. Pacman would iterate also a range of parent grid cells, extending it's bounds by half of parent grid size. (not shown in the image) This is faster if there are many large sprites.
Notice, iterating multiple cells is not that bad if you compact the objects to the cells, so iterating a list does not jump in memory. Only moving to the next cell in the range causes a jump, and likely only when moving in Y direction. So this is both work efficient and cache friendly, and it has no worst cases.
I list 2 alternatives commonly used and their disadvantages (You see those in tutorials much more often than the better loose method, because they are easier):
Put objects only in one cell, and only if they are fully inside the cell. If they intersect two cells, move them in the parent cell until they are fully contained. This is simple, but has fluctuating runtime. Worst case is: If all objects are at the center of the world, all objects end up in this single root cell that bounds the whole scene. In practice this might not happen too often, but it's still likely they interest a dividing line of any of the top levels from the hierarchy, and objects that do so end up performing large amounts of collision tests.
Put objects into multiple cells. This is much better in theory, but building the grid becomes slower and required memory is not constant. It would be easy to implement, e.g. using std::vector of objects per grid cell. But that's really slow because it causes dynamic allocation. It would be necessary to have some memory management working with a constant max pool size, and implementing this makes the approach as complicated as the loose proposal.
A different option would be to use a BVH. This also stores objects in only one node but makes the node bounds adaptive. But here we really need a tree and so traversal which is not cache friendly. So we use this in 3D more often when a volume grid would take too much memory and compaction becomes expensive.
EDIT: Ofc. it's likely you get away with only one level of grid, but thinking about the multi level approach helps to see the larger picture. Also i'm not 100% sure i did not make a mistake when talking about extends to guarantee we do not miss collisions. It's a bit confusing, but not really hard : )
Interesting! When I first started experimenting with collision detection and a very large number of sprites, my performance was horrible. I actually discovered on my own to use a grid system to reference the position of sprites on screen. For example, if you do it the basic way of checking every sprite against all sprites to see if they were colliding, this would eat up tremendous CPU because if you had an array full of say 15,000 sprites, you would have to cycle through that entire array to check all the sprites. So, I asked myself, is there a way to avoid cycling through the entire array of sprites and instead only check the sprites that possibly be near me?
I implemented that using a grid system, by referencing the position of the sprites on a grid … every sprite would then get a small rectangular box around it and checked with the grid to see if there were any sprites “in the vicinity” I then did collision detection on only the sprites that were “close to me”. This improved performance by a good margin but you have to face reality eventually and ask yourself, will I really ever have thousands of sprites on screen in a 2d game? Probably not.
@JoeJ Hello, thank you for these explanations. I will work on the grid on several levels, this method seems to me the most suitable for my game. Most other methods are more complex, because I really work on a weak system. Ideally I should work in ASM, but I can do C with decent performance. It's forbidden for me to make divisions / multiplications or any other calculation which could strangle the CPU during the game.
What I noticed was that the game slowed down when I went through the linked list containing the active enemies. I.e. ~ 10 bullets x 16 enemies. If I decide to test the collisions, the CPU is dead. This is why the grids on several levels should help me.
I have a few sprites of different sizes, but they are not the majority.
I suppose that to check the neighboring cells, I need to create a map in order to avoid any calculation to determine which are the neighboring cells. So I should add a neighbor struct containing left, right, top and bottom which are pointers to the cells.
Kenshoryu said: @JoeJ Hello, thank you for these explanations. I will work on the grid on several levels, this method seems to me the most suitable for my game. Most other methods are more complex, because I really work on a weak system. Ideally I should work in ASM, but I can do C with decent performance. It's forbidden for me to make divisions / multiplications or any other calculation which could strangle the CPU during the game.
How many sprites do you have? (And out of curiosity: What system is it that you are working for?)
Thing is, while such accelerations structures help a lot if numbers are big, they have some constant cost and if numbers are small it's not worth it. Simply testing each sprite vs. each other could be the faster solution.
I remember C64 had hardware sprite collision detection with interrupts. Maybe Genesis too?
30 sprites would be brute force 450 tests. I doubt using a grid can be faster. But if so, i would tend to use this option 2 from above:
JoeJ said: Put objects into multiple cells. This is much better in theory, but building the grid becomes slower and required memory is not constant. It would be easy to implement, e.g. using std::vector of objects per grid cell. But that's really slow because it causes dynamic allocation. It would be necessary to have some memory management working with a constant max pool size, and implementing this makes the approach as complicated as the loose proposal.
With 30 sprites you could use 4 bytes per cell with one bit for each, so memory is constant and none of the above problems would matter.
