I've got a working A-star maze solver.  The code is checked into the github Astar-Maze-Solver project.  I've tried to put it into a format in which it can be added to the Boost examples directory.

A little post-mortem.  A certain amount of difficultly for a newcomer to use the BGL is the price you pay for getting such a powerful and flexible toolkit.  However, I can identify three specific things that contributed to the challenge of writing this sample:
  1. A lack of examples of running A-star search on implicit graphs.
  2. A-star search bugs in Boost 1.43 that are fixed in the latest source.
  3. My confusion about whether or not to subclass Boost Graph Library structures.
(1) I hope this code can help other people with.

(2) hit me because I'm developing on OS X and getting my Boost from MacPorts, which currently only has released version 1.42.  It won't be an issue for people building against the latest version.

(3) caused me to go down a few blind alleys.  I by trying to subclass grid_graph, and when that didn't work made grid_graph a member of my own maze class.  Later still, I found that what I really needed was a grid graph from which I could selectively remove edges.  I would have liked to have used grid_graph and just subclassed its out edge iterator, but since subclassing BGL components is a bad idea I ended up writing my own grid implementation.

I've seen it mentioned elsewhere on this board, but I'll also suggest that a warning about subclassing BGL components should be prominent in the documentation.

Thanks for your help getting this and the implicit graph example into shape.  If there are more tweaks that would make them more suitable for the Boost examples directory, let me know.


2010/7/10 Jeremiah Willcock <jewillco@osl.iu.edu>
On Fri, 9 Jul 2010, W.P. McNeill wrote:

Is there a separate ticket number for this?  I'd like to put these in the README. BTW This is starting to come together now.  I should have a working maze search example soon.

I don't see a ticket for the bug -- I think you reported it through an email to the Boost list and not a formal ticket.  The trunk fix is in r63333 and the release branch fix is in r63554.  The fix should be in 1.44 (I'm pretty sure, but you might want to check to be really safe).  You can just grab grid_graph.hpp from the release branch (https://svn.boost.org/svn/boost/branches/release/boost/graph/grid_graph.hpp) if you want to try it yourself.

-- Jeremiah Willcock



On Tue, Jul 6, 2010 at 10:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
     On Tue, 6 Jul 2010, W.P. McNeill wrote:

           Looking through the error spew again, there are actually two errors.  The first is the one I already showed you.  Then beneath that
           there's another big error
           stack that winds through various astar_dispatch functions and ends with no matching function call to
           boost::detail::grid_graph_out_edge_at.
           main.cpp:38:   instantiated from here
           /opt/local/include/boost/iterator/transform_iterator.hpp:100: error: no matching function for call to
           ‘boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >::grid_graph_out_edge_at()’
           /opt/local/include/boost/graph/grid_graph.hpp:128: note: candidates are:
           boost::detail::grid_graph_out_edge_at<Graph>::grid_graph_out_edge_at(typename
           boost::graph_traits<G>::vertex_descriptor, const Graph*) [with Graph = boost::grid_graph<2ul, size_t, size_t>]
           /opt/local/include/boost/graph/grid_graph.hpp:119: note:                 boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
           size_t, size_t>
           >::grid_graph_out_edge_at(const boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >&)
           make: *** [main.o] Error 1

           Presumably the same issue.


Yes.  This has been fixed in Boost trunk, though, so please try the copy of grid_graph.hpp from there.

-- Jeremiah Willcock
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users




_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users