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.

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 igraph 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 Rmaze GitHub page, the Rmaze package vignette, and help files.

To install and test the package, run: devtools::install_github("Vessy/Rmaze") library("Rmaze")

Alternatively, you can run a Shiny app showcasing the basic Rmaze features as: Rmaze::runExample()

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:

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: gD <- igraph::simplify(igraph::graph.data.frame(df_hlp, directed=FALSE))

Next, will set up some edge and node attributes. For each edge, we will define an attribute called wall, that can be either ON or OFF. Initially all walls will be ON: gD <- igraph::set_edge_attr(gD , "wall", value = "ON")

For nodes, we will define an attribute called visited, that will be used later to keep track of which cells have been evaluated for the creation of the maze: gD <- igraph::set_vertex_attr(gD , "visited", value = 0)

These commands are a part of the makeGraph.R function. We can run this command and create and plot a maze of size 10-by-10 cells as: maze1 <- makeGraph(10, 10) plotMaze(maze1, 10, 10)

And this is the resulting maze:

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). current_cell_name = "A_1_1"

We will mark this cell as visited and set its corresponding node attribute visited to 1: igraph::V(gD)[which(igraph::V(gD)$name == current_cell_name )]$visited <- 1

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: v_adjacent <- igraph::neighbors(gD, igraph::V(gD)[which(igraph::V(gD)$name == current_cell_name )], "all")
index_adjacent_unvisited <- which(igraph::V(gD)[igraph::V(gD)[v_adjacent]]$visited == 0)
if (length(index_adjacent_unvisited) > 0){
index_adjacent_unvisited[sample(1:length(index_adjacent_unvisited), 1)]
igraph::E(gD)[current_cell_name %--% v_adjacent[randomly_select]$name]$wall <- "OFF"
nodes_stack <- c(current_cell_name, nodes_stack)
current_cell_name <- v_adjacent[randomly_select]$name }

If the current node does not have unvisited neighbors, it will be marked as finished: igraph::V(gD)[which(igraph::V(gD)$name == current_cell_name )]$visited <- 2

And, if the stack is not empty, we will pop a cell from the stack and make it the current cell: if (length(nodes_stack) > 0){ current_cell_name <- nodes_stack[1] nodes_stack <- nodes_stack[-1] }

This code is a part of the makeMaze_dfs.R function. To create a maze, run: maze1 <- makeGraph(10, 10) maze1 <- makeMaze_dfs(maze1) plotMaze(maze1, 10, 10)

Rmaze provides an option to visualize each step of the maze creation process . To do so, run: maze1 <- makeGraph(10, 10) maze1 <- makeMaze_dfs(maze1, stepBystep = TRUE, nrows=10, ncols=10) plotMaze(maze1, 10, 10)

Note that visualizing each step slows down the running time and this option is not recommended for larger mazes.

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: gD_hlp <- igraph::subgraph.edges(gD, igraph::E(gD)[igraph::E(gD)$wall == "OFF"], delete.vertices = FALSE) sp_start_end <- igraph::shortest_paths(gD_hlp, igraph::V(gD_hlp)[1], igraph::V(gD_hlp)[igraph::vcount(gD_hlp)], mode="all", output="vpath")

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.

To se a maze solution, run: plotMazeSolution(maze1, 10, 10)

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 makeImperfect.R function in Rmaze.
maze1 <- makeGraph(10, 10) maze1 <- makeMaze_dfs(maze1) maze1 <- makeImperfect(maze1) plotMaze(maze1, 10, 10)

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.

To see more details about a randomized version of Kruskal's and Prim's algorithms, see makeMaze_kruskal.R and makeMaze_prim.R functions in Rmaze. These two methods also create perfect mazes.
maze1 <- makeGraph(10, 10) maze2 <- makeMaze_prim(maze1) plotMaze(maze2, 10, 10) maze3 <- makeMaze_kruskal(maze1, stepBystep = TRUE, nrows=10, ncols=10) plotMaze(maze3, 10, 10)