V 6.1 Lightning-Fast ALT Bidirectional Pathfinding

Rating: No reviews yet
Downloads: 47
Change Set: 25973
Released: Jul 7, 2013
Updated: Jul 8, 2013 by pgeerkens
Dev status: Stable Help Icon

Recommended Download

Application V 6.1 Binaries
application, 174K, uploaded Jul 8, 2013 - 29 downloads

Other Available Downloads

Application V 6.1 Source
application, 207K, uploaded Jul 8, 2013 - 18 downloads

Release Notes

  1. Upgraded to Visual Studio 2012
  2. Added BidirectionalPathfinder class (using ALT) that runs 240 times faster than previous using:
    • A (serial) implementation of New Parallel Bidirectional A*;
    • Heap-on-Top priority queue implementation;
    • A 32x32 BlockedBoardStorage class that improves caching of board details;
    • Implementation of ALT (A* with Landmarks and Triangle-inequality heuristic); and
    • A few scattered miscellaneous code improvements
  3. Additional basic functionality pushed into the HexBoard utility class from the examples, including the BoardStorage. abstraction discussed above.

This faster A* implementation decreases the time for my most complex case (two long diagonals on a 750 x 420 terrain map) from 860 ms and 1,550 ms to under 5 ms. Total nodes expanded decreases from 160,000 and 230,000 respectively to 1,600, of over 330,000 on the whole board.

Preprocessing of 8 landmarks (4 corners and the midpoints of all 4 sides) runs in about 4 seconds in parallel on an i7 using a simple Dijkstra's implementation, for a 760 x 420 terrain map.

The two cases are the same path in opposite directions, so the Bidirectional implementation now merges them to the same test case.

Reviews for this release

No reviews yet for this release.