Monday, July 16, 2012

Data Structures For Bullet-Hell Shooters

For those not familiar with the genre, a bullet-hell shooter is a game that makes the player navigate through a moving field of hundreds, if not thousands, of projectiles that typically kill the player in one hit. Two of my favorites are Mars Matrix and Ikaruga. With the large number of potential collisions to detect, data structure optimization can greatly improve performance.

First off the problem needs to be broken into a few different cases: 1000s of projectiles (enemy bullets) and one or two targets (players), 100s of projectiles (player shots) and 10s of targets (enemies), and 1000s of projectiles that are also targets (bullet bullet collisions, think billiard balls). The reason for this distinction is that the test everything approach in these cases results in 1000s, 10,000s, and 1,000,000s of potential collisions respectively. The bigger the number, the bigger the impact of any improvement which needs to overcome the cost of the data structure.

For the sake of simplicity I'm going to assume that the bullets are going to be sorted into bins, and that the cost of testing if a bullet should go in a bin is the same as the cost of testing a bullet/target collision. Secondly, just about every algorithm has a worst case of all 1000 bullets stacked perfectly on top of each other. While some clustering of bullets will occur, we're going to assume that the bullets are fairly evenly distributed. If the bullets were all stacked up, the game would be too easy. This means that both the programmer and the game designer are working towards the best case and we should never see the worst case. In addition to those constraints, we are going to do all the calculations for all bullets in every update; no temporal optimizations. 

The solution to the first case is easy enough: test every bullet against one player. This results in N tests, where N is the number of bullets. Assuming we used any data structure at all, it will take at least N tests to create or update the data structure. So without actually checking for collisions yet, we've all ready done the same amount of work. Now with two to four players, you might be able to squeak out some improvement by using a data structure, but it might not be enough to justify going through the work of programming it. However, if you're going to implement one of the algorithms in the next section, it won't hurt too much to use it for this case in the name of code simplicity.

Now onto the second case. Think of a rectangle that is targets wide and bullets tall. The area of this rectangle represents how much work we have to do. The more square it is, the bigger the benefit from optimization. (A square represents an O(N^2) algorithm, A rectangle so thin it's a line is O(N) ) Because, this case the rectangle looks more like a thick line there is some room for optimization. The more targets there are, the more the optimization will pay off. The data structure I'm using in a prototype that I'm making is a two dimensional hash table of linked lists. The best way to visualize it is a grid of linked lists. Every bullet is added to the list of the square it's in. For the case of big bullets that overlap multiple squares, it is added to multiple lists. Then, for each player, do a collision test with all the bullets in the lists in the squares the player overlaps. Assuming that 1000 point sized bullets are evenly spaced in a 10x10 grid, there's only 10 bullets per square. So with a player overlapping at most 4 squares the work done is 1000(for building the data structure) + 40(tests) * number-of-players instead of 1000(bullets) * number-of-players. That's pretty good.

As awesome as it sounds, there are a few gotchas with this approach. Firstly, even though the more squares you divide the field into the better the performance is, there's a practical limit due to the fact that smaller squares means that the player will over lap more squares and have to hit test against more lists. My gut instinct says don't make the squares smaller than the player and assume that he always overlaps four squares. Secondly, if a large player hits a large bullet, there could be multiple collisions from different lists. You'll need to add a tag field to each bullet to test for a previous collision. And Finally, memory allocation of linked list nodes is going to be a burden. Pre-allocate a large array of nodes and just doll out nodes from there. Because you know that all the nodes are freed every frame you can free them all by nulling out the node reference in every square and setting the index of the next node to hand out back to the first node in the array.

As for the 1000 billiard balls collision case, that's big enough for it's own article.