Simple MazeGenerator

Community Forums/Showcase/Simple MazeGenerator

Rixarn

(Posted 2009) [#1]

Hi! My current proyect involves lot's of mini games, and some of them are mazes!

This little piece of code generates mazes using either DFS algorithm or Prim´s algorithm. Haven't implemented Kruskal's algorithm yet, but i don't think i'll be needing it.

This is the mazegen lib, still WIP


'-------------------------- 
'  Copyright (c) <2009>  <Carlos E. Jiménez Correa>
'  All rights reserved.

'  Redistribution And use in source And binary forms, with Or without
'  modification, are permitted provided that the following conditions
'  are met:
'  1.Redistributions of source code must retain the above copyright
'     notice, this list of conditions And the following disclaimer.
'  2.Redistributions in binary form must reproduce the above copyright
'     notice, this list of conditions And the following disclaimer in the
'     documentation And / Or other materials provided with the distribution.
'  3.Neither the name of copyright holders nor the names of its
'     contributors May be used To endorse Or promote products derived
'     from this software without specific prior written permission.
 
'  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS And CONTRIBUTORS
'  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
'  To, THE IMPLIED WARRANTIES OF MERCHANTABILITY And FITNESS For A PARTICULAR
'  PURPOSE ARE DISCLAIMED.IN NO EVENT SHALL COPYRIGHT HOLDERS Or CONTRIBUTORS
'  BE LIABLE For ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, Or
'  CONSEQUENTIAL DAMAGES (INCLUDING, but Not LIMITED To, PROCUREMENT OF
'  SUBSTITUTE GOODS Or SERVICES; LOSS OF USE, DATA, Or PROFITS; Or BUSINESS
'  INTERRUPTION) HOWEVER CAUSED And ON ANY THEORY OF LIABILITY, WHETHER IN
'  CONTRACT, Strict LIABILITY, Or TORT (INCLUDING NEGLIGENCE Or Otherwise)
'  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN If ADVISED OF THE
'  POSSIBILITY OF SUCH DAMAGE.
'--------------------------

'Version 1.0

Type TMazePlayer
	
	Field CellPath:TList
	
	Field celdasRetrocedidas:Int
	
	Field errores:Int
	
	Function Create:TMazePlayer()
		Local mp:TMazePlayer = New TMazePlayer
	
		mp.CellPath = CreateList()
		
		Return mp
	End Function
	
	Method clearvariables()
		cellpath.Clear()
		celdasRetrocedidas = 0
		errores = 0
	End Method
	
End Type

Type TMazeGame

	Field maze:TMaze
	Field player:TMazePlayer
	
	Const MAZEPRIM:Byte = 1
	Const MAZEDFS:Byte = 2

	'mazeType 1 = Prim maze, 2 = DFS Maze
	Function Create:TMazeGame(cellQX:Int, cellqy:Int, startX:Int, startY:Int, endx:Int, endy:Int, cellsize:Int, mazeType:Byte)
		Local g:TMazeGame = New TMazeGame
		
		Select mazetype
			Case 1'PRIM MAZE
				g.maze = TMazeGenPrim.createPrimMaze(cellqx, cellqy, startx, starty, endx, endy, cellsize)
			Case 2'DFS MAZE
				g.maze = TMazeGenDFS.createDFSMaze(cellqx, cellqy, startx, starty, endx, endy, cellsize)
		End Select
		
		g.player = TMazePlayer.Create()
		
		Return g
	End Function
	
	Method update()
	
		For Local cx:Int = 0 To maze.CellQX - 1
			For Local cy:Int = 0 To maze.CellQY - 1
			
				If maze.Cell[cx, cy].mouseOverCell()
					
					'Determina que el único punto de entrada del laberinto sea la celda de inicio.
					If maze.Cell[cx, cy] = maze.StartCell
						If maze.Cell[cx, cy].visited = 0
							maze.Cell[cx, cy].visited = 1
							player.CellPath.AddLast(maze.Cell[cx, cy])
							Return
						EndIf
					End If
					
'					'termina el fin del laberinto.
'					If maze.Cell[cx, cy] = maze.EndCell
'						
'					End If
					
					'cualquier otra celda
					If player.CellPath.Count() > 0

						Local cell:TMazeCell = TMazeCell(player.CellPath.Last())
						
						'si la celda que se está agregando ya está en la lista, entonces significa que se está haciendo un retroceso.
						If player.CellPath.Contains(maze.Cell[cx, cy]) And Not (maze.Cell[cx, cy] = TMazeCell(Player.CellPath.Last()))
							
							Local count:Int = 0
							For Local c:TMazeCell = EachIn player.CellPath
								count:+1
								If c = maze.Cell[cx, cy]
								Exit
								EndIf
							Next
							
							Local remove:Int = player.CellPath.Count() - count
							
							player.celdasRetrocedidas:+remove
							
							For Local i:Int = 1 To remove
								TMazeCell(Player.CellPath.Last()).visited = 0
								player.CellPath.RemoveLast()
							Next
							
							Else'no la contiene
							
							If cell <> Null
								If cellsConnected(cell, maze.Cell[cx, cy]) = True
								
									'si hay celdas retrocedidas, revisa si debe de marcar error o no.
									If player.celdasRetrocedidas > 3
										player.errores:+1
									End If
									
									player.celdasRetrocedidas = 0
									maze.Cell[cx, cy].visited = 1
									player.CellPath.AddLast(maze.Cell[cx, cy])
									Return
								EndIf
							EndIf
							
						EndIf'player.CellPath.Contains(m..
			
					
					End If'player.CellPath.Count()
					
				End If'maze.Cell[cx, cy].mouseOv
			Next
		Next
		
	End Method
	
	Method draw()
	
		If maze = Null Then Return
		
		maze.drawMaze()
		
	End Method
	
	'retorna 1 si las celdas están conectadas (que se puede transitar de una a otra)
	'retorna 0 si las celdas no están conectadas.
	Method cellsConnected:Byte(BaseCell:TMazeCell, AdjacentCell:TMazeCell)
		
		'descarta la celda si no es adjacente.
		If AdjacentCell.CordX < BaseCell.CordX - 1 Then Return False
		If Adjacentcell.CordX > BaseCell.CordX + 1 Then Return False
		If adjacentcell.CordY > BaseCell.CordY + 1 Then Return False
		If adjacentcell.CordY < BaseCell.CordY - 1 Then Return False
		
		'Si pasó significa que es adjacente, ahora se determina la posición con respecto de la celda base
		'y determina si está conectada o no.
		
		If adjacentCell.CordX = baseCell.CordX
			'arriba
			If adjacentcell.CordY = baseCell.CordY - 1 And adjacentcell.bottomwall = 0 And basecell.topwall = 0 Then Return True
			'abajo
			If adjacentCell.CordY = basecell.CordY + 1 And adjacentcell.topwall = 0 And basecell.bottomwall = 0 Then Return True
		EndIf
		
		If adjacentcell.CordY = baseCell.CordY
			'izquierda
			If adjacentcell.CordX = baseCell.CordX - 1 And adjacentcell.rightwall = 0 And basecell.leftwall = 0 Then Return True
			'derecha
			If adjacentcell.CordX = baseCell.CordX + 1 And adjacentcell.leftwall = 0 And basecell.rightwall = 0 Then Return True
		End If
		
		Return False
		
	End Method

EndType

'mazelib
Type TMaze

	'drawing coord for Maze
	Field MazeX:Int
	Field MazeY:Int
	
	'Cell Quantity 
	Field CellQX:Int
	Field CellQY:Int
	
	'Array of Mace CEllS
	Field Cell:TMazeCell[,]
	
	Field StartCell:TMazeCell
	Field EndCell:TMazeCell
	
	Field Cellsize:Int
	
	Function CreateMaze:TMaze(cellQX:Int, cellQY:Int, cellsize:Int)
		Local m:TMaze = New TMaze
		
		m.CellQX = cellQX
		m.CellQY = CellQY
		
		m.Cellsize = cellsize
		
		m.Cell = New TMazeCell[cellQX, CEllQY]
		
		Local cellID:Int = 0
		For Local cx:Int = 0 To cellqx - 1
			For Local cy:Int = 0 To cellqy - 1
				cellID:+1
				m.Cell[cx, cy] = TMazeCell.CreateBaseCell(cx, cy, cellId, m.CellSize)
			Next
		Next
		
		Return m
	End Function
	
	Method setStartCell(cell:TMazeCell)
		Self.StartCell = cell
	End Method
	
	Method setEndCell(cell:TMazeCell)
		Self.EndCell = cell
	End Method
	
	Method setMazeXY(x:Int, y:Int)
		Self.MazeX = x
		Self.MazeY = y
		
		For Local cx:Int = 0 To cellqx - 1
			For Local cy:Int = 0 To cellqy - 1
				cell[cx, cy].drawx = x
				cell[cx, cy].drawy = y
			Next
		Next
		
	End Method
	
	Method drawMaze()
		
		For Local qx:Int = 0 To CellQX - 1
			For Local qy:Int = 0 To CellQY - 1
				cell[qx, qy].draw()
			Next
		Next
	
	End Method
	
End Type

Type TMazeGen Abstract

	Function ClearVisitedCells(maze:TMaze)
		If maze.cellqx > 0 And maze.cellqy > 0
			For Local X:Byte = 0 To maze.CellQX - 1
				For Local Y:Byte = 0 To maze.CEllQY - 1
					maze.Cell[X, Y].visited = 0
				Next
			Next
		EndIf

	End Function
	
	Function CarveCell(FromCell:TMazeCell, ToCell:TMazeCell)
		
		'carving left
		If FromCell.CordX = ToCell.CordX - 1
			Tocell.leftwall = 0
			FromCell.rightwall = 0
		EndIf
		
		'carving right
		If FromCEll.CordX = ToCell.CordX + 1
			ToCell.rightwall = 0
			FromCell.leftwall = 0
		End If
		
		'carving top
		If FromCell.CordY = ToCell.CordY - 1
			ToCell.topwall = 0
			FromCell.bottomwall = 0
		End If
		
		'carving bottom
		If FromCell.CordY = ToCell.CordY + 1
			ToCEll.bottomwall = 0
			FromCell.topwall = 0
		End If
	
	End Function
	
End Type

Type TMazeCell

	Field CellId:Int
	Field CordX:Int 'x position in array
	Field CordY:Int 'y position in array

	Field drawx:Int
	Field drawy:Int
	
	Field drawxrelative:Int
	Field drawyrelative:Int

	Field visited:Byte = 0
	Field leftwall:Byte = 1
	Field rightwall:Byte = 1
	Field topwall:Byte = 1
	Field bottomwall:Byte = 1
	
	Field CellSize:Int
	
	Field CellType:Byte 'Celda inicial, final o regular.
	
	Field CellStatus:Byte = 0'Para manejar los distintos algoritmos de creación de laberintos, se marca el status de la celda
	'en esta variable.
	
	Const CELL_START:Byte = 1
	Const CELL_END:Byte = 2
	Const CELL_REG:Byte = 3
	
	Field solution:Int = 0 'if solution is 0 it hasnt been checked, if its -1, its not part of the solution and if its 1, its part of it
	Field solutionpathID:Int = 0 'the number of cell in the solution path(0,1,2,3 etc)
	Field cellpathid:Int 'id given when cell is visited, this is for path verification
	
	Field img:TImage
	
	Method New()
		SetWalls(1, 1, 1, 1)
	End Method
	
	Function CreateBaseCell:TMazeCell(CordX:Int, CordY:Int, CellID:Int, CellSize:Int)
		Local Cell:TMazeCell = New TMazeCell
		Cell.CordX = CordX
		Cell.CordY = CordY
		Cell.CellId = CellID
		Cell.drawxrelative = CordX * cellSize
		Cell.drawyrelative = CordY * cellsize
		cell.CellSize = cellsize
		Return Cell
	End Function
	
	Method SetCellType(CellType:Byte) 
		Self.CellType = CellType
	End Method
	
	Method SetWalls(leftwall:Byte, topwall:Byte, rightwall:Byte, bottomwall:Byte)
		Self.leftwall = leftwall
		Self.topwall = topwall
		Self.rightwall = rightwall
		Self.bottomwall = bottomwall
	End Method
	
	Method mouseOverCell:Byte()
		'se resta uno, para que exista un "espacio vacio" entre celda y celda de un pixel.
		If MouseX() >= (Self.drawxrelative + Self.drawx) + 1 And MouseX() <= (Self.drawxrelative + Self.drawx + Self.CellSize) - 1
			If MouseY() >= (Self.drawyrelative + Self.drawy) + 1 And MouseY() <= (Self.drawyrelative + Self.drawy + Self.CellSize) - 1
				Return 1
			End If
		End If
		
		Return 0
		
	End Method
	
'	Method cursorOvercell:Byte(cursor:Tcursor)
'		'se resta uno, para que exista un "espacio vacio" entre celda y celda de un pixel.
'		If cursor.X >= (Self.drawxrelative + Self.drawx) + 1 And cursor.X <= (Self.drawxrelative + Self.drawx + Self.CellSize) - 1
'			If cursor.Y >= (Self.drawyrelative + Self.drawy) + 1 And cursor.y <= (Self.drawyrelative + Self.drawy + Self.CellSize) - 1
'				Return 1
'			End If
'		End If
'		
'		Return 0
'	End Method
	
	Method draw()
	
		If leftwall = 1 Then DrawRect drawx + drawxrelative, drawy + drawyrelative, 1, cellsize
		If topwall = 1 Then DrawRect drawx + drawxrelative, drawy + drawyrelative, cellsize, 1
		If rightwall = 1 Then DrawRect drawx + drawxrelative + (cellsize - 1), drawy + drawyrelative, 1, cellsize
		If bottomwall = 1 Then DrawRect drawx + drawxrelative, drawy + drawyrelative + (cellsize - 1), cellsize, 1
		
		If Self.visited = 1
			DrawOval drawx + drawxrelative + 3, drawy + drawyrelative + 3, cellsize - 6, cellsize - 6
		End If
		
	'	DrawText Self.CordX + "," + Self.CordY, drawx + drawxrelative, drawy + drawyrelative
	
	End Method
	
	'crea una imagen de celda
	Function createCellImg:TImage(CellSize:Int, leftwall:Int, topwall:Int, rightwall:Int, bottomwall:Int)
	
		Local image:TImage = CreateImage(cellsize, cellsize)
		
		If leftwall = 1 Then DrawRect 0, 0, 1, cellsize
		If topwall = 1 Then DrawRect 0, 0, cellsize, 1
		If rightwall = 1 Then DrawRect cellsize - 1, 0, 1, cellsize
		If bottomwall = 1 DrawRect 0, cellsize - 1, cellsize, 1
		GrabImage(image, 0, 0)
		
		Return image
	
	EndFunction
	
End Type

Type TMazeGenPrim Extends TMazeGen Abstract
	
	Const PRIMCELL_FRONTIER:Byte = 1
	Const PRIMCELL_IN:Byte = 2
	Const PRIMCELL_OUT:Byte = 3

	'Genera un laberinto con el algoritmo de Prim.
	Function createPrimMaze:TMaze(cellQX:Int, CellQY:Int, startX:Int, startY:Int, endX:Int, endY:Int, cellsize:Int)
	
		Local maze:TMaze = TMaze.CreateMaze(cellQX, cellQY, cellsize)
		
		'Creates a list to store neightbors 
		Local FrontierCells:TList = CreateList()
		Local InCells:TList = CreateList()
		Local OutCells:TList = CreateList()
		
'		This requires storage proportional to the size of the Maze. During creation, each cell is one of three types: 
'		(1) "In": The cell is part of the Maze and has been carved into already, 
'		(2) "Frontier": The cell is not part of the Maze and has not been carved into yet, but is next to a cell that's already "in"
'		(3) "Out": The cell is not part of the Maze yet, and none of its neighbors are "in" either. 
'		
'		1. Start by picking a cell, making it "in", and setting all its neighbors to "frontier". 
'		2. Proceed by picking a "frontier" cell at random, and carving into it from one of its neighbor cells that are "in". 
'		3. Change that "frontier" cell to "in", and update any of its neighbors that are "out" to "frontier". 
'		4. The Maze is done when there are no more "frontier" cells left.
'		5. (which means there are no more "out" cells left either, so they're all "in").

		'sets all cells to OUT.
		For Local qx:Int = 0 To CellQX - 1
			For Local qy:Int = 0 To CEllQY - 1
				maze.Cell[qx, qy].cellstatus = PRIMCELL_OUT
				ListAddLast(OutCells, maze.Cell[qx, qy])
			Next
		Next
	
		maze.StartCell = maze.Cell[startX, startY]
		
		maze.startcell.SetCellType(TMazeCell.CELL_START)
		
		maze.EndCell = maze.Cell[endX, endY]
		
		maze.endcell.setCellType(TMazeCell.CELL_END)
			
		'(1) pick a random cell 
		Local pqx:Int = 1'Rand(0, Self.CellQX - 1)
		Local pqy:Int = 1'Rand(0, Self.CellQY - 1)
		
		'frontier cell
		Local fcell:TMazeCell = maze.Cell[pqx, pqy]
		Local ncell:TMazeCell 'neighbor-in cell
		
	 	Repeat

			'get new cell 
			pqx = fcell.CordX
			pqy = fcell.CordY
			
			'make cell IN.
			If maze.Cell[pqx, pqy].CellStatus <> PRIMCELL_IN
				SetPrimCell(maze.Cell[pqx, pqy], PRIMCELL_IN, incells, outcells, frontiercells)
			End If
			
			'set neighbors to frontier
			SetNeighborsToFrontier(maze, pqx, pqy, incells, outcells, frontiercells)
			
			'Pick a random frontier cell
			fcell:TMazeCell = TMazeCell(PickAndRemoveRndObj(FrontierCells))
			
			'pick a random neighbor that´s In from that cell
			nCell:TMazeCell = TMazeCell(PickAndRemoveRndObj(GetNeighborsIn(maze:TMaze, fcell)))
			
			'change frontier cell to IN
			SetPrimCell(fcell, PRIMCELL_IN, incells, outcells, frontiercells)
			
			'carve into it from selected IN neighbor
			CarveCell(ncell, fcell)
			
		Until FrontierCells.count() = 0
		
		ClearVisitedCells(maze)
		
		Return maze
		
	EndFunction
	
	Function PrimCellToString:String(val:Byte)
	
		Select val
		
			Case 1
				Return "Fr"
			Case 2
				Return "In"
			Case 3
				Return "Out"
		End Select
		
	End Function
	
	Function SetPrimCell(Cell:TMazeCell, CellStatus:Byte, incells:TList, outcells:TList, FrontierCells:TList)
	
		Select CellStatus
			
			Case PRIMCELL_FRONTIER
			
				If cell.CellStatus = PRIMCELL_IN
					ListRemove(inCells, cell)
				End If
				If CELL.CellStatus = PRIMCELL_OUT
					ListRemove(OutCells, cell)
				End If
				ListAddLast(FrontierCells, cell)
				
			Case PRIMCELL_IN
			
				If CELL.CellStatus = PRIMCELL_OUT
					ListRemove(OutCells, cell)
				End If
				If CELL.CellStatus = PRIMCELL_FRONTIER
					ListRemove(FrontierCells, cell)
				End If
				ListAddLast(InCells, cell)
				
			Case PRIMCELL_OUT
				If CELL.CellStatus = PRIMCELL_IN
					ListRemove(InCells, cell)
				End If
				If CELL.CellStatus = PRIMCELL_FRONTIER
					ListRemove(FrontierCells, cell)
				End If
				ListAddLast(OutCells, cell)
				
		End Select
		
		cell.CellStatus = CellStatus
	
	EndFunction
	
	Function SetNeighborsToFrontier(maze:TMaze, pqx:Int, pqy:Int, inCells:TList, outcells:TList, frontierCells:TList)
	
		'if neighbor aint IN then set them to frontier
		'left neighbor
		If (pqx - 1) >= 0
			If maze.Cell[pqx - 1, pqy].CellStatus = PRIMCELL_OUT
				
				SetPrimCell(maze.Cell[pqx - 1, pqy], PRIMCELL_FRONTIER, incells, outcells, frontiercells)
			
			EndIf
		End If
		
		'right neighbor
		If (pqx + 1) <= maze.CellQX - 1
			If maze.Cell[pqx + 1, pqy].CellStatus = PRIMCELL_OUT
				
				SetPrimCell(maze.Cell[pqx + 1, pqy], PRIMCELL_FRONTIER, incells, outcells, frontiercells)
				
			EndIf
			
		End If
		
		'top neighbor
		If (pqy - 1) >= 0
			If maze.Cell[pqx, pqy - 1].CellStatus = PRIMCELL_OUT
				
				SetPrimCell(maze.Cell[pqx, pqy - 1], PRIMCELL_FRONTIER, incells, outcells, frontiercells)

			EndIf
		End If
		
		'bottom neighbor
		If (pqy + 1) <= Maze.CellQY - 1
			If maze.Cell[pqx, pqy + 1].CellStatus = PRIMCELL_OUT
				
				SetPrimCell(maze.Cell[pqx, pqy + 1], PRIMCELL_FRONTIER, incells, outcells, frontiercells)
				
			EndIf
		EndIf
		
	End Function

	Function GetNeighborsIn:TList(maze:TMaze, baseCell:TMazeCell)
		
		Local cellsIn:TList = CreateList()
		
		'left neighbor
		If (baseCell.CordX - 1) >= 0
			If maze.Cell[baseCell.CordX - 1, baseCell.CordY].CellStatus = PRIMCELL_IN
				ListAddLast(cellsIn, maze.Cell[baseCell.CordX - 1, baseCell.CordY])
			EndIf
		EndIf
		
		'right neighbor
		If (baseCell.CordX + 1) <= maze.CellQX - 1
			If maze.Cell[baseCell.CordX + 1, baseCell.CordY].CellStatus = PRIMCELL_IN
				ListAddLast(cellsIn, maze.Cell[baseCell.CordX + 1, baseCell.CordY])
			EndIf
		EndIf
		
		'top neighbor
		If (baseCell.CordY - 1) >= 0
			If maze.Cell[baseCell.CordX, baseCell.CordY - 1].CellStatus = PRIMCELL_IN
				ListAddLast(cellsIn, maze.Cell[baseCell.CordX, baseCell.CordY - 1])
			EndIf
		EndIf
		
		'bottom neighbor
		If (baseCell.CordY + 1) <= maze.CellQY - 1
			If maze.Cell[baseCell.CordX, baseCell.CordY + 1].CellStatus = PRIMCELL_IN
				ListAddLast(cellsIn, maze.Cell[baseCell.CordX, baseCell.CordY + 1])
			EndIf
		EndIf
		
		Return cellsIn
		
	End Function
	
