Calypso88

A forum thread recently challenged my knowledge (and preconceptions) of gradients in Flash. I've always worked under the assumption that Flash uses 8 bits per color channel – zero to 0xFF for R, G, and B – end of story. Although this is generally considered the shallow end of the color-depth pool, it's always been more or less sufficient. The shallow color depth has long been considered the sweet spot between passable (even realistic) color recreation, and the exponential processing lode of adding more data to each pixel in a display.

The point where 8-bit graphics break down is when it comes time to interpolate a gradient. If you want to draw a smooth fade from black to 10% grey, you want as many colors in-between as there are pixels. In an 8-bit environment, you've only got about 26 shades of grey to work with so anything bigger than 26 pixels across is going to have blocks of pixels, all colored the same – in the biz, this is called “banding.”

Interestingly, while Flash is bound to 8-bit it will still import a 16-bit Tiff. When I realized this I figured there must be some trickery going on - either I could use 16-bit color in Flash or else the Tiff was getting the chop. Unfortunately, it turns out Flash downsamples the image into it's own color profile, but the importer is good enough to give us the courtesy of a good dithering first (provided you enabled it in Photoshop). Here's a little demo to show the dithering - if you squint you can see the banding on the originals.

Edit: Per Ben's comment, I've tweaked the colors below to make the banding a little more noticeable (if you still see flat-black bars, try cranking up your monitor's brightness/contrast). For all the headaches I've had from gradients in the past, making a bad one is really hard to reproduce on command! Scrub your cache and refresh for the glory of bad-gradation!

I know, I know – back-to-back entries, the sky must be falling.

I felt so guilty about posting that code yesterday that I was compelled to get this second version finished off tonight and optimized. And good news - I'm clocking it at 7 seconds! The big secret (ok, Bionic-Badger apparently already knew it in his comment a month ago) is to remove all the data constructs and just jam through the bitmap directly. So that's what I did.

I had a brief notion that recursion was the way to go (I loves me some recursion!), the code was benchmarking extremely fast since there isn't any storage, every child node just gets scoped into its own closure, however around fifteen thousand nested function calls is where Flash draws the line and throws in the towel (or stack overflow error, as the case may be). I'm still pretty sure I could get this algorithm down into the 2-3 second range if the recursion had worked...

Anyhow, my strategy was to color each explored pixel with an incremental number, so the first pixel becomes colored 1, the second 2, etc. Since we're in hex color land, this gives the weird side effect of black to blue gradients that shift up into the green space as the color channels overflow. It's bizarre to look at but kind of cool to see where the breadth-first approach explores different areas. After that mapping has taken place, it's a simple matter of tracing the path back from any given pixel by repeatedly finding its lowest-valued neighbor.

One final note; I've been noticing a strange discrepancy in the memory traces. About half the time I'm seeing 30-35mb and the rest of the time 2-3. I know this code is spinning off a lot of throw-away variables so I'm inclined to believe the higher numbers and speculate that the lower numbers are results of the Garbage Collector running at opportune times.

Maze pathfinder 2
source [748k]

A few weeks ago now, I got a comment on my last post asking for the source. The real (dirty little) reason I took so long on this, is that I was trying to find some time to rewrite this stuff and post a much better version alongside, but it just didn't happen. I'd still like to get a new version of this thing put together – I'm confident I can beat that 11 second benchmark – but in the meantime, anyone reading can take a chuckle at my schlocky earlier version. And for the curious, here's a link back to what I originally developed that code for - which is a roundabout apology/defense of my (very) liberal memory hogging.

Maze pathfinder [1mb]

I've gutted my pathfinder code and thrown it at a devilishly complex problem – specifically 4 megapixels of eye-squintingly difficult maze.

The big concern with this beast is managing resources; You can't simply jam the image into an array and go for broke, there has to be some sort of throttle to keep the code running in small, frame-sized chunks. The solution for that is to split my big loops up into loop-invariant code and run each iteration (or 20) on an EnterFrame event.

Next up is memory - my original engine was designed to run quickly so I could use it many times per frame without a noticeable slowdown. This means a lot of caching, specifically the entire map is put into memory as a 2-dimensional array, and then each node is given a link to it's viable neighbors. This is obviously overkill for a simple pathfinder, but if you're going to find a path on the same plane more than once, you've saved all the work from the first run into a crazy, multidimensional linked list (matrix? lattice?). If I were writing this from scratch I'd probably do away with the pre-caching step and do something tricky with byteArrays, but I'm not about to recode this whole thing just for a little stress-test. Consider this the official warning that this swf is a memory