# Overview

This is a maze solving game, with a maze overlay drawn on an extended (restricted) DataGridView. The DataGridView only accepts arrow key input.
The mazes are created in conjunction with a 2D array, and arrow key movement through the DataGridView is limited to clear paths. Navigation is blocked where walls are drawn. The solver part of the game finds and draws a path from the start cell to the end cell.

The game has three levels - Beginner, Intermediate, and Advanced, which translates to 30*30 cells, 40*40 cells, and 50*50 cells...

# Creating a Prim's Algorithm maze

When creating a random maze, each cell starts with four walls. Given a starting cell, the maze is created with each new cell being a random spur from a random branch of the existing maze. Walls between the random maze cell and the new cell are removed. This new cell is then added to the existing maze, and the process repeats until all of the cells in the grid have been visited.

`Public` `Sub` ``` createMaze(````ByVal` ``` m ````As` ``` Integer````, ``ByVal` `randomNumber ``As` `Random)`
`    ``'create new maze`

`    ``ReDim` `Grid.Cells(m - 1)`
`    ``For` `c ``As` `Integer` ``` = 0 ````To` ``` m - 1```
`        ``ReDim` `Grid.Cells(c)(m - 1)`
`        ``For` `r ``As` `Integer` ``` = 0 ````To` ``` m - 1```
`            ````Grid.Cells(c)(r) = ````New` ``` Grid.cellDetails```
`        ``Next`
`    ``Next`

`    ``For` `c ``As` `Integer` ``` = 0 ````To` ``` Grid.Cells.GetUpperBound(0)```
`        ``For` `r ``As` `Integer` ``` = 0 ````To` ``` Grid.Cells(0).GetUpperBound(0)```
`            ````Grid.Cells(c)(r).visited = ````False`
`            ````Grid.Cells(c)(r).NorthWall = ````True`
`            ````Grid.Cells(c)(r).SouthWall = ````True`
`            ````Grid.Cells(c)(r).WestWall = ````True`
`            ````Grid.Cells(c)(r).EastWall = ````True`
`        ``Next`
`    ``Next`

`    ``'Stop`

`    ``Dim` `maze ``As` `New` ``` List(Of Point)```

`    ``Dim` `unvisited ``As` `Integer` ``` = m ^ 2```

`    ````Grid.startPoint = ````New` ``` Point(randomNumber.````Next``(0, m), m - 1)`

`    ````Grid.Cells(Grid.startPoint.X)(m - 1).SouthWall = ````False`
`    ``maze.Add(``New` `Point(Grid.startPoint.X, m - 1))`
`    ``unvisited -= 1`

`    ``While` `unvisited > 0`
`        ``Dim` `p ``As` `Point = maze(randomNumber.``Next``(0, maze.Count))`
`        ``Dim` `choice ``As` `New` ``` List(Of Point)```
`        ``If` `p.X > 0 ``And` `p.X < m - 1 ``Then` `'c`
`            ``If` `p.Y > 0 ``And` `p.Y < m - 1 ``Then` `'r`
`                ``choice.AddRange(``New` `Point() {``New` `Point(p.X - 1, p.Y), ``New` `Point(p.X, p.Y - 1), ``New` `Point(p.X + 1, p.Y), ``New` `Point(p.X, p.Y + 1)}) ``'l,t,r,b`
`            ``ElseIf` `p.Y = 0 ``Then`
`                ``choice.AddRange(``New` `Point() {``New` `Point(p.X - 1, p.Y), ``New` `Point(p.X + 1, p.Y), ``New` `Point(p.X, p.Y + 1)}) ``'l,r,b`
`            ``ElseIf` `p.Y = m - 1 ``Then`
`                ``choice.AddRange(``New` `Point() {``New` `Point(p.X - 1, p.Y), ``New` `Point(p.X, p.Y - 1), ``New` `Point(p.X + 1, p.Y)}) ``'l,t,r`
`            ``End` `If`
`        ``ElseIf` `p.X = 0 ``Then` `'c`
`            ``If` `p.Y > 0 ``And` `p.Y < m - 1 ``Then` `'c`
`                ``choice.AddRange(``New` `Point() {``New` `Point(p.X, p.Y - 1), ``New` `Point(p.X + 1, p.Y), ``New` `Point(p.X, p.Y + 1)}) ``'t,r,b`
`            ``ElseIf` `p.Y = 0 ``Then`
`                ``choice.AddRange(``New` `Point() {``New` `Point(p.X + 1, p.Y), ``New` `Point(p.X, p.Y + 1)}) ``'r,b`
`            ``ElseIf` `p.Y = m - 1 ``Then`
`                ``choice.AddRange(``New` `Point() {``New` `Point(p.X, p.Y - 1), ``New` `Point(p.X + 1, p.Y)}) ``'t,r`
`            ``End` `If`
`        ``ElseIf` `p.X = m - 1 ``Then` `'c`
`            ``If` `p.Y > 0 ``And` `p.Y < m - 1 ``Then`
`                ``choice.AddRange(``New` `Point() {``New` `Point(p.X - 1, p.Y), ``New` `Point(p.X, p.Y - 1), ``New` `Point(p.X, p.Y + 1)}) ``'l,t,b`
`            ``ElseIf` `p.Y = 0 ``Then`
`                ``choice.AddRange(``New` `Point() {``New` `Point(p.X - 1, p.Y), ``New` `Point(p.X, p.Y + 1)}) ``'l,b`
`            ``ElseIf` `p.Y = m - 1 ``Then`
`                ``choice.AddRange(``New` `Point() {``New` `Point(p.X - 1, p.Y), ``New` `Point(p.X, p.Y - 1)}) ``'l,t`
`            ``End` `If`

