123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318 |
- // Copyright W.P. McNeill 2010.
- // Distributed under the Boost Software License, Version 1.0.
- // (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.
- //
- // This program generates a random maze and then tries to find the shortest
- // path from the lower left-hand corner to the upper right-hand corner. Mazes
- // are represented by two-dimensional grids where a cell in the grid may
- // contain a barrier. You may move up, down, right, or left to any adjacent
- // cell that does not contain a barrier.
- //
- // Once a maze solution has been attempted, the maze is printed. If a
- // solution was found it will be shown in the maze printout and its length
- // will be returned. Note that not all mazes have solutions.
- //
- // The default maze size is 20x10, though different dimensions may be
- // specified on the command line.
- /*
- IMPORTANT:
- ~~~~~~~~~~
- 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>
- #include <boost/lexical_cast.hpp>
- #include <boost/random/mersenne_twister.hpp>
- #include <boost/random/uniform_int.hpp>
- #include <boost/random/variate_generator.hpp>
- #include <boost/unordered_map.hpp>
- #include <boost/unordered_set.hpp>
- #include <ctime>
- #include <iostream>
- boost::mt19937 random_generator;
- // Distance traveled in the maze
- 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;
- // 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;
- }
- };
- 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
- //
- // The maze is grid of locations which can either be empty or contain a
- // barrier. You can move to an adjacent location in the grid by going up,
- // down, left and right. Moving onto a barrier is not allowed. The maze can
- // be solved by finding a path from the lower-left-hand corner to the
- // upper-right-hand corner. If no open path exists between these two
- // locations, the maze is unsolvable.
- //
- // The maze is implemented as a filtered grid graph where locations are
- // vertices. Barrier vertices are filtered out of the graph.
- //
- // 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 {
- public:
- 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()) {};
- // 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();
- }
- // 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();
- }
- 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;
- };
- // 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>
- {
- public:
- 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));
- }
- private:
- vertex_descriptor m_goal;
- };
- // Exception thrown when the goal vertex is found
- 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) {};
- void examine_vertex(vertex_descriptor u, const filtered_grid&) {
- if (u == m_goal)
- throw found_goal();
- }
- private:
- 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;
- }
- #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)
- 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();
- }
- // 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--;
- }
- }
- 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;
- }
|