Ye olde maze game generator.

Community Forums/Showcase/Ye olde maze game generator.

Ryan Burnside

(Posted 2009) [#1]

I sort of miss the old style maze games so I am working on a little generator that should make some interesting procedural levels. Now there are more maze games than Pacman but this is a mock up. I won't release the code until I get it running well. These levels are nice because they don't have dead ends that would stop a player in their tracks. There are some dead ends around the outside if you look but those will loop around when the engine is done. :)

Vorderman

(Posted 2009) [#2]

Could be really fun with 4 players at once and about 50 ghosts!

Ryan Burnside

(Posted 2009) [#3]

You could make a game like that with this.
Many players memorize winning patterns at Pacman's tables, it would be hard to memorize 65,535 possible table combinations however! So you have 65,535 possible levels of any reasonable size at your disposal with this system.

However the genre is more than just Pacman. Many of the maze type games like Amidar, Beserk, Pepper II, Rally X, Lady Bug and Wizard of Wor had unique playing styles and had little to do with eating dots. So, this is not limited to just Pacman clones (I think there are enough already).

Retimer

(Posted 2009) [#4]

Off-topic: what ever happened to that dungeon rpg of yours? I enjoyed playing that when I was away from my dev pc.

Ryan Burnside

(Posted 2009) [#5]

I have never made an RPG, I did however make a dungeon generator for the old roguelike games...

_Skully

(Posted 2009) [#6]

BTW: If you go through the maze and remove any walls that don't have any more than 1 adjacent wall you get rooms

ImaginaryHuman

(Posted 2009) [#7]

And combine the 4-player 50-ghost idea with `bomberman` style bomb-laying gameplay.

Vorderman

(Posted 2009) [#8]

Imagine that - 100 player Bomberman over the net....!!!

Ryan Burnside

(Posted 2009) [#9]

OK, I have got everything generating OK.

This generates a structure of tiles. Each tile in the array has walls, so you simply use the tiles to dictate character movement. I hvae not fleshed out a game yet but this is just a tool to generate a maze of tiles for your project. I will probably clean up the code a bit later. This is for blitzmax.

'///////////////////////////////////////////////////////////////
' ***maze generator***
' Ryan Burnside 2008 (Pixel_Outlaw)
'///////////////////////////////////////////////////////////////

'///////////////////////////////////////////////////////////////
' algorithem overview
' seed an array with cells that have 4 walls
' (a) choose 1 cell do a random walk untill a dead end is reached (knocking down walls between this cell and the former)
' do a check for cells that border already visited cells adding them to a waiting list
' pick a new cell from the waiting list and knock down a wall to a visited cell
' go to (a)
'///////////////////////////////////////////////////////////////

SuperStrict

AppTitle = "Random Walk Maze by Ryan Burnside 2008 B=Binary maze, L=line maze, D=dungeon"

SeedRnd(MilliSecs())
Global length:Int = 28   ' maze length |<--------->|
Global height:Int = 14 ' maze height
Global cell_width:Float = 16


Type cell
	Field n:Byte, e:Byte, s:Byte, w:Byte, u:Byte
EndType

Type position
	Field x:Int, y:Int
End Type

' create our array of cells
Global array:cell[length, height]
 
'holds cells waiting to be worked with
Global waiting_list:TList = New TList

'seed the array with cells
For Local x:Int = 0 To length - 1
	For Local y:Int = 0 To height - 1
		Local c:cell = New cell
		c.n = 1
		c.s = 1
		c.e = 1
		c.w = 1
		c.u = 1
		array[x, y] = c
	Next
Next

'function to take a random walk
Function rand_walk()
	' find all possible border cells

	Local list_length:Int = CountList(waiting_list)
	While list_length > 0

		Local chosen:position = position(waiting_list.ValueAtIndex(Rand(0, list_length - 1)))
 
		' starting square
		Local current_x:Int = chosen.x
		Local current_y:Int = chosen.y
		attach_former(current_x, current_y)
		While 1
			'1 find next cell from current x and y randomly if possible else exit
			'2 mark current x and y as visited
			'3 knock down wall between
			array[current_x, current_y].u = 0
	
			Local a:Int[] = select_next(current_x, current_y)
			' end prematurly if no passage is found
			If a[0] = current_x And a[1] = current_y
				Return
			Else
				current_x = a[0]
				current_y = a[1]
			End If
	
			
		Wend
	Wend
EndFunction

'function to select the next cell to walk from
Function select_next:Int[] (current_x:Int, current_y:Int)
	' store our x and y point into a returnable array
	Local return_array:Int[2]
	Local choices:String = ""

	' check cell to north, is it unvisited?
	If current_y - 1 >= 0
		If array[current_x, current_y - 1].u
			choices:+"n"
		EndIf
	End If
	' check to east
	If current_x + 1 <= length - 1
		If array[current_x + 1, current_y].u
			choices:+"e"
		EndIf
	End If
	'check to the south
	If current_y + 1 <= height - 1
		If array[current_x, current_y + 1].u
			choices:+"s"
		EndIf
	End If
	'check to the west
	If current_x - 1 >= 0
		If array[current_x - 1, current_y].u
			choices:+"w"
		EndIf
	End If


	' now select a random position from the alloted choices
	If choices.length > 0

		Local selection:String = Chr(choices[Rand(0, choices.length - 1)])
	 
		Select selection
			Case "n"
				return_array[0] = current_x
				return_array[1] = current_y - 1
				array[current_x, current_y - 1].s = 0
				array[current_x, current_y].n = 0
				Return return_array
			Case "e"
				return_array[0] = current_x + 1
				return_array[1] = current_y
				array[current_x + 1, current_y].w = 0
				array[current_x, current_y].e = 0
				Return return_array
			Case "s"
				return_array[0] = current_x
				return_array[1] = current_y + 1
				array[current_x, current_y + 1].n = 0
				array[current_x, current_y].s = 0
				Return return_array
			Case "w"
				return_array[0] = current_x - 1
				return_array[1] = current_y
				array[current_x - 1, current_y].e = 0
				array[current_x, current_y].w = 0
				Return return_array
		
		End Select
	Else
		return_array[0] = current_x
		return_array[1] = current_y
		Return return_array
	EndIf

End Function

Function add_waiting_best()
	' executed before each random walk (not during) 
	' scan through the entire array add all unvisited cells that have one visited neighbour to the waiting list

	' clear the list
	waiting_list.Clear()

	'Why is this better than add_waiting?
	' 1 pick a random start position in the array
	' 2 loop untill a position is found that is unvisited and has a neighbour
	' 3 return one position- no list making and clearing, no extra computations 

	Local x:Int = Rand(0, length - 1)
	Local y:Int = Rand(0, height - 1)
	Local max_turns:Int = length * height
	Local visited:Int = 0
	While 1
		visited:+1
		' if this cell is unvisited (condition 1) and has a visited neighbour (condition 2)
		If array[x, y].u

			If y - 1 >= 0
				If Not array[x, y - 1].u
					Local p:position = New position
					p.x = x
					p.y = y
					ListAddLast(waiting_list, p)
					Return
				EndIf
			End If

			' check to east
			If x + 1 <= length - 1
				If Not array[x + 1, y].u
					Local p:position = New position
					p.x = x
					p.y = y
					ListAddLast(waiting_list, p)
					Return
				EndIf
			End If

			'check to the south
			If y + 1 <= height - 1
				If Not array[x, y + 1].u
					Local p:position = New position
					p.x = x
					p.y = y
					ListAddLast(waiting_list, p)
					Return
				EndIf
			End If

			'check to the west
			If x - 1 >= 0
				If Not array[x - 1, y].u
					Local p:position = New position
					p.x = x
					p.y = y
					ListAddLast(waiting_list, p)
					Return
				EndIf
			End If
		EndIf
		x:+1
		If x > length - 1
			x = 0
			y:+1
			If y > height - 1
				y = 0
			End If
		End If

		If x > length - 1
			x = 0
		End If
		If y > height - 1
			y = 0
		End If
		If visited > max_turns
			Return
		EndIf
	Wend
End Function

Function attach_former(x:Int, y:Int)
	Local order:String = ""

	'check to north
	If y - 1 >= 0
		If Not array[x, y - 1].u
			order:+"n"
		EndIf
	End If

	' check to east
	If x + 1 <= length - 1
		If Not array[x + 1, y].u
			order:+"e"
		EndIf
	End If

	'check to the south
	If y + 1 <= height - 1
		If Not array[x, y + 1].u
			order:+"s"
		EndIf
	End If

	'check to the west
	If x - 1 >= 0
		If Not array[x - 1, y].u
			order:+"w"
		EndIf
	End If

	' select random neighbor
	If order.length > 0
		order = Chr(order[Rand(0, order.length - 1)])

		Select order
			Case "n"
				array[x, y - 1].s = 0
				array[x, y].n = 0
				Return
			Case "e"
				array[x + 1, y].w = 0
				array[x, y].e = 0
				Return
			Case "s"
				array[x, y + 1].n = 0
				array[x, y].s = 0
				Return
			Case "w"
				array[x - 1, y].e = 0
				array[x, y].w = 0
				Return
		End Select

	EndIf

End Function

Function draw()
	
	Cls
	
	For Local x:Int = 0 To length - 1
		For Local y:Int = 0 To height - 1
			'draw here
			SetColor(0, 255, 0)
			Local c:cell = array[x, y]
			Local a:Float = x * cell_width + 3
			Local b:Float = y * cell_width + 3
			
			' draw the walls
			If c.n
				DrawLine(a, b, a + cell_width, b)
			End If
			If c.e
				DrawLine(a + cell_width, b, a + cell_width, b + cell_width)
			End If
			If c.s
				DrawLine(a, b + cell_width, a + cell_width, b + cell_width)
			End If
			If c.w
				DrawLine(a, b, a, b + cell_width)
			End If
			
			' fake pac-man dot	
			DrawOval(a + cell_width / 2.0 - 1, b + cell_width / 2.0 - 1, 3, 3)
			
		Next
	Next
	
	' the clever
	DrawOval(16, 320, 128, 128)
	SetColor(0, 0, 0)
	For Local y:Int = 320 To 480 Step 2
		DrawLine(16, y, 160, y)
	Next
	SetColor(0, 255, 0)
	DrawOval(20, 324, 96, 96)
	SetColor(0, 0, 0)
	DrawOval(48, 348, 16, 16)
	SetRotation(- 45.0)
	DrawRect(80, 384, 64, 64)
	SetRotation(0)
EndFunction

Function remove_ends()
	For Local x:Int = 0 To length - 1
		For Local y:Int = 0 To height - 1
			'draw here
			Local c:cell = array[x, y]
			' store the possible walls for removal in a string
			Local removable:String = ""
			Local results:Int = 0
			If c.n And y <> 0
				removable:+"n"
				results:+1
			End If
			
			If c.e And x <> length - 1
				removable:+"e"
				results:+1
			End If
			
			If c.s And y <> height - 1
				removable:+"s"
				results:+1
			End If
			
			If c.w And x <> 0
				removable:+"w"
				results:+1
			End If
			
			
			If c.n + c.e + c.w + c.s > 2 ' if is a dead end
				'select the wall that is the dead end wall
				Local p:String = ""
				'north wall?
				If c.w And c.n And c.e
					p = "n"
				End If
				
				'east wall?
				If c.n And c.e And c.s
					p = "e"
				End If
				
				'south wall?
				If c.e And c.s And c.w
					p = "s"
				End If
				
				'west wall?
				If c.s And c.w And c.n
					p = "w"
				End If
				
				
				' select wall that was chosen
				Select p
					Case "n"
						c.n = False
						
						If y - 1 >= 0
							array[x, y - 1].s = False
						Else
							array[x, height - 1].s = False
						EndIf
						
					Case "e"
						c.e = False
						
						If x + 1 <= length - 1
							array[x + 1, y].w = False
						Else
							array[0, y].w = False
						EndIf
						
					Case "s"
						c.s = False
						If y + 1 <= height - 1
						array[x, y + 1].n = False
						Else
						array[x, 0].n = False
						EndIf
			
					Case "w"
						c.w = False
						If x - 1 >= 0
						array[x - 1, y].e = False
						Else
						array[x + length - 1, y].e = False
						EndIf
				End Select
			
			EndIf
		Next
	Next
EndFunction

array[length / 2, height / 2].u = 0
add_waiting_best()

While CountList(waiting_list) > 0
	add_waiting_best()
	rand_walk()
Wend

remove_ends()
Graphics 640, 480
SetClsColor(0, 0, 0)

While Not KeyDown(KEY_ESCAPE)
	' draw line maze if l is pressed

	Cls
	SetColor(0, 0, 0)
	draw
	Flip
	
	If KeyHit(KEY_SPACE)
		For Local x:Int = 0 To length - 1
			For Local y:Int = 0 To height - 1
			array[x, y].n = True
			array[x, y].e = True
			array[x, y].s = True
			array[x, y].w = True
			array[x, y].u = True
			
			Next
		Next
		array[length / 2, height / 2].u = 0
		add_waiting_best()

		While CountList(waiting_list) > 0
			add_waiting_best()
			rand_walk()
		Wend

		remove_ends()
	End If

Wend

SpaceAce

(Posted 2009) [#10]

Long, long ago I wrote a generator that creates perfect mazes (exactly one path between any two points in the maze.) I also wrote code to spawn entry and exit points, and rudimentary AI (with built-in error percentages and decision making delays to create a variety of skill levels) to run through the maze. The code is 100% working and very efficient. I never posted it on the forums, but if you run into any stumbling blocks, I can probably help you.

SpaceAce

Chroma

(Posted 2009) [#11]

Hey SpaceAce..would you mind posting your code too? I'd like to take a peek at it.

impixi

(Posted 2009) [#12]

@Chroma:
In case you haven't already seen it, I posted some maze-generation code in the archives a few years ago: TDungeon. The first example generates a perfect maze.

Ryan Burnside

(Posted 2009) [#13]

The main point of these maze type games is to create mazes that do not have dead ends. I have also mode a maze generator and a dungeon generator. I've been sick but play to show how enemy mosters would work. :)

Ryan Burnside

(Posted 2009) [#14]

I have now wrapped the entire abstraction into a single type. I've also added some new featuers.

I've put some thought into different types of possible levels.

Now when the maze object is created you have some generation options. You can have a normal maze (with dead ends) you can have a maze with no dead ends and you can also have a maze in which long stretches of wall have been reduced. The latter two options can be mixed and matched for different results. When I took a hard look at my former generations I noticed that something didn't look right when compared to games such as Pacman, the problem was that the stretches of walls were very long. To reduce this the new maze type will hunt out and cut out sections of long wall. It is all very hard to explain without you tinkering a bit with the outcomes.

If you simply want pure mazes like the classic Amazing Maze, then you would generate the mazes with dead end removal set to false and also remove_long_walls set to false.

If you want to generate a level with dead ends removed (like the former results) you set dead_end_removal to true. This creates long alleys that loop back and connect without ever ending in a dead end.

If you want to generate levels with long walls removed but dead ends still intact you may opt to set remove_long_walls to true and set remove_dead_ends to false. This would be more ideal for a Bomberman style game.

The final option (which creates more Pacman) like mazes with a high level of multidirectional travel is to set dead end removal to true and also long wall removal to true.

So there you have it, a simple type that can generate 4 types of mazes each very different with profound effects on how a game will be played.

Here is the code, you might want to hack out the draw method as it is just for show.

Have fun.

Normal maze shown here. (Not good for much)

Maze with Dead ends removed

Maze with long wall segments broken up.

Maze with dead ends AND long walls removed. (more like procedural pacman)

'///////////////////////////////////////////////////////////////
' ***maze generator***
' Ryan Burnside 2008 (Pixel_Outlaw)
'///////////////////////////////////////////////////////////////

'///////////////////////////////////////////////////////////////
' algorithem overview
' seed an array with cells that have 4 walls
' (a) choose 1 cell do a random walk untill a dead end is reached (knocking down walls between this cell and the former)
' do a check for cells that border already visited cells adding them to a waiting list
' pick a new cell from the waiting list and knock down a wall to a visited cell
' go to (a)
'///////////////////////////////////////////////////////////////

SuperStrict

Global cell_width:Float = 8


Type cell
	Field n:Byte, e:Byte, s:Byte, w:Byte, u:Byte
EndType

Type position
	Field x:Int, y:Int
End Type

Type maze

	Field array:cell[,], waiting_list:TList = New TList, length:Int, height:Int

	Function create_maze:maze(length:Int, height:Int, remove_dead_ends:Byte = True, remove_long_walls:Byte = True)
		Local m:maze = New maze
		Local a:cell[length, height]
		m.array = a
		m.length = length
		m.height = height
		m.reset()
		
		m.array[length / 2, height / 2].u = 0
		m.add_waiting_best()

		While CountList(m.waiting_list) > 0
			m.add_waiting_best()
			m.rand_walk()
		Wend
		
		If remove_dead_ends
		m.remove_ends()
		EndIf
		
		If remove_long_walls
		m.add_gaps()
		EndIf
		
		Return m
	EndFunction

	Method reset()
		'seed the array with cells
		For Local x:Int = 0 To length - 1
			For Local y:Int = 0 To height - 1
				Local c:cell = New cell
				c.n = 1
				c.s = 1
				c.e = 1
				c.w = 1
				c.u = 1
				array[x, y] = c
			Next
		Next
	End Method

	'function to take a random walk
	Method rand_walk()
		' find all possible border cells

		Local list_length:Int = CountList(waiting_list)
		While list_length > 0

			Local chosen:position = position(waiting_list.ValueAtIndex(Rand(0, list_length - 1)))
 
			' starting square
			Local current_x:Int = chosen.x
			Local current_y:Int = chosen.y
			attach_former(current_x, current_y)
			While 1
				'1 find next cell from current x and y randomly if possible else exit
				'2 mark current x and y as visited
				'3 knock down wall between
				array[current_x, current_y].u = 0
	
				Local a:Int[] = select_next(current_x, current_y)
				' end prematurly if no passage is found
				If a[0] = current_x And a[1] = current_y
					Return
				Else
					current_x = a[0]
					current_y = a[1]
				End If
	
			
			Wend
		Wend
	EndMethod

	'function to select the next cell to walk from
	Method select_next:Int[] (current_x:Int, current_y:Int)
		' store our x and y point into a returnable array
		Local return_array:Int[2]
		Local choices:String = ""

		' check cell to north, is it unvisited?
		If current_y - 1 >= 0
			If array[current_x, current_y - 1].u
				choices:+"n"
			EndIf
		End If
		' check to east
		If current_x + 1 <= length - 1
			If array[current_x + 1, current_y].u
				choices:+"e"
			EndIf
		End If
		'check to the south
		If current_y + 1 <= height - 1
			If array[current_x, current_y + 1].u
				choices:+"s"
			EndIf
		End If
		'check to the west
		If current_x - 1 >= 0
			If array[current_x - 1, current_y].u
				choices:+"w"
			EndIf
		End If


		' now select a random position from the alloted choices
		If choices.length > 0

			Local selection:String = Chr(choices[Rand(0, choices.length - 1)])
	 
			Select selection
				Case "n"
					return_array[0] = current_x
					return_array[1] = current_y - 1
					array[current_x, current_y - 1].s = 0
					array[current_x, current_y].n = 0
					Return return_array
				Case "e"
					return_array[0] = current_x + 1
					return_array[1] = current_y
					array[current_x + 1, current_y].w = 0
					array[current_x, current_y].e = 0
					Return return_array
				Case "s"
					return_array[0] = current_x
					return_array[1] = current_y + 1
					array[current_x, current_y + 1].n = 0
					array[current_x, current_y].s = 0
					Return return_array
				Case "w"
					return_array[0] = current_x - 1
					return_array[1] = current_y
					array[current_x - 1, current_y].e = 0
					array[current_x, current_y].w = 0
					Return return_array
		
			End Select
		Else
			return_array[0] = current_x
			return_array[1] = current_y
			Return return_array
		EndIf

	End Method

	Method add_waiting_best()
		' executed before each random walk (not during) 
		' scan through the entire array add all unvisited cells that have one visited neighbour to the waiting list

		' clear the list
		waiting_list.Clear()

		'Why is this better than add_waiting?
		' 1 pick a random start position in the array
		' 2 loop untill a position is found that is unvisited and has a neighbour
		' 3 return one position- no list making and clearing, no extra computations 

		Local x:Int = Rand(0, length - 1)
		Local y:Int = Rand(0, height - 1)
		Local max_turns:Int = length * height
		Local visited:Int = 0
		While 1
			visited:+1
			' if this cell is unvisited (condition 1) and has a visited neighbour (condition 2)
			If array[x, y].u

				If y - 1 >= 0
					If Not array[x, y - 1].u
						Local p:position = New position
						p.x = x
						p.y = y
						ListAddLast(waiting_list, p)
						Return
					EndIf
				End If

				' check to east
				If x + 1 <= length - 1
					If Not array[x + 1, y].u
						Local p:position = New position
						p.x = x
						p.y = y
						ListAddLast(waiting_list, p)
						Return
					EndIf
				End If

				'check to the south
				If y + 1 <= height - 1
					If Not array[x, y + 1].u
						Local p:position = New position
						p.x = x
						p.y = y
						ListAddLast(waiting_list, p)
						Return
					EndIf
				End If

				'check to the west
				If x - 1 >= 0
					If Not array[x - 1, y].u
						Local p:position = New position
						p.x = x
						p.y = y
						ListAddLast(waiting_list, p)
						Return
					EndIf
				End If
			EndIf
			x:+1
			If x > length - 1
				x = 0
				y:+1
				If y > height - 1
					y = 0
				End If
			End If

			If x > length - 1
				x = 0
			End If
			If y > height - 1
				y = 0
			End If
			If visited > max_turns
				Return
			EndIf
		Wend
	End Method

	Method attach_former(x:Int, y:Int)
		Local order:String = ""

		'check to north
		If y - 1 >= 0
			If Not array[x, y - 1].u
				order:+"n"
			EndIf
		End If

		' check to east
		If x + 1 <= length - 1
			If Not array[x + 1, y].u
				order:+"e"
			EndIf
		End If

		'check to the south
		If y + 1 <= height - 1
			If Not array[x, y + 1].u
				order:+"s"
			EndIf
		End If

		'check to the west
		If x - 1 >= 0
			If Not array[x - 1, y].u
				order:+"w"
			EndIf
		End If

		' select random neighbor
		If order.length > 0
			order = Chr(order[Rand(0, order.length - 1)])

			Select order
				Case "n"
					array[x, y - 1].s = 0
					array[x, y].n = 0
					Return
				Case "e"
					array[x + 1, y].w = 0
					array[x, y].e = 0
					Return
				Case "s"
					array[x, y + 1].n = 0
					array[x, y].s = 0
					Return
				Case "w"
					array[x - 1, y].e = 0
					array[x, y].w = 0
					Return
			End Select

		EndIf

	EndMethod

	Method draw()
	
		Cls
	
		For Local x:Int = 0 To length - 1
			For Local y:Int = 0 To height - 1
				'draw here
				SetColor(0, 255, 0)
				Local c:cell = array[x, y]
				Local a:Float = x * cell_width + 3
				Local b:Float = y * cell_width + 3
			
				' draw the walls
				If c.n
					DrawLine(a, b, a + cell_width, b)
				End If
				If c.e
					DrawLine(a + cell_width, b, a + cell_width, b + cell_width)
				End If
				If c.s
					DrawLine(a, b + cell_width, a + cell_width, b + cell_width)
				End If
				If c.w
					DrawLine(a, b, a, b + cell_width)
				End If
			
			Next
		Next
	EndMethod

	Method remove_ends()
	' this little option removes all dead ends from the maze, looping the edges if necessary
		For Local x:Int = 0 To length - 1
			For Local y:Int = 0 To height - 1
				'draw here
				Local c:cell = array[x, y]
				' store the possible walls for removal in a string
				Local removable:String = ""
				Local results:Int = 0
				If c.n And y <> 0
					removable:+"n"
					results:+1
				End If
			
				If c.e And x <> length - 1
					removable:+"e"
					results:+1
				End If
			
				If c.s And y <> height - 1
					removable:+"s"
					results:+1
				End If
			
				If c.w And x <> 0
					removable:+"w"
					results:+1
				End If
			
			
				If c.n + c.e + c.w + c.s > 2 ' if is a dead end
					'select the wall that is the dead end wall
					Local p:String = ""
					'north wall?
					If c.w And c.n And c.e
						p = "n"
					End If
				
					'east wall?
					If c.n And c.e And c.s
						p = "e"
					End If
				
					'south wall?
					If c.e And c.s And c.w
						p = "s"
					End If
				
					'west wall?
					If c.s And c.w And c.n
						p = "w"
					End If
				
				
					' select wall that was chosen
					Select p
						Case "n"
							c.n = False
						
							If y - 1 >= 0
								array[x, y - 1].s = False
							Else
								array[x, height - 1].s = False
							EndIf
						
						Case "e"
							c.e = False
						
							If x + 1 <= length - 1
								array[x + 1, y].w = False
							Else
								array[0, y].w = False
							EndIf
						
						Case "s"
							c.s = False
							If y + 1 <= height - 1
								array[x, y + 1].n = False
							Else
								array[x, 0].n = False
							EndIf
			
						Case "w"
							c.w = False
							If x - 1 >= 0
								array[x - 1, y].e = False
							Else
								array[x + length - 1, y].e = False
							EndIf
					End Select
			
				EndIf
			Next
		Next
	EndMethod
	
	Method add_gaps()
		' place breaks in long walls
		For Local y:Int = 0 To height - 1
			For Local x:Int = 0 To length - 1
				Local num_walls:Byte = array[x, y].n + array[x, y].e + array[x, y].s + array[x, y].w
				
				' add verticle breaks
				If y <> 0 And y < height - 1
				If array[x, y - 1].e And array[x, y + 1].e And x <> length - 1
					array[x, y].e = False
				End If
				
				
				If array[x, y - 1].w And array[x, y + 1].w And x <> 0
					array[x, y].w = False
				End If
				EndIf
				
				' add horizontal breaks
				If x <> 0 And x <> length - 1
				If array[x - 1, y].n And array[x + 1, y].n And y <> 0
					array[x, y].n = False
				End If
				
				If array[x - 1, y].s And array[x + 1, y].s And y <> height - 1
					array[x, y].s = False
				End If
				EndIf
				
			Next
		Next
	End Method

EndType




Graphics 800, 600
SetClsColor(0, 0, 0)
Global a:maze = maze.create_maze(32, 32, 1, 1)
While Not KeyDown(KEY_ESCAPE)
Cls
a.draw()
Flip
Wend