Implementing line of sight (LOS) in Flash/AS3 using bitmaps - bitmapHitTest anyone?

We've already had a few questions about our AS3-based line of sight routine and how it was done.
Because we're working in Flash, the immediate temptation was to draw a line between our two playing pieces as a movieclip, then use hitTest to see if there was any overlap.

As most Flash programmers already know, the problem with this approach is that hitTest only works on bounding rectangles, not shapes within the movieclips. So we'd end up with some "false positives".

the diagram above shows a hitTest is detected, even though it can be seen that the line of sight does not pass through the obstacle.

Luckily, AS3 has a way of doing pixel-perfect collision detection and there are examples of how to use it all over the interwebs. It's a function of the BitmapData object, and it's called.... erm....hitTest.

But bitmap-based hit-testing takes two bitmaps and compares every pixel in both images together, looking for a transparency value above (or below) a specific threshold. When you're comparing bitmaps that have been rotated things can get a bit tricky, and you have to apply transformation matrices and the like, but the basic idea is that where the transparency of one bitmap is not matched by a transparent area in the second image, there's a collision. This is how Flash can perform pixel-perfect collision detection.

It's a great, easy-to-use function. But it's not without it's problems.

Firstly, it's a function that uses a lot of computing power, every time it's called. Imagine comparing two relatively small 100x100 pixel images: behind the scenes, that's 10,000 pixels to test the transparency threshold of. You don't want to be doing that too often! And that's just on a couple of small images - our playing surface could easily fill the screen (and more) when six or eight board modules are connected together.

What we need is something like BitmapData.hitTest, but without chewing through so many cpu cycles.

Here's what we came up with.

Firstly, the line of sight movieclip and the obstacles movieclips are put on their own "layers" (contained within different movieclips at stage level). This allows us to take a snapshot of just a section of each layer and dump it into a bitmapData object. So starting with the top-left-most playing piece and extending only as far as the bottom-right-most playing piece, we grab a bitmap of the obstacle layer between these two points

in this example, we've drawn the contents of the captured bitmapdata objects to the screen so we can see what we're working with - in the final version these won't be displayed

Now we've got two portions of bitmaps which are substantially smaller than the playing surface. Time to use the bitmapData.hitTest function right?

Wrong. See, when we're capturing the data between two points on the playing surface, the line of sight always cuts through the bitmap from one corner at the top to the opposite corner on the bottom (in our case, above, we're going top-left to bottom-right, but it's just as possible that the LOS goes bottom-left to top-right).

Now if we know that our line of sight always bisects the bitmap along it's diagonal, we need only to check the points along the diagonal too. In fact, since we know that a playing piece is displayed onscreen by an object about 14 pixels square, we can even do this check along the diagonal in steps of 10 or 12 pixels.

Here's an example of reading a line-of-sight bitmap that passes through an obstacle:

We test the bitmap at 0,0 (the starting point of the line of sight) then at (10,4) and at (20,8) we can see that the line of sight hits a grey pixel (part of an obstacle). Suddenly, instead of comparing tens or hundreds of thousands of pixels, we've detected a collision after reading just three pixels in our image!

In a worst case (best case?) scenario, there is no obstacle and the line of  sight test requires 10 pixels to be compared before reaching the end of the green line.

Now all this wouldn't normally be an issue, and normally we'd recommend just using whichever method you're comfortable with. After all,  using bitmapData.hitTest is just a single line of code - it's easy enough to use.

But we're planning on compiling our code for tablets and smartphones - battery powered devices. And every extra cpu clock drains that battery, so the less work we put on the processor, the happier everyone will be. We're quite happy with our line-of-sight method. It's quick, it uses far few cycles that bitmap.hitTest, and most importantly of all, it works!