End Type

Type TMazeGenDFS Extends TMazeGen Abstract
	
	Function createDFSMaze:Tmaze(cellQX:Int, cellQY:Int, startX:Int, startY:Int, endX:Int, endY:Int, cellsize:Int)
	
		Local maze:TMaze = TMaze.CreateMaze(cellQX, cellQY, cellsize:Int)
	
		Local sx:Int '= 0 'selected cellx
		Local sy:Int '= 0 'selected celly
		
		Local NX:Int[] = [0, 1, 0, -1]   '0:top,1:right,2:bottom,3:left 
		Local NY:Int[] = [- 1, 0, 1, 0]   '0:top,1:right,2:bottom,3:left 

'		1) Start at a random cell in the grid. 
'		2) Look For a random neighbor cell you haven't been to yet. 
'		3) If you find one, move there, knocking down the wall between the cells. 
'		If you don't find one, back up to the previous cell. 
'		4) Repeat steps 2 And 3 Until you've been to every cell in the grid.
		
		Local visitedCells:Int = 0
		
		maze.StartCell = maze.Cell[startX, startY]
		
		maze.startcell.SetCellType(TMazeCell.CELL_START)
		
		maze.EndCell = maze.Cell[endX, endY]
		
		maze.endcell.setCellType(TMazeCell.CELL_END)

		'pick a random cell
		sx = Rand(0, maze.CellQX - 1)
		sy = Rand(0, maze.CellQY - 1)
		
		maze.Cell[sx, sy].visited = 1 'mark as visited
		VisitedCells:+1 'add one to visted cells
		
		Local cellStack:TList = CreateList()
		Local neighbor:TList = CreateList()     'creates a list to store neighbors for cell picking.
		
		ListAddFirst(CellStack, maze.Cell[sx, sy])
		
		'coordinates for neighbor checking, each value will be added like this: sx+(nx) and sy+(ny)
	
		Repeat
		
			'Chech which neighbors are visitable
			For Local n:Byte = 0 To 3
				'condicional for valid cell pick (avoiding unexisting neighbors)
				If ((sx + nx[n]) >= 0 And (sx + nx[n]) <= maze.CellQX - 1) And ((sy + ny[n]) >= 0 And (sy + ny[n]) <= maze.CellQY - 1)
					If maze.Cell[sx + nx[n], sy + ny[n] ].visited = 0
						ListAddLast(neighbor, n + "")         'add neighbor to list stack	
					EndIf
				EndIf
			Next
			
			Local exitpick:Byte = 0
			
			If neighbor.count() = 0 Then 'if no valid neighbor found
				ListRemove(CellStack, maze.Cell[sx, sy])   'remove cell from cellstack
				For Local LastCell:TMazeCell = EachIn CellStack 'return to last cell
					sx = LastCell.CordX
					sy = LastCell.CordY
					Exit
				Next
			EndIf
			
			'IF VALID NEIGHBOR FOUND..
			If neighbor.count() > 0
				
				ListAddFirst(CellStack, maze.Cell[sx, sy])    'add previos cell to assigned cell stack
				
				Repeat 'pick a valid neighbor
					
					Local randomcounter:Byte = Rand(0, neighbor.count()) 
					Local loopcounter:Byte = 0
					Local pickedneighbor:Byte = 0
			
					For Local s:String = EachIn neighbor 'pick a random neightbor from the list
						If randomcounter = loopcounter Then pickedneighbor = s.ToInt() 
						loopcounter:+1
					Next
					
					For Local s:String = EachIn neighbor 'scrolls for neighbors on list
					
						Local ne:Int = s.ToInt()   'get neighbor number to visit
						If ne = pickedneighbor 'got neighbor
							If maze.Cell[sx + nx[ne], sy + ny[ne] ].visited = 0 'if it hasnt been visited yet..
							
									'open path between cells
									Select ne
										Case 0'top
											maze.Cell[sx, sy].topwall = 0
											maze.Cell[sx + nx[ne], sy + ny[ne] ].bottomwall = 0
										Case 1'right
											maze.Cell[sx, sy].rightwall = 0
											maze.Cell[sx + nx[ne], sy + ny[ne] ].leftwall = 0
										Case 2'bottom
											maze.Cell[sx, sy].bottomwall = 0
											maze.Cell[sx + nx[ne], sy + ny[ne] ].topwall = 0
										Case 3'left
											maze.Cell[sx, sy].Leftwall = 0
											maze.Cell[sx + nx[ne], sy + ny[ne] ].rightwall = 0
									End Select
							
									'pick neighbor as valid option	and mark it as visited
									exitpick = 1 'exit repeat loop when this loop ends
									VisitedCells:+1
									maze.Cell[sx + nx[ne], sy + ny[ne] ].visited = 1
									
									sx = sx + nx[ne]  'get next current cell
									sy = sy + ny[ne]
									ListAddFirst(CellStack, maze.Cell[sx, sy])
									Exit'exit for/next loop
								Else
									ListRemove(neighbor, s)    'remove neighbor from valid options , and repeat process
							EndIf
						EndIf
					Next
					
					If neighbor.count() = 0 'means no valid neighbor has been found (dead end)
						For Local LastCell:TMazeCell = EachIn CellStack 'pick last cell
							sx = LastCell.CordX
							sy = LastCell.CordY
							Exit
						Next
						exitpick = 1
					EndIf
					
				Until exitpick = 1
				
			EndIf
			
			neighbor.Clear()  'clear neighbor list

		Until Visitedcells = (maze.CellQX * maze.CellQY)
		
		ClearVisitedCells(maze)
		
		Return maze

	End Function

