2d pixel-perfect collision detection with rotated graphics

[Qqwy]

I am trying to create a shoot-em-up/bullet hell game in HTML5. For this kind of game it is very important to have pixel-perfect collision detection as this makes the game feel fair. For speed purposes, I decided to use Pixi.js to render my objects to the screen, which has a high enough speed to render tons of them to the screen.

 

However, the next step would be to check for collision between objects. I read this article and managed to create a script that incorporates that concept.

(Basically:

-Create a black-and-white mask of all different kinds of objects

-When the bounding boxes of two objects hit, check for pixel-perfect collision

-Depending on the area that overlaps, check for the corresponding overlapping pixels in both masks

-If the pixel checked at a certain time is white in both masks, we have a collision.)

 

This works great and is fast.

 

However, I do not know how to modify this concept to include rotated objects. I read about the way this happens in most engines, which basically means to create a separate mask for each possible rotation, which would mean lots of masks if you want a fluid-looking rotation -> resource and performance heavy.

Another way would to re-draw a mask every time you check collision on an object to use its current rotation. However, this would also mean lots of drawing in the slow Canvas way and will probably also be far too slow.

 

So I am thinking that maybe there is a way to check the masks not linear (i.e. from top to bottom, left to right) but instead in a different way, maybe using advanced trigonometry, but my math is not good enough to produce a solution.

 

Or maybe there even is another, better way?

 

Thanks for your help,

 

~Qqwy

[_wumpus]

I'd counter that pixel perfect collision is not required to ensure the game feels fair. In so many commerical bullet hell shmups (and the arcade classic) the collision system is nothing more than non-rotated rectangles or just circles. 

 

If you look at many of the popular space shooters you'll see that the actual player collision box is often only the cockpit and bullets will pass by the hull without impact. Pixel-perfect collision will not make your game fair - that will be down to all your mechanics, your level design, your enemy behaviour, your controls and much more. I think you'll find yourself chasing a technical requirement that doesn't actually help you in any way.

[rich]

I have to agree here, most bullet hell shmups I've played have tiny hit areas in the center of the sprites for the player, and simple AABBs for the enemies. I would proceed on that basis first and see if it really does fail for you during play test.

[Qqwy]

I am trying to use typographical symbols as visible entities. This does look great. However, quite a few of them have irregular shapes. I do not think that defining bounding boxes would be a satisfiable solution to this problem.

Also, in HTML5 it is very hard to get the dimensions of a certain symbol. Quite a few symbols are placed in odd places in relation to the baseline of normal text. The only accurate way to check the dimensions of the visible part of a symbol would indeed be to print the symbol to a buffer and loop it per-pixel.

 

If I have an enemy as for instance:  ኧ, bounding boxes do not seem to be a viable solution to me.

[Felipe]

Hello,

I made a while ago an example of pixel perfect collision between 2 images. I haven't tested with rotated one though.

I don't know if it's the most optimized solution for this but it could help you.

 

Here is the demo:

http://shin.cl/pixelperfect/

 

The js file:

http://shin.cl/pixelperfect/main.js

 

ps: sorry about the spanish comments.

[TheHermit]

Does Pixi.js use WebGL? If so, you could write a shader to basically handle most of the collision tasks on GPU. The idea would be that you assign each non-colliding sprite 'category' to its own channel. Perhaps the player and their bullets is the alpha channel, enemy bullets are green and blue, and the enemies themselves are red. This would limit you to 255 enemies, 65535 enemy bullets, and 254 player bullets at once - probably enough.

 

You then render the sprites in three passes to a hidden buffer using a unique color index for each sprite and only modifying the sprite's particular channel. When two sprites of the same type overlap, have the new replace the old completely. When you're done, you can can through the pixels of the resulting buffer to see where collisions occured - any pixel that has non-zero values in two different collision channels. The values of the channels tell you then what objects collided.

 

Oh, and make sure not to use interpolation or you'll get really weird results.

 

For speed, you can gracefully downgrade accuracy by using a lower-resolution hidden buffer than the full resolution of your game. Every-two-pixel-perfect collision is probably not noticeably different from pixel-perfect collision for example, but will be 4 times faster.

[Qqwy]

Hello,

I made a while ago an example of pixel perfect collision between 2 images. I haven't tested with rotated one though.

I don't know if it's the most optimized solution for this but it could help you.

 

Here is the demo:

http://shin.cl/pixelperfect/

 

The js file:

http://shin.cl/pixelperfect/main.js

 

ps: sorry about the spanish comments.

Thank you! That indeed looks very similar to the code I have right now as well as the article I linked to in the first post. Seems pretty optimized to me, but I'm no expert of course.

As soon as there are more than two objects, speed might be increased by changing the bounding box collision part (that checks for overlaps between all objects) to check horizontally and vertically separately, to reduce the amount of checks that have to be made. However, I have not tried this myself yet either.

 

I'll upload my current collision test to the internet tomorrow so you can, if you want, see my (poorly structured and probably also poorly optimized right now...) collision code.

 

Does Pixi.js use WebGL? If so, you could write a shader to basically handle most of the collision tasks on GPU. The idea would be that you assign each non-colliding sprite 'category' to its own channel. Perhaps the player and their bullets is the alpha channel, enemy bullets are green and blue, and the enemies themselves are red. This would limit you to 255 enemies, 65535 enemy bullets, and 254 player bullets at once - probably enough.

 

You then render the sprites in three passes to a hidden buffer using a unique color index for each sprite and only modifying the sprite's particular channel. When two sprites of the same type overlap, have the new replace the old completely. When you're done, you can can through the pixels of the resulting buffer to see where collisions occured - any pixel that has non-zero values in two different collision channels. The values of the channels tell you then what objects collided.

 

