Title: Pathfinder
Author: David J. Stein, Esq.
Version: 1.0
Written: June, 2005


Abstract: This application uses an implementation of the A* ("A-Star") algorithm to find the shortest path through a set of rectangular obstacles. The application demonstrates an optimizing step-by-step search of the obstacle space. The core class includes additional functionality for computing an eight-directional step path to the goal using run-slice computation.

Installation Instructions: Nothing unusual - simply run the enclosed executable.

Operation Instructions: The A* algorithm takes incremental steps toward finding a path through an obstacle space. The application can utilize the A* algorithm in be used in one of three ways: it can step through the solution by button-clicks; it can animate through the solution process at variable rates; or it may simply run through one pathfinding problem and display the result. The corresponding "Solve (Step)", "Solve (Animate)", and "Solve (Full)" buttons accomplish these tasks. In addition, the search space can be customized by controlling the number and sizes of the obstacles.

Comments: The application is written as two classes: the Pathfinder back-end class and its associated classes, and the front-end simulator. The core class may therefore be reused in any other application with minimal extra effort (though the application should use CollisionRect objects to model the obstacle space.) Also, the Pathfinder class features a Step function that computes a step path based on a standard eight-way direction control, relying on run-slice computation for improved performance.

Application History: The algorithm within this application was written in 1999 as a navigation technique, but the application has been updated for general use as a demonstration of A* pathfinding. Additionally, the old code was written to perform on comparatively primitive hardware (a Pentium Celeron machine) in a high-performance application, and therefore features some optimization techniques, like loop unrolling, that make the code faster but messier. The code is therefore pretty ugly, but perfectly functional.

Questions/Comments: Please contact David J. Stein, Esq. via email at djs10@po.cwru.edu.

Terms and Conditions of Use: Please see the enclosed "License.html" file for terms and conditions of use of this software package.