ceph/src/boost/libs/graph/example/astar_maze.cpp

   1
   2 //          Copyright W.P. McNeill 2010.
   3 // Distributed under the Boost Software License, Version 1.0.
   4 //    (See accompanying file LICENSE_1_0.txt or copy at
   5 //          http://www.boost.org/LICENSE_1_0.txt)
   6
   7
   8 // This program uses the A-star search algorithm in the Boost Graph Library to
   9 // solve a maze.  It is an example of how to apply Boost Graph Library
  10 // algorithms to implicit graphs.
  11 //
  12 // This program generates a random maze and then tries to find the shortest
  13 // path from the lower left-hand corner to the upper right-hand corner.  Mazes
  14 // are represented by two-dimensional grids where a cell in the grid may
  15 // contain a barrier.  You may move up, down, right, or left to any adjacent
  16 // cell that does not contain a barrier.
  17 //
  18 // Once a maze solution has been attempted, the maze is printed.  If a
  19 // solution was found it will be shown in the maze printout and its length
  20 // will be returned.  Note that not all mazes have solutions.
  21 //
  22 // The default maze size is 20x10, though different dimensions may be
  23 // specified on the command line.
  24
  25 /*
  26    IMPORTANT:
  27    ~~~~~~~~~~
  28
  29    This example appears to be broken and crashes at runtime, see https://github.com/boostorg/graph/issues/148
  30
  31 */
  32
  33
  34 #include <boost/graph/astar_search.hpp>
  35 #include <boost/graph/filtered_graph.hpp>
  36 #include <boost/graph/grid_graph.hpp>
  37 #include <boost/lexical_cast.hpp>
  38 #include <boost/random/mersenne_twister.hpp>
  39 #include <boost/random/uniform_int.hpp>
  40 #include <boost/random/variate_generator.hpp>
  41 #include <boost/unordered_map.hpp>
  42 #include <boost/unordered_set.hpp>
  43 #include <ctime>
  44 #include <iostream>
  45
  46 boost::mt19937 random_generator;
  47
  48 // Distance traveled in the maze
  49 typedef double distance;
  50
  51 #define GRID_RANK 2
  52 typedef boost::grid_graph<GRID_RANK> grid;
  53 typedef boost::graph_traits<grid>::vertex_descriptor vertex_descriptor;
  54 typedef boost::graph_traits<grid>::vertices_size_type vertices_size_type;
  55
  56 // A hash function for vertices.
  57 struct vertex_hash {
  58   typedef vertex_descriptor argument_type;
  59   typedef std::size_t result_type;
  60   std::size_t operator()(vertex_descriptor const& u) const {
  61     std::size_t seed = 0;
  62     boost::hash_combine(seed, u[0]);
  63     boost::hash_combine(seed, u[1]);
  64     return seed;
  65   }
  66 };
  67
  68 typedef boost::unordered_set<vertex_descriptor, vertex_hash> vertex_set;
  69 typedef boost::vertex_subset_complement_filter<grid, vertex_set>::type
  70         filtered_grid;
  71
  72 // A searchable maze
  73 //
  74 // The maze is grid of locations which can either be empty or contain a
  75 // barrier.  You can move to an adjacent location in the grid by going up,
  76 // down, left and right.  Moving onto a barrier is not allowed.  The maze can
  77 // be solved by finding a path from the lower-left-hand corner to the
  78 // upper-right-hand corner.  If no open path exists between these two
  79 // locations, the maze is unsolvable.
  80 //
  81 // The maze is implemented as a filtered grid graph where locations are
  82 // vertices.  Barrier vertices are filtered out of the graph.
  83 //
  84 // A-star search is used to find a path through the maze. Each edge has a
  85 // weight of one, so the total path length is equal to the number of edges
  86 // traversed.
  87 class maze {
  88 public:
  89   friend std::ostream& operator<<(std::ostream&, const maze&);
  90   friend void random_maze(maze&);
  91
  92   maze():m_grid(create_grid(0, 0)),m_barrier_grid(create_barrier_grid()) {};
  93   maze(std::size_t x, std::size_t y):m_grid(create_grid(x, y)),
  94        m_barrier_grid(create_barrier_grid()) {};
  95
  96   // The length of the maze along the specified dimension.
  97   vertices_size_type length(std::size_t d) const {return m_grid.length(d);}
  98
  99   bool has_barrier(vertex_descriptor u) const {
 100     return m_barriers.find(u) != m_barriers.end();
 101   }
 102
 103   // Try to find a path from the lower-left-hand corner source (0,0) to the
 104   // upper-right-hand corner goal (x-1, y-1).
 105   vertex_descriptor source() const {return vertex(0, m_grid);}
 106   vertex_descriptor goal() const {
 107     return vertex(num_vertices(m_grid)-1, m_grid);
 108   }
 109
 110   bool solve();
 111   bool solved() const {return !m_solution.empty();}
 112   bool solution_contains(vertex_descriptor u) const {
 113     return m_solution.find(u) != m_solution.end();
 114   }
 115
 116 private:
 117   // Create the underlying rank-2 grid with the specified dimensions.
 118   grid create_grid(std::size_t x, std::size_t y) {
 119     boost::array<std::size_t, GRID_RANK> lengths = { {x, y} };
 120     return grid(lengths);
 121   }
 122
 123   // Filter the barrier vertices out of the underlying grid.
 124   filtered_grid create_barrier_grid() {
 125     return boost::make_vertex_subset_complement_filter(m_grid, m_barriers);
 126   }
 127
 128   // The grid underlying the maze
 129   grid m_grid;
 130   // The barriers in the maze
 131   vertex_set m_barriers;
 132   // The underlying maze grid with barrier vertices filtered out
 133   filtered_grid m_barrier_grid;
 134   // The vertices on a solution path through the maze
 135   vertex_set m_solution;
 136   // The length of the solution path
 137   distance m_solution_length;
 138 };
 139
 140
 141 // Euclidean heuristic for a grid
 142 //
 143 // This calculates the Euclidean distance between a vertex and a goal
 144 // vertex.
 145 class euclidean_heuristic:
 146       public boost::astar_heuristic<filtered_grid, double>
 147 {
 148 public:
 149   euclidean_heuristic(vertex_descriptor goal):m_goal(goal) {};
 150
 151   double operator()(vertex_descriptor v) {
 152     return sqrt(pow(double(m_goal[0] - v[0]), 2) + pow(double(m_goal[1] - v[1]), 2));
 153   }
 154
 155 private:
 156   vertex_descriptor m_goal;
 157 };
 158
 159 // Exception thrown when the goal vertex is found
 160 struct found_goal {};
 161
 162 // Visitor that terminates when we find the goal vertex
 163 struct astar_goal_visitor:public boost::default_astar_visitor {
 164   astar_goal_visitor(vertex_descriptor goal):m_goal(goal) {};
 165
 166   void examine_vertex(vertex_descriptor u, const filtered_grid&) {
 167     if (u == m_goal)
 168       throw found_goal();
 169   }
 170
 171 private:
 172   vertex_descriptor m_goal;
 173 };
 174
 175 // Solve the maze using A-star search.  Return true if a solution was found.
 176 bool maze::solve() {
 177   boost::static_property_map<distance> weight(1);
 178   // The predecessor map is a vertex-to-vertex mapping.
 179   typedef boost::unordered_map<vertex_descriptor,
 180                                vertex_descriptor,
 181                                vertex_hash> pred_map;
 182   pred_map predecessor;
 183   boost::associative_property_map<pred_map> pred_pmap(predecessor);
 184   // The distance map is a vertex-to-distance mapping.
 185   typedef boost::unordered_map<vertex_descriptor,
 186                                distance,
 187                                vertex_hash> dist_map;
 188   dist_map distance;
 189   boost::associative_property_map<dist_map> dist_pmap(distance);
 190
 191   vertex_descriptor s = source();
 192   vertex_descriptor g = goal();
 193   euclidean_heuristic heuristic(g);
 194   astar_goal_visitor visitor(g);
 195
 196   try {
 197     astar_search(m_barrier_grid, s, heuristic,
 198                  boost::weight_map(weight).
 199                  predecessor_map(pred_pmap).
 200                  distance_map(dist_pmap).
 201                  visitor(visitor) );
 202   } catch(found_goal fg) {
 203     // Walk backwards from the goal through the predecessor chain adding
 204     // vertices to the solution path.
 205     for (vertex_descriptor u = g; u != s; u = predecessor[u])
 206       m_solution.insert(u);
 207     m_solution.insert(s);
 208     m_solution_length = distance[g];
 209     return true;
 210   }
 211
 212   return false;
 213 }
 214
 215
 216 #define BARRIER "#"
 217 // Print the maze as an ASCII map.
 218 std::ostream& operator<<(std::ostream& output, const maze& m) {
 219   // Header
 220   for (vertices_size_type i = 0; i < m.length(0)+2; i++)
 221     output << BARRIER;
 222   output << std::endl;
 223   // Body
 224   for (int y = m.length(1)-1; y >= 0; y--) {
 225     // Enumerate rows in reverse order and columns in regular order so that
 226     // (0,0) appears in the lower left-hand corner.  This requires that y be
 227     // int and not the unsigned vertices_size_type because the loop exit
 228     // condition is y==-1.
 229     for (vertices_size_type x = 0; x < m.length(0); x++) {
 230       // Put a barrier on the left-hand side.
 231       if (x == 0)
 232         output << BARRIER;
 233       // Put the character representing this point in the maze grid.
 234       vertex_descriptor u = {{x, vertices_size_type(y)}};
 235       if (m.solution_contains(u))
 236         output << ".";
 237       else if (m.has_barrier(u))
 238         output << BARRIER;
 239       else
 240         output << " ";
 241       // Put a barrier on the right-hand side.
 242       if (x == m.length(0)-1)
 243         output << BARRIER;
 244     }
 245     // Put a newline after every row except the last one.
 246     output << std::endl;
 247   }
 248   // Footer
 249   for (vertices_size_type i = 0; i < m.length(0)+2; i++)
 250     output << BARRIER;
 251   if (m.solved())
 252     output << std::endl << "Solution length " << m.m_solution_length;
 253   return output;
 254 }
 255
 256 // Return a random integer in the interval [a, b].
 257 std::size_t random_int(std::size_t a, std::size_t b) {
 258   if (b < a)
 259     b = a;
 260   boost::uniform_int<> dist(a, b);
 261   boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
 262   generate(random_generator, dist);
 263   return generate();
 264 }
 265
 266 // Generate a maze with a random assignment of barriers.
 267 void random_maze(maze& m) {
 268   vertices_size_type n = num_vertices(m.m_grid);
 269   vertex_descriptor s = m.source();
 270   vertex_descriptor g = m.goal();
 271   // One quarter of the cells in the maze should be barriers.
 272   int barriers = n/4;
 273   while (barriers > 0) {
 274     // Choose horizontal or vertical direction.
 275     std::size_t direction = random_int(0, 1);
 276     // Walls range up to one quarter the dimension length in this direction.
 277     vertices_size_type wall = random_int(1, m.length(direction)/4);
 278     // Create the wall while decrementing the total barrier count.
 279     vertex_descriptor u = vertex(random_int(0, n-1), m.m_grid);
 280     while (wall) {
 281       // Start and goal spaces should never be barriers.
 282       if (u != s && u != g) {
 283         wall--;
 284         if (!m.has_barrier(u)) {
 285           m.m_barriers.insert(u);
 286           barriers--;
 287         }
 288       }
 289       vertex_descriptor v = m.m_grid.next(u, direction);
 290       // Stop creating this wall if we reached the maze's edge.
 291       if (u == v)
 292         break;
 293       u = v;
 294     }
 295   }
 296 }
 297
 298 int main (int argc, char const *argv[]) {
 299   // The default maze size is 20x10.  A different size may be specified on
 300   // the command line.
 301   std::size_t x = 20;
 302   std::size_t y = 10;
 303
 304   if (argc == 3) {
 305     x = boost::lexical_cast<std::size_t>(argv[1]);
 306     y = boost::lexical_cast<std::size_t>(argv[2]);
 307   }
 308
 309   random_generator.seed(std::time(0));
 310   maze m(x, y);
 311   random_maze(m);
 312   if (m.solve())
 313     std::cout << "Solved the maze." << std::endl;
 314   else
 315     std::cout << "The maze is not solvable." << std::endl;
 316   std::cout << m << std::endl;
 317   return 0;
 318 }