Maze Generator in Excel using VBA

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:

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:

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:

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:

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 :Facebooktwittergoogle_plusredditpinterestmail