A* Demo

This demo features A* pathfinding using the DirectX sample framework.

For the provided scenes, a simple 2D grid is used.  Two heuristic methods are provided, and a weighting option can be applied to these heuristics to influence the search.

  1. The first heuristic method is the Euclidean distance from the current node to the destination node.  This is just simply the length of the vector from the current node to the goal node.
  2. The second heuristic method is the cardinal/intercardinal distance.  This heuristic is specifically used for square grids, and represents the shortest distance traveled on an open grid assuming you can only move one square at a time in a cardinal direction or diagonally to an adjacent square.

Some observations when making this demo:

  • A heuristic weighting of 0 (i.e. not using the heuristic at all) is equivalent to a breadth-first search
  • The larger the heuristic weight is, the closer the algorithm is to Dijkstra’s algorithm
  • When using the cardinal/intercardinal heuristic, the exact solution is immediately found on an open grid if you slightly bias towards the heuristic (heuristic weight = 1.01)
This entry was posted in Demos, Projects. Bookmark the permalink.

Comments are closed.