Optimization for a bullet hell?

[dudemanthing]

Hey everyone!

While designing a bullet hell shooter (http://en.wikipedia.org/wiki/Bullet_hell#Bullet_hell), I thought of an important way of optimizing the collision detections between the player and the hundreds or thousands of on-screen bullets.

The detection method I am using is the popular pixel perfect detection method by Troy Gilbert:
http://troygilbert.com/2009/08/pixel-perfect-collision-detection-revisited/

Instead of pushing the thousands of bullets in an array, looping through it, and checking for a hit for each one, we can just make one container DisplayObjectContainer (for example, a MovieClip or a Sprite) and spawn each bullet inside that container with addChild.

Then all we have to do is check if the player's hitbox touches the container, which will let us know if it's come into contact with a bullet, and if so kill the player and clear the screen of bullets.

However, this doesn't work the other way, for player's bullets on enemies, because of enemy HP and needing to know hits on specific enemies. Luckily the number of bullets from the player tends to be much smaller than the number of enemy bullets.

[bluemagica]

Well the shortcut is good, but I would suggest you to take a completely different approach. You should use divided-space collision checking. If you implement in properly, you can test through atleast 5000-6000 objects easily, without affecting your framerate. The idea is simple, divide your board into quadrants. Then register each object to it's respective grid cell, based on it's x,y. then you simply hittest those objects which lie in the same quadrant cell. And in your case, you will only need to test the quadrants where the enemy or player is, and that means you get even better optimized performance.

[Gnoll]

That's called a QuadTree.

You can find a nice example here http://lab.polygonal.de/2007/09/09/quadtree-demonstration/

[bluemagica]

Actually, a quad-tree is a further optimized version where you repeatedly sub-divide each quadrant. What I explained is the very basic of "spatial locality" based collision detection.

[TOdorus]

Good tips one the broadphase guys, but what about the actual check?


The detection method I am using is the popular pixel perfect detection...

Stop right there. You don't need pixel perfect. You can choose: a few objects with precision or a lot of objects with less precision. The cheapest method of collision detection I've found yet is circlebased collision detection.



//Pythagoras for the win!

//square distance between the two centres
var dX:Number = circleA.x - circleB.x;
var dY:Number = circleA.y - circleB.y;
var dist2:Number = dX*dX+dY*dY;

//compare squared distance to the sum of the squared radiusses
if(dist2 <= radiusA *radiusA + radiusB*radiusB){
//COLLISION!
}
Cheap as can be, but you are limited in your design. Projectiles and ships need to be somewhat circular.

You can also use rectangle based collision in conjunction with circlebased, but it's a bit more expensive as you need to check 2 lines instead of 1 and you use a slightly different method (you don't need Pythoagoras as you check on two fixed axes).

[bluemagica]

Well, I personally prefer calling this distance based collision detection, rather than their geometric names, cause essentially you are checking the distance between two objects! And yeh, these are the best methods while dealing with spatial-locality, because often in these situations you won't even consider the visual side of things, rather deal with pure numbers. Kind of like a particle engine, where each particle is just a bunch of numbers, and on-screen they are just a pixel.

But on the other hand, flash's pixel level collision detection is pretty fast if you work with a pure bitmap based game(though not needed in this case), and I don't think it will give too much of an overhead, if employed correctly. Again as todorus said, bitmap based collision detection is a bit overkill here, and especially if you are going to use that CDK, cause as far as I know, it will draw your sprite onto a canvas and then do the checking, thereby wasting a lot of resources in the process.

[dudemanthing]

What about irregular hitboxes (e.g enemy ships)? What should I do in those situations?