// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-
// This program uses the A-star search algorithm in the Boost Graph Library to
// solve a maze. It is an example of how to apply Boost Graph Library
// algorithms to implicit graphs.
IMPORTANT:
~~~~~~~~~~
- This example appears to be broken and crashes at runtime, see https://github.com/boostorg/graph/issues/148
+ This example appears to be broken and crashes at runtime, see
+ https://github.com/boostorg/graph/issues/148
*/
-
#include <boost/graph/astar_search.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/grid_graph.hpp>
typedef double distance;
#define GRID_RANK 2
-typedef boost::grid_graph<GRID_RANK> grid;
-typedef boost::graph_traits<grid>::vertex_descriptor vertex_descriptor;
-typedef boost::graph_traits<grid>::vertices_size_type vertices_size_type;
+typedef boost::grid_graph< GRID_RANK > grid;
+typedef boost::graph_traits< grid >::vertex_descriptor vertex_descriptor;
+typedef boost::graph_traits< grid >::vertices_size_type vertices_size_type;
// A hash function for vertices.
-struct vertex_hash {
- typedef vertex_descriptor argument_type;
- typedef std::size_t result_type;
- std::size_t operator()(vertex_descriptor const& u) const {
- std::size_t seed = 0;
- boost::hash_combine(seed, u[0]);
- boost::hash_combine(seed, u[1]);
- return seed;
- }
+struct vertex_hash
+{
+ typedef vertex_descriptor argument_type;
+ typedef std::size_t result_type;
+ std::size_t operator()(vertex_descriptor const& u) const
+ {
+ std::size_t seed = 0;
+ boost::hash_combine(seed, u[0]);
+ boost::hash_combine(seed, u[1]);
+ return seed;
+ }
};
-typedef boost::unordered_set<vertex_descriptor, vertex_hash> vertex_set;
-typedef boost::vertex_subset_complement_filter<grid, vertex_set>::type
- filtered_grid;
+typedef boost::unordered_set< vertex_descriptor, vertex_hash > vertex_set;
+typedef boost::vertex_subset_complement_filter< grid, vertex_set >::type
+ filtered_grid;
// A searchable maze
//
// A-star search is used to find a path through the maze. Each edge has a
// weight of one, so the total path length is equal to the number of edges
// traversed.
-class maze {
+class maze
+{
public:
- friend std::ostream& operator<<(std::ostream&, const maze&);
- friend void random_maze(maze&);
+ friend std::ostream& operator<<(std::ostream&, const maze&);
+ friend void random_maze(maze&);
- maze():m_grid(create_grid(0, 0)),m_barrier_grid(create_barrier_grid()) {};
- maze(std::size_t x, std::size_t y):m_grid(create_grid(x, y)),
- m_barrier_grid(create_barrier_grid()) {};
+ maze()
+ : m_grid(create_grid(0, 0)), m_barrier_grid(create_barrier_grid()) {};
+ maze(std::size_t x, std::size_t y)
+ : m_grid(create_grid(x, y)), m_barrier_grid(create_barrier_grid()) {};
- // The length of the maze along the specified dimension.
- vertices_size_type length(std::size_t d) const {return m_grid.length(d);}
+ // The length of the maze along the specified dimension.
+ vertices_size_type length(std::size_t d) const { return m_grid.length(d); }
- bool has_barrier(vertex_descriptor u) const {
- return m_barriers.find(u) != m_barriers.end();
- }
+ bool has_barrier(vertex_descriptor u) const
+ {
+ return m_barriers.find(u) != m_barriers.end();
+ }
- // Try to find a path from the lower-left-hand corner source (0,0) to the
- // upper-right-hand corner goal (x-1, y-1).
- vertex_descriptor source() const {return vertex(0, m_grid);}
- vertex_descriptor goal() const {
- return vertex(num_vertices(m_grid)-1, m_grid);
- }
+ // Try to find a path from the lower-left-hand corner source (0,0) to the
+ // upper-right-hand corner goal (x-1, y-1).
+ vertex_descriptor source() const { return vertex(0, m_grid); }
+ vertex_descriptor goal() const
+ {
+ return vertex(num_vertices(m_grid) - 1, m_grid);
+ }
- bool solve();
- bool solved() const {return !m_solution.empty();}
- bool solution_contains(vertex_descriptor u) const {
- return m_solution.find(u) != m_solution.end();
- }
+ bool solve();
+ bool solved() const { return !m_solution.empty(); }
+ bool solution_contains(vertex_descriptor u) const
+ {
+ return m_solution.find(u) != m_solution.end();
+ }
private:
- // Create the underlying rank-2 grid with the specified dimensions.
- grid create_grid(std::size_t x, std::size_t y) {
- boost::array<std::size_t, GRID_RANK> lengths = { {x, y} };
- return grid(lengths);
- }
-
- // Filter the barrier vertices out of the underlying grid.
- filtered_grid create_barrier_grid() {
- return boost::make_vertex_subset_complement_filter(m_grid, m_barriers);
- }
-
- // The grid underlying the maze
- grid m_grid;
- // The barriers in the maze
- vertex_set m_barriers;
- // The underlying maze grid with barrier vertices filtered out
- filtered_grid m_barrier_grid;
- // The vertices on a solution path through the maze
- vertex_set m_solution;
- // The length of the solution path
- distance m_solution_length;
-};
+ // Create the underlying rank-2 grid with the specified dimensions.
+ grid create_grid(std::size_t x, std::size_t y)
+ {
+ boost::array< std::size_t, GRID_RANK > lengths = { { x, y } };
+ return grid(lengths);
+ }
+ // Filter the barrier vertices out of the underlying grid.
+ filtered_grid create_barrier_grid()
+ {
+ return boost::make_vertex_subset_complement_filter(m_grid, m_barriers);
+ }
+
+ // The grid underlying the maze
+ grid m_grid;
+ // The barriers in the maze
+ vertex_set m_barriers;
+ // The underlying maze grid with barrier vertices filtered out
+ filtered_grid m_barrier_grid;
+ // The vertices on a solution path through the maze
+ vertex_set m_solution;
+ // The length of the solution path
+ distance m_solution_length;
+};
// Euclidean heuristic for a grid
//
// This calculates the Euclidean distance between a vertex and a goal
// vertex.
-class euclidean_heuristic:
- public boost::astar_heuristic<filtered_grid, double>
+class euclidean_heuristic
+: public boost::astar_heuristic< filtered_grid, double >
{
public:
- euclidean_heuristic(vertex_descriptor goal):m_goal(goal) {};
+ euclidean_heuristic(vertex_descriptor goal) : m_goal(goal) {};
- double operator()(vertex_descriptor v) {
- return sqrt(pow(double(m_goal[0] - v[0]), 2) + pow(double(m_goal[1] - v[1]), 2));
- }
+ double operator()(vertex_descriptor v)
+ {
+ return sqrt(pow(double(m_goal[0] - v[0]), 2)
+ + pow(double(m_goal[1] - v[1]), 2));
+ }
private:
- vertex_descriptor m_goal;
+ vertex_descriptor m_goal;
};
// Exception thrown when the goal vertex is found
-struct found_goal {};
+struct found_goal
+{
+};
// Visitor that terminates when we find the goal vertex
-struct astar_goal_visitor:public boost::default_astar_visitor {
- astar_goal_visitor(vertex_descriptor goal):m_goal(goal) {};
+struct astar_goal_visitor : public boost::default_astar_visitor
+{
+ astar_goal_visitor(vertex_descriptor goal) : m_goal(goal) {};
- void examine_vertex(vertex_descriptor u, const filtered_grid&) {
- if (u == m_goal)
- throw found_goal();
- }
+ void examine_vertex(vertex_descriptor u, const filtered_grid&)
+ {
+ if (u == m_goal)
+ throw found_goal();
+ }
private:
- vertex_descriptor m_goal;
+ vertex_descriptor m_goal;
};
// Solve the maze using A-star search. Return true if a solution was found.
-bool maze::solve() {
- boost::static_property_map<distance> weight(1);
- // The predecessor map is a vertex-to-vertex mapping.
- typedef boost::unordered_map<vertex_descriptor,
- vertex_descriptor,
- vertex_hash> pred_map;
- pred_map predecessor;
- boost::associative_property_map<pred_map> pred_pmap(predecessor);
- // The distance map is a vertex-to-distance mapping.
- typedef boost::unordered_map<vertex_descriptor,
- distance,
- vertex_hash> dist_map;
- dist_map distance;
- boost::associative_property_map<dist_map> dist_pmap(distance);
-
- vertex_descriptor s = source();
- vertex_descriptor g = goal();
- euclidean_heuristic heuristic(g);
- astar_goal_visitor visitor(g);
-
- try {
- astar_search(m_barrier_grid, s, heuristic,
- boost::weight_map(weight).
- predecessor_map(pred_pmap).
- distance_map(dist_pmap).
- visitor(visitor) );
- } catch(found_goal fg) {
- // Walk backwards from the goal through the predecessor chain adding
- // vertices to the solution path.
- for (vertex_descriptor u = g; u != s; u = predecessor[u])
- m_solution.insert(u);
- m_solution.insert(s);
- m_solution_length = distance[g];
- return true;
- }
-
- return false;
-}
+bool maze::solve()
+{
+ boost::static_property_map< distance > weight(1);
+ // The predecessor map is a vertex-to-vertex mapping.
+ typedef boost::unordered_map< vertex_descriptor, vertex_descriptor,
+ vertex_hash >
+ pred_map;
+ pred_map predecessor;
+ boost::associative_property_map< pred_map > pred_pmap(predecessor);
+ // The distance map is a vertex-to-distance mapping.
+ typedef boost::unordered_map< vertex_descriptor, distance, vertex_hash >
+ dist_map;
+ dist_map distance;
+ boost::associative_property_map< dist_map > dist_pmap(distance);
+
+ vertex_descriptor s = source();
+ vertex_descriptor g = goal();
+ euclidean_heuristic heuristic(g);
+ astar_goal_visitor visitor(g);
+
+ try
+ {
+ astar_search(m_barrier_grid, s, heuristic,
+ boost::weight_map(weight)
+ .predecessor_map(pred_pmap)
+ .distance_map(dist_pmap)
+ .visitor(visitor));
+ }
+ catch (found_goal fg)
+ {
+ // Walk backwards from the goal through the predecessor chain adding
+ // vertices to the solution path.
+ for (vertex_descriptor u = g; u != s; u = predecessor[u])
+ m_solution.insert(u);
+ m_solution.insert(s);
+ m_solution_length = distance[g];
+ return true;
+ }
+ return false;
+}
#define BARRIER "#"
// Print the maze as an ASCII map.
-std::ostream& operator<<(std::ostream& output, const maze& m) {
- // Header
- for (vertices_size_type i = 0; i < m.length(0)+2; i++)
- output << BARRIER;
- output << std::endl;
- // Body
- for (int y = m.length(1)-1; y >= 0; y--) {
- // Enumerate rows in reverse order and columns in regular order so that
- // (0,0) appears in the lower left-hand corner. This requires that y be
- // int and not the unsigned vertices_size_type because the loop exit
- // condition is y==-1.
- for (vertices_size_type x = 0; x < m.length(0); x++) {
- // Put a barrier on the left-hand side.
- if (x == 0)
- output << BARRIER;
- // Put the character representing this point in the maze grid.
- vertex_descriptor u = {{x, vertices_size_type(y)}};
- if (m.solution_contains(u))
- output << ".";
- else if (m.has_barrier(u))
- output << BARRIER;
- else
- output << " ";
- // Put a barrier on the right-hand side.
- if (x == m.length(0)-1)
+std::ostream& operator<<(std::ostream& output, const maze& m)
+{
+ // Header
+ for (vertices_size_type i = 0; i < m.length(0) + 2; i++)
output << BARRIER;
- }
- // Put a newline after every row except the last one.
output << std::endl;
- }
- // Footer
- for (vertices_size_type i = 0; i < m.length(0)+2; i++)
- output << BARRIER;
- if (m.solved())
- output << std::endl << "Solution length " << m.m_solution_length;
- return output;
+ // Body
+ for (int y = m.length(1) - 1; y >= 0; y--)
+ {
+ // Enumerate rows in reverse order and columns in regular order so that
+ // (0,0) appears in the lower left-hand corner. This requires that y be
+ // int and not the unsigned vertices_size_type because the loop exit
+ // condition is y==-1.
+ for (vertices_size_type x = 0; x < m.length(0); x++)
+ {
+ // Put a barrier on the left-hand side.
+ if (x == 0)
+ output << BARRIER;
+ // Put the character representing this point in the maze grid.
+ vertex_descriptor u = { { x, vertices_size_type(y) } };
+ if (m.solution_contains(u))
+ output << ".";
+ else if (m.has_barrier(u))
+ output << BARRIER;
+ else
+ output << " ";
+ // Put a barrier on the right-hand side.
+ if (x == m.length(0) - 1)
+ output << BARRIER;
+ }
+ // Put a newline after every row except the last one.
+ output << std::endl;
+ }
+ // Footer
+ for (vertices_size_type i = 0; i < m.length(0) + 2; i++)
+ output << BARRIER;
+ if (m.solved())
+ output << std::endl << "Solution length " << m.m_solution_length;
+ return output;
}
// Return a random integer in the interval [a, b].
-std::size_t random_int(std::size_t a, std::size_t b) {
- if (b < a)
- b = a;
- boost::uniform_int<> dist(a, b);
- boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
- generate(random_generator, dist);
- return generate();
+std::size_t random_int(std::size_t a, std::size_t b)
+{
+ if (b < a)
+ b = a;
+ boost::uniform_int<> dist(a, b);
+ boost::variate_generator< boost::mt19937&, boost::uniform_int<> > generate(
+ random_generator, dist);
+ return generate();
}
// Generate a maze with a random assignment of barriers.
-void random_maze(maze& m) {
- vertices_size_type n = num_vertices(m.m_grid);
- vertex_descriptor s = m.source();
- vertex_descriptor g = m.goal();
- // One quarter of the cells in the maze should be barriers.
- int barriers = n/4;
- while (barriers > 0) {
- // Choose horizontal or vertical direction.
- std::size_t direction = random_int(0, 1);
- // Walls range up to one quarter the dimension length in this direction.
- vertices_size_type wall = random_int(1, m.length(direction)/4);
- // Create the wall while decrementing the total barrier count.
- vertex_descriptor u = vertex(random_int(0, n-1), m.m_grid);
- while (wall) {
- // Start and goal spaces should never be barriers.
- if (u != s && u != g) {
- wall--;
- if (!m.has_barrier(u)) {
- m.m_barriers.insert(u);
- barriers--;
+void random_maze(maze& m)
+{
+ vertices_size_type n = num_vertices(m.m_grid);
+ vertex_descriptor s = m.source();
+ vertex_descriptor g = m.goal();
+ // One quarter of the cells in the maze should be barriers.
+ int barriers = n / 4;
+ while (barriers > 0)
+ {
+ // Choose horizontal or vertical direction.
+ std::size_t direction = random_int(0, 1);
+ // Walls range up to one quarter the dimension length in this direction.
+ vertices_size_type wall = random_int(1, m.length(direction) / 4);
+ // Create the wall while decrementing the total barrier count.
+ vertex_descriptor u = vertex(random_int(0, n - 1), m.m_grid);
+ while (wall)
+ {
+ // Start and goal spaces should never be barriers.
+ if (u != s && u != g)
+ {
+ wall--;
+ if (!m.has_barrier(u))
+ {
+ m.m_barriers.insert(u);
+ barriers--;
+ }
+ }
+ vertex_descriptor v = m.m_grid.next(u, direction);
+ // Stop creating this wall if we reached the maze's edge.
+ if (u == v)
+ break;
+ u = v;
}
- }
- vertex_descriptor v = m.m_grid.next(u, direction);
- // Stop creating this wall if we reached the maze's edge.
- if (u == v)
- break;
- u = v;
}
- }
}
-int main (int argc, char const *argv[]) {
- // The default maze size is 20x10. A different size may be specified on
- // the command line.
- std::size_t x = 20;
- std::size_t y = 10;
-
- if (argc == 3) {
- x = boost::lexical_cast<std::size_t>(argv[1]);
- y = boost::lexical_cast<std::size_t>(argv[2]);
- }
-
- random_generator.seed(std::time(0));
- maze m(x, y);
- random_maze(m);
- if (m.solve())
- std::cout << "Solved the maze." << std::endl;
- else
- std::cout << "The maze is not solvable." << std::endl;
- std::cout << m << std::endl;
- return 0;
+int main(int argc, char const* argv[])
+{
+ // The default maze size is 20x10. A different size may be specified on
+ // the command line.
+ std::size_t x = 20;
+ std::size_t y = 10;
+
+ if (argc == 3)
+ {
+ x = boost::lexical_cast< std::size_t >(argv[1]);
+ y = boost::lexical_cast< std::size_t >(argv[2]);
+ }
+
+ random_generator.seed(std::time(0));
+ maze m(x, y);
+ random_maze(m);
+ if (m.solve())
+ std::cout << "Solved the maze." << std::endl;
+ else
+ std::cout << "The maze is not solvable." << std::endl;
+ std::cout << m << std::endl;
+ return 0;
}
projects / ceph.git / blobdiff