<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="http://www.r-bloggers.com/networks-mazes-and-r-rmaze/"></div></div><div><a data-url="http://www.r-bloggers.com/networks-mazes-and-r-rmaze/" data-counturl="http://www.r-bloggers.com/networks-mazes-and-r-rmaze/" data-count="horizontal" data-text="Networks, mazes, and R (Rmaze)" class="twitter-share-button" data-via="rbloggers" href="https://twitter.com/share"></a></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://www.vesnam.com/Rblog/mazes-graphs-and-r/"> Fun with R</a></strong>, and kindly contributed to <a rel="nofollow" href="http://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Like many people who work with networks (aka graphs), I like to emphasize their usability and applicability to different problems. If some phenomena can be described by its objects and relationships among those objects – well, hello networks. One of the problems that can be addressed with networks is a maze generator problem, where the maze cells represent objects and the relationships among those objects can be defined as “a path” or “a wall.” Thus, we can model maze cells as network nodes and their relationship as network edges, where “a path” means an edge between two nodes and “a wall” means no direct connection, i.e., no edge. There are already a number of maze generating algorithms that rely on graph theoretical techniques, i.e., the recursive backtracker algorithm that represents a modified version of depth first search, and modified versions of Kruskal’s and Prim’s spanning tree algorithms adjusted for creating mazes.</p>
<p>I did not work on maze generating problem before, but I was wondering how easy it is to implement a maze generator, especially given a decent number of options for network analysis provided in the <a target="_blank" href="https://cran.r-project.org/web/packages/igraph/index.html">igraph</a> package. Turns out, pretty simple and straight forward. I will go over some of the steps here, but for the complete code (three methods mentioned above, maze plotting, and maze randomization) and details see the my <a target="_blank" href="https://github.com/Vessy/Rmaze">Rmaze</a> GitHub page, the <a target="_blank" href="https://github.com/Vessy/Rmaze/blob/master/vignettes/tutorial.Rmd">Rmaze package vignette</a>, and help files. </p>
<p>To install and test the package, run:<code><br>
devtools::install_github(&quot;Vessy/Rmaze&quot;)<br>
library(&quot;Rmaze&quot;)<br>
</code></p>
<p>Alternatively, you can run a Shiny app showcasing the basic <a target="_blank" href="https://github.com/Vessy/Rmaze">Rmaze</a> features as:<code><br>
Rmaze::runExample()<br>
</code></p>
<p>To create a maze representation in the form of a network, we first have to create a grid network that will represent maze cells and all walls or paths among those cells. For this initial step, we will create a maze with all walls on. Basically, we want to create a structure like this:</p>
<div class="wp-caption"><a target="_blank" href="http://www.vesnam.com/Rblog/grid/"><img sizes="(max-width: 300px) 100vw, 300px" srcset="http://i1.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/grid-300x288.jpg?resize=300%2C288 300w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/grid.jpg 515w" alt="Maze grid" class="wp-image-366" src="http://i1.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/grid-300x288.jpg?resize=300%2C288" data-recalc-dims="1"></a>
<p class="wp-caption-text">Maze grid</p>
</div>
<p>This structure can be represented as a graph, that can be represented as a list of edges. We will assume that such edge list is stored a data frame called df_hlp. We can use this data frame to created a graph: <code><br>
 gD &lt;- igraph::simplify(igraph::graph.data.frame(df_hlp, directed=FALSE))
 </code></p>
<p>Next, will set up some edge and node attributes. For each edge, we will define an attribute called <em>wall</em>, that can be either ON or OFF. Initially all walls will be ON: <code><br>
 gD &lt;- igraph::set_edge_attr(gD , &quot;wall&quot;, value = &quot;ON&quot;)
 </code></p>
