PathFinder is an application for visualizing path finding algorithms written in by Armin and me.

The source code of pathfinder was published at sourceforge.net (project page).

The application can visualize the whole calculation of the implemented path finding algorithms.
These algorithms are:

  • A*
  • Depth first
  • Breadth first
  • Hill climbing
  • Beam search
  • British museum
  • Branch and bound
  • Dijkstra
  • Depth limited
  • Great deluge

Because of a very generic and abstract application design it is very simple to add new algorithms to the repository.

The core data model of PathFinder is a more or less simple graph (nodes connected by edges), that can be overlayed by an image for better visualization (e.g. a map like in the upper picture).
The algorithms try to find a path from a start node to a destination nodes. Depending on the choosen algorithm this path should be the shortest path or just one path. Using the build in graph editor (picture below), the user is able to simply create own graphs.

The most of these algorithms can be heavily parameterized to control the way the algorithm works.
While working, the algorithm notifies the application about each calculation step. So, after the algorithm completes, the user is able to re-run the calculation in every speed or just step by step.
This is great for understandig how a algorithm works or to look for weaknesses in a new algorithm.

After a calculation completes, also some statistics are stored in a history.
Some of these values are:

  • Time for calculation
  • Steps in the graph model
  • Length of the path (and the air distance between start and destination for comparison)
  • Count of backtracking nodes (this are nodes visited by the algorithm for calculation but not used in the path)
  • The parameters given to the algorithm

Using the history, it is possible to compare differend algorithms or different parameters with each other.
Therefore the pure statistic values can be compared, or the paths can be viewed together on the same graph. So it is very easy to see the differences of algorithms or the impacts of parameters.

The application is written completely in Java (1.6 standard edition) and was part of a projekt at our university.