End Type

Function SolveMazeArray:TList(MazeArray:TMazeCell[,], CellQX:Int, CellQY:Int, startCell:TMazeCell, EndCell:TMazeCell)
	'stores cells if they are part of the solution.
	Local SolutionPath:TList = CreateList()   'if a cell is confirmed to be part of the solution its added here.
	
	Local neighbors:TList = CreateList()   'temporal neighbor picking
	Local SolutionPathID:Int
	
	Local sx:Int
	Local sy:Int
	
	Local nx:Int[] =[0, 1, 0, - 1]  '0:top,1:right,2:bottom,3:left 
	Local ny:Int[] = [- 1, 0, 1, 0]  '0:top,1:right,2:bottom,3:left 

	'pick starting cell and flag it as part of the solution"
	startCell.solution = 1
	startCell.solutionpathID = SolutionPathID;SolutionPathID:+1
	
	'add cell to solution path list
	ListAddFirst(SolutionPath, startCell)
'	Print "Added:" + MazeArray[0, 0].CellId
	
	'select starting point
	sx = startcell.CordX
	sy = startcell.CordY
	
	Repeat

		'Check which neighbors are visitable
		For Local n:Byte = 0 To 3
			Local newSx:Int
			Local newSy:Int
			newSx:Int = sx + nx[n] 
			newSy:Int = sy + ny[n] 
			
			'condicional for valid cell pick (avoiding unexisting neighbors)
			If ((newSx) >= 0 And (newSx) <= CellQX - 1) And ((newSy) >= 0 And (newSy) <= CellQY - 1) 
				If mazeArray[newSx, newSy].solution = 0 'only get non used cells
					
					Select n
						Case 0'TOP
							If mazearray[sx, sy].topwall = 0 Then ListAddLast(neighbors, n + "") 
						Case 1'RIGHT
							If mazearray[sx, sy].rightwall = 0 Then ListAddLast(neighbors, n + "") 
						Case 2'BOTTOM
							If mazearray[sx, sy].bottomwall = 0 Then ListAddLast(neighbors, n + "") 
						Case 3'LEFT
							If mazearray[sx, sy].leftwall = 0 Then ListAddLast(neighbors, n + "") 
					End Select
