00001 00027 #ifndef MSMAZES_CORE_MAZE_MAKER_STANDARD_HPP 00028 #define MSMAZES_CORE_MAZE_MAKER_STANDARD_HPP 00029 00030 // std::vector 00031 #include <vector> 00032 // std::back_inserter 00033 #include <iterator> 00034 // boost::mpl::true_ and boost::mpl::false_ 00035 #include <boost/mpl/bool.hpp> 00036 // boost::mpl::void_ 00037 #include <boost/mpl/void.hpp> 00038 // boost::tie 00039 #include <boost/utility.hpp> 00040 // boost::property_map, boost::get, and boost::put 00041 #include <boost/property_map.hpp> 00042 // boost::uniform_int 00043 #include <boost/random/uniform_int.hpp> 00044 // boost::variate_generator 00045 #include <boost/random/variate_generator.hpp> 00046 // boost::graph_traits 00047 #include <boost/graph/graph_traits.hpp> 00048 // boost::vecS, boost::listS, and boost::undirectedS 00049 #include <boost/graph/graph_selectors.hpp> 00050 // boost::property, boost::no_property, boost::vertex_index1_t, 00051 // boost::vertex_index2_t, and boost::edge_weight_t 00052 #include <boost/graph/properties.hpp> 00053 // boost::null_visitor 00054 #include <boost/graph/visitors.hpp> 00055 // boost::adjacency_list 00056 #include <boost/graph/adjacency_list.hpp> 00057 // boost::copy_graph 00058 #include <boost/graph/copy.hpp> 00059 // boost::kruskal_minimum_spanning_tree 00060 #include <boost/graph/kruskal_min_spanning_tree.hpp> 00061 // boost::randomize_property 00062 #include <boost/graph/random.hpp> 00063 00064 namespace msmazes { 00065 00067 00088 struct StandardMazeMaker 00089 { 00093 typedef boost::mpl::void_ 00094 DefaultPolicy; 00095 00099 typedef boost::mpl::false_ 00100 RequiresRandomInputs; 00101 00106 typedef boost::mpl::false_ 00107 RestartsOnDeadEnd; 00108 00113 typedef boost::mpl::true_ 00114 BuildsLastVisitedMap; 00115 00121 template < 00122 typename MazeStructType 00123 , typename Pattern 00124 , typename RNGEngine 00125 , typename MazePolicy 00126 > 00127 static void 00128 makeMaze( 00129 MazeStructType& maze 00130 , const Pattern& pattern 00131 , RNGEngine& rng_engine 00132 , const MazePolicy& policy 00133 ) 00134 { 00135 typedef typename Pattern::Cell 00136 Cell; 00137 typedef typename Pattern::CellEqualityPolicy 00138 CellEqualityPolicy; 00139 typedef typename Pattern::Graph 00140 BaseGraph; 00141 typedef boost::graph_traits<BaseGraph> 00142 BaseGraphTraits; 00143 typedef typename BaseGraphTraits::vertices_size_type 00144 BaseIndex; 00145 typedef typename BaseGraphTraits::vertex_descriptor 00146 BaseVertex; 00147 typedef boost::adjacency_list< 00148 boost::listS 00149 , boost::vecS 00150 , boost::undirectedS 00151 , boost::no_property 00152 , boost::property<boost::edge_weight_t,unsigned int> 00153 , boost::no_property 00154 > 00155 UtilGraph; 00156 typedef boost::graph_traits<UtilGraph> 00157 UtilGraphTraits; 00158 typedef typename UtilGraphTraits::vertices_size_type 00159 UtilIndex; 00160 typedef typename UtilGraphTraits::vertex_descriptor 00161 UtilVertex; 00162 typedef typename UtilGraphTraits::edge_descriptor 00163 UtilEdge; 00164 typedef std::vector<UtilEdge> 00165 SpanningTree; 00166 typedef typename MazeStructType::Graph 00167 MazeGraph; 00168 typedef boost::graph_traits<MazeGraph> 00169 MazeGraphTraits; 00170 typedef typename MazeGraphTraits::vertices_size_type 00171 MazeIndex; 00172 typedef typename MazeGraphTraits::vertex_descriptor 00173 MazeVertex; 00174 typedef std::vector<MazeVertex> 00175 MazeVertexVector; 00176 typedef boost::uniform_int<unsigned int> 00177 RNGDistribution; 00178 typedef boost::variate_generator<RNGEngine&,RNGDistribution> 00179 RandomWeightGenerator; 00180 00181 const BaseGraph& base_graph = pattern.getGraph(); 00182 const Cell& src_cell = pattern.getSourceCell(); 00183 const Cell& tgt_cell = pattern.getTargetCell(); 00184 00185 UtilGraph util_graph; 00186 boost::null_visitor null_vis; 00187 00188 boost::copy_graph( 00189 base_graph 00190 , util_graph 00191 , boost::vertex_copy(null_vis).edge_copy(null_vis) 00192 ); 00193 00194 RNGDistribution rng_distribution(0, 16383); 00195 RandomWeightGenerator random_weight(rng_engine, rng_distribution); 00196 00197 boost::randomize_property<boost::edge_weight_t>( 00198 util_graph 00199 , random_weight 00200 ); 00201 00202 SpanningTree spanning_tree; 00203 00204 boost::kruskal_minimum_spanning_tree( 00205 util_graph 00206 , std::back_inserter(spanning_tree) 00207 ); 00208 00209 const MazeIndex maze_vertex_count = (spanning_tree.size() << 1) + 3; 00210 00211 MazeGraph& 00212 maze_graph = maze.getGraph(); 00213 UtilVertex 00214 source = UtilGraphTraits::null_vertex(); 00215 UtilVertex 00216 target = UtilGraphTraits::null_vertex(); 00217 typename boost::property_map<UtilGraph,boost::vertex_index_t>::type 00218 u_index_map = boost::get(boost::vertex_index_t(), util_graph); 00219 typename UtilGraphTraits::vertex_iterator 00220 u_vi, u_vend; 00221 CellEqualityPolicy 00222 are_equal_cells; 00223 00224 for ( 00225 boost::tie(u_vi, u_vend) = boost::vertices(util_graph); 00226 u_vi != u_vend; 00227 ++u_vi 00228 ) 00229 { 00230 const Cell& 00231 cell = pattern.getCell(boost::get(u_index_map, *u_vi)); 00232 00233 if (are_equal_cells(cell, src_cell)) 00234 { 00235 source = *u_vi; 00236 } 00237 00238 if (are_equal_cells(cell, tgt_cell)) 00239 { 00240 target = *u_vi; 00241 } 00242 } 00243 00244 while (boost::num_vertices(maze_graph) < maze_vertex_count) 00245 { 00246 boost::add_vertex(maze_graph); 00247 } 00248 00249 MazeIndex 00250 vertex_count = boost::num_vertices(maze_graph); 00251 MazeVertex 00252 out_vertex = MazeGraphTraits::null_vertex(); 00253 00254 while (vertex_count > maze_vertex_count) 00255 { 00256 out_vertex = boost::vertex(--vertex_count, maze_graph); 00257 boost::clear_vertex(out_vertex, maze_graph); 00258 boost::remove_vertex(out_vertex, maze_graph); 00259 } 00260 00261 typename boost::property_map<MazeGraph,boost::vertex_index1_t>::type 00262 out_parent_map = boost::get(boost::vertex_index1_t(), maze_graph); 00263 typename boost::property_map<MazeGraph,boost::vertex_index2_t>::type 00264 out_source_map = boost::get(boost::vertex_index2_t(), maze_graph); 00265 typename MazeGraphTraits::vertex_iterator 00266 out_vi, out_vend; 00267 00268 boost::tie(out_vi, out_vend) = boost::vertices(maze_graph); 00269 maze.setSourceVertex(*out_vi); 00270 boost::clear_vertex(*out_vi, maze_graph); 00271 00272 const MazeVertex 00273 true_source = *(++out_vi); 00274 UtilIndex 00275 source_index = boost::get(u_index_map, source); 00276 00277 boost::clear_vertex(true_source, maze_graph); 00278 boost::put(out_parent_map, true_source, source_index); 00279 boost::put(out_source_map, true_source, source_index); 00280 boost::put(out_parent_map, maze.getSourceVertex(), source_index); 00281 boost::put(out_source_map, maze.getSourceVertex(), source_index); 00282 boost::add_edge(maze.getSourceVertex(), true_source, maze_graph); 00283 00284 const UtilIndex 00285 util_vertex_count = boost::num_vertices(util_graph); 00286 std::vector<MazeVertexVector> 00287 vertex_vector(util_vertex_count); 00288 UtilVertex 00289 parent = UtilGraphTraits::null_vertex(); 00290 UtilIndex 00291 parent_index; 00292 typename SpanningTree::iterator 00293 eend = spanning_tree.end(); 00294 00295 for ( 00296 typename SpanningTree::iterator ei = spanning_tree.begin(); 00297 ei != eend; 00298 ++ei 00299 ) 00300 { 00301 source = boost::source(*ei, util_graph); 00302 source_index = boost::get(u_index_map, source); 00303 parent = boost::target(*ei, util_graph); 00304 parent_index = boost::get(u_index_map, parent); 00305 00306 out_vertex = *(++out_vi); 00307 boost::clear_vertex(out_vertex, maze_graph); 00308 boost::put(out_parent_map, out_vertex, parent_index); 00309 boost::put(out_source_map, out_vertex, source_index); 00310 vertex_vector[source_index].push_back(out_vertex); 00311 00312 out_vertex = *(++out_vi); 00313 boost::clear_vertex(out_vertex, maze_graph); 00314 boost::put(out_parent_map, out_vertex, source_index); 00315 boost::put(out_source_map, out_vertex, parent_index); 00316 vertex_vector[parent_index].push_back(out_vertex); 00317 } 00318 00319 maze.setTargetVertex(*(++out_vi)); 00320 source_index = boost::get(u_index_map, target); 00321 vertex_vector[source_index].push_back(*out_vi); 00322 boost::clear_vertex(*out_vi, maze_graph); 00323 boost::put(out_parent_map, *out_vi, util_vertex_count); 00324 boost::put(out_source_map, *out_vi, source_index); 00325 00326 typename MazeVertexVector::iterator 00327 child_i, child_end; 00328 00329 for ( 00330 boost::tie(out_vi, out_vend) = boost::vertices(maze_graph); 00331 out_vi != out_vend; 00332 ++out_vi 00333 ) 00334 { 00335 out_vertex = *out_vi; 00336 00337 if ( 00338 (out_vertex != maze.getSourceVertex()) 00339 && (out_vertex != maze.getTargetVertex()) 00340 ) 00341 { 00342 MazeVertexVector& 00343 v_vector = vertex_vector[ 00344 boost::get(out_parent_map, out_vertex) 00345 ]; 00346 00347 child_end = v_vector.end(); 00348 00349 for ( 00350 child_i = v_vector.begin(); 00351 child_i != child_end; 00352 ++child_i 00353 ) 00354 { 00355 boost::add_edge(out_vertex, *child_i, maze_graph); 00356 } 00357 } 00358 } 00359 } 00360 }; 00361 } // namespace msmazes 00362 00363 #endif /* MSMAZES_CORE_MAZE_MAKER_STANDARD_HPP */
Multi-State Mazes in C++ is hosted by . Use the Table of Contents for navigation.