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 <jewillco@osl.iu.edu> wrote:
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