The following video shows a maze being created in Excel using a depth-first search algorithm using backtracking:
How it Works
The program works by randomly selecting a cell from a predefined range on a worksheet. It then looks at all the neighbouring cells that haven’t been visited to see which cell it can move to next. It randomly picks one of these cells and moves to it by removing the dividing border between the current cell and the new location it wants to move to. It keeps on repeating this process until the entire board range is filled. If it moves to a cell where there are no possible onward moves, it simply goes back to the previous cell, and looks for any unvisited cells from that location. It will keep on retracing it’s steps to find any neighbouring cells that haven’t been visited, before it resumes picking a direction randomly again.
Introducing the Stack
The current location of the cell is stored within a data structure known as a Stack. The stack holds the history of the programs current path. Since a stack is a LIFO (last in first out) data structure, the first cell on the stack is always the current location in the program. Hence, removing the object that is at the top of the stack will always leave the previous location as the top item. This is how the program moves recursively. By adding the current location and removing it when necessary from the Stack in order to go back and reevaluate its path. In VBA a stack can be implemented like so:
|
1 2 3 |
Dim moStack As Object Set moStack = CreateObject("System.Collections.Stack") |
However, it is better to wrap the Stack up in its own class and create class methods that are typically associated with stacks. This is so that we have an abstract view of the stack to work with. The class methods we create include adding items to the stack (known as Push), removing the last item added (known as Pop), and retrieving the item that is at the top of the stack. The following code is a class called clsStack which is used in the solution above:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
Option Explicit Dim moStack As Object Private Sub Class_Initialize() Set moStack = CreateObject("System.Collections.Stack") End Sub Public Function Push(ByVal Value As Range) moStack.Push Value End Function Public Function Pop() As Variant Pop = moStack.Pop End Function Public Function Top() As Range Dim arr As Variant arr = moStack.ToArray() Set Top = arr(LBound(arr)) End Function Private Sub Class_Terminate() If (Not moStack Is Nothing) Then moStack.Clear Set moStack = Nothing End If End Sub |
Making use of a Dictionary
In addition to monitoring the current cell, the program also needs to keep track of all visited cells. These can be stored in any data structure like an array or a collection. However, storing the items in a dictionary is particularly beneficial, because a dictionary has its on Exist method, which can be used to check if a cell has been visited or not. Storing items in a dictionary involves assigning a unique key to the value that is being added to the dictionary. The Exist method looks for the key within the items stored in the dictionary, so the solution makes use of this by storing the cell address as the key (since this will always be unique), and the cell object as the value. Like the stack the dictionary object is wrapped up in its own class. Below is the dictionary class called clsVisited:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
Option Explicit Private mdicVisited As Scripting.Dictionary Private Sub Class_Initialize() Set mdicVisited = New Scripting.Dictionary End Sub Private Sub Class_Terminate() Set mdicVisited = Nothing End Sub Public Function Count() As Integer Count = mdicVisited.Count End Function Public Function Add(ByVal rngCell As Range) If mdicVisited Is Nothing Then Set mdicVisited = New Scripting.Dictionary End If mdicVisited.Add rngCell.Address, rngCell End Function Public Function IsRangeVisited(ByVal rngCell As Range) As Boolean IsRangeVisited = mdicVisited.Exists(rngCell.Address) End Function |
Custom Range Object Wrapper
The Stack and Dictionary classes, are the main data structures used in the solution. However, I also created another data class called clsNextCell. This is because for every cell that the program considers moving to, I wanted to assign the location of that cell in relation to the current cell as a reference point. So the clsNextCell class is essentially a data wrapper for each range object in the maze but with an additional attribute called Direction. The code for this cell is found below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Option Explicit Private mRange As Range Private mintDirection As Integer Property Get Cell() Set Cell = mRange End Property Property Get Direction() Direction = mintDirection End Property Public Sub SetRangeNext(ByVal rng As Range, ByVal iDirection As Integer) Set mRange = rng mintDirection = iDirection End Sub |
And the Rest..
The remainder of the code consists of standard Excel formatting techniques which are used to animate the movement of the maze. I also introduced a very slight delay in the movement of the current cell to keep the animation smooth for the video. You can explore the formatting techniques in the solution from the link below. Hopefully, this post has given you some insight into simple maze creation, as well the possible uses of stacks and dictionaries in VBA code.
You can download the application from the video from here (however please take time to read the disclaimer about content found on this site).
Share :
