Note: 2020 -- Contemplating reinvisioning this as a set of Jupyter Notebook pages, with 3D visualizations
PathFinder2D is an open-source experiment in various 2D shortest-path algorithms and techniques. Primary conversation about this software originally occured in the newsgroup news://comp.ai.games (2004).
This software was originally written in C++ using MSVC++ 6 Professional SP5 + MS Platform SDK.
All references to the timings of a “test” machine (pre version 1.28) 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.
Thanks, --min
Development A* Heap Integer No Closed (v4) A* Heap Integer (v3i) A* Heap (v3) A* Complete (v2c) A* Linked-list (v2) A* Array (v1) Dijkstra Breadth-First Search Best-First Search Depth-First Search D* Right-Hand Rule
Notes: Presearch Editing the graphics files Selecting new start/end points
v1.30 February 2017. Pulled from an Windows Installer copy archived in an off-line of Intrafoundation.com and cleaned up a bit for Visual Studio 2015 and hosting on Github.
v1.28 Final August 2012. Recompiled both 64-bit and 32-bit versions.
v1.27 Final November 2004. Cleaned up files and re-released with installation software.
v1.26 Final June 2004. Slight update to the code-base. Added a Zig-Zag pattern. Misc cleanup. Recompile. Hm. Oh, for 1.26 I reversed the colors of the starting and ending points. Seems more natural for green to be GO/START and red to be STOP/END. Removed the OpenGL code from project as the (as yet) unfinished Patherfinder3D project more properly makes use of complicated 3D code. (Seems the 2D version should be as simple as possible as far as the graphics interface it uses. K.I.S.S. etc.) This might actually be the final version this time unless you, the reader, happen to find a bug or want to add more test patterns or PathFinding Algorithms you’ve coded to this code-base.
I hope this source-code has been of use to any of you struggling to optimize the path-finding routines of your commercial (or otherwise) game projects. Thank you.
--Lewis Sellers. A.K.A. “Min”
June 2004.
- v1.25 ? Not sure what changes we made to 1.25 as it wasn’t logged. Presumably the OpenGL 3D code.
- v1.24 July 19th 2003-07-19 Started to add some OpenGL animation code. For the future there are basically 7 areas of improvement for PathFinder2D:
- Completing/Expanding the 3d animation code.
- Adding as many shortest-path algorithms as exist for 2d maps
- Improving the code for all classes of this program
- Adding option to change map size to 16x16,32x32,64x64,128x128,256x256 or 512x512. (Means making all algs use new/delete for world maps).
- Adding option to use multilayer maps
- Maybe adding in a Daedulas-like maze generator or two for testing purposes :--)
- Adding proper algorithm descriptions to the help file.
- v1.23 Final Added Best-First. Cleaned up various other things including menus. Considered making help CHMs. Cleaned up maps and added more Daedalus maze maps. Fixed a lockup bug that could happen with Dijkstra’s paint function when you changed start positions.
- v1.22 Final Pathfinder2D was listed on gameai.com. Because of this I promoted the dev version of A* v4 to it’s own Alg class, so that anyone wanting to experiment with their own variants can simply use the “development” algorithm class. Have a map that crashes pathfinder? Send it in. Added Gates Maze to explore effects of large number of open nodes. A* v3 and v4 are perhaps a little too eager to find the best route and can tend to wander erratically. Hm.
- v1.21 Final Less bugs. J Mainly in linked list A*. Stay tuned for PathFinder3D. ;-)
- v1.20 Final Added “presearch” to avoid pathing when there is no path. Aside from possible bug fixes and user contributions (don’t be shy) this is probably going to be the last update to this software for a long time. I’ve done what I wanted to do with it.
- v1.19 July 8th 2003, early morning. Final minor cleanup.
- v1.18 July 6th 2003 Combined A* _WORLD and _NODES into one data structure for v4 of A*. Straightened up help file.
- v1.17 July 6th 2003 DEBUG12 16.7ms. Removed linked-lists from A* v3 as performs several other small optimizations. Getting hard to get any more ms now.
- v1.16 July 5th 2003 DEBUG12 18.3ms. Lots of cleanup in all classes. Changed TGA load/save to inverse the data so it appears the same intensity scale in a graphics editor. TGA load can also now handle upside-down TGAs. After mulling it over finally changed the multi-AI pathing function around to a more cache-friendly FIFO priority queue system (it used to do them all simultaneously.) The newest A* is fast enough now that worrying about a few complex paths bogging down everything else isn’t as great as a concern now.
- v1.15 July 4th 2003. Stabilized the buggy 1.14 version. DEBUG1 is now DEBUG12. DEBUG12 20.9ms.
- v1.14 Reworked most everything. A* finally works correctly (albeit slightly slower now). Because of the reworking of the path-finding algorithms all previous mentioned timings are now invalid for comparison.
- v1.12-1.13 Unreleased.
- v1.11 Final
- v1.8 - 1.10 Bugs. Added DrawMode. Cut A* speed by another 1/3.
- v1.7 Added new A* using double linked-lists. Runs in 1/3 time of old implementation. Major class changes to make adding new algs easier.
- v1.6 A* seems "fixed" with a weight of 1.0. Hm. Also changed Dijkstra to linked-list, which made it about exactly 50x faster. One of these days I'll make A* linked-list too. (See _AStar.cpp). Few more suggestions by Eternal on comp.ai.games.
- v1.5 Added BFS. Fixed Dijkstra. Moved "common" functions to Algorithm.cpp. Changed BFS to have overlapping FIFO buffer for speed. A* still doesn't exactly work right.
- v1.4 Changed name from AStar to PathFinder. Added Dijkstra.
- v1.3 Reworked to do faster add/deletes. Still needs a sorted list for finding best f. Added high-resolution performance counter by suggestion of Eternal Vigilance. Also various tweak suggestions by Michael Horsch and Justin Heyes-Jones from comp.ai.games.
- v1.2 Minor debuggings + (fairly) significant speed optimizations.
- v1.1 Fixed many, many bugs. Added timers, etc.
The “development” algorithm is a place reserved for me (and other people) to play around with experimental twists on shortest-path algorithms. Once it stabilizes it gets promoted to its own category. If you implemented a new shortest-path algorithm here (or new variant on one) feel free to send it (and documentation fit for a HLP file) to webmaster@intrafoundation.com.
v 4. combined _WORLD and _NODES into a single data structure.
The 4th version of A* that is currently under development is completing DEBUG12 in 11.96ms. Version 4 was originally based on the integer version of “A* Heap Integer” (ie, 3bi). The main problem with 3bi is it was very unfriendly to the both L1 and L2 caches. V4 is an attempt to solve this by rearranging the data structure on which A* operates.
We tried to address problems with the large data structure by combining _WORLD and _NODE structures into one. This had several benefits, but an odd outcome of this strategy is that now the “node” and it’s “yx” coordinate are the same thing. When you specify a y/x address you also implicitly know its node number and visa-versa.
F + g are now kept in the heap structure and exist only so long as the open node itself does. One result of this is that there is very little data left to turn into “pretty graphics”. This also means the memory footprint of v4 is considerably smaller than v3 and currently fits completely within the 256kb L2 cache.
V4 unlike all other algorithms uses a fixed “Manhattan” distance metric (as V4 is mean to be close to “production” code we decided to choose the best and go with it)
For V4 anything that can be done to make the code fast, stable and suitable for production is on the table.
Frankly, at this point I’m somewhat out of ideas on how to make it any faster without dropping down to assembly.
todo v1.20 ! if leaf>=max_leafs remove last leaf, then add new leaf ? presearch for all no-paths and mark as permantly_no_path if start/end there !! consider delayed queuing if f over best_f*e (or n-nodes) to prevent heaps with levels greater than x (say 5 to 7). Ie, above level n is sort-delayed everything else.
v 3bi. Changed from float to integer
Version 3bi, ie “A* Heap Integer” (released in Pathfinder v1.18) is essentially the same as 3b, ie “A* Heap”. The only difference is that all float operations were converted to integer. The net positive effect is a few ms speedup. The downside is that (currently) fractional costs are not accumulated thus making the path-finding somewhat less accurate.
A particular note is that turning on 1.4 diagonals currently have no effect. (This may be addressed in the future).
v 3b. removed all trace of linked-lists. V 3a. added heaps to v2 linked-list code.
The 3rd implementation of the A* (A-Star) path-finding algorithm. This version is theoretically about as fast as it is possible to make it algorithmically. That is not to say that the code structure itself can not be further optimized.
For v1.14 (3a) what was created used a linked-list structure similar to V2 but sort-insertions were speeded up by using a priority queue “heap”. Initially the correctly working version was completing in about 26ms for DEBUG12 on the test machine. Next version (1.115) was doing 20.9ms. That same day v1.16 was completing in 18.3ms.
In version v1.17 all references to linked-lists were removed as they now served no purpose that the heap was not already fulfilling. This only gained a few ms increase in speed because of the cache-miss problems associated with the large data structures.
And, before you ask, the ROUTES graphic is supposed to look like that. It uses a technique generally called a “dirty rectangle” to avoid having to clear the routing information when a new path is solved. This, theoretically, saves a few milliseconds.
This is essentially the same as the v2 linked-list A* algorithm except that it keeps it’s CLOSED nodes available to test against for better path data. Slower than general A*.
[currently unfinished. want to finish it? feel free to complete the code and submit a description for this hlp file.]
One of the simplest path-finding algorithms there is, BFS is rather slow, but consistently so.
Slightly more complex than Breadth-first or Depth-first, uses a distance heuristic to guide it to the goal.
The implementation introduced with PathFinder2D v1.23 was hacked together in half an hour using the heap version of A*.
Version History: Added v1.23. Based on A* Heap version.
[unimplemented]
This is an implementation of Dijkstra’s algorithm using only OPEN nodes. Could be faster, but it’s not bad as is.
[unimplemented]
[unimplemented]
The second attempt at A* uses linked lists and inserts nodes in order as they are added.
Originally it was decently fast at about 32ms using DEBUG12 on the test machine. However, it was giving slightly suboptimal results (nothing major as the only people who would notice would be your various path-finding experts) so I finally tracked down the bug and fixed it. Well… now it runs properly, but three times slower at around 90ms. Now, if it hadn’t been that I’d already started on an even faster version using heaps I would have seriously had to consider just leaving it slightly buggy but 3x faster.
The very first attempt at an A* algorithm, it uses a simple static array to store node data. It is very slow. DEBUG12 completed in about 330ms on the test machine for the major version 1.11. Come the next release v1.14 however where most the algorithms were corrected it was running around 357ms. For v1.16 while fixing a bug with the pipe maze rendering, saw a few very obvious (now) ways to speedup the path-finding, so now the array version runs in 215ms.
Aside from a few internally generated test graphics, PathFinder2D gets all it’s map data from TARGA (ie, TGA) graphics files. All these files are 256x256 256 color TARGAs. They software can load either compressed or uncompressed files of either top-to-bottom or bottom-to-top varieties.
The loader itself converts them into the internal terrain representation that it uses, which is simply the numeric range 0 to 15 (ie, reduces them to 16-color grayscale). Internally, 0 is considered to have no cost weight at all, while 15 is impassable. Generally 0 is not used except in special occasion. For “paved roads” etc you would use 1.
When creating these TGA images in external paint programs as 256-shade grayscale images this ordering is inversed: 0 to 15 are considered to be impassable terrain. Scales of 240 and above have no weight at all.
NOTE: PathFinder has its own internal editor now.
To change the start and end points, simply press the LEFT mouse button where you want the starting (GREEN) point to be and the RIGHT mouse button to place the (RED) goal point.
To avoid trying to path from a start point to a goal point when there can be NO PATH a “presearch” has been implemented as of v1.20. The presearch is performed after any new map is loaded but before any pathing is done. It provides a way for any of the pathing algorithms to quickly check if there is any need in attempting to path the points.
The concept as it occurred to me is fairly simple and seems to work. Basically, the master map in the Setup class has the field “group” added to the world map. The presearch performs a series of floodfills against a map until everything is filled. Each floodfill action occurs with a unique group number. The end result is that you end up with a map consisting group ids for every point in the map. If the start point and end point both have the same group number, it is assumed that a path can be draw between the two points. Otherwise it is assumed the two points are isolated from each other by impassable terrain.