maker_walkthrough.hpp

Go to the documentation of this file.

#ifndef MSMAZES_CORE_MAZE_MAKER_WALKTHROUGH_HPP
#define MSMAZES_CORE_MAZE_MAKER_WALKTHROUGH_HPP

// std::list
#include <list>
// std::vector
#include <vector>
// std::map
#include <map>
// std::random_shuffle
#include <algorithm>
// boost::is_same
#include <boost/type_traits/is_same.hpp>
// boost::mpl::true_ and boost::mpl::false_
#include <boost/mpl/bool.hpp>
// boost::tie
#include <boost/utility.hpp>
// boost::random_number_generator
#include <boost/random/random_number_generator.hpp>
// boost::property_map, boost::associative_property_map,
// boost::get, and boost::put
#include <boost/property_map.hpp>
// boost::graph_traits
#include <boost/graph/graph_traits.hpp>
//#include <boost/graph/adjacency_list.hpp> must be included before this file.
// msmazes::makePath and msmazes::makeRandomPaths
#include <msmazes/core/graph/path_utility.hpp>
// msmazes::removeCrossEdges
#include <msmazes/core/graph/remove_cross_edges.hpp>

namespace msmazes {

struct SimpleWalkthroughMazePolicy
{
    template <
        typename Pattern
      , typename CellIndex
    >
    static bool
        shouldAddEdge(
            const Pattern& pattern
          , const CellIndex source_index
          , const CellIndex parent_index
          , const CellIndex target_index
        )
    {
        return true;
    }
};

struct NoNegativeTurnWalkthroughMazePolicy
{
    template <
        typename Pattern
      , typename CellIndex
    >
    static bool
        shouldAddEdge(
            const Pattern& pattern
          , const CellIndex source_index
          , const CellIndex parent_index
          , const CellIndex target_index
        )
    {
        if (source_index == parent_index)
        {
            return
                pattern.getYawTurn(source_index, parent_index, target_index)
             == 0;
        }
        else
        {
            return
                pattern.getYawTurn(source_index, parent_index, target_index)
             >= 0;
        }
    }
};


struct WalkthroughMazeMaker
{
    typedef SimpleWalkthroughMazePolicy
            DefaultPolicy;

    typedef boost::mpl::false_
            RequiresRandomInputs;

    typedef boost::mpl::false_
            RestartsOnDeadEnd;

    typedef boost::mpl::true_
            BuildsLastVisitedMap;

