Index

Part 7:Modifying the Maze Class

Now here we are going to do some modifications to the maze class. First thing I want to do here is make a small modification to the Draw() method. After removing the dead ends from the maze, you will have some 2x2 cell areas that will loop and look empty with the way things are being drawn now, so I am going to add corners to the cells to make the loops more visible.

	Method Draw(w:Int, h:Int)
		For Local y:Int = 0 Until Height
			For Local x:Int = 0 Until Width
				If grid[x,y].paths & TCell.North = 0 Then DrawLine x*w,y*h,x*w+w,y*h
				If grid[x,y].paths & TCell.East = 0 Then DrawLine x*w+w-1,y*h,x*w+w-1,y*h+h
				If grid[x,y].paths & TCell.South = 0 Then DrawLine x*w,y*h+h-1,x*w+w,y*h+h-1
				If grid[x,y].paths & TCell.West = 0 Then DrawLine x*w,y*h,x*w,y*h+h
				Plot x*w,y*h
				Plot x*w+w-1,y*h
				Plot x*w,y*h+h-1
				Plot x*w+w-1,y*h+h-1
			Next
		Next
	End Method

The rest of the modifications will be done within the Create() function.

First thing we want to do is limit the maze generation to only half of the grid. first, locate the following lines in the code

		For Local y:Int = 0 Until Height
			For Local x:Int = 0 Until Width
				If y > 0 Then maze.grid[x,y]._north = maze.grid[x,y-1]
				If x < Width-1 Then maze.grid[x,y]._east = maze.grid[x+1,y]
				If y < Height-1 Then maze.grid[x,y]._south = maze.grid[x,y+1]
				If x > 0 Then maze.grid[x,y]._west = maze.grid[x-1,y]
			Next
		Next
		
		Local list:TList = CreateList()
		list.AddLast(maze.grid[Rand(0,Width-1),Rand(0,Height-1)])

Now to make the maze only generate in the left half, you only need to change where it says Width to Width/2.

		For Local y:Int = 0 Until Height
			For Local x:Int = 0 Until Width/2 '<-change here
				If y > 0 Then maze.grid[x,y]._north = maze.grid[x,y-1]
				If x < Width/2-1 Then maze.grid[x,y]._east = maze.grid[x+1,y] '<-And here
				If y < Height-1 Then maze.grid[x,y]._south = maze.grid[x,y+1]
				If x > 0 Then maze.grid[x,y]._west = maze.grid[x-1,y]
			Next
		Next
		
		Local list:TList = CreateList()
		list.AddLast(maze.grid[Rand(0,Width/2-1),Rand(0,Height-1)]) '<- And here

Now the maze will be restricted to only the left half of the grid. You can compile and run the program to verify that it does indeed only render the first half.

The next thing I want to change is to randomly select between the Growing Tree and Recursive Backtracking algorithms. This will help keep all the levels from looking the same. First, we will put the Local cell:TCell declaration outside the While loop. We will also add a variable called test. This will hold a random double from 0 to 1. Within the while loop, we will generate another random double and compare it to test. If it is lower than test, we will use Recursive Backtracking, otherwise we will use Growing Tree. By making test random, we can vary how often one algorithm is selected over the other in a given maze.

		Local test:Double = RndDouble()
		Local cell:TCell
		While Not list.IsEmpty()
			If RndDouble() < test
				cell = TCell(list.Last()) 'Recursive Backtracking
			Else
				cell = TCell(list.ValueAtIndex(Rand(0,list.Count()-1))) 'Growing Tree
			End If

After the While loop, we go through the generated maze looking for dead ends. When we find one, we get any adjacent dead ends to link to. If no adjacent dead ends exists, then we pick a random unlinked cell to link to. The loop will go through the left half of the grid except for the middle column. It will be dealt with differently when we connect the two halves together.

		For Local x:Int = 0 Until Width/2-1
			For Local y:Int = 0 Until Height
				If maze.grid[x,y].DeadEnd()
					Local directions:Int[] = maze.grid[x,y].getDeadEnds()
					If directions = Null Then directions = maze.grid[x,y].getUnlinked()
					If directions Then maze.grid[x,y].Link(directions[Rand(0,directions.length-1)])
				End If
			Next
		Next

