# Part 6: modifying the Cell Class

Now that we have our program generating mazes, we need to modify it so that there are no dead ends, and the left half mirrors the right half. We will start out by modifying the cell class.

First thing we need to do is add a method that can test if a cell is a dead end. A dead end will only have one path leading from it, so all we need to do is test if there is only 1 bit set in the paths field. There is a simple formula for that: n And Not(n & (n-1)). The n & (n-1) part simply flips off the lowest on bit of the number while leaving all upper bits alone. If there is only 1 on bit, then the result will be 0. For example, 0010 would become 0000, but 1010 would become 1000. The Not logical operator before the formula just flips the result so that 0 becomes True and any non 0 becomes False.

There is a small problem with the formula in that if there are no bits set, it will return True. We need to first test for 0, which is what the n And part at the beginning does. Our example here will have no cells without at least one path, so the n And part is not really needed. If you plan on modifying the program so that there will be cells with no paths, then you need to keep it in. I leave it in here just for completeness.

``````	Method DeadEnd:Int()
Return paths And Not(paths & (paths-1))
End Method
``````

The next thing we need to do is create a method which will return all directions to cells which are dead ends. This method will look a lot like our getUnvisited method.

``````	Method getDeadEnds:Int[]()
Local de:Int[4]
Local top:Int = 0
de[top] = North
top :+ 1
EndIf
de[top] = East
top :+ 1
End If
de[top] = South
top :+ 1
End If
de[top] = West
top :+ 1
End If
If top = 0 Then Return Null
Return de[..top]
End Method
``````

Last modification to our cell class will be to return all directions leading to a cell not linked with this one. This is almost identical to the getUnvisited method, except all unlinked cells will be added, not just unvisited ones.

``````	Method getUnlinked:Int[]()
Local ul:Int[4]
Local top:Int = 0
If _north And (paths & North) = 0
ul[top] = North
top :+ 1
End If
If _east And (paths & East) = 0
ul[top] = East
top :+ 1
End If
If _south And (paths & South) = 0
ul[top] = South
top :+ 1
End If
If _west And (paths & West) = 0
ul[top] = West
top :+ 1
End If
If top = 0 Then Return Null
Return ul[..top]
End Method
``````

The purpose of the last three methods is to determine the best cell to link a dead end to. Preferably, we want to link two dead ends together. If another dead end doesn't exist next to this one, then link randomly to any cell not already linked to.

The entire cell class looks like this.

``````Type TCell
Field paths:Int

Const North:Int = 1
Const East:Int = 2
Const South:Int = 4
Const West:Int = 8

Field _north:TCell, _east:TCell, _south:TCell, _west:TCell

Method Destroy()
_north = Null
_east = Null
_south = Null
_west = Null
End Method

paths :| Direction
Select Direction
Case North
_north.paths :| South
Return _north
Case South
_south.paths :| North
Return _south
Case East
_east.paths :| West
Return _east
Case West
_west.paths :| East
Return _west
End Select
End Method

Method getUnvisited:Int[]()
Local uv:Int[4]
Local top:Int = 0
If _north And _north.paths = 0
uv[top] = North
top :+ 1
End If
If _east And _east.paths = 0
uv[top] = East
top :+ 1
End If
If _south And _south.paths = 0
uv[top] = South
top :+ 1
End If
If _west And _west.paths = 0
uv[top] = West
top :+ 1
End If

If top = 0 Then Return Null
Return uv[..top]
End Method

Return paths And Not(paths & (paths-1))
End Method

Local de:Int[4]
Local top:Int = 0
de[top] = North
top :+ 1
EndIf
de[top] = East
top :+ 1
End If
de[top] = South
top :+ 1
End If
de[top] = West
top :+ 1
End If
If top = 0 Then Return Null
Return de[..top]
End Method

Local ul:Int[4]
Local top:Int = 0
If _north And (paths & North) = 0
ul[top] = North
top :+ 1
End If
If _east And (paths & East) = 0
ul[top] = East
top :+ 1
End If
If _south And (paths & South) = 0
ul[top] = South
top :+ 1
End If
If _west And (paths & West) = 0
ul[top] = West
top :+ 1
End If
If top = 0 Then Return Null
Return ul[..top]
End Method
End Type
``````

Created with Tutorial Markup (c)2018 James Chamblin