maker_memory.hpp

Go to the documentation of this file.

#ifndef MSMAZES_CORE_MAZE_MAKER_MEMORY_HPP
#define MSMAZES_CORE_MAZE_MAKER_MEMORY_HPP

// std::vector
#include <vector>
// std::random_shuffle
#include <algorithm>
// boost::mpl::true_ and boost::mpl::false_
#include <boost/mpl/bool.hpp>
// boost::mpl::void_
#include <boost/mpl/void.hpp>
// boost::tie
#include <boost/utility.hpp>
// boost::property_map, boost::get, and boost::put
#include <boost/property_map.hpp>
// boost::random_number_generator
#include <boost/random/random_number_generator.hpp>
// boost::graph_traits
#include <boost/graph/graph_traits.hpp>
// boost::vertex_index_t and boost::vertex_index1_t
#include <boost/graph/properties.hpp>
//#include <boost/graph/adjacency_list.hpp> must be included before this file.

namespace msmazes {


struct MemoryMazeMaker
{
    typedef boost::mpl::void_
            DefaultPolicy;

    typedef boost::mpl::true_
            RequiresRandomInputs;

    typedef boost::mpl::true_
            RestartsOnDeadEnd;

    typedef boost::mpl::false_
            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::Graph
                BaseGraph;
        typedef boost::graph_traits<BaseGraph>
                BaseGraphTraits;
        typedef typename BaseGraphTraits::vertex_descriptor
                BaseVertex;
        typedef typename BaseGraphTraits::vertices_size_type
                BaseIndex;
        typedef std::vector<BaseIndex>
                BaseIndexVector;
        typedef typename BaseIndexVector::size_type
                VectorIndex;
        typedef boost::random_number_generator<RNGEngine,VectorIndex>
                Shuffler;
        typedef typename MazeStructType::Graph
                MazeGraph;
        typedef boost::graph_traits<MazeGraph>
                MazeGraphTraits;
        typedef typename MazeGraphTraits::vertex_descriptor
                MazeVertex;

        const BaseGraph& base_graph = pattern.getGraph();

        BaseIndex
            base_index;
        BaseIndexVector
            index_vector;
        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;

        for (
            boost::tie(in_vi, in_vend) = boost::vertices(base_graph);
            in_vi != in_vend;
            ++in_vi
        )
        {
            base_index = boost::get(in_index_map, *in_vi);
            index_vector.push_back(base_index);
        }

        MazeGraph& maze_graph = maze.getGraph();
        Shuffler   shuffler(rng_engine);

        std::random_shuffle(index_vector.begin(), index_vector.end(), shuffler);
        base_index = boost::num_vertices(base_graph);
        ++base_index;
        ++base_index;

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

        typename MazeGraphTraits::vertices_size_type
            maze_vertex_count = boost::num_vertices(maze_graph);
        MazeVertex
            out_vertex = MazeGraphTraits::null_vertex();

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

        MazeVertex in_vertex = boost::vertex(0, maze_graph);

        maze.setSourceVertex(in_vertex);
        out_vertex = boost::vertex(--maze_vertex_count, maze_graph);
        maze.setTargetVertex(out_vertex);
        boost::clear_vertex(out_vertex, maze_graph);

        while (maze_vertex_count > 0)
        {
            boost::clear_vertex(
                boost::vertex(--maze_vertex_count, maze_graph)
              , maze_graph
            );
        }

        typename boost::property_map<MazeGraph,boost::vertex_index1_t>::type
            out_parent_map = boost::get(boost::vertex_index1_t(), maze_graph);
        VectorIndex
            vector_index = VectorIndex();

        boost::put(out_parent_map, out_vertex, pattern.getCellCount());
        base_index = index_vector[vector_index];
        boost::put(out_parent_map, in_vertex, base_index);
        in_vertex = boost::vertex(base_index + 1, maze_graph);
        boost::put(out_parent_map, in_vertex, base_index);
        boost::add_edge(maze.getSourceVertex(), in_vertex, maze_graph);

        while (++vector_index < index_vector.size())
        {
            base_index = index_vector[vector_index];
            out_vertex = boost::vertex(base_index + 1, maze_graph);
            boost::add_edge(in_vertex, out_vertex, maze_graph);
            boost::put(out_parent_map, out_vertex, base_index);
            in_vertex = out_vertex;
        }

        boost::add_edge(out_vertex, maze.getTargetVertex(), maze_graph);
    }
};
}  // namespace msmazes

#endif  /* MSMAZES_CORE_MAZE_MAKER_MEMORY_HPP */

---

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