Calypso88

This stunning video turned up in my news feeds today and it got me thinking:

Lightning, you cheeky bastard! Is that naturally occurring pathfinding or are you just happy to see me!?

As soon as I saw the beginning of that video I was reminded of my first maze test, and the unintended (yet quite interesting to watch) motion as the algorithm chewed through the possible paths. What's more, my latest maze experiment was built around the concept of tracing the path-of-least-resistance through a bitmap – precisely how the lightning is searching through the ionosphere for a positive electrical ground!

It took me about 5 minutes to overwrite the old maze with some render clouds and throw a little glow filter at the final path - and the result already looks pretty good. This is definitely a rough pass (there's a pixel-trap somewhere that's hanging the algorithm so I just jammed it all into a try/catch and ignored the timeout error), and there is a lot of weird clumping that I need to iron out, but the core concept is there.

Keep an eye out – I'll try and put up an animated (and less buggy) version sometime this weekend.

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]

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 hog - running this swf may crash your browser/OS/hardware/whatever. Fair warning.

So the bottom line here is that this solution runs slowly…very slowly…like bring-a-tent slow. It’s thinking about 80 nodes (pixels) every frame (currently slated at 60fps but it’s dropping), and there are just under four million pixels to go through so it takes some time. My first test completed in just over 65 minutes (although about a third of that time was spent drawing the path back to the start once it had been identified). The version below has some optimizations that bring the scanning and pathfinding time down to about 25 minutes and another eight to draw the final path. A screenshot of the solution is included for the impatient.

Note: Testing this thing was a nightmare...obviously the real problems all happen after the loading and parsing passes so it takes forever. I tried socking that data into a SharedObject but it crashed safari thrice in a row so I gave up on that idea. Also, I wasted an hour getting confusing results out of my parser only to figure out that I had left jpeg encoding on and the source image was no longer true black and white.

pathfinder [344k]

original maze

solution

UPDATE: Per the comment below, I’ve pulled the limits off this baby and thrown caution (and smooth, steady framerates) to the wind. I benched this version at 51 seconds in XP. Not bad, considering it only required massaging a couple of variables.

fast version

UPDATE 2: This post has been getting a lot of direct traffic lately so I'm updating my progress here. Basically I recoded the solver to map out the solution in under 10 seconds. You can hit the pathfinding category below for the full saga or jump directly to the fastest attempt:

super-fast version

Using a number of better resources, I’ve cobbled together a very basic A* implementation. Currently the path-overlay is disrupting mouse-behavior, and the timer readout is in a weird place in the display-tree (hence the drop-shadow). Still, even though this is a remedial exercise and just the first building-block of something useful, I’m quite happy with it.

Click around to create barriers, and drag the start and end markers around the grid. Next step: diagonals!

I’ve piddled away the better part of a year without touching this project. A few days ago I got motivated to rebuild my code and start implementing A*. The shot below is both an amusing oversight in my code as well as a visual metaphor of exactly how this project is progressing.