Thursday, July 26, 2012

Data Structures For Bullet-Hell Shooters pt. 2

I was originally considering writing up a solution to the 1000's of billiard balls problem using a modified quad-tree approach, but then I realized that it only takes approximately 1000 bullets to cover the screen. So having a O(n log(n)) solution with a large constant multiplier will never out perform an O(n^2) algorithm with a fractional constant that approaches 1/n rendering the average case close to O(n). So, unless you modelling atomic interactions, it probably won't get you much for the complexity.

Instead of writing up the quad-tree, I'm going to do a quick writeup on doing the collision test with the grid of bins then talk about some (pre-mature) optimization tips. Get ready, this is really quick. Assuming you've created the data structure in the previous article (or any data structure, really), just change your update loop to:


Bam! That was easy. Now onto the Optimizations.

Quick Optimizations

Sort objects by potential interactions. The basic premise is that if an object can only collide with objects that have not yet been inserted into the data structure, then you can just insert it without collision testing anything. Now, I'm not talking about a real time sort of every item in the game (that would be quite the comparison function); I'm talking about it at a conceptual level. For example lets say you have fireballs, oil puddles, and players. Fireballs can ignite oil puddles and players, and oil puddles can make a player slip. Because fireballs can't interact with themselves just insert them all first with no collision testing. Then collision test all of your oil puddles against the fireballs followed by a batch insertion of the puddles (so you don't test oil puddles against themselves). Finally Collision test your players against everything.

Create a combined collision-test-and-insert. This takes advantage of the fact that you've all ready calculated which bins the object interacts with. When separate, the two functions will do twice the work. As a follow up to the oil puddles in the previous example, a batch collide followed by a batch insert will be more efficient for a large number of oil puddles because you've eliminated testing oil puddles against themselves (potential O(n^2) growth). However, for a small number of oil puddles, the combined collision-insert will be faster because you don't have the duplicate bin lookup (O(n) growth).

Create a fast path for point objects; they can never cross bin boundaries. To make this optimization even better if all your bullets are the same size then you can change all the bullets point sized and add the size change to the player's radius. The collision results will be the same with much less work.

Create a second list for static objects in every bin. The static particle don't need to be cleared from the data structure every frame so why do the extra work? Just keep them separate bin from the dynamic particles. This also adds an extra step when deleting a particle: you have to manually remove it from the list.

Eliminate redundant collision tests with tagging. In our grid scheme, large objects are tested against multiple lists. If a second large object is in multiple lists then the two objects can collide multiple times in one update. Once for each list that they share. To test for this, each object can have a flag for if it has all ready been seen. The problem with this approach is that you have to clear all the flags before testing the next object. There is an old optimization for this using a tag instead of a flag. Each object gets an unique ID and a tag. After testing for a collision, the target gets tagged with the sources ID. Then before each collision just check if the ID equals the tag. The tag doesn't need to be cleared when colliding the next object because the tag is going to be something other then the current tag.