In this post we are going to build a maze solver in Excel using VBA, to do this we will simulate a little person walking through a maze, they will be practicing the “right-hand rule,” that is, you can successfully escape any maze by placing your right hand (or left I suppose, as long as you are consistent) on a wall and continue walking until you find the exit. This will work in any ordinary, 2 dimensional maze provided that you start at the beginning. Similarly, the end must be an exit out of the maze. if the end is hiding somewhere in the middle you may never find it this way but that scenario also suggests that the maze isn’t two dimensional so we don’t have to worry about it here. The right-hand rule is a well-known solution so we aren’t setting out to prove anything this time around but we will be creating a simulation in VBA which will be very easy to set up and even more fun to watch in action. So let us begin.
Pretend it is you standing in a maze, then pretend there is a grid lain out on top of the maze, locations can be determined by rows and columns. This will help us get our bearings in the maze. Pretend you are also blind, how do you find a wall to keep your hand pressed upon? It is simple, stick out your right hand and walk in a straight line until you hit a wall. This is exactly what our little AI maze walker will perform and they will do this by testing the row next to them. If the row is empty, meaning there is no wall there, then take another step in that direction. Keep doing this until you find a wall. If said row contains a wall then they will know that they have hit a wall. Keep the right hand pressed there and start walking forward. In reality, a person would walk forward from this point on, our AI doesn’t inherently know what forward is so we shall have to teach them that, this will also be done using rows and columns and it will also be very simple.
First we will set up the maze playing area. To keep this as simple as possible, I decided to make the walls black, this way we can test to see if the maze runner hits a wall by simply checking the color of the cell, its devilishly simple! The first thing I did was to make each cell a perfect square, 20 by 20 pixels. This translates to a column width of 2.14 and a row height of 15. Next, paint the entire area black. Now, make some paths by painting some cells white and create any kind of maze of any size you like. Be sure to have a cell containing “End” at the exit of the maze. You can write “Start” somwhere as well, as I have done, but it isn’t necessary. Mine looks like this for reference:
Not the hardest maze ever conceived but it looks pretty at least.
In previous blog posts I have used the notation Cells(r,c), in this post I want to use the ActiveCell notation. For one thing it is nice to change it up sometimes and also I want to start the maze walker from wherever the user decides to click and this method makes that quite easy.
Here is the navigation key, I am going to use the activecell.offset method a lot here so I would like to introduce how we are going to be thinking about directions and movements on the spreadsheet. Since right and left change often it can get a little confusing so I will sometimes use North, South, East, and West. If we want to investigate a cell directly to the North of the active cell we can call this activecell.offset(-1,0). This means one cell closer to the top of your computer screen, or one cell to the North, -1 denotes one row to the North and 0 is the column reference. Here is a nifty visual guide:
And here is that same guide superimposed over a section of my maze:
Now let’s define four variables, these will be all we need in order to find a wall and move forward while hugging the right wall at all times:
Dim rhandr As Integer
Dim rhandc As Integer
Dim fwr As Integer
Dim fwc As Integer
Dim colorselect As Integer
“rhandr” stands for right hand row and “rhandc” is right hand column. These two variables will tell us where the right hand is touching and will inform the direction that the maze runner will go in next. If rhandr= 0 and rhandc = 1 then we know that the right hand is resting on a column to the right and the runner is facing up in relation to the grid over the maze. If they could move one step to their right they would be in a cell one column to the East of where they currently are, cell(r, c+1). If rhandr = -1 and rhandc = 0 then we know that the right hand is resting on a row just above the active cell, if they could walk an additional step to their right they would be in a cell one row north, cell(r-1,c), etc.
The fifth variable will allow us to paint the path the walker follows any color we want, for simplicity I am going to use the Excel color index. If colorselect is 3 then the path will be painted red, if it is 47 then the path will be a weird purple color. If you need to be reminded of which color is which in the color index just run this code:
Sub color()
For r = 1 To 56
Cells(r, 1).Interior.ColorIndex = r
Next r
End Sub
And column one will be filled with all 56 colors of the color index.
Notice that a color index value of 1 is black, this is how we will be testing for “walls,” we will actually just test an adjacent cell’s color index and if it is equal to 1 then we will know that a wall is there and we cannot move into that cell.
The first order of business is to find the nearest right wall. This will be our first sub routine and I called it “findright.” To start, I want to create an input box that lets the user select the color they would like to use. Any number from 0 to 56 will work as this is the range of colors built in to Excel’s color index. Once that information has been entered the macro will find the nearest wall to the right by utilizing the .offsetfunction. The direction of right for us is the cell adjacent to the active cell in the next column up, so cell(r, c+1). If the active cell is in column c (3) then the macro will check the color of the cell in the same row but in column d (4). If the cell’s color index is not 1 (not black) then the cell will be selected as the new active cell before looping again and testing the color of the cell to the right of the new active cell. If that cell’s color index is 1 (black) then the macro will end the loop because the maze runner has hit a wall on the right. It is really pretty straight forward as seen in the below VBA code:
Sub findright()
If ActiveCell.Interior.ColorIndex = 1 Then
MsgBox (“You are on a wall.”)
Exit Sub
End If
colorselect = Application.InputBox(“What color?”)
If colorselect = 1 Then
MsgBox (“Please do not select black, it will ruin your maze!”)
Exit Sub
End If
Call paint
Do Until ActiveCell.Offset(0, 1).Interior.ColorIndex = 1
ActiveCell.Offset(0, 1).Select
Call paint
‘End If
Loop
rhandr = 0
rhandc = 1
Call run
End Sub
You will notice three additional things happening there. The very first thing that macro does is check to see if we started the maze while standing on a wall, if that is the case it will simply let you know and exit the routine. The second thing is to ensure that the user hasn’t selected the color black, if they do then the maze runner will build a wall behind them as they move about the maze. This will destroy all your hard work so I included a very simple check to ensure that that doesn’t happen. The third thing is that a sub routine “Paint” is being called within that loop. Every time the active cell changes we will color the cell, this is how we will track the path that the maze walker takes. The color will be, of course, the color that the user entered into the message box that pops up at the beginning.
After the wayward mazer finds a wall and sticks their right hand on it they will immediately begin walking. Let’s look at the macro that handles this function.
The next subroutine, called “run,” will ascertain which direction “forward” is and move the active cell in that direction by one cell so long as there is no wall present. First it will run a check to find where exactly the right hand is resting. The first time around we know that the right hand is pressed against a column directly to the right of the active cell, c+1. This is because we just made the active cell move to the right until it couldn’t move any farther. So cell (r,c+1) has a wall and that is where the right hand rests. If right hand column is 1 then we know that we must move either a row up or a row down. We cannot move a column to the left because then we risk taking our hand off the wall and we cannot move a column to the right because there is a wall there. Let’s introduce two more variables in order to move the runner along correctly: fwr and fwc, forward row and forward column respectively. As per the previous logic, if we can’t move in a column direction than fwr must be either -1 or 1. In this case it is -1 and can only be -1 otherwise it will throw our navigation system off. If you think about why it is quite simple, picture an actual person standing in the maze you made, from above with their right hand on a column forward to them is to move up the rows, meaning row -1 from their current position. Making forward +1 would see the person walking backward, you could solve the maze this way of course, as long as you follow the rule and keep all other variables consistent but to keep it realistic I will do it this way. Here is another handy chart to show the relationship between rhandr, rhandc, fwr, and fwc:
Before taking the first step the mazer has to ensure that they have their hand firmly pressed against the wall so each and every time we run through the steps the first test will be to ensure that we cannot turn right from our current position. Easy to do, simply make sure that the cell directly to the right of the maze runner is still a wall. If that condition holds then take a step forward, forward having been determined previously. You can see that in action below:
If ActiveCell.Offset(rhandr, rhandc).Interior.ColorIndex = 1 Then
Call stepforward
Remember, because this is the first step we know that rhandr = 0 and rhandc = 1, because forward is up the page, North, and the right hand is pressed against a column directly to the mazer’s right, so this condition will hold true. Move down to the sub routine that handles stepping forward.
This will be fairly straight forward. We have determined where “forward” is (either a cell in an adjacent row or an adjacent column) so all we need to do is plug in the variables fwr and fwc and test to see if there is a wall where we seek to go. Use this: If ActiveCell.Offset(fwr, fwc).Interior.ColorIndex = 1 Then…
If there is a wall we have to turn the maze runner, if not we can simply select cell(fwr, fwc) and paint it. We have taken the first step in the maze! Now we can look at what happens when we run into a wall and have to turn.
Recall that in the sub routine called “run” the very first thing we do is check to make sure that the maze runner is still sticking to the right wall, if they can turn right they will. Before dealing with that, lets return to the sub routine “stepforward.” What happens if we cannot step forward any longer, meaning there is a wall inhabiting cell(fwr, fwc)? Simple, turn the mazer. This should hopefully feel a little intuitive, first get the direction of movement then turn left (because we already tested turning right). If the direction of movement was to the left along the grid, i.e. fwr = 0 and fwc = -1 (which would mean rhandr = -1 and rhandc = 0) then rhandr should become 0 (only turn 90 degrees at a time) and rhandc would become -1 to reflect the maze runner turning left. They were previously moving from right to left along the grid (East to West) now they are moving from top to bottom (North to South) along the grid. The right hand would be pressed against a column to their right and since they are facing down, this would be a column in the – direction according to the grid. If this is all a bit confusing see this:
To make the turn all we have to do is change the variables to reflect which direction
we have just instructed the mazer to turn. In practice it is simple, get the direction they were moving in and redefine the rhandr and rhandc variables to what they should be after a left turn. It is very simple and looks like this:
Sub stepforward()
If ActiveCell.Offset(fwr, fwc).Interior.ColorIndex = 1 Then
If fwr = 1 Then
rhandr = 1
rhandc = 0
fwr = 0
End If
If fwc = 1 Then
rhandr = 0
rhandc = 1
fwc = 0
End If
If fwr = -1 Then
rhandr = -1
rhandc = 0
fwr = 0
End If
If fwc = -1 Then
rhandr = 0
rhandc = -1
fwc = 0
End If
Else
ActiveCell.Offset(fwr, fwc).Select
Call paint
End If
End Sub
There are only four possible directions of travel and so it is easy enough to just run through the possibilities like this and adjust the variables accordingly. In the event where there is a possibility of turning right, the maze runner will always take this route as it is necessary in order to ensure that the right hand rule is strickly maintained. In this event, the argument is exactly the same as for a left turn however the values held by the variables will be tuned to the opposite direction of a left turn. You can see how right turns are handles here:
Sub run()
Do Until ActiveCell.Value = “End”
‘Cells(2, 3).Select
If rhandc = -1 Then fwr = 1
If rhandc = 0 Then fwr = 0
If rhandc = 1 Then fwr = -1
If rhandr = -1 Then fwc = -1
If rhandr = 0 Then fwc = 0
If rhandr = 1 Then fwc = 1
If ActiveCell.Offset(rhandr, rhandc).Interior.ColorIndex = 1 Then
Call stepforward
Else
ActiveCell.Offset(rhandr, rhandc).Select
Call paint
If fwc = -1 Then
rhandc = 1
rhandr = 0
End If
If fwr = -1 Then
rhandr = 1
rhandc = 0
End If
If fwc = 1 Then
rhandr = 0
rhandc = -1
End If
If fwr = 1 Then
rhandr = -1
rhandc = 0
End If
End If
Loop
End Sub
To recap, we have given the maze runner a sense of direction and instructions on how to maintain them while turning all about, this way and that, as they struggle through the maze. If the maze runner has turned left, rerun through the loops, try turning right. If this cannot be done then move down again to the next subroutine. Try moving forward. If this still cannot be done then rerun through the loops. Check right, check forward, turn left. Check right, check forward, turn left. This will continue until the maze runner has landed on a cell marked “End.”
Here is how it should look after a run through, I selected a nice blue color:
If you follow the route with your finger or pointer you can see that the maze runner has performed exactly as designed and adhered to the right hand rule throughout the ordeal, ultimately surviving the maze!
As always there is more you can do, ensure that the user enters a number between 1 and 56 for colorselectof course, which would be easy to do. And also, if you start the maze runner somewhere in the middle they may well circle a middle wall until the end of time. There are ways to determine if they are going in an endless loop of course and we can write rules to break out of these loops but maybe that is for another day.
Spreadsheet:
Full Code:
Dim rhandr As Integer
Dim rhandc As Integer
Dim fwr As Integer
Dim fwc As Integer
Dim colorselect As Integer
Sub findright()
If ActiveCell.Interior.ColorIndex = 1 Then
MsgBox (“You are on a wall.”)
Exit Sub
End If
colorselect = Application.InputBox(“What color?”)
If colorselect = 1 Then
MsgBox (“Please do not select black, it will ruin your maze!”)
Exit Sub
End If
Call paint
Do Until ActiveCell.Offset(0, 1).Interior.ColorIndex = 1
ActiveCell.Offset(0, 1).Select
Call paint
Loop
rhandr = 0
rhandc = 1
Call run
End Sub
Sub run()
Do Until ActiveCell.Value = “End”
If rhandc = -1 Then fwr = 1
If rhandc = 0 Then fwr = 0
If rhandc = 1 Then fwr = -1
If rhandr = -1 Then fwc = -1
If rhandr = 0 Then fwc = 0
If rhandr = 1 Then fwc = 1
If ActiveCell.Offset(rhandr, rhandc).Interior.ColorIndex = 1 Then
Call stepforward
Else
ActiveCell.Offset(rhandr, rhandc).Select
Call paint
If fwc = -1 Then
rhandc = 1
rhandr = 0
End If
If fwr = -1 Then
rhandr = 1
rhandc = 0
End If
If fwc = 1 Then
rhandr = 0
rhandc = -1
End If
If fwr = 1 Then
rhandr = -1
rhandc = 0
End If
End If
Loop
End Sub
Sub stepforward()
If ActiveCell.Offset(fwr, fwc).Interior.ColorIndex = 1 Then
If fwr = 1 Then
rhandr = 1
rhandc = 0
fwr = 0
End If
If fwc = 1 Then
rhandr = 0
rhandc = 1
fwc = 0
End If
If fwr = -1 Then
rhandr = -1
rhandc = 0
fwr = 0
End If
If fwc = -1 Then
rhandr = 0
rhandc = -1
fwc = 0
End If
Else
ActiveCell.Offset(fwr, fwc).Select
Call paint
End If
End Sub
Sub paint()
ActiveCell.Interior.ColorIndex = colorselect
End Sub