The long way around.
June 26th, 2008
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.
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.
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: