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
```

Created with Tutorial Markup (c)2018 James Chamblin