graph/example/astar_maze.cpp

//          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;
}