'		
				EndIf
			EndIf
		Next
		
		Local exitpick:Byte = 0
		
		If neighbors.count() = 0 Then 'if no valid neighbor found then it´s a dead end
			MazeArray[sx, sy].solution = -1 'flag cell as not being part of the solution path
			ListRemove(SolutionPath, MazeArray[sx, sy])        'remove cell from solution path
			'Print "Removed:" + MazeArray[sx, sy].CellId
			SolutionPathID:-1
			For Local LastCell:TMazeCell = EachIn SolutionPath 'return to last cell
				sx = LastCell.CordX
				sy = LastCell.CordY
				Exit
			Next
		EndIf
		
		If neighbors.Count() > 0 'check for neighbors and assign one, if possible
		
			mazeArray[sx, sy].solution = 1 'flag it
			SolutionPathID:+1
				
			Local randomcounter:Byte = Rand(0, neighbors.count()) 
			Local loopcounter:Byte = 0
			Local pickedneighbor:Byte = 0

'				Print "------------------"
'				Print "SX:" + sx
'				Print "SY:" + sy
'				Print "NextPick:"
'				For Local s:String = EachIn neighbors
'					Print s.ToInt() + "="
'					Print nx[S.ToInt()] + "," + ny[s.ToInt()] 
'				Next
'				
			For Local s:String = EachIn neighbors 'pick a random neightbor from the list
				pickedneighbor = s.ToInt() 
				If randomcounter = loopcounter Then Exit
				loopcounter:+1
			Next