The next part will copy the left half of the maze to the right half, but mirrored. Column 0 is copied to column 14, column 1 to column 13, and so on. The east and west path bits need to be swapped as well.

		For Local x:Int = 0 Until Width/2
			For Local y:Int = 0 Until Height
				Local nx:Int = Width-1-x
				maze.grid[nx,y].paths = maze.grid[x,y].paths
				If maze.grid[x,y].paths & TCell.East
					maze.grid[nx,y].paths :| TCell.West
				Else
					maze.grid[nx,y].paths :& ~TCell.West
				End If
				If maze.grid[x,y].paths & TCell.West
					maze.grid[nx,y].paths :| TCell.East
				Else
					maze.grid[nx,y].paths :& ~TCell.East
				End If
			Next
		Next

Now comes the time to link the left half of the grid to the right half. I decided that about 1/3 of the grid height looked best. First, I went through the middle column looking for dead ends, when I found one, I connected it to the dead end on the opposite half. I also kept a counter (crossCount) that counted the number of connections made from the dead ends.

		Local crossCount:Int = 0
		For Local y:Int = 0 Until Height
			If maze.grid[Width/2,y].DeadEnd()
				maze.grid[Width/2,y].paths :| TCell.West
				maze.grid[Width/2-1,y].paths :| TCell.East
				crossCount :+ 1
			End If
		Next

Next, I go from where crossCOunt leaves off and continue to Height/3, picking a row randomly and connecting it to the other half. In my MineBlast game, I decided I would only pick a row as long as it was not already connected, and the row above and below were not already connected. This presented a small bug in my code. it was possible, depending on where the first few rows were picked, that no more rows exists with that criteria, causing an endless loop as the program endlessly searched for a row randomly. So to fix this, I simply created an array with each row as an element, then shuffled the rows around. Now picking the next random row was as simple as picking the next element in the array. If I reach the end of the array before all connections are made, then I abort the loop and leave the maze as is.

		Local choose:Int[Height]
		For Local i:Int = 0 Until Height
			choose[i] = i
		Next
		For Local i:Int = 0 Until Height
			Local temp:Int = choose[i]
			Local r:Int = Rand(0,Height-1)
			choose[i] = choose[r]
			choose[r] = temp
		Next
		Local n:Int = 0
		For Local i:Int = crossCount To Height/3
			Local choice:Int = choose[0]
			While maze.grid[Width/2,choice].paths & TCell.West <> 0 Or ..
					(choice > 0 And maze.grid[Width/2,choice-1].paths & TCell.West <> 0) Or ..
					(choice < Height-1 And maze.grid[Width/2,choice+1].paths & TCell.West <> 0)
				n :+ 1
				If n = Height Then Exit
				choice = choose[n]
			Wend
			If n = Height Then Exit
			maze.grid[Width/2-1,choice].paths :| TCell.East
			maze.grid[Width/2,choice].paths :| TCell.West
		Next					

That's it. All modifications are now done. The entire maze class looks like this.

