Efficient C++ pathfinders on 2D grids using variations of A* search.

An algorithm to find the shortest path from a given source to a given sink. It often gets little notice in theoretical computer science because there are nearly linear time algorithms to solve the more general problem of finding single source shortest paths (to all destinations) on any graph with non-negative edge weights. But in practice, when all you really care about is the shortest path to a particular target and there is some domain information that is available one can handily beat the performance of a simple breadth first search or Dijkstra. This is something not often taught in CS classes but the idea is to fudge the weights of the underlying graph (using the available domain information) in such a way that running Dijkstra on the graph with modified weights biases the search direction towards the target. In an implementation however, one doesn't actually modify the weights but uses a priority queue with priorities /different from the distance labels/ to achieve the same effect.

Suppose you're given a 2D grid with 0/1s corresponding to impassable/passable locations and a given pair of source and target locations in the grid. Each location not on the boundary has 4 neighbors in the N, S, W and E directions unless some of them are not passable (there's also the option of considering 8 neighbors per non-boundary location) and is at unit distance away from it. Find the shortest path from the source to target or decided there is none.

The API is very simple and explained on this page that inspired me to learn more about pathfinding.

   int FindPath(const int nStartX, const int nStartY,
                const int nTargetX, const int nTargetY,
                const unsigned char* pMap, const int nMapWidth, const int nMapHeight,
                int* pOutBuffer, const int nOutBufferSize);

Depending on the particular algorithm you choose from pathfinders.h the name of the function would change. For example in grids with 8 neighbors per location you would call one with the Diag suffix.

Breadth first search, A* using the Manhattan distance heuristic with/without tiebreaking, and A* with lower bound computation using landmarks.

Currently you can run benchmarks to compare the different algorithms like this.

make # might fail because you don't have boost installed
./a.out < maps/starcraft/GhostTown.map

                 BFS -- avg time: 3.648ms	avg nodes:   154413
               AStar -- avg time: 3.238ms	avg nodes:    33288
      AStarLandmarks -- avg time: 4.502ms	avg nodes:    32399
          AStarNoTie -- avg time: 3.377ms	avg nodes:    34534
             BFSDiag -- avg time: 8.263ms	avg nodes:   155472
           AStarDiag -- avg time: 5.012ms	avg nodes:    30826
  AStarLandmarksDiag -- avg time: 8.387ms	avg nodes:    45012
      AStarNoTieDiag -- avg time: 5.018ms	avg nodes:    36760

Some cool related stuff.

• l1 pathfinder
• Map source for benchmarks