Maze Generator: 2D recursive backtracker

Monkey Forums/Monkey Code/Maze Generator: 2D recursive backtracker

AdamRedwoods

(Posted 2013) [#1]

2D Maze Generator
recursive backtracker

- creates the long and windy maze, fewer branches
- guarantees a solution
- also uses a minimum step check to keep complexity up
- optional step-through
- repeatable using Maze(w,h,seed)
- instant game! fun for the whole family! ;D

''Maze Generator
''recursive-backtracker
''(c) Adam Piette 2013
'' written using Monkey Programming Language

''use this to step through creation
#MAZESTEP=False

Import mojo



Class MazeUnit
	Field x:Int,y:Int, nearExit:Int=0
	
	Method Copy:MazeUnit()
		Local m:MazeUnit = New MazeUnit
		m.x=x; m.y=y; m.nearExit=nearExit
		Return m
	End
End

Class Maze
	
	Const _WALL:Int=1
	Const _VISIT:Int=2
	Const _START:Int=3
	Const _END:Int=4
	
	Const MAZENORTH:Int=1
	Const MAZEEAST:Int=2
	Const MAZESOUTH:Int=4
	Const MAZEWEST:Int=8

	Field width:Int,height:Int
	Field map:Int[][]
	Field unitstack:Stack<MazeUnit>
	Field startx:Int,starty:Int
	Field endx:Int, endy:Int
	Field hasExit:Bool=False
	
	Method New(w:Int,h:Int, seed:Int=0)
	
		If seed=0 Then seed=Millisecs()
		Seed = seed
		
		width=w; height=h

		Self.Create()
	End
	
	
	Method Create:Void()
		
		Print "creating maze.."
		
		''reset
		unitstack = New Stack<MazeUnit>
		map = Allocate<Int>.Array2D(width,height)
		hasExit=False
		
		''keep start/end out of corners
		If Int(Rnd()+0.5)
			startx= Rnd()*(width-2)+1
			starty= 0
		Else
			starty = Rnd()*(height-2)+1
			startx=0
		Endif
		
		If Int(Rnd()+0.5)
			endx= Rnd()*(width-2)+1
			endy= height-1
		Else
			endy = Rnd()*(height-2)+1
			endx=width-1
		Endif
		
		''create first step
		Local unit:MazeUnit = New MazeUnit
		unit.x=startx
		unit.y=starty

		If unit.x
			unit.y+=1
		Else
			unit.x+=1
		Endif
		
		'Print "start "+startx+" "+starty
		
		unitstack.Push(unit)
		SetWallBorder(startx,starty,endx,endy)
		

#if MAZESTEP=1
		MazeStep()
#else		
		While Not unitstack.IsEmpty()
			MazeStep()
		Wend
		Finish()
#endif	
		
		
	End
	
	Method Finish:Void()
		'' no exit??
		If Not hasExit
			Print "unsolvable"
			Create()
			Return 
		Endif
		
		Cleanup()
		
		Print"done."; Return
	End
	
	Method MazeStep:Void()
		
		If unitstack.IsEmpty() Then Return ''used for step through

		
		Local unit:MazeUnit
		unit = unitstack.Pop()
		Local px:Int=unit.x
		Local py:Int=unit.y
		
		''choose random direction
		Local newdir:Int = GetDirection(px, py)
		
		Local ex:Int = CheckExit(px, py)
		If ex
			''mark unit as visited and remove from stack
			map[unit.x][unit.y] = _VISIT
			newdir = ex
			
			''reset if too easy
			If unit.nearExit < width*0.9 Then Create()
			
			Print "wall connected at proximity:"+unit.nearExit
			
			Return
		Endif
		
		''check for mazewalls, pop on dead end
		If newdir=0
			map[unit.x][unit.y] = _VISIT
			Return 'Continue
		Endif
		
		''put up walls and push
		If newdir=MAZENORTH Then py=py-1
		If newdir=MAZESOUTH Then py=py+1
		If newdir=MAZEWEST Then px=px-1
		If newdir=MAZEEAST Then px=px+1
		
		Local wall:Int=0
		
		''check for near exit, if so force no wall
		wall=SetWall(px,py, unit.x,unit.y)
	
		If Not wall
			''push old back on
			Local oldunit:MazeUnit = unit.Copy()
			unitstack.Push(oldunit)
			
			'set new
			''move to px py
			map[unit.x][unit.y] = _VISIT
			unit.x=px; unit.y=py
			unit.nearExit+=1
		Endif
		
		unitstack.Push(unit)
		
	End
	
	Method SetWall:Int(x:Int,y:Int, prevx:Int, prevy:Int)
		'Print "setwall "+x+" "+y
			
		''check map for visited units, if so and not prevunit, then put up wall
		''check only for visited unit
		If y-1>=0 And map[x][y-1]=_VISIT And y-1<>prevy Then map[x][y]=_WALL; Return 1
		If y+1<=height-1 And map[x][y+1]=_VISIT And y+1<>prevy Then map[x][y]=_WALL; Return 1
		If x-1>=0 And map[x-1][y]=_VISIT And x-1<>prevx Then map[x][y]=_WALL; Return 1
		If x+1<=width-1 And map[x+1][y]=_VISIT And x+1<>prevx Then map[x][y]=_WALL; Return 1
		
		''CHECK DIAGONALS for a 'thicker' maze
		''check in new path direction
		Local dirx:Int = x-prevx
		Local diry:Int = y-prevy
		
		If (y+diry>=0 And y+diry<=height-1)
			If (x+dirx>=0 And x+dirx<=width-1)
				If dirx=0
					If x-1>=0 And map[x-1][y+diry]=_VISIT Then map[x][y]=_WALL;Return 1
					If x+1<=width-1 And map[x+1][y+diry]=_VISIT Then map[x][y]=_WALL;Return 1
				Else
					If y-1>=0 And map[x+dirx][y-1]=_VISIT Then map[x][y]=_WALL;Return 1
					If y+1<=height-1 And map[x+dirx][y+1]=_VISIT Then map[x][y]=_WALL;Return 1
				Endif
			Endif
		Endif
		
		Return 0
	End
	
	Method SetWall:Void(x:Int,y:Int,fill:Int)
		If (fill & MAZENORTH) And (y-1>0) map[x][y-1] = _WALL
		If (fill & MAZESOUTH) And (y+1<(height-1)) map[x][y+1] = _WALL
		If (fill & MAZEWEST) And (x-1>0) map[x-1][y] = _WALL
		If (fill & MAZEEAST) And (x+1<(width-1)) map[x+1][y] = _WALL
	End
	
	Method SetWallBorder:Void(sx:Int,sy:Int,ex:Int,ey:Int)

		For Local y:Int=0 To height-1
			map[0][y] = _WALL
		Next
		For Local y:Int=0 To height-1
			map[width-1][y] = _WALL
		Next
		For Local x:Int=0 To width-1
			map[x][0] = _WALL
		Next
		For Local x:Int=0 To width-1
			map[x][height-1] = _WALL
		Next
		
		''mark start/end
		map[sx][sy]=_START
		map[ex][ey]=_END
		
	End
	
	Method GetDirection:Int(x:Int,y:Int)
	
		'Print "Getdirection "+x+" "+y	
			
		Local a:Int[] = [MAZENORTH,MAZESOUTH,MAZEWEST,MAZEEAST]
		Local b:Int[] = []
		
		If (y-1<0 Or (y-1>=0 And map[x][y-1]<>0)) Then a[0] = 0
		If (y+1>height-1 Or (y+1<=height-1 And map[x][y+1]<>0)) Then a[1] = 0
		If (x-1<0 Or (x-1>=0 And map[x-1][y]<>0)) Then a[2] = 0
		If (x+1>width-1 Or (x+1<=width-1 And map[x+1][y]<>0)) Then a[3] = 0
		
		Local j:Int=0
		For Local i:Int=0 To 3
			If a[i]<>0
				b = b.Resize(j+1)
				b[j]=a[i]
				j+=1
			Endif
		Next
		
		If j=0 Then Return 0
		
		Local d:Int = Int(Rnd()*(j))
		
		'Print j+" new:"+d
			
		Return b[d]
		
	End
	
	Method CheckExit:Int(x:Int, y:Int)
		''if we are diagonal or 2 spaces from exit
		'' then make a path To Exit Then mark Exit as visited (as To Not Repeat)
		
		''if it is set to visited, then we already have a path to exit
		If map[endx][endy] <>_END Then Return 0
		
		If (y-2>=0 And map[x][y-2]=_END) Then SetExit(); Return 1
		If (y+2<=height-1 And map[x][y+2]=_END) Then SetExit(); Return 1
		If (x-2>=0 And map[x-2][y]=_END) Then SetExit(); Return 1
		If (x+2<=width-1 And map[x+2][y]=_END) Then SetExit(); Return 1
		
		If (y-1>=0)
			If x-1>=0 And map[x-1][y-1]=_END Then SetExit(); Return 1
			If x+1<=width-1 And map[x+1][y-1]=_END Then SetExit(); Return 1
		Endif
		If (y+1<=height-1)
			If x-1>=0 And map[x-1][y+1]=_END Then SetExit(); Return 1
			If x+1<=width-1 And map[x+1][y+1]=_END Then SetExit(); Return 1
		Endif
		
		If (x-1>=0)
			If y-1>=0 And map[x-1][y-1]=_END Then SetExit(); Return 1
			If y+1<=height-1 And map[x-1][y+1]=_END Then SetExit(); Return 1
		Endif
		If (x+1<=width-1)
			If y-1>=0 And map[x+1][y-1]=_END Then SetExit(); Return 1
			If y+1<=height-1 And map[x+1][y+1]=_END Then SetExit(); Return 1
		Endif
		
		Return 0
		
	End
	
	Method SetExit:Void(i:Int=_VISIT)

		''carve out exit connector
		If endx<>0 And endx<>width-1
			If endy-1>0
				map[endx][endy-1] = _VISIT
			Else
				map[endx][endy+1] = _VISIT
			Endif
		Else
			If endx-1>0
				map[endx-1][endy] = _VISIT
			Else
				map[endx+1][endy] = _VISIT
			Endif
		Endif
		
		hasExit=True
		
		map[endx][endy] = i
	End
	
	Method Cleanup:Void()
		''do we need to cleanup (we have a connection)
		If map[endx][endy] <> _VISIT Then Return
		
		''fill disconnects
		For Local y:Int=0 To height-1
			For Local x:Int=0 To width-1
				If map[x][y]=0 Then map[x][y]=_WALL 
			Next
		Next

		For Local y:Int=0 To height-1
			For Local x:Int=0 To width-1
				If map[x][y]=_VISIT Then map[x][y]=0
			Next
		Next
		
		map[endx][endy]=_END ''reset this
		
	End
End

Class Allocate<T>
	Function Array2D:T[][]( i:Int, j:Int)
	    Local arr:T[][] = New T[i][]
	    For Local ind = 0 Until i
	        arr[ind] = New T[j]
	    Next
	    Return arr		
	End
End

Function Main()
	New Game
End

Class Game Extends App
	Field maze:Maze
	Field blocksize:Int=5
	Field size:Int=20
	Field reset:Bool=False
	
	
	Method OnCreate()
		maze = New Maze(size,size)
		blocksize = DeviceWidth()/(size*2)
		
		SetUpdateRate 30
	End
	
	Method OnUpdate()
		If KeyHit(KEY_1) Then size=10; reset=True
		If KeyHit(KEY_2) Then size=20; reset=True
		If KeyHit(KEY_3) Then size=30; reset=True
		If KeyHit(KEY_4) Then size=40; reset=True
		If KeyHit(KEY_5) Then size=50; reset=True
		If KeyHit(KEY_6) Then size=60; reset=True
		If KeyHit(KEY_Z) Then reset=True
		
		If KeyHit(KEY_SPACE) Then maze.MazeStep
		
		If reset
			reset=False
			maze = New Maze(size,size)
			blocksize = DeviceWidth()/(size*1.5)
		End
	End
	
	Method OnRender()
		Cls 0,0,0
		If maze
			SetColor(150,150,150)
			For Local y:Int=0 To maze.height-1
				For Local x:Int=0 To maze.width-1
					If maze.map[x][y]=maze._WALL Then DrawRect(x*blocksize,y*blocksize,blocksize,blocksize)
					If maze.map[x][y]=maze._VISIT Then SetColor(255,150,150);DrawRect(x*blocksize,y*blocksize,blocksize,blocksize);SetColor(150,150,150)
					If maze.map[x][y]=maze._START Then SetColor(150,255,150);DrawRect(x*blocksize,y*blocksize,blocksize,blocksize);SetColor(150,150,150)
					If maze.map[x][y]=maze._END Then SetColor(150,150,255);DrawRect(x*blocksize,y*blocksize,blocksize,blocksize);SetColor(150,150,150)
				Next
			Next
		Endif
	End
End

Tri|Ga|De

(Posted 2013) [#2]

Is this playable?
If yes how do I do it.

Gerry Quinn

(Posted 2013) [#3]

Just copy the lot into a Monkey file and run it (HTML is fastest)

It seems to generate some disconnected areas, it would be worth while detecting and removing those. But a nice maze, in general.

Halfdan

(Posted 2013) [#4]

Is this playable?
If yes how do I do it.

Take a screenshot, print it then you will just need a pen

Lots of fun!

AdamRedwoods

(Posted 2013) [#5]

It seems to generate some disconnected areas, it would be worth while detecting and removing those.

updated.

p.s. this could be enhanced to create "rooms" and then you have a nice D&D map.

impixi

(Posted 2013) [#6]

Nice. You inspired me to post my own updated maze/dungeon generation code here in the archives. :)