Pathfinding

(May 2014)

Two applications have been created to demonstrate two different pathfinding algorithms: The Lee algorithm and the A* algorithm. Both algorithms find the shortest path between a start and an end point.

Lee Algorithm

The Lee algorithm is guaranteed to find the shortest path but is not quick as it takes a breadth first approach to searching, exploring all possible options.

The application can demonstrate the Lee algorithm in two settings: in a maze or in a place of randomly positioned walls. The second option is not gauranteed to have a path connecting the start and target positions which is something all pathfnding algorithms must be able to handle.

A* Algorithm

The A* algorithm incorporates heuristics, allowing a 'best-fit-depth-search' method to be executed. Depending on the number of obstacles this greatly reduces the number of cells checked compared to the Lee algorithm.

The heuristic method used by the implementation is the Manhattan method which adds the horizontal and vertical distance from the current cell to the target cell. This method is sufficient as the implementation does not take diagonal movement into consideration.

Like the Lee algorithm, the A* algorithm can be demonstrated in two settings: in a maze or in a place of randomly positioned walls.