Fork me on GitHub

Pixel-perfect collision detection with 5000+ particles

UPDATE: This post is here for historical purposes. The SWF has been moved to a new location.

And yes, it runs perfectly fine. I’ve run it at 60+ FPS with 7,000 particles, but that actually isn’t the limitation (unless your particles are crunching heavy math for eg movement). Rather it’s the size and number of sprites that we’re colliding with the particles.

vonLocal Collision Detection

To squeeze all the juice out of Flash I employed a couple tricks. The first was the particles themselves–they’re blitted to a single bitmap which is used as the source image for grabbing collision data from. The particles are also drawn with the raster engine in Flash (multiple setPixel32() ops to give the illusion of a line… a choppy one anyway) instead of the vector renderer (lineTo()). The second trick was to only grab a Vector of pixels from the regions we cared about (within sprite boundaries) every so often, then to loop through the Vector and test it against our desired conditions. Also, since the particle bitmap is more sparse than our sprites as far as opaque pixels go, we test the particle bitmap first, resulting in a lot fewer passes on the first round of conditional statements.

So my poor man’s method of making lines is done by interpolating the position of a particle from the previous to the current frame, for a total of 3 setPixel32() operations per iteration. (We can use setPixel() for a solid performance gain, but at a different kind of cost that I’ll explain later.) To give the particles a long tail we simply decrease the alpha of the particle bitmap a little bit every frame, making older particles fade more as time goes by. This means we can skip fillRect() to clear the bitmap every frame, but I’m wondering if that’s faster or slower than ColorTransform. Haven’t tested, for shame.

I’ll admit that I haven’t tried this method with bitmap-based particles but those would work just as well, in theory (using blitted rendering). One of my current projects demands those trailing things so I didn’t look into it. If you try it, please comment on this post below with your findings

