builder.hpp

Go to the documentation of this file.

#ifndef MSMAZES_CORE_FSM_BUILDER_HPP
#define MSMAZES_CORE_FSM_BUILDER_HPP

// std::map
#include <map>
// std::random_shuffle
#include <algorithm>
// std::pair and std::make_pair
#include <utility>
// boost::function_requires and basic concept check templates
#include <boost/concept_check.hpp>
// boost::tie
#include <boost/utility.hpp>
// boost::is_same
#include <boost/type_traits/is_same.hpp>
// boost::mpl::true_ and boost::mpl::false_
#include <boost/mpl/bool.hpp>
// boost::random_number_generator
#include <boost/random/random_number_generator.hpp>
// boost::queue
#include <boost/pending/queue.hpp>
// boost::property_map, boost::associative_property_map,
// boost::make_iterator_property_map, and boost::get
#include <boost/property_map.hpp>
// boost::graph_traits
#include <boost/graph/graph_traits.hpp>
// boost::vertex_index_t
#include <boost/graph/properties.hpp>
// boost::predecessor_recorder and boost::null_visitor
#include <boost/graph/visitors.hpp>
// boost::breadth_first_visit, boost::bfs_visitor, and boost::make_bfs_visitor
#include <boost/graph/breadth_first_search.hpp>
// boost::make_reverse_graph
#include <boost/graph/reverse_graph.hpp>
// msmazes::MazeStruct
#include <msmazes/core/maze/struct.hpp>
// msmazes::MazeMakerTraits
#include <msmazes/core/maze/traits_maker.hpp>
// msmazes::FSMInputMakerTraits
#include <msmazes/core/fsm/input/traits_maker.hpp>
// msmazes::FSMNoInputMaker
#include <msmazes/core/fsm/input/maker_no.hpp>

namespace msmazes {


struct DefaultArgumentValidationPolicy
{
    template <
        typename MazeMaker
      , typename FSMInputMaker
      , typename MazePolicy
      , typename ArgumentPack
    >
    static bool
        areValidArguments(
            const MazeMaker& maze_maker
          , const FSMInputMaker& input_maker
          , const MazePolicy& policy
          , const ArgumentPack& p
        )
    {
        return true;
    }
};


template <
#ifndef MSMAZES_DOX
    typename PatternType
  , typename ArgumentValidationPolicyType = DefaultArgumentValidationPolicy
#endif  /* MSMAZES_DOX */
>
class FSMBuilder
{
 public:
#ifdef MSMAZES_DOX
    typedef implementation_defined ArgumentValidationPolicy;
#else
    typedef ArgumentValidationPolicyType
            ArgumentValidationPolicy;
#endif  /* MSMAZES_DOX */

#ifdef MSMAZES_DOX
    typedef implementation_defined Pattern;
#else
    typedef PatternType
            Pattern;
#endif  /* MSMAZES_DOX */

#ifdef MSMAZES_DOX
    typedef implementation_defined Cell;
#else
    typedef typename Pattern::Cell
            Cell;
#endif  /* MSMAZES_DOX */

#ifdef MSMAZES_DOX
    typedef implementation_defined Direction;
#else
    typedef typename Pattern::Direction
            Direction;
#endif  /* MSMAZES_DOX */

 private:
    typedef typename Pattern::CellIndex
            CellIndex;

 protected:
#ifdef MSMAZES_DOX
    typedef implementation_defined MazeStructType;
#else
    typedef MazeStruct<CellIndex>
            MazeStructType;
#endif  /* MSMAZES_DOX */

 public:
#ifdef MSMAZES_DOX
    typedef unspecified MazeGraph;
#else
    typedef typename MazeStructType::Graph
            MazeGraph;
#endif  /* MSMAZES_DOX */

#ifdef MSMAZES_DOX
    typedef unspecified InputIndex;
#else
    typedef typename MazeStructType::EdgeIndex
            InputIndex;
#endif  /* MSMAZES_DOX */

