Where to get ASIPathFinder:
- Github project page: http://github.com/pokeb/asi-path-finder
- Download the latest version: http://github.com/pokeb/asi-path-finder/tarball/master
- License (BSD): http://github.com/pokeb/pokeb/asi-path-finder/master/LICENSE
I regret that I cannot provide support for ASIPathFinder, but if you find it useful, please drop me an email and let me know!
What is ASIPathFinder?
ASIPathFinder is a complete implementation of a cooperative path finding algorithm, and will probably be most useful for writing Real Time Strategy games. It is written in Objective-C, and is compatible with Mac OS and iPhone OS.
What is a co-operative path finder?
A co-operative path finder allows multiple objects to find a path on a map, planning ahead to alert other objects of where they’re going to travel. This means that an object can avoid other objects ahead of time, before they collide.
ASIPathFinder is based on code I originally wrote for my Space Harvest game for iPod Touch and iPhone. Download the game to get a feel for its capabilities.
Key features
- 3 stage path finding - initial assessment (A*), partial path finding avoiding other units, and movement with handling of unanticipated collisions
- Designed for real-time operation - path assessment and path finding can be paused and resumed later to keep frame rates manageable
- Relatively efficient - ASIPathFinder was originally designed for 1st generation iPhone OS devices, which are pretty slow by desktop standards. In Space Harvest it supports path finding for many units across terrain with a huge number of impassable obstacles
- Does not rely on ‘hinting’ maps with pre-calculated intermediate way points. This means it works well with dynamically changing obstacles, but may be less performant than other implementations if obstacles are static.
- Written in Objective-C (though much of the core stuff uses manual memory management with malloc() for speed), compatible with Mac and iPhone OS.
- Comes with a sample application that demonstrates the core approach, and highlights examples of where it works, and the cases where it will be unable to resolve a collision
I’ve deliberately made these instructions relatively general - they describe how ASIPathFinder works, but don’t make much detailed reference to the code itself. The code is fairly well commented, but the hard part is understanding the overall process, and that’s what I’ve attempted to cover here. Additionally, I hope this may be useful to anyone implementing their own co-operative path finder, regardless of whether they program in Objective-C or not.
Acknowledgments
ASIPathFinder is a variation on techniques described by David Silver in this paper:
http://webdocs.cs.ualberta.ca/~silver/David_Silver/Publications_files/coop-path-AIWisdom.pdf.
I would strongly recommend reading this before doing anything with ASIPathFinder. Though my implementation is slightly different, the overall approach (reverse A* for initial assessment, with partial path finding and a reservation table after that) is taken directly from this paper.
ASISearchNodeList is based on the binary heap algorithm as explained by Patrick Lester here:
http://www.policyalmanac.org/games/binaryHeaps.htm.
The sample application uses enormgeo’s EGODatabase class to store its data.