Having finally gotten this working, I wanted to share it. As the topic
states, this is an implementation of an infinite, implicit graph, and an
example that searches the graph with astar_search_no_init. I didn't find
any examples out there of anyone doing this particular thing, so I hope it
may be helpful to my fellow travelers.
This code is a bastardization of some stuff from a game I'm working on
(blatant plug: http://snarglequest.blogspot.com/) and the "city search"
example code from the BGL docs. I'm sure it could be more concise, but I
hope you'll find it accessible.
Oh, and critiques would of course be welcome. I said it's working, not
perfect; I'm sure there are many things I could be doing in better ways,
and I'd love to know about them.
Luke
/**
* Example use of boost::astar_search_no_init on an infinite,
implicitly-defined graph.
*
* The graph type used here is XYGraph, representing an infinite grid of
squares. Each
* square is connected to its eight neighbors; however, the example shows
how to use
* boost::filtered_graph to make the search take place only along
orthogonal edges.
*/
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <utility>
#include
#include
#include
#include
#include
namespace Direction
{
enum id
{
MIN = 0,
N = MIN, S, E, W, NW, NE, SE, SW, NONE
};
}
struct XY : public boost::additive >
{
typedef int X;
typedef int Y;
XY(X x = 0, Y y = 0);
// Same square counts.
bool adjacentTo(XY const& that) const;
XY & operator=(XY const& that);
XY & operator+=(XY const& that);
bool operator<(XY const& that) const;
X x;
Y y;
XY neighbor(Direction::id direction) const;
std::set<XY> allNeighbors() const;
};
std::ostream & operator<<(std::ostream & os, XY const& xy);
struct neighbor_iterator;
/*
* Model of:
* * Graph
* * IncidenceGraph
*/
struct XYGraph
{
XYGraph();
// Graph concept requirements
typedef XY vertex_descriptor;
typedef std::pair edge_descriptor;
typedef boost::undirected_tag directed_category;
typedef boost::disallow_parallel_edge_tag edge_parallel_category;
typedef boost::incidence_graph_tag traversal_category;
// IncidenceGraph concept requirements
typedef neighbor_iterator out_edge_iterator;
typedef int degree_size_type;
};
namespace boost
{
template <> struct graph_traits<XYGraph>
{
typedef XYGraph G;
typedef G::vertex_descriptor vertex_descriptor;
typedef G::edge_descriptor edge_descriptor;
typedef G::out_edge_iterator out_edge_iterator;
typedef G::directed_category directed_category;
typedef G::edge_parallel_category edge_parallel_category;
typedef G::traversal_category traversal_category;
typedef G::degree_size_type degree_size_type;
typedef void in_edge_iterator;
typedef void vertex_iterator;
typedef void vertices_size_type;
typedef void edge_iterator;
typedef void edges_size_type;
};
}
// IncidenceGraph concept requirements
std::pair out_edges(XYGraph::vertex_descriptor v, XYGraph
const& g);
XYGraph::degree_size_type out_degree(XYGraph::vertex_descriptor v, XYGraph
const& g);
XYGraph::vertex_descriptor source(XYGraph::edge_descriptor e, XYGraph
const& g);
XYGraph::vertex_descriptor target(XYGraph::edge_descriptor e, XYGraph
const& g);
// Iterator
struct neighbor_iterator :
public boost::iterator_facade,
boost::forward_traversal_tag,
std::pair >
{
public:
neighbor_iterator();
neighbor_iterator(XY xy, Direction::id direction);
neighbor_iterator & operator=(neighbor_iterator const& that);
std::pair operator*() const;
void operator++();
bool operator==(neighbor_iterator const& that) const;
bool equal(neighbor_iterator const& that) const { return
operator==(that); }
void increment() { operator++(); }
private:
XY xy;
Direction::id direction;
};
struct orthogonal_only;
template <typename Graph> class distance_heuristic;
struct found_goal {}; // exception for termination
// visitor that terminates when we find the goal
class astar_goal_visitor : public boost::default_astar_visitor
{
public:
astar_goal_visitor(XY goal) : m_goal(goal) {}
virtual void examine_vertex(XY xy, XYGraph const& g) {
std::cout << "Exploring " << xy << "..." << std::endl;
if(xy == m_goal)
throw found_goal();
}
virtual void examine_vertex(XY xy, boost::filtered_graph const& g) {
std::cout << "Exploring " << xy << "..." << std::endl;
if(xy == m_goal)
throw found_goal();
}
private:
XY m_goal;
};
template
class default_map
{
public:
typedef K key_type;
typedef V data_type;
typedef std::pair value_type;
default_map(V const& defaultValue)
: defaultValue(defaultValue)
{}
V & operator[](K const& k)
{
if (m.find(k) == m.end())
{
m[k] = defaultValue;
}
return m[k];
}
private:
std::map m;
V const defaultValue;
};
struct PredecessorMap
{
PredecessorMap() {}
PredecessorMap(PredecessorMap const& that) : m(that.m) {}
typedef XY key_type;
typedef XY value_type;
typedef XY & reference_type;
typedef boost::read_write_property_map_tag category;
XY & operator[](XY xy) { return m[xy]; }
std::map m;
};
XY get(PredecessorMap const& pm, XY xy)
{
std::map::const_iterator found = pm.m.find(xy);
return (found != pm.m.end()) ? found->second : xy;
}
void put(PredecessorMap & pm, XY key, XY value)
{
pm.m[key] = value;
}
// Filter used to traverse grid only along orthogonal (non-diagonal) edges.
struct orthogonal_only
{
typedef std::pair Edge;
bool operator()(Edge const& edge) const
{
return edge.first.x == edge.second.x || edge.first.y ==
edge.second.y;
}
};
// Euclidean distance heuristic (square root omitted)
template <typename Graph>
class distance_heuristic : public boost::astar_heuristic
{
public:
distance_heuristic(XY goal)
: m_goal(goal) {}
unsigned operator()(XY xy)
{
int dx = m_goal.x - xy.x;
int dy = m_goal.y - xy.y;
unsigned retval = static_cast<unsigned>(dx * dx + dy * dy);
return retval;
}
private:
XY m_goal;
};
int main(int argc, char **argv)
{
XYGraph baseGraph;
boost::filtered_graph g(baseGraph,
orthogonal_only());
//BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<
boost::filtered_graph >));
XY start(0,0);
XY goal(5,7);
std::cout << "Start vertex: " << start << std::endl;
std::cout << "Goal vertex: " << goal << std::endl;
PredecessorMap p;
typedef boost::associative_property_map< default_map >
DistanceMap;
typedef default_map WrappedDistanceMap;
WrappedDistanceMap wrappedMap =
WrappedDistanceMap(std::numeric_limits<unsigned>::max());
wrappedMap[start] = 0;
DistanceMap d = DistanceMap(wrappedMap);
try {
astar_search_no_init(g,
start,
distance_heuristic<XYGraph>(goal)
, visitor(astar_goal_visitor(goal))
. distance_map(d)
. predecessor_map(boost::ref(p))
. weight_map(boost::associative_property_map<
default_map,unsigned> >(
default_map,unsigned>(1)))
. vertex_index_map(boost::associative_property_map<
std::map >(std::map()))
. rank_map(boost::associative_property_map<
std::map >(std::map()))
. color_map(boost::associative_property_map<
std::map >(
std::map()))
. distance_compare(std::less<unsigned>())
. distance_combine(std::plus<unsigned>())
);
} catch(found_goal const&) { // found a path to the goal
std::list<XY> shortest_path;
for(XY xy = goal;; xy = p[xy]) {
shortest_path.push_front(xy);
if(p[xy] == xy)
break;
}
std::cout << "Shortest path from " << start << " to "
<< goal << ": ";
std::list<XY>::iterator spi = shortest_path.begin();
std::cout << start;
for(++spi; spi != shortest_path.end(); ++spi)
std::cout << " -> " << (*spi);
std::cout << std::endl;
return 0;
}
std::cout << "Didn't find a path from " << start << "to"
<< goal << "!" << std::endl;
return 0;
}
XYGraph::XYGraph()
{}
std::pair
out_edges(XYGraph::vertex_descriptor v,
XYGraph const& g)
{
return std::make_pair(
XYGraph::out_edge_iterator(v, Direction::MIN),
XYGraph::out_edge_iterator(v, Direction::NONE) );
}
XYGraph::degree_size_type
out_degree(XYGraph::vertex_descriptor v,
XYGraph const& g)
{
return v.allNeighbors().size();
}
XYGraph::vertex_descriptor
source(XYGraph::edge_descriptor e,
XYGraph const& g)
{
return e.first;
}
XYGraph::vertex_descriptor target(
XYGraph::edge_descriptor e,
XYGraph const& g)
{
return e.second;
}
neighbor_iterator::neighbor_iterator()
{}
neighbor_iterator::neighbor_iterator(XY xy, Direction::id direction)
: xy(xy)
, direction(direction)
{
}
neighbor_iterator & neighbor_iterator::operator=(neighbor_iterator const&
that)
{
xy = that.xy;
direction = that.direction;
return *this;
}
std::pair neighbor_iterator::operator*() const
{
std::pair const retval = std::make_pair(xy,
xy.neighbor(direction));
return retval;
}
void neighbor_iterator::operator++()
{
direction = static_castDirection::id(int(direction) + 1);
}
bool neighbor_iterator::operator==(neighbor_iterator const& that) const
{
return xy == that.xy && direction == that.direction;
}
XY::XY(X x, Y y)
: x(x)
, y(y)
{
}
bool XY::adjacentTo(XY const& that) const
{
return abs(x - that.x) <= 1 && abs(y - that.y) <= 1;
}
XY & XY::operator=(XY const& that)
{
x = that.x;
y = that.y;
return *this;
}
XY & XY::operator+=(XY const& that)
{
x += that.x;
y += that.y;
return *this;
}
bool XY::operator<(XY const& that) const
{
return x < that.x || (x == that.x && y < that.y);
}
std::ostream & operator<<(std::ostream & os, XY const& xy)
{
os << "(" << xy.x << "," << xy.y << ")";
return os;
}
XY XY::neighbor(Direction::id direction) const
{
using namespace Direction;
int dx = 0, dy = 0;
switch (direction)
{
case NW:
case W:
case SW:
dx = -1;
break;
case NE:
case E:
case SE:
dx = 1;
}
switch (direction)
{
case NW:
case N:
case NE:
dy = -1;
break;
case SW:
case S:
case SE:
dy = 1;
}
XY const neighbor(x + dx, y + dy);
return neighbor;
}
std::set<XY> XY::allNeighbors() const
{
std::set<XY> neighbors;
for (int dx = -1; dx <= 1; ++dx)
for (int dy = -1; dy <= 1; ++dy)
neighbors.insert(XY(x+dx,y+dy));
return neighbors;
}