    template <
        typename MazeStructType
      , typename Pattern
      , typename RNGEngine
      , typename MazePolicy
    >
    static void
        makeMaze(
            MazeStructType& maze
          , const Pattern& pattern
          , RNGEngine& rng_engine
          , const MazePolicy& policy
        )
    {
        typedef typename Pattern::Cell
                Cell;
        typedef typename Pattern::CellEqualityPolicy
                CellEqualityPolicy;
        typedef typename Pattern::Graph
                BaseGraph;
        typedef boost::graph_traits<BaseGraph>
                BaseGraphTraits;
        typedef typename BaseGraphTraits::vertices_size_type
                BaseIndex;
        typedef typename BaseGraphTraits::vertex_descriptor
                BaseVertex;
        typedef typename MazeStructType::Graph
                MazeGraph;
        typedef boost::graph_traits<MazeGraph>
                MazeGraphTraits;
        typedef typename MazeGraphTraits::vertices_size_type
                MazeIndex;
        typedef typename MazeGraphTraits::vertex_descriptor
                MazeVertex;
        typedef std::vector<MazeVertex>
                MazeVertexVector;
        typedef std::map<MazeVertex,MazeVertex>
                MazeVertexMap;
        typedef boost::associative_property_map<MazeVertexMap>
                PredecessorMap;
        typedef boost::random_number_generator<RNGEngine,BaseIndex>
                Shuffler;
        typedef std::list<MazeVertex>
                Path;

        const BaseGraph& base_graph = pattern.getGraph();
        MazeGraph& maze_graph = maze.getGraph();
        BaseIndex base_vertex_count = boost::num_vertices(base_graph);
        BaseVertex source = BaseGraphTraits::null_vertex();
        BaseVertex target = BaseGraphTraits::null_vertex();
        Shuffler shuffler(rng_engine);
        typename Path::size_type min_path_length = base_vertex_count >> 1;

        maze.setSourceVertex(MazeGraphTraits::null_vertex());
        maze.setTargetVertex(MazeGraphTraits::null_vertex());

        if (
            boost::is_same<
                MazePolicy
              , NoNegativeTurnWalkthroughMazePolicy
            >::value
        )
        {
            ++min_path_length;
        }
        else
        {
            min_path_length += base_vertex_count;
        }

        const Cell& src_cell = pattern.getSourceCell();
        const Cell& tgt_cell = pattern.getTargetCell();

        MazeIndex
            maze_vertex_count = 3;
        typename boost::property_map<BaseGraph,boost::vertex_index_t>::type
            in_index_map = boost::get(boost::vertex_index_t(), base_graph);
        typename BaseGraphTraits::vertex_iterator
            in_vi, in_vend;
        CellEqualityPolicy
            are_equal_cells;

        for (
            boost::tie(in_vi, in_vend) = boost::vertices(base_graph);
            in_vi != in_vend;
            ++in_vi
        )
        {
            const Cell&
                cell = pattern.getCell(boost::get(in_index_map, *in_vi));

            if (are_equal_cells(cell, src_cell))
            {
                source = *in_vi;
            }

            if (are_equal_cells(cell, tgt_cell))
            {
                target = *in_vi;
            }

            maze_vertex_count += boost::out_degree(*in_vi, base_graph);
        }

        while (boost::num_vertices(maze_graph) < maze_vertex_count)
        {
            boost::add_vertex(maze_graph);
        }

        MazeIndex
            vertex_count = boost::num_vertices(maze_graph);
        MazeVertex
            out_vertex = MazeGraphTraits::null_vertex();

        while (vertex_count > maze_vertex_count)
        {
            out_vertex = boost::vertex(--vertex_count, maze_graph);
            boost::clear_vertex(out_vertex, maze_graph);
            boost::remove_vertex(out_vertex, maze_graph);
        }

        typename boost::property_map<MazeGraph,boost::vertex_index1_t>::type
            out_parent_map = boost::get(boost::vertex_index1_t(), maze_graph);
        typename boost::property_map<MazeGraph,boost::vertex_index2_t>::type
            out_source_map = boost::get(boost::vertex_index2_t(), maze_graph);
        typename MazeGraphTraits::vertex_iterator
            out_vi, out_vend;

        boost::tie(out_vi, out_vend) = boost::vertices(maze_graph);
        maze.setSourceVertex(*out_vi);
        boost::clear_vertex(*out_vi, maze_graph);

        const MazeVertex true_source = *(++out_vi);
        BaseIndex source_index = boost::get(in_index_map, source);

        boost::clear_vertex(true_source, maze_graph);
        boost::put(out_parent_map, true_source, source_index);
        boost::put(out_source_map, true_source, source_index);
        boost::put(out_parent_map, maze.getSourceVertex(), source_index);
        boost::put(out_source_map, maze.getSourceVertex(), source_index);
        boost::add_edge(maze.getSourceVertex(), true_source, maze_graph);

        std::vector<MazeVertexVector> vertex_vector(base_vertex_count);
        BaseVertex parent_vertex = BaseGraphTraits::null_vertex();
        BaseIndex parent_index;
        typename BaseGraphTraits::adjacency_iterator in_ai, in_aend;

        for (
            boost::tie(in_vi, in_vend) = boost::vertices(base_graph);
            in_vi != in_vend;
            ++in_vi
        )
        {
            parent_vertex = *in_vi;
            parent_index  = boost::get(in_index_map, parent_vertex);

            for (
                boost::tie(in_ai, in_aend)
                  = boost::adjacent_vertices(parent_vertex, base_graph);
                in_ai != in_aend;
                ++in_ai
            )
            {
                out_vertex = *(++out_vi);
                boost::clear_vertex(out_vertex, maze_graph);
                source_index = boost::get(in_index_map, *in_ai);
                boost::put(out_parent_map, out_vertex, parent_index);
                boost::put(out_source_map, out_vertex, source_index);
                vertex_vector[source_index].push_back(out_vertex);
            }
        }

        maze.setTargetVertex(*(++out_vi));
        source_index = boost::get(in_index_map, target);
        vertex_vector[source_index].push_back(*out_vi);
        boost::clear_vertex(*out_vi, maze_graph);
        boost::put(out_parent_map, *out_vi, base_vertex_count);
        boost::put(out_source_map, *out_vi, source_index);

        MazeVertex                          in_vertex;
        BaseIndex                           target_index;
        typename MazeVertexVector::iterator child_i, child_end;

        for (
            boost::tie(out_vi, out_vend) = boost::vertices(maze_graph);
            out_vi != out_vend;
            ++out_vi
        )
        {
            in_vertex = *out_vi;

            if (
                (in_vertex != maze.getSourceVertex())
             && (in_vertex != maze.getTargetVertex())
            )
            {
                parent_index = boost::get(out_parent_map, in_vertex);
                source_index = boost::get(out_source_map, in_vertex);

                MazeVertexVector& v_vector = vertex_vector[parent_index];

                std::random_shuffle(v_vector.begin(), v_vector.end(), shuffler);
                child_end = v_vector.end();

                for (
                    child_i = v_vector.begin();
                    child_i != child_end;
                    ++child_i
                )
                {
                    out_vertex   = *child_i;
                    target_index = boost::get(out_parent_map, out_vertex);

                    if (
                        (target_index != source_index)
                     && MazePolicy::shouldAddEdge(
                            pattern
                          , source_index
                          , parent_index
                          , target_index
                        )
                    )
                    {
                        boost::add_edge(in_vertex, out_vertex, maze_graph);
                    }
                }
            }
        }

        MazeVertexMap  v_map;
        PredecessorMap p_map(v_map);
        Path           path;

        while (path.empty())
        {
            makeRandomPaths(
                input_graph_arg = maze_graph
              , source_vertex_arg = true_source
              , shuffler_arg = shuffler
              , output_predecessor_map_arg = p_map
            );

            if (
                !makePath(
                    true_source
                  , maze.getTargetVertex()
                  , p_map
                  , path
                )
             || (path.size() < min_path_length)
            )
            {
                path.clear();
            }
        }

        removeCrossEdges(
            path_begin_arg = path.begin()
          , path_end_arg = path.end()
          , input_graph_arg = maze_graph
        );
    }
};
}  // namespace msmazes

#endif  /* MSMAZES_CORE_MAZE_MAKER_WALKTHROUGH_HPP */

---

Multi-State Mazes in C++ is hosted by . Use the Table of Contents for navigation.