V6.0 - Faster (Bidirectional) PathFinding

Rating: No reviews yet
Downloads: 14
Change Set: 25943
Released: Jul 5, 2013
Updated: Jul 6, 2013 by pgeerkens
Dev status: Stable Help Icon

Recommended Download

Application Binaries-V6.0
application, 168K, uploaded Jul 6, 2013 - 7 downloads

Other Available Downloads

Application Source-V6.0
application, 200K, uploaded Jul 6, 2013 - 7 downloads

Release Notes

  1. Upgraded to Visual Studio 2012
  2. Added BidirctionalPathfinder class that runs 2-3 times faster than previous using:
    1. A (serial) implementation of New Parallel Bidirectional A*;
    2. Heap-on-Top priority queue implementation;
    3. A 32x32 LayeredBoardStorage class that improves caching of board details;
    4. 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 0.86 and 1.55 seconds to 0.43 seconds. Total nodes expanded decreases from 160,000 and 230,000 respectively to 80,000, of over 330,000 on the whole board..

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.