Boost logo

Boost Users :

Subject: Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search
From: W.P. McNeill (billmcn_at_[hidden])
Date: 2010-07-05 14:28:52


I'm using my own graph class because I need an implicit graph for the task
I'm trying to do.

Here's the full background: I'm writing a program that solves a maze using
a-star search. (It's on github as Searchable Graph
Example<http://github.com/wpm/Boost-Searchable-Grid-Example>.)
 The maze is a grid of cells in which you can move up, down, right and left.
 Cells are either empty or blocked. The cost of entering an empty cell is
1, and the cost of entering a blocked cell is infinity.

(This is actually a warm-up for a more sophisticated graph search program,
but that one also operates on a grid, so a lot of this code will be
reusable. Plus, I think an a-star maze search example would be useful for
others to see.)

Because the graph topology is a grid, it seemed like the best way to
implement this is with an implicit graph. I first tried adding edge and
vertex properties to Boost's grid_graph class, but I ran into compile
errors, some of which are documented earlier in this thread. Even after I
worked around those errors I hit others, and it seemed like I was writing an
awful lot of boilerplate code to use grid_graph, so it would be easier to
implement my own grid.

Now I'm writing my own grid class (called maze_search::maze in the code on
github). It will have an out edge iterator that determines the the grid
structure, a read/write boolean vertex property for whether or not a cell is
blocked, and a read-only edge weight property that returns the cost of
entering a cell. I've finished the iterator and the edge weight property,
and am starting to look at the vertex property.

On Sun, Jul 4, 2010 at 7:48 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Sun, 4 Jul 2010, W.P. McNeill wrote:
>
> The property type problem was because I didn't have property_traits<>
>> correctly defined. I rewrote this from scratch and defined my own grid
>> object instead of using Boost's grid_graph. Now I can get a-star to run,
>> but only if I use the latest version of astar_search.hpp. If I use
>> the Boost 1.42 version installed on my machine by Macports, it fails to
>> compile because of bug 3917.
>>
>> Is 3917 fixed in version 1.43? (I'm guessing that's what the
>> struckthrough "Boost 1.43.0" in the Milestone field of the bug report
>> means.)
>>
>
> I'm pretty sure the fix made it into 1.43. The milestone fields are not
> really up to date, though. Are you now using your own graph class just in
> order to add an internal property map?
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net