A* Path Search

0.1.0

Author:

Brad Kratochvil (brad@kratochvil.name)

Here is a simple C++ implementation of A* I put together a few years ago for doing path planning with our Magmite robots. The code is fairly clean, and should be easy to use for other simple path planning tasks. It is composed primarily of two classes:

• Node: a node in the search path
• PathPlan: the class for generating the plan.

If you are not familiar with A* searches, check out Wikipedia's entry on it.

http://en.wikipedia.org/wiki/Graph_traversal

To download the code, go to:

http://brad.kratochvil.name/software/a-star/a-star.tgz

As a simple example of the path planning, the following code:

int 
main()
{
  int width=10;
  int height=10;

  uint8_t maze[]={000,000,000,000,000,000,000,000,000,000,
                  000,000,255,255,255,255,255,255,255,000,
                  000,000,000,000,000,000,255,000,255,000,
                  000,000,000,000,000,000,255,255,255,000,
                  000,000,000,000,000,000,000,000,000,000,
                  000,000,000,000,000,255,255,255,000,000,
                  000,000,000,000,255,255,000,000,000,000,
                  000,255,255,255,255,255,000,255,255,255,
                  000,255,255,255,255,255,000,255,000,255,
                  000,255,255,255,255,255,000,000,000,000
                };

  output_map(maze, width, height);

  PathPlan plan(maze, width, height);

  std::vector<Node> trajectory = plan.GenerateGraph(0,0,9,9);

  output_map(maze, width, height, trajectory);
  output_traj(trajectory);

  return 0;
}

will output the following, where the ***s represent the selected path.

/// -------------------------------------------
///       0   1   2   3   4   5   6   7   8   9
///   0   0   0   0   0   0   0   0   0   0   0
///   1   0   0 255 255 255 255 255 255 255   0
///   2   0   0   0   0   0   0 255   0 255   0
///   3   0   0   0   0   0   0 255 255 255   0
///   4   0   0   0   0   0   0   0   0   0   0
///   5   0   0   0   0   0 255 255 255   0   0
///   6   0   0   0   0 255 255   0   0   0   0
///   7   0 255 255 255 255 255   0 255 255 255
///   8   0 255 255 255 255 255   0 255   0 255
///   9   0 255 255 255 255 255   0   0   0   0
/// -------------------------------------------
/// -------------------------------------------
///       0   1   2   3   4   5   6   7   8   9
///   0   0   0   0   0   0   0   0   0   0   0
///   1   0 *** 255 255 255 255 255 255 255   0
///   2   0   0 *** ***   0   0 255   0 255   0
///   3   0   0   0   0 *** *** 255 255 255   0
///   4   0   0   0   0   0   0 *** ***   0   0
///   5   0   0   0   0   0 255 255 255 ***   0
///   6   0   0   0   0 255 255   0 ***   0   0
///   7   0 255 255 255 255 255 *** 255 255 255
///   8   0 255 255 255 255 255 *** 255   0 255
///   9   0 255 255 255 255 255   0 *** *** ***
/// -------------------------------------------
/// 

---