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<weighted_grid, edge_weight_t> { typedef edge_weight_map type; typedef edge_weight_map const_type; }; 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: ... /opt/local/include/boost/graph/astar_search.hpp:350: instantiated from ‘void boost::detail::astar_dispatch1(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, 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<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::detail::error_property_not_found, Params = boost::bgl_named_params<boost::astar_goal_visitor, boost::graph_visitor_t, boost::no_property>]’ /opt/local/include/boost/graph/astar_search.hpp:372: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, P = boost::astar_goal_visitor, T = boost::graph_visitor_t, R = boost::no_property]’ main.cpp:36: instantiated from here ... (Line 36 main.cpp is the last line of the astar_search call.) 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. Any idea what I'm doing wrong? Thanks.