'				Print "Picked:" + pickedneighbor
'				Print "New Pick SX:" + (sx + nx[pickedneighbor] ) + " New PickSY:" + (sy + ny[pickedneighbor] ) 
'				Print "--------------------------"
'			'	check if we can advance to that neighbor
'				Local nx:Int[] =[0, 1, 0, - 1] '0:top,1:right,2:bottom,3:left 
'				Local ny:Int[] =[- 1, 0, 1, 0]   '0:top,1:right,2:bottom,3:left 

			'Move to picks neighbor
			Local newpicksx:Int = sx + nx[pickedneighbor] 
			Local newpicksy:Int = sy + ny[pickedneighbor] 
			
			sx = MazeArray[newpicksx, newpicksy].CordX
			sy = MazeArray[newpicksx, newpicksy].CordY
			
			ListAddFirst(SolutionPath, mazeArray[newpicksx, newpicksy])    'add previos cell to assigned cell stack
		'	Print "added:" + mazearray[newpicksx, newpicksy].CellId
		
			'clear list of neighbors for next cicle
			neighbors.Clear() 
				
		End If
	
	Until MazeArray[sx, sy].celltype = TMazeCell.CELL_END
	
	MazeArray[sx, sy].solution = 1
	
	For Local mx:Int = 0 To CellQX - 1
		For Local My:Int = 0 To CEllQY - 1
			mazearray[mx, My].solution = 0
			mazearray[mx, My].solutionpathID = 0
		Next
	Next
	
	Return SolutionPath

