Wednesday, November 5, 2008

A* for ActionScript, with an incomplete heuristic function

I have finished my (first completely working) implementation of A* for ActionScript. However, the heuristic function is a constant function and thus not implemented, so 'A*' is just breadth first search. Technically, I believe it is correct to still call it A*, but I'm not certain since I'm not keeping track of my path cost, and my heuristic is more of an artful description of something that always returns the same value but has not been implemented... I suppose I am feeling a bit discouraged since the assignment is due tomorrow at 5 p.m. and it is 3:21 a.m. and I still have a bit to do in order to make it perfect. However, I think choosing which path to recurse down first based on a heuristic shouldn't be too big of an addition now that everything else is working well.

I feel very happy that I choose to implement this in ActionScript. I like being able to share my programs with people online and notice the Google search terms that bring others to my site. I gain satisfaction when I see that someone from China, Spain, or some other distant place, spent 20 minutes reading about some technical issue on my site.

Press space bar to switch between blocking off nodes, selecting a start position and selecting an ending position.

Click HERE to view this in it's own web page.

My sister would be proud of my photoshopping skills on the waving hand. I also have to give a shout-out to Michael Baczynski for the cool data structures library (I didn't have to write my own FIFO thanks to him.)

As always, my complete source code is available. Please don't hesitate to contact me if you have any questions. I plan on making it more of an actual A* implementation, and if time permitting, possible using Michael Baczynski's graph data structure and implementing A* in his (very well designed) framework. I did not plan on doing that from the beginning, even though I'm sure it would have saved me time, since I did not see him code until after I already made my own graph, and adjacency list, management routines.

Thanks for Laurie Phillips for finding a bug in my code.

No comments: