I intentionally used associative_property_map<> structures for the
predecessor and distance maps for space efficiency. Since I know not every
vertex in the grid will be visited, it made sense to have a map keyed on
vertices rather than a vector with elements for all the vertices. Am I
right in thinking that iterator_property_map won't work for this
implementation? (Since std::map does not model a Random Access Iterator.)
Of course for time efficiency it may still be better to create vectors for
the entire grid rather than maps, particularly for small mazes. But I want
to use maps to illustrate the principle. Also, a hash map would be better
than std::map, but there's no standard hash map implementation so I stay
away from it. (I'm waiting for a Boost hash_map :-)
Using map structures brings up another question: am I correct in thinking
that astar_search_no_init(...) does not permit named parameters so that I
have to create all the various maps myself? (That is what I have gleaned
from looking at the source and experimenting, but I've been wrong before.)
I ask because the real project I'm using this maze search as a warmup for
is aimed at a class of problems where most of the grid is not visited, so I
want to avoid the O(V) initialization by
calling astar_search_no_init(...) with maps that have the correct default
values.
On Mon, Jul 12, 2010 at 1:12 PM, Jeremiah Willcock
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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users