EndFunction

Function PickRndObj:Object(List:TList)
	
	Local pick:Int = Rand(1, list.count())
	Local cnt:Int = 1
	
	For Local o:Object = EachIn List
		If cnt = pick
			Return o
		End If
		cnt:+1
	Next

End Function

Function PickAndRemoveRndObj:Object(list:TList)
	Local Pick:Int = Rand(1, list.count())
	Local cnt:Int = 1
	
	For Local o:Object = EachIn List
		If cnt = Pick
			Local obj:Object = o
			list.Remove(o)
			Return obj
		End If
		cnt:+1
	Next
End Function

First example showing how to generate mazes.

SuperStrict

Include "mazelib.bmx"

SeedRnd MilliSecs()

Graphics 1024, 768

Local mazeDFS:TMaze = TMazeGenDFS.createDFSMaze(10, 10, 0, 0, 9, 9, 40)
mazeDFS.setMazeXY(50, 100)

Local mazePRim:TMaze = TMazeGenPrim.createPrimMaze(10, 10, 0, 0, 9, 9, 40)
mazePrim.setMazeXY(562, 100)

Local text1:String = "A simple demostration of two 10x10 mazes using each algorithm."
Local text2:String = "Press Return key to generate new mazes"

Repeat

	DrawText text1, (1024 - TextWidth(text1)) / 2, 20
	DrawText text2, (1024 - TextWidth(text2)) / 2, 40
		
	DrawText "A perfect maze using DFS algorithm", 50, 80
	mazeDFS.drawMaze()
	
	DrawText "A perfect maze using Prim's algorithm", 562, 80
	mazePrim.drawMaze()
	
	If KeyHit(KEY_RETURN)
		mazeDFS = TMazeGenDFS.createDFSMaze(10, 10, 0, 0, 9, 9, 40)
		mazeDFS.setMazeXY(50, 100)
		mazePRim = TMazeGenPrim.createPrimMaze(10, 10, 0, 0, 9, 9, 40)
		mazePrim.setMazeXY(562, 100)
	End If
	
	Flip(1) ;Cls()
