2D collision detection: Performance by indexing in a grid
Indexing is a great way to imrpove the performance of your collisions detection. If you have a lot of object that can collide with each other, it's good to have an index so you don't have to iterate throught all of them for every object you're testing. It will definatly increase your performance a lot. Let's say you have 100 objects on your map. If you need to test every of those 100 objects with each other, it would roughly be 10000 (100 * 100) computations. If you have 10000 objects, you're facing 100 millions of comparisons. The indexing should be done in different ways, depending on the layout and behaviour of your elements.
The grid
The basic principle by indexing the elements in a grid is that divide your map into sections. The sections can span over either X, Y or both. When an element intersects a section, it's indexed within that section. An element can span over multiple section and are then indexed within them. The size of the sections depends on how big (or small) the most common elements are in your game. If for instance all moving elements are 100 high and 60 wide, the section should be at least 100 high and 60 wide. If it's smaller, the elements will always span multiple sections and there would have to be more lookups to adjacent elements to test for collisions against. You should try different sizes of the sections and see where the least amount of testing and the lowest computational cost is.
The gris has been divided over both X and Y axis.
The grid has been divided over the Y axis that spans from the start of the map to the end of the map. We don't really store the start and stop of the map since the values doesn't matter.
The grid has been divided over the X axis and each section spans from the top of the map to the bottom of it. We don't really store the top and bottom of the map since the values doesn't matter.
Indexing an object
I have constructed a grid where the sections are 100 wide and 100 high. In that grid, the player top left position is 60,30 (X: 60, Y: 30). He's 15 units wide and 40 units high.
Since the grid is 100x100, I divide both parts of the players position with 100 and round down. That means that his top left corner is in 0,0 on the grid. Since he's only 15 units wide and 40 high, his bottom right positions is 75, 70. I divide this with 100, round down, and notice that his bottom left is also in the same section. If I index him, I would only index his element at 0,0.
There's a another element at 180,75 which our player can collide with. He's also 15 units wide and 40 high. His top left position divided is 1,0 (180/100, 75/100) and his bottom right position is 1,1 (195/100, 115/100). Therefore we index him at both of those positions.
Indexing with Dictionary or Array[]
Since all sections have zero or more elements, they should be indexed with a List<Element>. This list are then indexed to their corresponding positions within the grid. I have tried using both (Dictionary<string,List<Element>>) and and array (List<Element>[,]). What I have found is that the insertion is much faster with the array, but it's less dynamic. You have to calculate the size of the array and be sure that an element can never step outside it's bounds. In my tests, the dictionary is about 8% slower when it comes to getting the indexed items out of it. To me, it doesn't matter much, but it could matter if performance is tight.
If you're using an array, you must be able to precalc it's size. Resizing an array can be very expensive depending on the number of objects in it.
Static and dynamic elements
A static element would be defined as an element which does not move. Never ever. And dynamic element will move at some point during the game. The static elements can easily be indexed in an array since they'll never move. Unless new static elements will be added, the size of the array can be precalculated. The dynamic elements will have to be stored in collections which can be contain a variable amount of elements. So, the statics can easily be stored in arrays in arrays. First the array which contains all the sections of the grid and then an array which contains all static elements within the grid. That makes traversal as fast as possible.
