PathFinder2D

v1.26 July 2004

PathFinder2D is an open-source experiment in various 2D shortest-path path-finding algorithms and techniques. Primary conversation about this software occurs in the newsgroup news://comp.ai.games.

This software was written in C++ using MSVC++ 6 Professional SP5 + MS Platform SDK.

All references to the timings of a “test” machine refer to an old Athlon 1.1ghz with 32/32kb L1 and 256kb L2 cache.

This software was improved with the chatty help of:

• Eternal Vigilance
• Michael Horsch
• Dmitriy Iassenev
• Randolph M. Jones
• Amit Patel
• Justin Heyes-Jones
• Steven Woodcock (http://www.gameai.com)

New v1.16 maze examples generated by Daedalus 1.3 created by Walter D. Pullen - http://www.astrolog.org/labyrnth/maze.htm.

NOTE: If you notice ANY bugs in this software (either observationally or in the source code) feel free to email. One of the ideas behind this software is to provide a set of reference examples to test production game code against. And to do that the code must be as accurate and bug free as possible.

The Algorithms:

• A* Heap, Integer, No Closed
• A* Heap, Integer
• A* Heap
• A* Complete
• A* Linked-list
• A* Array
• Dijkstra
• Breadth-First Search (BFS)
• Best-First Search
• Depth-First Search (DFS)