Until KeyDown(KEY_ESCAPE) Or AppTerminate()

Second example let's user solve them.

SuperStrict

Include "mazelib.bmx"

SeedRnd MilliSecs()

Graphics 1024, 768

Local mazeGameDFS:TMazeGame = TMazeGame.Create(10, 10, 0, 0, 9, 9, 40, TMazeGame.MAZEDFS)
mazeGameDFS.maze.setMazeXY(50, 100)

Local mazeGamePRim:TMazeGame = TMazeGame.Create(10, 10, 0, 0, 9, 9, 40, TMazeGame.MAZEPRIM)
mazeGamePrim.maze.setMazeXY(562, 100)

Local text1:String = "A simple demostration of two 10x10 mazes using each algorithm."
Local text2:String = "Press Return key to generate new mazes"
Local text3:String = "Use the mouse to solve the mazes."

'Print mazegamedfs.maze.StartCell.CordX + ":" + mazegamedfs.maze.StartCell.drawx + "," + mazegamedfs.maze.StartCell.drawy
'Print mazegamedfs.maze.EndCell.CordX + ":" + mazegamedfs.maze.StartCell.drawx + "," + mazegamedfs.maze.EndCell.drawx

Repeat

	DrawText text1, (1024 - TextWidth(text1)) / 2, 20
	DrawText text2, (1024 - TextWidth(text2)) / 2, 34
	DrawText text3, (1024 - TextWidth(text3)) / 2, 46
	
	DrawText "A perfect maze using DFS algorithm", 50, 80
	mazegamedfs.update()
	mazeGameDFS.draw()
	
	Local S:TMazeCell = mazegameDFS.maze.StartCell
	Local E:TMazeCell = mazegameDFS.maze.EndCell
	
	DrawText "ENTRACE", S.drawx + s.drawxrelative, s.drawy + s.drawyrelative + 5
	DrawText "EXIT", E.drawx + E.drawxrelative, E.drawy + E.drawyrelative + 5
	
	DrawText "A perfect maze using Prim's algorithm", 562, 80
	mazeGamePrim.draw()
	mazegamePrim.update()
	
	 S = mazegamePRIM.maze.StartCell
	 E = mazegamePRIM.maze.EndCell
	
	DrawText "ENTRACE", S.drawx + s.drawxrelative, s.drawy + s.drawyrelative + 5
	DrawText "EXIT", E.drawx + E.drawxrelative, E.drawy + E.drawyrelative + 5
	
	If KeyHit(KEY_RETURN)
		mazegameDFS = TMazeGame.Create(10, 10, 0, 0, 9, 9, 40, TMazeGame.MAZEDFS)
		mazegameDFS.maze.setMazeXY(50, 100)
		mazegamePRim = TMazeGame.Create(10, 10, 0, 0, 9, 9, 40, TMazeGame.MAZEPRIM)
		mazegamePrim.maze.setMazeXY(562, 100)
	End If
	
	Flip(1) ;Cls()
Until KeyDown(KEY_ESCAPE) Or AppTerminate()

There´s also a function in the lib that solves those mazes, and returns a list of cells that are part of the solution.

Im using this maze generators in a tiled dungeon maze, (still haven't had the time to clean my messy tile engine code, but i will eventually.) And the main goal is to remember the path from finish to start (backwards ^^)...The camera hovers the maze from exit to start and then lets the player solve it, with a limited amount of time.

WERDNA

(Posted 2009) [#2]

Hey this looks pretty cool Rixarn!

I'll check it out when I get a chance.

Rixarn

(Posted 2009) [#3]

Cool! if you make any improvements let me know, thanks :)

WERDNA

(Posted 2009) [#4]

This is really cool Rixarn!

I finally got around to taking a good look at this, and this would actually
prove quite useful in a few games that I have planned :)

Is there any way to scale the mazes to a bigger\smaller size?

if you make any improvements let me know,

A; your code is pretty good as it is, and not likely to be easily improved upon.
B; I only know a little bit about BlitzMax :)
Usually I stick with Blitz3D

Keep up the good work!

WERDNA