On Mon, 12 Jul 2010, W.P. McNeill wrote:
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.
One more that has hit other people is named parameters (especially the thing about using "." between arguments rather than ",").
(1) I hope this code can help other people with.
Yes, and thank you for doing the example.
(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.
OK. I don't think anyone had tried astar_search with an implicit graph before the earliest bug report on the issue (the first one, though, was about implicit graphs that don't have num_vertices() and astar_search's failure on those).
(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.
The subclassing thing is based on STL; you are not supposed to subclass STL containers either. If you want to selectively remove edges, look at boost::graph::filtered_graph (http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/filtered_graph.html). You should be able to wrap that on top of the existing grid_graph.
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.
Where do you think that should go?
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.
One minor thing: maze_traversal_catetory should be maze_traversal_category. I think using filtered_graph might replace all of that code, however. You might also want to use iterator_property_map or shared_array_property_map instead of associative_property_map for performance. If you want to really make the code Boost-like (and I'm not suggesting or requiring that you do this), you can also use Boost.Program_options, Boost.Lexical_cast and Boost.Random to replace the corresponding C functions that you are using now. You are also free to use "using namespace std;" and/or "using namespace boost;" in examples; you can put those in if you think it will make the code more readable. -- Jeremiah Willcock