<p>For nodes, we will define an attribute called <em>visited</em>, that will be used later to keep track of which cells have been evaluated for the creation of the maze: <code><br>
gD &lt;- igraph::set_vertex_attr(gD , &quot;visited&quot;, value = 0) </code></p>
<p>These commands are a part of the <a target="_blank" href="https://github.com/Vessy/Rmaze/blob/master/R/makeGraph.R">makeGraph.R</a> function. We can run this command and create and plot a maze of size 10-by-10 cells as:<code><br>
maze1 &lt;- makeGraph(10, 10)
</code><code><br>
plotMaze(maze1, 10, 10)<br>
</code></p>
<p>And this is the resulting maze:</p>
<div class="wp-caption"><a target="_blank" rel="attachment wp-att-372" href="http://www.vesnam.com/Rblog/mazes-graphs-and-r/mash/"><img sizes="(max-width: 300px) 100vw, 300px" srcset="http://i2.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/mash-300x300.jpeg?resize=300%2C300 300w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/mash-150x150.jpeg 150w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/mash.jpeg 612w" alt="10x10 maze grid created using the makeGraph command" class="wp-image-372" src="http://i2.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/mash-300x300.jpeg?resize=300%2C300" data-recalc-dims="1"></a>
<p class="wp-caption-text">10x10 maze grid created using the makeGraph command</p>
</div>
<p>Now let's create a real maze using the recursive backtracker algorithm (a modified version of depth first search). We will assume that the initial cell is cell in the first row and first column (cell/node denoted as A_1_1). <code><br>
current_cell_name = &quot;A_1_1&quot;<br>
</code></p>
<p>We will mark this cell as visited and set its corresponding node attribute <em>visited</em> to 1: <code><br>
igraph::V(gD)[which(igraph::V(gD)$name == current_cell_name )]$visited &lt;- 1
</code></p>
<p>Next, we will find all adjacent cells that were not visited before, and if such cells exist, we will randomly choose on of the unvisited neighbours and remove a wall between these two cells. Then we will push the current cell to the stack and make the chosen cell the current cell:<code><br>
v_adjacent &lt;- igraph::neighbors(gD,  igraph::V(gD)[which(igraph::V(gD)$name == current_cell_name )], &quot;all&quot;)
</code><br>
<code> index_adjacent_unvisited &lt;- which(igraph::V(gD)[igraph::V(gD)[v_adjacent]]$visited == 0)
</code><br>
<code>if (length(index_adjacent_unvisited) > 0){<br>
</code><br>
<code>index_adjacent_unvisited[sample(1:length(index_adjacent_unvisited), 1)]<br>
</code><br>
<code>igraph::E(gD)[current_cell_name %--% v_adjacent[randomly_select]$name]$wall &lt;- &quot;OFF&quot;
</code><br>
<code>nodes_stack &lt;- c(current_cell_name, nodes_stack)
</code><br>
<code>current_cell_name &lt;- v_adjacent[randomly_select]$name
}   
</code></p>
<p>If the current node does not have unvisited neighbors, it will be marked as finished: <code><br>
igraph::V(gD)[which(igraph::V(gD)$name == current_cell_name )]$visited &lt;- 2
</code></p>
<p>And, if the stack is not empty, we will pop a cell from the stack and make it the current cell: <code><br>
if (length(nodes_stack) > 0){<br>
        current_cell_name &lt;- nodes_stack[1]

        nodes_stack &lt;- nodes_stack[-1]
}
</code></p>
<p>This code is a part of the <a target="_blank" href="https://github.com/Vessy/Rmaze/blob/master/R/makeMaze_dfs.R">makeMaze_dfs.R</a> function. To create a maze, run: <code><br>
maze1 &lt;- makeGraph(10, 10)
</code><code><br>
maze1 &lt;- makeMaze_dfs(maze1)
</code><code><br>
plotMaze(maze1, 10, 10)<br>
</code></p>
<div class="wp-caption"><a target="_blank" href="http://www.vesnam.com/Rblog/maze_ex1/"><img sizes="(max-width: 300px) 100vw, 300px" srcset="http://i2.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1-300x300.jpeg?resize=300%2C300 300w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1-150x150.jpeg 150w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1.jpeg 612w" alt="Maze generated using the recursive backtracker algorithm" class="wp-image-357" src="http://i2.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1-300x300.jpeg?resize=300%2C300" data-recalc-dims="1"></a>
<p class="wp-caption-text">Maze generated using the recursive backtracker algorithm</p>
</div>
<p><a target="_blank" href="https://github.com/Vessy/Rmaze">Rmaze</a> provides an option to visualize each step of the maze creation process . To do so, run:<code><br>
maze1 &lt;- makeGraph(10, 10)
</code><code><br>
maze1 &lt;- makeMaze_dfs(maze1, stepBystep = TRUE, nrows=10, ncols=10)
</code><code><br>
plotMaze(maze1, 10, 10)<br>
</code></p>
<p>Note that visualizing each step slows down the running time and this option is not recommended for larger mazes.</p>
<div class="wp-caption"><a target="_blank" href="http://www.vesnam.com/Rblog/dfs_sbs_ex2/"><img sizes="(max-width: 300px) 100vw, 300px" srcset="http://i0.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/dfs_sbs_ex2-300x300.jpeg?resize=300%2C300 300w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/dfs_sbs_ex2-150x150.jpeg 150w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/dfs_sbs_ex2.jpeg 612w" alt="A step-by-step maze generation process" class="wp-image-358" src="http://i0.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/dfs_sbs_ex2-300x300.jpeg?resize=300%2C300" data-recalc-dims="1"></a>
<p class="wp-caption-text">A step-by-step maze generation process - white cells are unvisited maze cells, red cells are the maze cells on stack, and the blue cells are the maze cells that have been visited and removed from the stack</p>
</div>
<p>A maze solution is defined as the shortest path between the start and end maze cells. Assuming that the starting maze cell is cell 1-1 (denoted as A_1_1) and the ending maze cell is {maze_size_rows}-{maze_size_columns} (denoted as A_nrows_ncols), the maze solution can be find as: <code><br>
gD_hlp &lt;- igraph::subgraph.edges(gD, igraph::E(gD)[igraph::E(gD)$wall == &quot;OFF&quot;], delete.vertices = FALSE)
</code><code><br>
sp_start_end &lt;- igraph::shortest_paths(gD_hlp, igraph::V(gD_hlp)[1], igraph::V(gD_hlp)[igraph::vcount(gD_hlp)], mode=&quot;all&quot;, output=&quot;vpath&quot;)
</code></p>
<p>Note that igraph does not automatically differentiate between edge attributes, so we had to create a copy of our graph (i.e. subgraph) that contains only edges that represent paths (edges without walls), and use this graph to calculate the shortest path.</p>
<p>To se a maze solution, run:<code><br>
plotMazeSolution(maze1, 10, 10)<br>
</code></p>
<div class="wp-caption"><a target="_blank" href="http://www.vesnam.com/Rblog/maze_ex1_sol/"><img sizes="(max-width: 300px) 100vw, 300px" srcset="http://i2.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_sol-300x300.jpeg?resize=300%2C300 300w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_sol-150x150.jpeg 150w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_sol.jpeg 612w" alt="The maze solution" class="wp-image-356" src="http://i2.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_sol-300x300.jpeg?resize=300%2C300" data-recalc-dims="1"></a>
<p class="wp-caption-text">The maze solution</p>
</div>
<p>This algorithm creates a perfect maze. A perfect maze is a maze without loops and without inaccessible areas. Such maze has exactly one solution (there is exactly one path from each maze cell to another maze cell). Starting with a perfect maze, we can transform it into an imperfect maze. The imperfect maze is created by randomly adding or removing specified percentages of maze walls from the perfect maze. In the process of randomization, it is important to ensures that the added and removed walls do not interfere with the existence of the maze solution. To see more details, see <a target="_blank" href="https://github.com/Vessy/Rmaze/blob/master/R/makeImperfect.R">makeImperfect.R</a> function in <a target="_blank" href="https://github.com/Vessy/Rmaze">Rmaze</a>.<br>
<code><br>
maze1 &lt;- makeGraph(10, 10)
</code><code><br>
maze1 &lt;- makeMaze_dfs(maze1)
</code><code><br>
maze1 &lt;- makeImperfect(maze1)
</code><code><br>
plotMaze(maze1, 10, 10)<br>
</code></p>
<p>
<div class="wp-caption"><a target="_blank" href="http://www.vesnam.com/Rblog/maze_ex1_imp/"><img sizes="(max-width: 300px) 100vw, 300px" srcset="http://i1.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_imp-300x300.jpeg?resize=300%2C300 300w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_imp-150x150.jpeg 150w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_imp.jpeg 612w" alt="Imperfect maze that contains loops, inaccessible areas, and may have more than one solution" class="wp-image-355" src="http://i1.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_imp-300x300.jpeg?resize=300%2C300" data-recalc-dims="1"></a>
<p class="wp-caption-text">Imperfect maze that contains loops, inaccessible areas, and may have more than one solution</p>
</div>
<p>
The imperfect mazes may contain loops, inaccessible areas, and may have more than one solution. As such, their solution may vary from the solution of the perfect maze from which they have been built.</p>
<div class="wp-caption"><a target="_blank" href="http://www.vesnam.com/Rblog/maze_ex1_imp_sol/"><img sizes="(max-width: 300px) 100vw, 300px" srcset="http://i2.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_imp_sol-300x300.jpeg?resize=300%2C300 300w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_imp_sol-150x150.jpeg 150w, http://www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_imp_sol.jpeg 612w" alt="A solution to the imperfect maze" class="wp-image-354" src="http://i2.wp.com/www.vesnam.com/Rblog/wp-content/uploads/2016/07/maze_ex1_imp_sol-300x300.jpeg?resize=300%2C300" data-recalc-dims="1"></a>
<p class="wp-caption-text">A solution to the imperfect maze</p>
</div>
<p>To see more details about a randomized version of Kruskal's and Prim's algorithms, see <a target="_blank" href="https://github.com/Vessy/Rmaze/blob/master/R/makeMaze_kruskal.R">makeMaze_kruskal.R</a> and <a target="_blank" href="https://github.com/Vessy/Rmaze/blob/master/R/makeMaze_prim.R">makeMaze_prim.R</a> functions in <a target="_blank" href="https://github.com/Vessy/Rmaze">Rmaze</a>. These two methods also create perfect mazes.<br>
<code><br>
maze1 &lt;- makeGraph(10, 10)
</code><code><br>
maze2 &lt;- makeMaze_prim(maze1)
</code><code><br>
plotMaze(maze2, 10, 10)<br>
</code><code><br>
maze3 &lt;- makeMaze_kruskal(maze1, stepBystep = TRUE, nrows=10, ncols=10)
</code><code><br>
plotMaze(maze3, 10, 10)<br>
</code></p>
<p><div><div><div><div data-width="55" data-show-faces="false" data-send="true" data-layout="box_count" data-height="62" data-href="http://www.r-bloggers.com/networks-mazes-and-r-rmaze/"></div></div><div><a data-url="http://www.r-bloggers.com/networks-mazes-and-r-rmaze/" data-counturl="http://www.r-bloggers.com/networks-mazes-and-r-rmaze/" data-count="vertical" data-text="Networks, mazes, and R (Rmaze)" class="twitter-share-button" data-via="rbloggers" href="https://twitter.com/share"></a></div><div></div></div><div></div></div>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://www.vesnam.com/Rblog/mazes-graphs-and-r/"> Fun with R</a></strong>.</div>
<hr>
<a rel="nofollow" href="http://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="http://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="http://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="http://www.r-bloggers.com/?s=tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="http://www.r-bloggers.com/?s=data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="http://www.r-bloggers.com/?s=Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="http://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="http://www.r-bloggers.com/?s=ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="http://www.r-bloggers.com/?s=boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="http://www.r-bloggers.com/?s=map">maps</a>, <a title="Animation in R" rel="nofollow" href="http://www.r-bloggers.com/?s=animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="http://www.r-bloggers.com/?s=RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="http://www.r-bloggers.com/?s=sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="http://www.r-bloggers.com/?s=LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="http://www.r-bloggers.com/?s=SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="http://www.r-bloggers.com/?s=eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="http://www.r-bloggers.com/?s=git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="http://www.r-bloggers.com/?s=hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="http://www.r-bloggers.com/?s=Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="http://www.r-bloggers.com/?s=regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="http://www.r-bloggers.com/?s=PCA">PCA</a>, <a title="Time series" rel="nofollow" href="http://www.r-bloggers.com/?s=time+series">time series</a>, <a title="finance trading" rel="nofollow" href="http://www.r-bloggers.com/?s=trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/1DH2xFz4fgU"></a></div>