for (i = 0; i < _numParticles; ++i) {   p = particles[i];   // get our velocity from the perlin noise map   vel = noiseMap.getPixel(p.x>>3, p.y>>3); // because noiseMap is 1/9 the size of particleMap
  var brightness:Number = vel / 0xFFFFFF;
  var speed:Number = 0.1 + brightness * p.speed;
  var angle:Number = 360 * (brightness * p.wander) * 0.0175; // roughly PI / 180 to convert to radians
  p.vx = Math.cos(angle) * speed;
  p.vy = Math.sin(angle) * speed;
  // absolute value for velocity calculations
  var pvx:Number = p.vx < 0 ? -p.vx : p.vx; // use bitwise sign flippage   var pvy:Number = p.vy < 0 ? -p.vy : p.vy;   // poor man's lineTo ENGAGED   var nx:Number = p.x + (p.vx >> 1); // where we are now + half the distance to where we will be
  var ny:Number = p.y + (p.vy >> 1);
  var mx:Number = nx - p.x; // then half THAT distance for a third position...
  var my:Number = ny - p.y;
  // actually apply velocity to pixel
  p.x += p.vx;
  p.y += p.vy;
  // bounds-check
  if (p.y < 0) p.y = h - 1;   else if (p.y > h) p.y = 1;
  if (p.x < 0) p.x = w - 1;   else if (p.x > w) p.x = 1;
  // pick our color based on speed
  speed *= 60;
  if (speed > 255) speed = 255;
  color = 255 << 24 | speed << 16 | speed << 8 | speed;   // render the particle three times, each in different places to get a line-ish thing going   particleMap.setPixel32(p.x, p.y, color);   particleMap.setPixel32(mx, my, color);   particleMap.setPixel32(nx, ny, color);   }   // and we're done. release the pixels!   particleMap.unlock(_r);

So that gives us some spotty-but-close-enough trails to help with our collision detection. It works like this: We create a single bitmap to use as a canvas for our particles. We render those particles using setPixel32() as mentioned above. Sprites will use this bitmap as a source for collision data. Every other frame or so (more on this later) the sprites will grab a section of pixels from the particle bitmap using something like getVector() (>= Flash 10) or getPixels() (< Flash 10), using their own position and dimensions for the sourceRect parameter.

shipVec = buffer.getVector(_rc); // get an array of pixels from the whole sprite
_rc.x = int(this.x); // change rect to particleBMD's coordinate space
_rc.y = int(this.y);
pixVec = _particlebmd.getVector(_rc); // grab an array of the same area of pixels that our sprite is occupying
var a:uint;
var i:int = 0;
for (i; i < _l; ++i) {   _pval = pixVec[int(i)]; // first look at the particle's image for opaque pixels   a = _pval >> 24;
  if (a < 100) continue;   // it found an opaque-ish pixel, so let's see if there's an opaque pixel in the ship there too   _sval = shipVec[int(i)];   a = _sval >> 24;
  if (a < 100) continue;   /* if we get this far then we have a collision because one     * of the ship's pixels is overlapping a particle's pixel.     * we're only going to collide with red-colored particles though */   _pval = _pval >> 16 & 0xFF; // red channel extraction
  if (_pval > 100) {
    var px:int = int(i % w); // translate 1d array coordinate to 2d grid coordinates
    var py:int = int(i / h);
    buffer.setPixel32(px,py,0xFF4e88c9); // colliding pixels are painted on the top of our sprite in a cold blue-ish color

As you can see on line 133 and 136, each sprite has a block of pixels ready to examine on each tick. The sprite loops through that block and compares every pixel of its own with the pixels in the Vector it got. If there’s a match (eg both pixels are opaque) then look at the particle’s pixel in detail to see if it’s the droid one we’re looking for and record its findings.

So you can alter line 151 so that the sprites check for specific colors in the particle bitmap, like anything brighter than dark grey (which I did here, or anything with an alpha greater than 0.1 or… use your imagination I guess?).

Because grabbing a new Vector from the particle bitmap can be so expensive (depending on the size of the sprite), you can time limit the collection so it only samples the particle bitmap once in a short while. In the demo SWF above I sample it once every 100 milliseconds or so, which comes out to about 24 samples a second (given 25 milliseconds per frame at 60 FPS)… as opposed to 2400 samples a second. The casual human eye can’t tell the difference but it yields a significant increase in performance. Most performance tricks I’ve learned are based are smoke and mirror stuff like this.

You can use setPixel() (no alpha) but you’ll have to test for color–obviously for a color that isn’t what the background of the particle bitmap is, so it’s a little more tricky. It’s also totally possible to use other sprites as particles as long as you blit them (using copyPixels() or setVector()) to a single bitmap that can be checked by other sprites that collide with them. If you don’t know what blitting is, 8bitRocket has a good rundown (it’s where I first learned about it actually).

And that’s pretty much it. You can download the example files/source below.

download source


4 Comments on "Pixel-perfect collision detection with 5000+ particles"

  1. AdityaGameProgrammer January 13, 2010 at 8:41 pm -

    Hi Von Birnbaum
    This is a pretty neat visualization and it handles detection nicely too.This implementing the simpler reaction to handling the collision. a relatively higher pegged reaction handling and of a similar volume collision detection is here at gskinners the
    proximity manager. hes plotting the lines to the particles in proximity to 4 bases. which is pretty impressive.
    I have used the cdk for handling pixel perfect detection which is also based on blitting and had to use another mechanism to handle the reactions . the simple multiple ball pixel perfect collision and reaction at which i guess has the costlier math involved in regards to handling reaction after collision detection.


  2. Stevan January 21, 2010 at 6:18 pm -

    Nice demo, but utterly useless in the real world.

  3. Juan Carlos February 28, 2011 at 6:30 am -

    Hello, Corey. The class is missing in the Ship class. Thanks.

  4. Corey February 28, 2011 at 10:18 pm -

    Oh man, sorry about that. Download that class here. I just modified someone else’s Vector2D class (slight optimizations)–pretty generic stuff, so you’re not missing anything interesting.