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: <a href="http://github.com/wpm/Boost-Searchable-Grid-Example">http://github.com/wpm/Boost-Searchable-Grid-Example</a>.  My intent is for this to be a resource for other people writing a-star searches.<div>
<br></div><div>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&#39;m missing.</div>
<div><br></div><div>My graph class is a rank-2 grid graph called weighted_grid defined like so:</div><div><br></div><div>  typedef grid_graph&lt;2&gt; weighted_grid;</div><div><br></div><div>I have a simple map that returns a weight of zero for every edge.</div>
<div><br></div><div><div>  struct edge_weight_map {</div><div>    typedef float value_type;</div><div>    typedef float reference;</div><div>    typedef edge_descriptor key_type;</div><div>    typedef readable_property_map_tag category;</div>
<div><br></div><div>    reference operator[](key_type e) const {</div><div>      // All edges have a weight of zero.</div><div>      return 0;</div><div>    }</div><div>  };</div></div><div><br></div><div>I associate this map with the weighted_grid class by specializing property_map.</div>
<div><br></div><div><div>  template&lt;&gt;</div><div>  struct property_map&lt;weighted_grid,</div><div>                      edge_weight_t&gt; {</div><div>    typedef edge_weight_map type;</div><div>    typedef edge_weight_map const_type;</div>
<div>  };</div></div><div><br></div><div>I&#39;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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>However, the following call does not build:</div><div><br></div><div><div>  vertex_descriptor source = vertex(0, g), goal = vertex(3, g);</div><div>  astar_search(g,</div><div>               source,</div>
<div>               euclidean_heuristic(goal),</div><div>               visitor(astar_goal_visitor(goal)) );</div></div><div><br></div><div>I get a long error spew.  The first relevant problem appears to be here:</div><div>
<br></div><div><div>...</div><div>/opt/local/include/boost/graph/astar_search.hpp:350:   instantiated from ‘void boost::detail::astar_dispatch1(VertexListGraph&amp;, typename boost::graph_traits&lt;G&gt;::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&amp;) [with VertexListGraph = boost::grid_graph&lt;2ul, size_t, size_t&gt;, AStarHeuristic = boost::euclidean_heuristic, CostMap = boost::detail::error_property_not_found, DistanceMap = boost::detail::error_property_not_found, WeightMap = boost::edge_weight_map, IndexMap = boost::grid_graph_index_map&lt;boost::grid_graph&lt;2ul, size_t, size_t&gt;, boost::array&lt;size_t, 2ul&gt;, size_t&gt;, ColorMap = boost::detail::error_property_not_found, Params = boost::bgl_named_params&lt;boost::astar_goal_visitor, boost::graph_visitor_t, boost::no_property&gt;]’</div>
<div>/opt/local/include/boost/graph/astar_search.hpp:372:   instantiated from ‘void boost::astar_search(VertexListGraph&amp;, typename boost::graph_traits&lt;G&gt;::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params&lt;P, T, R&gt;&amp;) [with VertexListGraph = boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, P = boost::astar_goal_visitor, T = boost::graph_visitor_t, R = boost::no_property]’</div>
<div>main.cpp:36:   instantiated from here</div></div><div>...</div><div><br></div><div>(Line 36 main.cpp is the last line of the astar_search call.)</div><div><br></div><div>This error message seems to be telling me that the weight map property for edges is missing, but I think I have properly implemented the get(edge_weight, g) function the documentation says is used to create the default weight map.</div>
<div><br></div><div>Any idea what I&#39;m doing wrong?  Thanks.</div><meta charset="utf-8"><meta charset="utf-8">