On Mon, 1 Mar 2010, Damien Maupu wrote:
Hi,
Some weeks ago, I wrote on this mailing list, that I succeed achieving an A* search using an implicit graph. A Boost user emailed me to send him an example of my implementation. As the web is lacking of such example, I think the best place to send such example would be here as it might help others in the future.
My example might not be the best, the most optimized or most well-coded. I am open to suggestions, corrections and comments. Let me know if something unclear. The code comes below.
Are you willing to license this under the Boost Software License? If so, please put in that banner (and the accompanying copyright notice) and report the code. After that, I can add it to the examples directory in BGL. Is that the intent: that this becomes an example? Or did you intend it to become something else? Why is there a separate header file from the implementation?
Few words to quickly explain the code: The goal is to A* search a graph (named m_SearchGraph) that grows (i.e. m_SearchGraph is implicit) based on another graph (named MyGraph). The search starts from 2D point (_startX, _startZ) and must get enough close (less than error "_epsilon") to 2D point (_goalX, _goalZ). The example is dumb and simply increment current position whatever the node in MyGraph (i.e. currX++, currZ++, currWeight += sqrt(2)). User need to adapt this dummy behavior depending on its needs (search for "//to change"). Most adaptations have to be done in "examine_vertex" (and also by providing ref/ptr to needed objects to the visitor constructor)
PS: The implementation assumes both graphs are adjacency_list with "vecs" for both edges and vertices (in which a vertex/edge descriptor is equivalent to an "int", for my understanding)
Why not use a vertex_index_map?
PS2: Id == descriptor (e.g. edgeId == edge_descriptor)
That is very unlikely to be true; for example, compressed_sparse_row_graph has a structure as an edge descriptor but its edge indices are still numbers. -- Jeremiah Willcock