Maze Router Applet - A* Algorithm

This applet demonstrates a variation on Maze Routing that reduces the execution time compared to the Lee Algorithm.

To Use the Applet

The routing surface is represented as a grid in which each gridpoint can be the source of a connection, a destination of a connection, or a wire that connects adjacent gridpoints. To route connections, follow the prompt and click on the source and destination points. The applet will then show the search performed by the algorithm and the final connection that is made. You can make additional connections by clicking to select additional source and destination points.

To erase all connections and start over, click on the "CLEAR" button.





About the A* Algorithm

The A* Algorithm is a variation on the Lee Algorithm that reduces execution time during the expansion phase by biasing the search in the direction of the target.  Unlike the Lee Algorithm, which uses the distance from the source as its cost function, Hadlock's algorithm uses a value known as a cost

f = g + h

where g is the distance of a labelled grid from the source (i.e., the cost used in the Lee algorithm), and h is a an estimate of the cost from the labeled gridpoint to the target (i.e., the Manhattan distance from the gridpoint to the target).  Thus nodes which are closer to the target have lower costs than nodes that are further from the target.  Since the expansion algorithm selects nodes with the lowest cost for expansion, this biases the search in the direction of the target.  When an obstacle is reached, a detour is necessary and nodes labeled with higher values are expanded.  The backtrace phase operates identically to the Lee Algorithm.

Because it still does exhaustive search as a fallback, the A* algorithm still guarantees that a minimum-cost connection will be found if it exists.

References

 
F. Rubin, "The Lee path connection algorithm",  IEEE Transactions on Computers, Vol. C-23, 1974,  pp 907 - 914.

Wikipedia, "A* search algorithm", February 2007.




| CadApplets Home | Channel Router Applet | Maze Router Applet | Multilayer Maze Routing | Placement | Iterative Imp. | Annealing |

Last updated on January 25, 2007 by John A. Nestor