Oh, and make sure not to use interpolation or you'll get really weird results.

 

For speed, you can gracefully downgrade accuracy by using a lower-resolution hidden buffer than the full resolution of your game. Every-two-pixel-perfect collision is probably not noticeably different from pixel-perfect collision for example, but will be 4 times faster.

Pixi.js does use WebGL. However, shaders are not really supported right now (It is on the roadmap for the next version though?). Although your solution seems to be a rather involved one, it is a very interesting concept, and I might give it a go. As I work with rendered text symbols right now, I can easily re-colour them without using shaders, but only testing will tell about if this technique will be fast enough.

 

Lowering the resolution is a great idea.

 

 

 

By the way, I suddently had another idea.

What if I were to 'cheat' with masks? What if I would create a mask of each picture similar to how I do it now, but then with the background being solid black, and the actual object being transparent? If I would then draw (in Pixi.JS for speed purposes) the overlapping parts of two colliding objects on a white canvas, I would only have white pixels where those two objects collided. This is including rotation.

 

But I'm not sure if this is better than theHermit's proposed way.

 

Thank you very much for your replies!

[Qqwy]

All right, a slight update. I tried implementing the many-colours idea.

 

This is what it looks like now

 

It seems to work. However, there are a few drawbacks:

-It seems to be the case that a WebGL instance seems to be linked to a Canvas. It is impossible to create more than one instance. Ergo, it is impossible to do the collision detection by drawing with WebGL in another canvas.

This means that the game will slow down significantly because I will have to rely on drawing with the plain canvas commands again. This might become a very big bottleneck.(or actually, bottlenecks become increasingly small, I guess? )

-Simply drawing the text symbol in a certain colour on the collision map is not enough. I had to loop all of the pixels to ensure that they were not translucent, in order to get all of the pixels of a certain object the correct colour. (There is no quick way to turn off antialiasing for canvases, sadly).

-To increase performance, the script does not go through all of the buffer, but only the parts where it knows that two bounding boxes are colliding, and in that area only looks for the two specific kinds of colours of those two objects.

-Something I didn't realize at the start was that setting the blending mode to Lighten is very important. Lots of wasted debugging time, *sigh*.

 

In any case, this seems to work *for now*. If there is anyone who could think of a way to still do all the drawing in WebGL, I'd be all ears.

[TheHermit]

So for WebGL I know there's a way to render directly to texture for this kind of thing, so you don't have to display it. I've seen this in Three.js, for example in the glow tutorial. Its used for a lot of post-processing effects like blurs and such. You might need to have your own shaders to do it though.

[hustlerinc]

Have you considered AABB combined with getImageData()? I don't know if it's resource heavy though.

[Paul-Andre]

Instead of using actual pixel perfect collision, you might choose a few significant points on your spaceship, and check only at these points. If you use a webGL shader, this will not work for people who don't have webGL such as myself.

[AshleyScirra]

I'm a little late to this thread, but we wrote a pixel-perfect collision engine for Construct Classic (in C++) that supported rotation and stretching. It was one of the most difficult bits of software I've ever worked on (and bug prone - it took ages to make it bulletproof! But maybe that was our relative inexperience).

 

I don't think you can really use the GPU for collision tests in general. If you have to read back pixels from the canvas you'll stall the rendering pipeline which will hit the framerate pretty bad, and the GPU<->CPU bridge tends to be pretty slow on some systems as well.

 

Our approach was:

- make a bitmask in memory for the base unrotated unscaled collision mask (1 bit per pixel, so each byte covered an 8x1 row of pixels)

- upon testing collisions, lazy-generate a new bitmask with that object's scale and rotation. This is really hard, since if you want pixel-perfect accuracy you have to get some fairly subtle details like rounding to match what's rendered. Even allocating the right size buffer is non-trivial, since if the object width is not a multiple of 8, you need to deal with a right-hand gutter.

- each instance of an object caches a single scaled/rotated bitmask. If its rotation or scale changes and it needs to test a new collision, it will throw away the mask, regenerate a new one, and then test with that. If its rotation or scale is not changing, it can keep using the same mask, removing the need to keep regenerating.

- object intersection is tested by bitwise AND on the areas of the scaled and rotated bitmasks that intersect. Again, non-trivial since you're forced in to byte alignments, and for best performance you need to use 4, 8 or even 16 byte alignments. However the benefit is if you can get it working, you can perform the tests as ints and therefore check 32 pixels for collision per iteration, or 64 pixels on a 64-bit machine, or even 128 or 256 if you get in to SSE/AVX. The larger sizes are pretty cool because for medium sized sprites you can basically check an entire row of the collision per iteration, which is so fast it's practically negligible. I don't think we actually went that far in Classic though.

 

The collision check itself is so simple (one bitwise AND per 32 pixels, check if not zero, repeat) that the bottleneck is by a long margin the generation of the scaled/rotated mask. If you have a continuously rotating sprite continuously checking a collision, it will generate a new mask every time it tests for a collision. This is far harder to optimise; unlike the collision test itself it's difficult to get it to work with more than one bit per loop iteration. If you're working in Javascript, you will have an even harder time; I doubt it will perform well unless your game does not need this case, or you compile it down with something like asm.js.

 

tl;dr - don't bother, use collision polygons - that's what we switched to in Construct 2!

[rich]

tl;dr - don't bother, use collision polygons - that's what we switched to in Construct 2!

 

Awesome