`        ``End` `If`
`        ``choice.RemoveAll(``Function``(pt) Grid.Cells(pt.X)(pt.Y).visited)`

`        ``If` `choice.Count = 0 ``Then` `Continue ``While`
`        ``Dim` `p2 ``As` `Point = choice(randomNumber.``Next``(0, choice.Count))`
`        ``If` `p.X = p2.X ``And` `p2.Y < p.Y ``Then`
`            ``If` `Grid.Cells(p.X)(p.Y).NorthWall ``Then`
`                ````Grid.Cells(p.X)(p.Y).NorthWall = ````False`
`                ````Grid.Cells(p2.X)(p2.Y).SouthWall = ````False`
`                ````Grid.Cells(p2.X)(p2.Y).visited = ````True`
`                ``unvisited -= 1`
`                ``maze.Add(``New` `Point(p2.X, p2.Y))`
`            ``Else`
`                ````Continue ````While`
`            ``End` `If`
`        ``ElseIf` `p.X = p2.X ``And` `p2.Y > p.Y ``Then`
`            ``If` `Grid.Cells(p.X)(p.Y).SouthWall ``Then`
`                ````Grid.Cells(p.X)(p.Y).SouthWall = ````False`
`                ````Grid.Cells(p2.X)(p2.Y).NorthWall = ````False`
`                ````Grid.Cells(p2.X)(p2.Y).visited = ````True`
`                ``unvisited -= 1`
`                ``maze.Add(p2)`
`            ``Else`
`                ````Continue ````While`
`            ``End` `If`
`        ``ElseIf` `p.X > p2.X ``And` `p2.Y = p.Y ``Then`
`            ``If` `Grid.Cells(p.X)(p.Y).WestWall ``Then`
`                ````Grid.Cells(p.X)(p.Y).WestWall = ````False`
`                ````Grid.Cells(p2.X)(p2.Y).EastWall = ````False`
`                ````Grid.Cells(p2.X)(p2.Y).visited = ````True`
`                ``unvisited -= 1`
`                ``maze.Add(p2)`
`            ``Else`
`                ````Continue ````While`
`            ``End` `If`
`        ``ElseIf` `p.X < p2.X ``And` `p2.Y = p.Y ``Then`
`            ``If` `Grid.Cells(p.X)(p.Y).EastWall ``Then`
`                ````Grid.Cells(p.X)(p.Y).EastWall = ````False`
`                ````Grid.Cells(p2.X)(p2.Y).WestWall = ````False`
`                ````Grid.Cells(p2.X)(p2.Y).visited = ````True`
`                ``unvisited -= 1`
`                ``maze.Add(p2)`
`            ``Else`
`                ````Continue ````While`
`            ``End` `If`
`        ``End` `If`

