New to the forum, collision question

[sudo]

Hi all, found this forum about two hours ago... just finished reading posts, but I still have a question.

How do most people handle collisions in a bullet hell game? Is a straight bounding-box effort going to cut it for speed, or do I need to consider a spatial hash, or something similar? I'm thinking in terms of potentially thousands of bullets at any time, so want to be as optimised as possible.

I'm writing in C++, using OpenGL.

[wondersonic]

According to me bounding-box is really efficient for 2D but you have to think about the box size generally being smaller than the real *bounding* box.

[sudo]

Thanks for the input. I wasn't sure if I was about to make a classic newbie mistake or something!

[ZacharyB]

One time, I was browsing youtube and happened upon a conversation about optimization in bullet-hell. I remarked that it might be worthwhile to only draw collision boxes for bullets near the player.

I'm not a programmer, so I have no idea how viable this is, or if it even saves on processing, since you would have to check which bullets are close... but it seems logical.

[Udderdude]

You aren't going to have thousands of bullets on-screen and have the game still playable. Even the most insane bullet hell games never go above a few hundred. Any remotely modern PC is going to be able to handle it.

Just straight bounding box on everything should be fastest. If you know which bullets are going to be fast/slow, you can skip hit detection every other frame for the slow ones.

[louisg]

Here's some optimizations you can try if it's still too slow, for whatever reason:

- Do bounding box by figuring out where the boxes *can't* collide. That way, you can fail out of the function early (e.g., if bottom1 < top2, there is no way the box is overlapping, so return false)

- Divide the screen into a grid and do a quick check to see that the bullet is actually reasonably hittable

[sudo]

Thanks again for all the input!

I guess I'll have to try writing up a quick spatial hash test to see if it's going to gain me any noticeable performance boost... as opinion seems to be split I can't even make up my own mind - intuition isn't working this time...

I know from experience that a spatial hash is the bomb in a situation where all objects need to be checked against each other, but I know that isn't the case in a bullet hell game... but at the same time, there are still a lot of things to check, so maybe it will help after all... There must be a good reason why it isn't standard practice in shmups though!

[wondersonic]

I finally found the video that will help you (remembered seeing it on another forum):

http://www.youtube.com/watch?v=GFMIStCZgQc

you can see hit-boxes

[kemical]

instead of bounding boxes, maybe use circles..you just need to check for one point inside a radius or the distance between the objects, something like that?

*edit*
http://ubuntu-gamedev.wikispaces.com/2D ... +Detection

[sudo]

Thanks again all.

To let you all know where I'm at now, I did some quick and dirty tests, and it seems that checking a couple of thousand "bullet" bboxes against a couple of hundred "enemy" bboxes every frame won't be a problem really... I guess I should really do a quick and dirty spatial hash test as well to see if it would help any more... but it seems kind of futile considering the highly acceptable results I'm already getting without one.

I guess the key to my whole problem (that I was overlooking) is that with bullets in a shmup, there's no need to check all objects in a scene against each other for collisions, they are neatly divided into collision groups by their very nature (player bullets, enemy bullets, enemies, players etc), so a spatial hash won't add much to performance (I would imagine in some cases it might even slow things down).

EDIT:
Thanks for that link, kemical. I'm genuinely surprised that the circle overlap test is faster than a box overlap test, but I'm certainly going to give it a try. In many respects, it would suit my project better than boxes. I'll have to do some tests and see!

EDIT:
I've done tests now comparing circle testing vs box testing, and my results suggest that on average circle tests take about 50% longer than box tests. Never mind... it was a nice thought

[wondersonic]

The good thing with circle detection is that you can find where the collision occured and put an explosion animation at a precise point.

For the shmup I'm working on I prefered to use optimized pixel perfect collision detection using opengl tricks (scissors, transparency test, occlusion query, more at least 5 pixels overlap) so that my explosions are very precise (note that accrding to scenes I check every 1, 2 or 4 frames).

You can see some "old" code here.

This video shows how the player bullets hit the robot "perfectly".

Of course one of the biggest optimization is, as you find out, to remember that it is not useful to test every objects against every others.

[Motorherp]

Hi sudo. You might want to take a look at these two collision detection tutorials I've written over at my shmup development website. I've specialised in game physics and collision for quite some time and these are the most efficient algorithms I'm aware off for shmup style environments:

Art of Collision Part 1
Art of Collision Part 2

Hope they help

[BarfHappy]

It is really simple in fact. when i say 0x it means hexa
In cave danmaku, only the center of the bullet is checked against a fixed rectangle around the center of the ship.
In dodonpachi daioujou black label , the rectangle is 0x160 units wide and 0x180 units high.
the ship has a 0x9300 units of vertical movement and 0x5000 units of horizontal movement to give you an idea.

To ease the check, some bullets have an oscillating flag (per bullet) that tells if the bullet is to be checked or not, hence why you sometimes miraculously survive, because it was on your ship rectangle the frame the bullet inactive.

How they do ? easy
for each bullet they do:

if(bullet flagged as non colliding skip to next bullet)
deltaY1=0x100
deltaY2=0x80
deltaX1=0x80
deltaX2=0x80
D0=YShip+deltaY1
D1=YShip-deltaY2
D2=XShip+deltaX1
D3=XShip-deltaX2
D4=YBullet
if(D4>D0) skip to next bullet
if(D1>D4) skip to next bullet
D4=XBullet
if(D4>D2) skip to next bullet
if(D3>D4) skip to next bullet
Set bullet as collided with ship
if(not invincible) go to ship destroyed
process next bullet

simple no ?