 private:
    typedef boost::graph_traits<MazeGraph>
            MazeGraphTraits;
    typedef typename MazeStructType::Vertex
            MazeVertex;
    typedef typename MazeGraphTraits::vertex_iterator
            MazeVertexIterator;
    typedef typename MazeGraphTraits::out_edge_iterator
            MazeOutEdgeIterator;
    typedef std::map<MazeVertex,MazeVertex>
            MazeVertexMap;
    typedef boost::associative_property_map<MazeVertexMap>
            PredecessorMap;

 public:
#ifdef MSMAZES_DOX
    typedef unspecified StateIndex;
#else
    typedef typename MazeGraphTraits::vertices_size_type
            StateIndex;
#endif  /* MSMAZES_DOX */

 private:
    Pattern                  _pattern;
    bool                     _is_ready;
    bool                     _restarts_on_dead_end;
    MazeStructType           _maze;
    boost::queue<MazeVertex> _queue;
    MazeVertexMap            _v_map;
    PredecessorMap           _successor_map;

    FSMBuilder(const FSMBuilder& copy)
    {
    }

 public:

    FSMBuilder()
      : _pattern()
      , _is_ready(false)
      , _restarts_on_dead_end(false)
      , _maze()
      , _queue()
      , _v_map()
      , _successor_map(_v_map)
    {
    }


    virtual ~FSMBuilder()
    {
    }

 private:
    template <
        typename RNGEngine
      , typename FSMInputMaker
    >
    void _makeMazeInputs(
        RNGEngine& rng_engine
      , const FSMInputMaker& input_maker
      , boost::mpl::false_
    )
    {
        MazeGraph&
            maze_graph = _maze.getGraph();
        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 boost::property_map<MazeGraph,boost::edge_index_t>::type
            edge_index_map = boost::get(boost::edge_index_t(), maze_graph);
        MazeVertexIterator
            vi, vi_end;
        MazeOutEdgeIterator
            ei, ei_end;
        InputIndex
            input;
        MazeVertex
            edge_target;

        for (
            boost::tie(vi, vi_end) = boost::vertices(maze_graph);
            vi != vi_end;
            ++vi
        )
        {
            boost::put(_successor_map, *vi, *vi);
            input = InputIndex();

            for (
                boost::tie(ei, ei_end) = boost::out_edges(*vi, maze_graph);
                ei != ei_end;
                ++ei
            )
            {
                edge_target = boost::target(*ei, maze_graph);
                boost::put(
                    edge_index_map
                  , *ei
                  , (
                        boost::is_same<FSMInputMaker,FSMNoInputMaker>::value
                      ? input
                      : (*vi == _maze.getSourceVertex())
                      ? FSMInputMaker::getInput(
                            _pattern
                          , boost::get(out_source_map, edge_target)
                          , boost::get(out_parent_map, edge_target)
                          , boost::get(out_parent_map, edge_target)
                        )
                      : FSMInputMaker::getInput(
                            _pattern
                          , boost::get(out_source_map, *vi)
                          , boost::get(out_parent_map, *vi)
                          , boost::get(out_parent_map, edge_target)
                        )
                    )
                );
                ++input;
            }
        }
    }

    template <
        typename RNGEngine
      , typename FSMInputMaker
    >
    void _makeMazeInputs(
        RNGEngine& rng_engine
      , const FSMInputMaker& input_maker
      , boost::mpl::true_
    )
    {
        typedef boost::random_number_generator<RNGEngine,InputIndex>
                Shuffler;
        typedef std::vector<InputIndex>
                InputVector;

        InputVector input_vector;

        for (
            InputIndex input = InputIndex();
            input < _maze.getMaxOutDegree();
            ++input
        )
        {
            input_vector.push_back(input);
        }

        MazeGraph&
            maze_graph = _maze.getGraph();
        typename boost::property_map<MazeGraph,boost::edge_index_t>::type
            edge_index_map = boost::get(boost::edge_index_t(), maze_graph);
        MazeVertexIterator
            vi, vi_end;
        MazeOutEdgeIterator
            ei, ei_end;
        typename InputVector::size_type
            index;
        Shuffler
            shuffler(rng_engine);

        for (
            boost::tie(vi, vi_end) = boost::vertices(maze_graph);
            vi != vi_end;
            ++vi
        )
        {
            boost::put(_successor_map, *vi, *vi);
            std::random_shuffle(
                input_vector.begin()
              , input_vector.end()
              , shuffler
            );
            index = typename InputVector::size_type();

            for (
                boost::tie(ei, ei_end) = boost::out_edges(*vi, maze_graph);
                ei != ei_end;
                ++ei
            )
            {
                boost::put(edge_index_map, *ei, input_vector[index]);
                ++index;
            }
        }
    }

