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:
June 28th, 2008 at 4:31 pm
Hmm, I made a maze solving program for this maze in Flash as well and it only took about 16 seconds total solve time and 36MB of memory.
You don’t need to cache the map or use a byteArray, just use a BitmapData object so you can display the graphics while accessing the pixel information directly. There’s no point in caching map data; caching is only useful if you access data repeatedly, and you only traverse a path in this maze once. I did store a list of nodes (nodes being any junction between two paths) in case there were loops, but otherwise you don’t need to store so much data.
After caching and mapping, the solving takes a long time because your program is animating the search. I noticed that the the CPU rarely went above 10% while running your pathfinder, which means it wasn’t running as fast as it could. Watching it might be entertaining at first, but quickly gets boring, and could be accelerated as time passes. No amount of caching tricks or whatever will speed up your pathfinder if it’s limited by the animation. You can still animate the pathfinding, just do more calculations per frame. Your audience will thank you too.
Finally, the choice of search can affect how quickly the solution is found. Using a depth-first search (DFS) instead of the breadth-first search of your pathfinder dramatically reduced the amount of time needed to search the maze, though it might depend on the maze itself.
Otherwise, your program seems to work, but needs a little work to be more efficient.
June 28th, 2008 at 8:47 pm
Hey Badger, you’re completely right.
When I wrote this I was testing on my mac after a long day of developing, so my machine was pretty bogged down. My initial mac test ran right around an hour (hence the per-frame throttling), after some optimization and a clean reboot into XP I’ve been able to get that down to seven minutes…I’m sure I could cut that down more if I overloaded each frame and didn’t update the display bitmap.
For efficiency, I’m using the A-star algorithm. I’m certainly no expert, but as I understand it, it’s a combination of breadth and depth. When multiple paths are animating at once, it’s actually switching between two or more ‘best’ solutions at any given time, as the viability of each one changes in relation to the other. It’s so crazy in this specific maze because there are tons of paths and the real solution is so convoluted – but I know it’s working because of the white space to the right that never get’s explored.
Anyhow, I’d love to see your solution and source if you’re willing to post it. If I have some time I’d also like to optimize mine and see how much faster I can get it.
July 9th, 2008 at 12:27 am
Wow, I just ran your new version and, while notably faster, the amount of RAM it consumes is just enormous. Running it directly in the standalone Flash Player consumed no less than 668 MB of RAM after the solution was found (about 460 MB just prior to the search). There were even delays in the search caused by my system having to page memory to the swap file. I clocked about 6-seconds for pre-processing and 24-seconds for actual searching. By comparison, and not for bragging, my code manages about 11 seconds total time, and 35MB of RAM. I don’t know what you are actually storing for data, but it uses far too much memory.
The thing with A* which is different than other search algorithms is that it is designed for finding the shortest path, not necessarily finding the solution as soon as possible time. It really isn’t appropriate for maze traversal since there is rarely more than one solution. Still, from the demo, it looks like you’re using a branching search algorithm that explores every possible path in each iteration, not actually A*. In theory this exhaustive branching search should yield the solution in the fastest possible time; in practice, however, the search gets bogged down in the number of paths it has to search in each search frontier expansion, especially with Actionscript. In an even larger maze than this, with far more branches, you may run out of memory without on-the-fly pruning. I had considered implementing some pruning code, but this maze is not actually complex enough to require it.
If you’re willing to share your code for this maze, I’ll give you a copy of mine as well.
March 26th, 2010 at 2:45 am
[...] growth, so that choice is well justified. But, on the other hand, the traversal order seems …Calypso88 Blog Archive The long way around.Using a depth-first search (DFS) instead of the breadth-first search of your pathfinder dramatically [...]