Excel Maze Generator Kruskal

In a previous post, we have seen how to generate a maze in Excel using VBA macros and following the randomized depth-first search algorithm. In this post, we see how to create a maze in Excel using the randomized Kruskal’s algorithm. This other method allows creating larger maze structures, faster and without halting or breaking the code. On the other hand, it renders simple maze patterns that are easier to solve compared to patterns of similar size created with randomized depth-first search. Therefore, it is often used to create much larger maze structures in Excel.

Maze Generation Algorithms

There are many different algorithms that can be used to generate a maze with a computer. We have seen an overview of some of them in a previous post (Excel Maze Generator). In that post, we saw how to implement the randomized depth-first search algorithm to create a maze in Excel. That algorithm is probably the simplest way to do it. However, there are some limitations, especially when computing that with Excel VBA. It usually requires some time to complete and is limited to a certain grid size.

The randomized Kruskal’s algorithm, on the other hand, helps create the maze much faster and grow much larger. However, it tends to produce regular patterns that are fairly easy to solve. Therefore, it probably makes more sense for rather larger maze structures, while randomized depth-first search works better for a smaller maze.

The process to implement the randomized Kruskal’s algorithm to create a maze in Excel is the following. Starting from a grid of cells with all the walls around and a unique set (or identification number) assigned to each cell, the algorithm randomly removes walls when they separate two cells from different sets. When that border is removed, the two cells are regrouped and assigned the same set (any of the two sets). The process repeats and continues until, eventually, all the cells in the grid belong to the same set.

 

Excel Maze Layout

The layout consists of a rectangular grid with size determined by the number of columns and rows entered in cells BC12 and BC14 respectively. The first macro formats the layout to set a certain column width and row height, font size, interior color, and add thick borders around each cell in the grid. These properties can be changed as needed to fit to different screen resolutions and maze sizes.

After formatting, we need to assign a set or identification number to each cell in the grid. That’s a precondition needed to implement the randomized Kruskal’s algorithm to create a maze in Excel. One way to do that is to loop and assign a number to each cell in the same range (grid), starting with number 1 up to the total number of cells in the grid. Another possibility is to add the numbers (sets) to the same range in another (hidden) worksheet or to add them to a two-dimension array, thus hiding that part of the process.   

  

  For Each cell In MazeRng
      n = n + 1
      cell.Value = n
  Next cell
 

This means, each cell has a unique set or identification number at the beginning. Then, as we start removing walls from the grid, concurrent cells will share the same set, until, eventually, they all belong to the same set. See below an example of a simple grid of cells right at the start of the process.

 

Maze Generation Process

The second macro in this version of Excel Maze Generator using Kruskal’s algorithm (CaveMacro subroutine) consists of a Do loop that repeats for as long as needed to create the maze. Each time it loops, it picks a random cell and random wall around that cell using the code below.

 
  Randomize
  r = Int(Rnd * MazeRng.Rows.Count) + MazeRng.Row
  c = Int(Rnd * MazeRng.Columns.Count) + MazeRng.Column
  wall = Int(Rnd * 4) + 1 '1-xlEdgeLeft 2-xlEdgeRight 3-xlEdgeTop 4-xlEdgeBottom
 

Next, a condition checks if there is any border edge in that random location, and if so, it determines if that wall separates two cells from different sets. In the example below, cell H3 (r=3 and c=8) and border xlEdgeLeft (wall=1) are randomly selected. The two cells separated by that wall (cells H3 and G3) belong to different sets: cell G3 belongs to set 14 and cell H3 belongs to set 15. Hence, the wall can be removed and both cells are given the same set (set 15, as that was the set of the selected cell).

The process continues and keeps selecting random cells and walls (border edges), and then checking if the wall can be removed. If the wall separates two cells that belong to the same set, nothing happens.

In this other example, the wall between cells C5 and D5 has been selected. As those two cells belong to different sets (C5 belongs to set 25 and D5 to set 27), the wall can be removed and cells are regrouped.

The process continues and the grid begins to turn into a maze. The example given starts from a rather small grid and is caving a fairly simple pattern. As explained earlier, the randomized Kruskal’s algorithm creates very simple maze patterns for small grids.

Eventually, all the cells become members of the same set. The image below shows the configuration just before that happens. We can see that there are just two different sets left; two cells belong to set 2 and all the other cells to set 40.

 

As soon as a wall between two cells from those different sets is selected, the wall is removed and all cells become part of the same set. At this point, we can exit the loop.

As a last step, we remove the set number in all cells. It is irrelevant which set they all belong to. In this example, and in this version of Excel Maze Generator using Kruskal’s algorithm, the set values are added directly to cells in the same range and worksheet where the maze is created. Alternatively, they can be kept in other (hidden) worksheet or within a two-dimension array, thus hiding that part of the process if needed.

Download Excel Maze Generator Kruskal