    void _makeSolutionMap()
    {
        typedef boost::predecessor_recorder<PredecessorMap,boost::on_tree_edge>
                PredVisitor;
        typedef boost::bfs_visitor<std::pair<PredVisitor,boost::null_visitor> >
                BFSVisitor;

        MazeGraph&
            maze_graph = _maze.getGraph();
        PredVisitor
            pred_vis(_successor_map);
        boost::null_visitor
            null_vis;
        BFSVisitor
            bfs_vis
              = boost::make_bfs_visitor(std::make_pair(pred_vis, null_vis));

        boost::breadth_first_visit(
            boost::make_reverse_graph(maze_graph)
          , _maze.getTargetVertex()
          , _queue
          , bfs_vis
          , boost::make_iterator_property_map(
                std::vector<boost::default_color_type>(
                    boost::num_vertices(maze_graph)
                ).begin()
              , boost::get(boost::vertex_index_t(), maze_graph)
              , boost::white_color
            )
        );
    }

 protected:
    template <
        typename RNGEngine
      , typename MazeMaker
      , typename FSMInputMaker
      , typename MazePolicy
      , typename ArgumentPack
    >
    bool
        initialize(
            RNGEngine& rng_engine
          , const MazeMaker& maze_maker
          , const FSMInputMaker& input_maker
          , const MazePolicy& policy
          , const ArgumentPack& p
        )
    {
        typedef typename MazeMakerTraits<MazeMaker>::RequiresRandomInputs
                MazeMakerRequiresRandomInputs;
        typedef typename MazeMakerTraits<MazeMaker>::RestartsOnDeadEnd
                MazeMakerRestartsOnDeadEnd;
        typedef typename MazeMakerTraits<MazeMaker>::BuildsLastVisitedMap
                MazeMakerBuildsLastVisitedMap;
        typedef typename FSMInputMakerTraits<
                    FSMInputMaker
                >::RequiresLastVisitedMap
                FSMInputMakerRequiresLastVisitedMap;

        BOOST_STATIC_ASSERT(
            MazeMakerBuildsLastVisitedMap::value
         || !FSMInputMakerRequiresLastVisitedMap::value
        );

        if (
            ArgumentValidationPolicy::areValidArguments(
                maze_maker
              , input_maker
              , policy
              , p
            )
        )
        {
            _is_ready = false;
            _pattern.initialize_with_named_params(p);
            MazeMaker::makeMaze(_maze, _pattern, rng_engine, policy);
            _maze.setMaxOutDegree(
                boost::is_same<FSMInputMaker,FSMNoInputMaker>::value
              ? typename MazeStructType::EdgeIndex()
              : FSMInputMaker::getInputCount(_pattern)
            );
            _restarts_on_dead_end = MazeMakerRestartsOnDeadEnd::value;
            _makeMazeInputs(
                rng_engine
              , input_maker
              , MazeMakerRequiresRandomInputs()
            );
            _makeSolutionMap();
            _is_ready = true;

            return true;
        }
        else
        {
            return false;
        }
    }

    inline const MazeStructType& getMazeStruct() const
    {
        return _maze;
    }

 public:
    inline const Pattern& getPattern() const
    {
        return _pattern;
    }

    inline const MazeGraph& getMazeGraph() const
    {
        return _maze.getGraph();
    }

    inline bool isReady() const
    {
        return _is_ready;
    }

