Index

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
		If _north And _north.DeadEnd()
			de[top] = North
			top :+ 1
		EndIf
		If _east And _east.DeadEnd()
			de[top] = East
			top :+ 1
		End If
		If _south And _south.DeadEnd()
			de[top] = South
			top :+ 1
		End If
		If _west And _west.DeadEnd()
			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
	
	Method Link:TCell(Direction:Int)
		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
	
	Method DeadEnd:Int()
		Return paths And Not(paths & (paths-1))
	End Method
	
	Method getDeadEnds:Int[]()
		Local de:Int[4]
		Local top:Int = 0
		If _north And _north.DeadEnd()
			de[top] = North
			top :+ 1
		EndIf
		If _east And _east.DeadEnd()
			de[top] = East
			top :+ 1
		End If
		If _south And _south.DeadEnd()
			de[top] = South
			top :+ 1
		End If
		If _west And _west.DeadEnd()
			de[top] = West
			top :+ 1
		End If
		If top = 0 Then Return Null
		Return de[..top]
	End Method
	
	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
End Type

Index

Created with Tutorial Markup (c)2018 James Chamblin