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.