    template <
        typename TransitionFunction
    >
    void
        buildTransitionFunction(
            TransitionFunction& transition_function
        ) const
    {
        if (isReady())
        {
            const MazeGraph& g           = getMazeGraph();
            const InputIndex input_count = _maze.getMaxOutDegree();

            transition_function.resize(boost::num_vertices(g), input_count);

            typename
              boost::property_map<MazeGraph,boost::vertex_index_t>::const_type
                out_index_map
                  = boost::get(boost::vertex_index_t(), g);
            typename
              boost::property_map<MazeGraph,boost::edge_index_t>::const_type
                edge_index_map
                  = boost::get(boost::edge_index_t(), g);
            const MazeVertex target = _maze.getTargetVertex();

            MazeVertexIterator  vi, vi_end;
            MazeOutEdgeIterator ei, ei_end;
            StateIndex          state;

            for (
                boost::tie(vi, vi_end) = boost::vertices(g);
                vi != vi_end;
                ++vi
            )
            {
                if (*vi != target)
                {
                    state = boost::get(out_index_map, *vi);

                    for (
                        boost::tie(ei, ei_end) = boost::out_edges(*vi, g);
                        ei != ei_end;
                        ++ei
                    )
                    {
                        transition_function.setTransition(
                            state
                          , boost::get(edge_index_map, *ei)
                          , boost::get(out_index_map, boost::target(*ei, g))
                        );
                    }

                    if (_restarts_on_dead_end)
                    {
                        for (
                            InputIndex input = InputIndex();
                            input < input_count;
                            ++input
                        )
                        {
                            if (transition_function(state, input) == state)
                            {
                                transition_function.setTransition(
                                    state
                                  , input
                                  , boost::get(
                                        out_index_map
                                      , _maze.getSourceVertex()
                                    )
                                );
                            }
                        }
                    }
                }
            }
        }
    }

    inline StateIndex getSourceState() const
    {
        return
            isReady()
          ? boost::get(
                boost::get(boost::vertex_index_t(), _maze.getGraph())
              , _maze.getSourceVertex()
            )
          : StateIndex();
    }

    inline StateIndex getTargetState() const
    {
        return
            isReady()
          ? boost::get(
                boost::get(boost::vertex_index_t(), _maze.getGraph())
              , _maze.getTargetVertex()
            )
          : StateIndex();
    }

    bool hasSolutionFromState(const StateIndex source_state) const
    {
        const MazeGraph& maze_graph = getMazeGraph();

        MazeVertex u = boost::vertex(source_state, maze_graph);

        while (u != boost::get(_successor_map, u))
        {
            u = boost::get(_successor_map, u);
        }

        return u == _maze.getTargetVertex();
    }

    InputIndex getCorrectInput(const StateIndex source_state) const
    {
        const MazeGraph& maze_graph = getMazeGraph();
        const MazeVertex u = boost::vertex(source_state, maze_graph);
        const MazeVertex v = boost::get(_successor_map, u);

        typename boost::property_map<MazeGraph,boost::edge_index_t>::const_type
            edge_index_map = boost::get(boost::edge_index_t(), maze_graph);

        MazeOutEdgeIterator ei, ei_end;

        for (
            boost::tie(ei, ei_end) = boost::out_edges(u, maze_graph);
            ei != ei_end;
            ++ei
        )
        {
            if (boost::target(*ei, maze_graph) == v)
            {
                return boost::get(edge_index_map, *ei);
            }
        }

        return _maze.getMaxOutDegree();
    }

    const Cell& getStateCell(const StateIndex state) const
    {
        const MazeGraph& maze_graph = getMazeGraph();
        const MazeVertex v          = boost::vertex(state, maze_graph);

        return
            (v == _maze.getSourceVertex())
          ? _pattern.getEntranceCell()
          : (v == _maze.getTargetVertex())
          ? _pattern.getExitCell()
          : _pattern.getCell(
                boost::get(boost::get(boost::vertex_index1_t(), maze_graph), v)
            );
    }

    Direction getStateDirection(const StateIndex state) const
    {
        const MazeGraph& maze_graph = getMazeGraph();
        const MazeVertex v          = boost::vertex(state, maze_graph);

        return
            _pattern.getEdgeDirection(
                boost::get(boost::get(boost::vertex_index2_t(), maze_graph), v)
              , boost::get(boost::get(boost::vertex_index1_t(), maze_graph), v)
            );
    }
};
}  // namespace msmazes

#endif  /* MSMAZES_CORE_FSM_BUILDER_HPP */

---

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