Type TMaze
	Field grid:TCell[,]
	Field Width:Int, Height:Int
	
	Function Create:TMaze(Width:Int, Height:Int)
		Local maze:TMaze = New TMaze
		maze.Width = Width
		maze.Height = Height
		
		maze.grid = New TCell[Width,Height]
		
		For Local y:Int = 0 Until Height
			For Local x:Int = 0 Until Width
				maze.grid[x,y] = New TCell
			Next
		Next
		
		For Local y:Int = 0 Until Height
			For Local x:Int = 0 Until Width/2
				If y > 0 Then maze.grid[x,y]._north = maze.grid[x,y-1]
				If x < Width/2-1 Then maze.grid[x,y]._east = maze.grid[x+1,y]
				If y < Height-1 Then maze.grid[x,y]._south = maze.grid[x,y+1]
				If x > 0 Then maze.grid[x,y]._west = maze.grid[x-1,y]
			Next
		Next
		
		Local list:TList = CreateList()
		list.AddLast(maze.grid[Rand(0,Width/2-1),Rand(0,Height-1)])
		
		Local test:Double = RndDouble()
		Local cell:TCell
		While Not list.IsEmpty()
			If RndDouble() < test
				cell = TCell(list.Last()) 'Recursive Backtracking
			Else
				cell = TCell(list.ValueAtIndex(Rand(0,list.Count()-1))) 'Growing Tree
			End If
			Local directions:Int[] = cell.getUnvisited()
			If directions = Null
				list.Remove(cell)
			Else
				list.AddLast(cell.Link(directions[Rand(0,directions.length-1)]))
			End If
		Wend
		For Local x:Int = 0 Until Width/2-1
			For Local y:Int = 0 Until Height
				If maze.grid[x,y].DeadEnd()
					Local directions:Int[] = maze.grid[x,y].getDeadEnds()
					If directions = Null Then directions = maze.grid[x,y].getUnlinked()
					If directions Then maze.grid[x,y].Link(directions[Rand(0,directions.length-1)])
				End If
			Next
		Next
		For Local x:Int = 0 Until Width/2
			For Local y:Int = 0 Until Height
				Local nx:Int = Width-1-x
				maze.grid[nx,y].paths = maze.grid[x,y].paths
				If maze.grid[x,y].paths & TCell.East
					maze.grid[nx,y].paths :| TCell.West
				Else
					maze.grid[nx,y].paths :& ~TCell.West
				End If
				If maze.grid[x,y].paths & TCell.West
					maze.grid[nx,y].paths :| TCell.East
				Else
					maze.grid[nx,y].paths :& ~TCell.East
				End If
			Next
		Next
		Local crossCount:Int = 0
		For Local y:Int = 0 Until Height
			If maze.grid[Width/2,y].DeadEnd()
				maze.grid[Width/2,y].paths :| TCell.West
				maze.grid[Width/2-1,y].paths :| TCell.East
				crossCount :+ 1
			End If
		Next
		Local choose:Int[Height]
		For Local i:Int = 0 Until Height
			choose[i] = i
		Next
		For Local i:Int = 0 Until Height
			Local temp:Int = choose[i]
			Local r:Int = Rand(0,Height-1)
			choose[i] = choose[r]
			choose[r] = temp
		Next
		Local n:Int = 0
		For Local i:Int = crossCount To Height/3
			Local choice:Int = choose[0]
			While maze.grid[Width/2,choice].paths & TCell.West <> 0 Or ..
					(choice > 0 And maze.grid[Width/2,choice-1].paths & TCell.West <> 0) Or ..
					(choice < Height-1 And maze.grid[Width/2,choice+1].paths & TCell.West <> 0)
				n :+ 1
				If n = Height Then Exit
				choice = choose[n]
			Wend
			If n = Height Then Exit
			maze.grid[Width/2-1,choice].paths :| TCell.East
			maze.grid[Width/2,choice].paths :| TCell.West
		Next					
		Return maze
	End Function
	
	Method Draw(w:Int, h:Int)
		For Local y:Int = 0 Until Height
			For Local x:Int = 0 Until Width
				If grid[x,y].paths & TCell.North = 0 Then DrawLine x*w,y*h,x*w+w,y*h
				If grid[x,y].paths & TCell.East = 0 Then DrawLine x*w+w-1,y*h,x*w+w-1,y*h+h
				If grid[x,y].paths & TCell.South = 0 Then DrawLine x*w,y*h+h-1,x*w+w,y*h+h-1
				If grid[x,y].paths & TCell.West = 0 Then DrawLine x*w,y*h,x*w,y*h+h
				Plot x*w,y*h
				Plot x*w+w-1,y*h
				Plot x*w,y*h+h-1
				Plot x*w+w-1,y*h+h-1
			Next
		Next
	End Method
			
	Method Delete()
		For Local x:Int = 0 Until Width
			For Local y:Int = 0 Until Height
				grid[x,y].Destroy()
			Next
		Next
	End Method
End Type

Now when you run the program, you should see some nice pacman like mazes generated.

Entire program:

SuperStrict

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