`    ``End` `While`

`End` `Sub`

# Solving with Recursive BackTracking

Given a starting cell, each cell N, E, S, W of the starting cell (where not out of bounds, and the cell hasn't already been visited and processed) is recursively processed to assess whether it is a valid path. For each of these (potentially) four cells, the process is repeated, until a processed cell is out of bounds, in which case the solver returns false, or, a processed cell is the target cell (end point), in which case the solver returns true. Any cell returning false is discarded. Those cells returning true are added to the solution list in reverse order - end cell to start cell.

`Public` `Function` ``` solveMaze(````ByVal` ``` m ````As` ``` Integer````, ``ByVal` `xPos ``As` `Integer````, ````ByVal` ``` yPos ````As` ``` Integer````, ``ByVal` `alreadySearched(,) ``As` `Boolean````, ````ByVal` ``` solution ````As` ``` List(Of Point)) ````As` ``` Boolean```
`    ``Dim` `correctPath ``As` `Boolean` ``` = ````False`
`    ``'should the computer check this cell`
`    ``Dim` `shouldCheck ``As` `Boolean` ``` = ````True`
`    ``'Check for out of boundaries`
`    ``If` `xPos >= m ``OrElse` `xPos < 0 ``OrElse` `yPos >= m ``OrElse` `yPos < 0 ``Then`
`        ````shouldCheck = ````False`
`    ``Else`
`        ``'Check if at finish`
`        ``If` `New` ``` Point(xPos, yPos) = Grid.endPoint ````Then`
`            ````correctPath = ````True`
`            ````shouldCheck = ````False`
`        ``End` `If`

`        ``'Check if previously searched`
`        ``If` `alreadySearched(xPos, yPos) ``Then`
`            ````shouldCheck = ````False`
`        ``End` `If`
`    ``End` `If`

`    ``'Search the cell`
`    ``If` `shouldCheck ``Then`
`        ``'mark cell as searched`
`        ````alreadySearched(xPos, yPos) = ````True`

`        ``'Check right cell`
`        ````correctPath = correctPath ````Or` ``` If````(Grid.Cells(xPos)(yPos).EastWall = ``False````, solveMaze(m, xPos + 1, yPos, alreadySearched, solution), ````False``)`
`        ``'Check down cell`
`        ````correctPath = correctPath ````Or` ``` If````(Grid.Cells(xPos)(yPos).SouthWall = ``False````, solveMaze(m, xPos, yPos + 1, alreadySearched, solution), ````False``)`
`        ``'check left cell`
`        ````correctPath = correctPath ````Or` ``` If````(Grid.Cells(xPos)(yPos).WestWall = ``False````, solveMaze(m, xPos - 1, yPos, alreadySearched, solution), ````False``)`
`        ``'check up cell`
`        ````correctPath = correctPath ````Or` ``` If````(Grid.Cells(xPos)(yPos).NorthWall = ``False````, solveMaze(m, xPos, yPos - 1, alreadySearched, solution), ````False``)`
`    ``End` `If`

`    ``'add cell to solution path`
`    ``If` `correctPath ``Then`
`        ``solution.Add(``New` `Point(xPos, yPos))`
`    ``End` `If`

`    ``Return` `correctPath`

`End` `Function`

# Conclusion

Using a proven predefined algorithm, it's easy to create Random Mazes.
Analyzing these Mazes with a recursive technique quickly finds the shortest clear path from start point to end point.
This game works through the combined use of a restricted DataGridView and two 2D arrays...

## Articles related to game programming

VB.Net - WordSearch
VB.Net - Vertex
VB.Net - Perspective
VB.Net - MasterMind
VB.Net - OOP BlackJack
VB.Net - Numbers Game
VB.Net - HangMan
Console BlackJack - VB.Net | C#
TicTacToe - VB.Net | C#
OOP Sudoku - VB.Net | C#
OctoWords VB.Net | C#
OOP Buttons Guessing Game VB.Net | C#
OOP Tangram Shapes Game VB.Net | C#
VB.Net - Three-card Monte
VB.Net - Pascal's Pyramid
VB.Net - Split Decisions
(Office) Wordsearch Creator
VB.Net - Event Driven Programming - LockWords Game
C# - Crack the Lock
VB.Net - Totris