Path Finding: A* and Best-First Search
Posted on September 14, 2008 at 03:05:00 AM
I just finished my A* implementation. I found it surprisingly amazing how similar A* is to best-first search (BFS). In a nutshell, A* is BFS with addition of the cost and F values. The main differences is that you must calculate your cost, and sum the cost the the heuristic value (your F score) and then sort your open list by F score instead of just the heuristic (as in BFS).
In the demo screen shots below, you will see two paths traced from the start (the green block) and stop (the red block) points. The cyan path is BFS and the yellow path is A*. For both paths, the successors were chosen from 4 directions.
Feel free to play with the demo here.