Type TMaze
	Field grid:TCell[,]
	Field Width:Int, Height:Int
	
	Function Create:TMaze(Width:Int, Height:Int)
		Local maze:TMaze = New TMaze
		maze.Width = Width
		maze.Height = Height
		
		maze.grid = New TCell[Width,Height]
		
		For Local y:Int = 0 Until Height
			For Local x:Int = 0 Until Width
				maze.grid[x,y] = New TCell
			Next
		Next
		
		For Local y:Int = 0 Until Height
			For Local x:Int = 0 Until Width/2
				If y > 0 Then maze.grid[x,y]._north = maze.grid[x,y-1]
				If x < Width/2-1 Then maze.grid[x,y]._east = maze.grid[x+1,y]
				If y < Height-1 Then maze.grid[x,y]._south = maze.grid[x,y+1]
				If x > 0 Then maze.grid[x,y]._west = maze.grid[x-1,y]
			Next
		Next
		
		Local list:TList = CreateList()
		list.AddLast(maze.grid[Rand(0,Width/2-1),Rand(0,Height-1)])
		
		Local test:Double = RndDouble()
		Local cell:TCell
		While Not list.IsEmpty()
			If RndDouble() < test
				cell = TCell(list.Last()) 'Recursive Backtracking
			Else
				cell = TCell(list.ValueAtIndex(Rand(0,list.Count()-1))) 'Growing Tree
			End If
			Local directions:Int[] = cell.getUnvisited()
			If directions = Null
				list.Remove(cell)
			Else
				list.AddLast(cell.Link(directions[Rand(0,directions.length-1)]))
			End If
		Wend
		For Local x:Int = 0 Until Width/2-1
			For Local y:Int = 0 Until Height
				If maze.grid[x,y].DeadEnd()
					Local directions:Int[] = maze.grid[x,y].getDeadEnds()
					If directions = Null Then directions = maze.grid[x,y].getUnlinked()
					If directions Then maze.grid[x,y].Link(directions[Rand(0,directions.length-1)])
				End If
			Next
		Next
		For Local x:Int = 0 Until Width/2
			For Local y:Int = 0 Until Height
				Local nx:Int = Width-1-x
				maze.grid[nx,y].paths = maze.grid[x,y].paths
				If maze.grid[x,y].paths & TCell.East
					maze.grid[nx,y].paths :| TCell.West
				Else
					maze.grid[nx,y].paths :& ~TCell.West
				End If
				If maze.grid[x,y].paths & TCell.West
					maze.grid[nx,y].paths :| TCell.East
				Else
					maze.grid[nx,y].paths :& ~TCell.East
				End If
			Next
		Next
		Local crossCount:Int = 0
		For Local y:Int = 0 Until Height
			If maze.grid[Width/2,y].DeadEnd()
				maze.grid[Width/2,y].paths :| TCell.West
				maze.grid[Width/2-1,y].paths :| TCell.East
				crossCount :+ 1
			End If
		Next
		Local choose:Int[Height]
		For Local i:Int = 0 Until Height
			choose[i] = i
		Next
		For Local i:Int = 0 Until Height
			Local temp:Int = choose[i]
			Local r:Int = Rand(0,Height-1)
			choose[i] = choose[r]
			choose[r] = temp
		Next
		Local n:Int = 0
		For Local i:Int = crossCount To Height/3
			Local choice:Int = choose[0]
			While maze.grid[Width/2,choice].paths & TCell.West <> 0 Or ..
					(choice > 0 And maze.grid[Width/2,choice-1].paths & TCell.West <> 0) Or ..
					(choice < Height-1 And maze.grid[Width/2,choice+1].paths & TCell.West <> 0)
				n :+ 1
				If n = Height Then Exit
				choice = choose[n]
			Wend
			If n = Height Then Exit
			maze.grid[Width/2-1,choice].paths :| TCell.East
			maze.grid[Width/2,choice].paths :| TCell.West
		Next					
		Return maze
	End Function
	
	Method Draw(w:Int, h:Int)
		For Local y:Int = 0 Until Height
			For Local x:Int = 0 Until Width
				If grid[x,y].paths & TCell.North = 0 Then DrawLine x*w,y*h,x*w+w,y*h
				If grid[x,y].paths & TCell.East = 0 Then DrawLine x*w+w-1,y*h,x*w+w-1,y*h+h
				If grid[x,y].paths & TCell.South = 0 Then DrawLine x*w,y*h+h-1,x*w+w,y*h+h-1
				If grid[x,y].paths & TCell.West = 0 Then DrawLine x*w,y*h,x*w,y*h+h
				Plot x*w,y*h
				Plot x*w+w-1,y*h
				Plot x*w,y*h+h-1
				Plot x*w+w-1,y*h+h-1
			Next
		Next
	End Method
			
	Method Delete()
		For Local x:Int = 0 Until Width
			For Local y:Int = 0 Until Height
				grid[x,y].Destroy()
			Next
		Next
	End Method
End Type

SeedRnd(MilliSecs())
Local maze:TMaze = TMaze.Create(10,15)

Graphics 400,600
While Not KeyHit(KEY_ESCAPE) And Not AppTerminate()
	Cls
	maze.Draw(40,40)
	Flip
	If KeyHit(KEY_N) Then maze = TMaze.Create(10,15)
Wend

Index

Created with Tutorial Markup (c)2018 James Chamblin