Pathfinder Library for Processing
Pathfinder is a collection of search algorithms. It currently allows you to perform A*, Greedy-Best-First-Search and Dijkstra. Each has their own benefits and advantages so you can use whichever suits you.
Pathfinder is object orientated, nodes are connected via wires called connectors, these can be modified to make certain paths favourable to A* and Dijkstra (to simulate different terrain for example). You can build your own web of nodes with custom connections or you can use the built in cuboid map generator to make a simple flat map or cube of connected nodes. If you use a flat map the distance calculator will use 2D distance measuring to keep your processor quiet.
This library assumes you know how to utilise Java's ArrayList class, a dynamic array for objects.
Before you start using the library you may want to read about the different search algorithms and find out which suits your task:
Comparison of A*, BFS and Dijkstra
A* (Accurate and fast, but ignorant of teleportation)
Wikipedia definition
A*
Pathfinding for Beginners
A*
Algorithm Tutorial (This
one comes with a range of good links)
Best-First-Search (Stupid - but fastest - good for game A.I.)
Dijkstra (Accurate - accounts for teleportation, but slow)
Wikipedia definition
Algorithm
and Java demos
Description
of algorithm
Documentation
Examples
If you put together any work using the Pathfinder library Just drop me a line and I'll be happy to link to it here. Same goes for if you find any bugs, typos or just simply don't understand how this library works. Contact me at the Processing forums (st33d) or mail me:
Download
To add the library to your project, put the unzipped folder ai_path
into the folder processing-###/libraries/
Next time you start Processing you should have a menu option of Sketch > Import
Library > ai.pathfinder
Click on that option to add the code: import ai.pathfinder.*;
Source code can be downloaded here.
The Pathfinder Library is released under the GNU Lesser General Public License
Tested with Processing and compiled with Eclipse
Thanks to Tom Carden for the algorithm this library is based on.
Powered by cans (not bottles) of Coca-Cola and Funk Spectrum.
Flash AStar classes
I've had cause recently to convert the AStar part of the Pathfinder to Flash. It's a cut down implementation that doesn't use Connectors.