|  | Intrafoundation Software > Freeware Mac OS X Gaming ColdFusion DOS Windows PHP Commercial Top All > > > |
## PathFinder2D (1.27) `November 23 2004` by Lewis A. Sellers `Send related correspondence to: webmaster@intrafoundation.com` Windows Application [w/ C/C++ source code] ### Description PathFinder2D is an open-source experiment in various 2D shortest-path path-finding algorithms and techniques. Primar conversation about this software occurs in th 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 - Daedalus Maze Generator. 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) ### Manual Pathfinder2D PathFinder2D is an open-source experiment in various 2D shortest-path 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. Thanks, --min The Algorithms: 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 ### Development 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. ### Heap Integer No Closed (version 4) 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. ### Heap Integer (version 3bi) 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). ### Heap (version 3b) 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. ### Complete 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.] ### BFS Breadth-First Search One of the simplest path-finding algorithms there is, BFS is rather slow, but consistently so. ### Best-First Search 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. ### Depth-First Search [unimplemented] ### Dijkstra This is an implementation of Dijkstra's algorithm using only OPEN nodes. Could be faster, but it's not bad as is. ### Right-Hand Rule [unimplemented] ### (Dynamic A*) [unimplemented] ### Linked-list (version 2) 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. ### Arrays (version 1) 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. ## Editing the graphic files 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. ## Selecting new start/end points 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. ## Presearch 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. ### Version History version 1.8 Bugs. Added DrawMode. Cut A* speed by another 1/3. version 1.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. version 1.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. version 1.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. version 1.4 Changed name from AStar to PathFinder. Added Dijkstra. version 1.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. version 1.27 `November 01 2004` Cleaned up files and re-released with installation software. version 1.26 `June 01 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. version 1.25 `June 01 2004` Not sure what changes we made to 1.25 as it wasn't logged. Presumably the OpenGL 3D code. version 1.24 `July 19 2003` Started to add some OpenGL animation code. For the future there are basically 7 areas of improvement for PathFinder2D: 1) Completing/Expanding the 3d animation code. 2) Adding as many shortest-path algorithms as exist for 2d maps 3) Improving the code for all classes of this program 4) Adding option to change map size to 16x16,32x32,64x64,128x128,256x256 or 512x512. (Means making all algs use new/delete for world maps). 5) Adding option to use multilayer maps 6) Maybe adding in a Daedulas-like maze generator or two for testing purposes :--) 7) Adding proper algorithm descriptions to the help file. version 1.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. version 1.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. version 1.21 Final Less bugs. Mainly in linked list A*. Stay tuned for PathFinder3D. ;-) version 1.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. version 1.2 Minor debuggings + (fairly) significant speed optimizations. version 1.19 `July 08 2003` early morning. Final minor cleanup. version 1.18 `July 06 2003` version 1.17 `July 06 2003` DEBUG12 16.7ms. Removed linked-lists from A* v3 as performs several other small optimizations. Getting hard to get any more ms now. version 1.16 `July 05 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. version 1.15 `July 04 2003` Stabilized the buggy 1.14 version. DEBUG1 is now DEBUG12. DEBUG12 20.9ms. version 1.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. version 1.13 Unreleased. version 1.11 Final version 1.1 Fixed many, many bugs. Added timers, etc. #### [Manual friendly version] | ### Download We hope you find your download of use. (807 KB) version 1.27 (`November 23 2004`) `views 2812` downloads 2864 (June 29 2007) ### Gallery ### Related External Links aStarTutorial (views 58) Game AI Resources: Pathfinding (views 53) GameDev.net Artificial Intelligence (views 41) ### Comments Leave a comment Lewis Sellers `November 28 2006` (Fixed the download issue.) Reply to comment in forums rivo `July 23 2003` Really nice, but why is there no Linux version? Reply to comment in forums ??????? `July 14 2003` ????? Reply to comment in forums Amit Patel `June 29 2003` Looks nice! http://www-cs-students.stanford.edu/~amitp/ Reply to comment in forums /\/\ark `June 27 2003` Holy Shit, dude!! Amazing. Reply to comment in forums DEEDEE `June 22 2003` Reply to comment in forums Leave a comment View all product comments/replies