| |
| // 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. |
| |
| |
| #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:std::unary_function<vertex_descriptor, std::size_t> { |
| 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 maze random_maze(std::size_t, std::size_t); |
| |
| 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 underlying maze grid with barrier vertices filtered out |
| filtered_grid m_barrier_grid; |
| // The barriers in the maze |
| vertex_set m_barriers; |
| // 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(m_goal[0] - v[0], 2) + pow(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, 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. |
| maze random_maze(std::size_t x, std::size_t y) { |
| maze m(x, y); |
| 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; |
| } |
| } |
| return m; |
| } |
| |
| |
| 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 = random_maze(x, y); |
| |
| 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; |
| } |