Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search

On Wed, 30 Jun 2010, W.P. McNeill wrote:

I am trying to write a simple example of an a-star search over a 2-dimensional grid using the Boost Graph Library.  The source is hosted here: http://github.com/wpm/Boost-Searchable-Grid-Example.  My intent is for this to be a resource for other people writing a-star searches. I am seeing an error about a missing weight map when I try to compile the call to astar_search().  As far as I can tell, everything is in order.  I hoping someone has insight into what I'm missing.

My graph class is a rank-2 grid graph called weighted_grid defined like so:

  typedef grid_graph<2> weighted_grid;

I have a simple map that returns a weight of zero for every edge.

  struct edge_weight_map {     typedef float value_type;     typedef float reference;     typedef edge_descriptor key_type;     typedef readable_property_map_tag category;

    reference operator[](key_type e) const {       // All edges have a weight of zero.       return 0;     }   };

I associate this map with the weighted_grid class by specializing property_map.

  template<>   struct property_map {     typedef edge_weight_map type;     typedef edge_weight_map const_type;   };

Since you didn't write the grid_graph class, this is not the correct way to add property maps. You will need to use an external property map (such as iterator_property_map) as your weight map, and then pass it in explicitly to the astar_search() function.

I've defined valid expression functions for this property map along with a Euclidean distance heuristic and a visitor that throws an exception when a goal vertex is reached.  The complete source is viewable at the URL given above.

With these definitions I can do concept checks on the ReadablePropertyMap, ReadablePropertyGraph, VertexListGraph, and AStarHeuristic concepts.  I can instantiate a weighted_grid.  I can get the edge weight map using get(edge_weight, g) and the vertex index map using get(vertex_index, g).  I think I have written everything I need to do a-star search.

However, the following call does not build:

  vertex_descriptor source = vertex(0, g), goal = vertex(3, g);   astar_search(g,                source,                euclidean_heuristic(goal),                visitor(astar_goal_visitor(goal)) );

I get a long error spew.  The first relevant problem appears to be here:

The error here doesn't have enough of the instantiation stack to be useful. Just use an explicit weight map, though, and that is more likely to work. -- Jeremiah Willcock