[BMAX] Maze generation problems.

[Pixel_Outlaw]

I cannot find the problem with my maze generation program. It is so close do being done yet there is a simple problem. You will notice that there is a clear path around the outside of three of the sides this is not desirable and I cannot figure out why it happens consistently.

The algorithm is very simple.

Fill an array with cells.
Each cell has a visited variable initially set to false.

1. Find a visited cell that touched an unvisited cell and knock down the wall separating them
2. set the the cell's visited value to true

repeat


Ah well, maybe my code will work better. It is pretty damn fast too!

Code: [Select]

Strict

'map generator Ryan Burnside 2008
'may lead to erectile dysfunction
'use two applications daily
'consult your doctor as needed
 
SeedRnd(MilliSecs())
Global columns:Int = 220
Global rows:Int = 199
Global cell_width:Float = 3
Global temp_map:cell[columns, rows]
Global visited_list:TList = New TList ' holds cells that need to be visited

' fills array with a way to store wall and visited data
Type cell
' directional n,e,s,w are used in drawing walls
Field n:Int = 1, e:Int = 1, s:Int = 1, w:Int = 1, visited = 0,x:Int, y:Int
End Type

' this holds positions in an array-a wrapper object
Type position
Field x:Int, y:Int
EndType

' seed array with cells
For Local x = 0 To columns - 1
For Local y = 0 To rows - 1
Local s:cell = New cell
Local c:cell = New cell
c.x = x
c.y = y
c.n = 1
c.e = 1
c.w = 1
c.s = 1
c.visited = 0
temp_map[x, y] = c
Next
Next

' draw the cells
Function draw()

For Local x = 0 To columns - 1
For Local y = 0 To rows - 1
' set some placeholders to cut down on drawing time
Local a:Float = x * cell_width
Local b:Float = y * cell_width
If temp_map[x, y].n
DrawLine(a, b, a + cell_width, b)
End If
If temp_map[x, y].s
DrawLine(a, b + cell_width, a + cell_width, b + cell_width)
End If
If temp_map[x, y].w
DrawLine(a, b, a, b + cell_width)
End If
If temp_map[x, y].e
DrawLine(a + cell_width, b, a + cell_width, b + cell_width)
End If


Next
Next
EndFunction

' removes a wall between a given position and a touching visited cell
Function remove_wall(choose_x:Float, choose_y:Float)

' set up a string of possible directions
Local directions:String = ""
' choose a neighbouring cell that has been visited and connect

' north cell possible?
If choose_y - 1 >= 0 And temp_map[choose_x, choose_y - 1].visited = True
directions:+"n"
End If

' east cell possible?
If choose_x + 1 <= columns - 1 And temp_map[choose_x + 1, choose_y].visited = True
directions:+"e"
End If

' south cell possible?
If choose_y + 1 <= rows - 1 And temp_map[choose_x, choose_y + 1].visited = True
directions:+"s"
End If

'west cell possible?
If choose_x - 1 >= 0 And temp_map[choose_x - 1, choose_y].visited = True
directions:+"w"
EndIf

'shuffle the string and take the firest digit
If directions.Length > 0
Local start_slice = Rand(0, directions.Length - 1)
Local end_slice = start_slice + 1
directions = directions[start_slice..end_slice]
' this may be imperfect

Select directions
Case "n"
temp_map[choose_x, choose_y - 1].s = False
temp_map[choose_x, choose_y].n = False
Case "e"
temp_map[choose_x + 1, choose_y].w = False
temp_map[choose_x, choose_y].e = False
Case "s"
temp_map[choose_x, choose_y + 1].n = False
temp_map[choose_x, choose_y].s = False
Case "w"
temp_map[choose_x - 1, choose_y].e = False
temp_map[choose_x, choose_y].w = False
End Select
End If

End Function

' add non visited touching cells to the visited list
Function add_touching(choose_x:Float, choose_y:Float)
' set up a position to add to the list if need be
Local P:position = New position

' add the neighbouring cells that have not been visited and are connected

' north cell possible?
If choose_y - 1 >= 0
If temp_map[choose_x, choose_y - 1].visited = False
p.x = choose_x
p.y = choose_y - 1
ListAddFirst(visited_list, p)
EndIf
End If

' east cell possible?
If choose_x + 1 <= columns - 1
If temp_map[choose_x + 1, choose_y].visited = False
p.x = choose_x + 1
p.y = choose_y
ListAddFirst(visited_list, p)
EndIf
End If

' south cell possible?
If choose_y + 1 <= rows - 1
If temp_map[choose_x, choose_y + 1].visited = False
p.x = choose_x
p.y = choose_y + 1
ListAddFirst(visited_list, p)
EndIf
End If

'west cell possible?
If choose_x - 1 >= 0
If temp_map[choose_x - 1, choose_y].visited = False
p.x = choose_x - 1
p.y = choose_y
ListAddFirst(visited_list, p)
EndIf
EndIf

End Function

' combind remove_wall and add_touching with logic
Function carve()
' start the first cell, set the visited to true and add to the unvisited list
temp_map:cell[columns - 1, 0].visited = True

Local a:position = New position
a.x = columns - 1
a.y = 0
ListAddLast(visited_list, a)
 
While CountList(visited_list) > 0
' 1 visit a random cell from the unvisited list
' 2 knock down a wall connected from the chosen cell to a visited cell
' 3 set visited to true
' 4 add neighbours that are unvisited
' 5 remove chosen from unvisited list

Local chosen:position = position(visited_list.ValueAtIndex(Rand(0, CountList(visited_list) - 1)))
Local choose_x:Int = chosen.x
Local choose_y:Int = chosen.y

remove_wall(choose_x, choose_y)
temp_map[choose_x, choose_y].visited = True
add_touching(choose_x, choose_y)

For Local l:position = EachIn(visited_list)
If l.x = choose_x And l.y = choose_y
ListRemove(visited_list, l)
End If
Next
 
Wend
End Function


Graphics (800, 600)  ' start demo
carve()
draw()
Flip
WaitKey()

Here is a pic, you will see the undesirable paths along three of the sides.

I think the problem might be in the way I'm using slices in the remove_wall(choose_x:Float, choose_y:Float) function.

[Paul]

I haven't got time to look at your code, but you could just crop the image after it's done, just ignore the first line of pixels?

[rain_storm]

cropping is a fast solution you might also be able to work around it with a pseudo random number generator and then run that value through the built in random function. They are preatty easy to build here is one I made myself the numbers generated do not repeat not even once within the tested range (65536 calls = 65536 seemingly random returns after that though the entire sequence repeats perfectly)  they are not truely random but that may be a good thing in this case because a truely random maze will never be perfect.

Code: [Select]

range = 65535 // maximum value to be returned
s = 7 // required so that [seed = 0] will not break the generator
p = 5 // modifies the seed to produce a new seed value
sub rnd()
  // 2048  unique numbers ... seed = 2 + and(mod(15, seed)*seed, 65535)
  // 4096  unique numbers ... seed = 2 + and(mod(7, seed)*seed, 65535)
  // 8192  unique numbers ... seed = 1024 + and(mod(7, seed)*seed, 65535)
  // 16384 unique numbers ... seed = 4096 + and(mod(3, seed)*seed, 65535)
  // 16384 unique numbers ... seed = 4096 + and(mod(11, seed)*seed, 65535)
  // 16536 unique numbers ... seed = 4 + and(mod(13, seed)*seed, 65535)
  // 22428 unique numbers ... seed = 4 + and(mod(17, seed)*seed, 65535)
  // 32254 unique numbers ... seed = 3 + and(mod(5, seed)*seed, 65535)
  // 32768 unique numbers ... seed = 5 + and(mod(3, seed)*seed, 65535)
  // 65536 unique numbers ... seed = 7 + and(mod(5, seed)*seed, 65535)
  local seed
  seed = s + and(mod(p, seed)*seed, range)
  return and(seed-s, range)
end sub


[Pixel_Outlaw]

I was able to fix the problem. I wanted to reuse a cell object in the function that found unvisited neighbouring cells. I never changed the cell object between adding it to the list and this caused the problem.


Edited code if anyone wants.

Code: [Select]

Strict

Framework brl.GLMax2D
Import BRL.Random


SetGraphicsDriver GLMax2DDriver()
AppTitle = "Ryan Burnside 2008"

'map generator Ryan Burnside 2008
'use two applications daily
'consult your doctor as needed
 
SeedRnd(MilliSecs())
Global columns:Int = 100
Global rows:Int = 100
Global cell_width:Float = 4
Global temp_map:cell[columns, rows]
Global visited_list:TList = New TList ' holds cells that need to be visited

' fills array with a way to store wall and visited data
Type cell
' directional n,e,s,w are used in drawing walls
Field n:Int = 1, e:Int = 1, s:Int = 1, w:Int = 1, visited = 0,x:Int, y:Int
End Type

' this holds positions in an array-a wrapper object
Type position
Field x:Int, y:Int
EndType

' seed array with cells
For Local x = 0 To columns - 1
For Local y = 0 To rows - 1
Local s:cell = New cell
Local c:cell = New cell
c.x = x
c.y = y
c.n = 1
c.e = 1
c.w = 1
c.s = 1
c.visited = 0
temp_map[x, y] = c
Next
Next

' draw the cells
Function draw()

For Local x = 0 To columns - 1
For Local y = 0 To rows - 1
' set some placeholders to cut down on drawing time
Local a:Float = x * cell_width
Local b:Float = y * cell_width
If temp_map[x, y].n
DrawLine(a, b, a + cell_width, b)
End If
If temp_map[x, y].s
DrawLine(a, b + cell_width, a + cell_width, b + cell_width)
End If
If temp_map[x, y].w
DrawLine(a, b, a, b + cell_width)
End If
If temp_map[x, y].e
DrawLine(a + cell_width, b, a + cell_width, b + cell_width)
End If


Next
Next
EndFunction

' removes a wall between a given position and a touching visited cell
Function remove_wall(choose_x:Float, choose_y:Float)

' set up a string of possible directions
Local directions:String = ""
' choose a neighbouring cell that has been visited and connect

' north cell possible?
If choose_y - 1 >= 0 And temp_map[choose_x, choose_y - 1].visited = True
directions:+"n"
End If

' east cell possible?
If choose_x + 1 <= columns - 1 And temp_map[choose_x + 1, choose_y].visited = True
directions:+"e"
End If

' south cell possible?
If choose_y + 1 <= rows - 1 And temp_map[choose_x, choose_y + 1].visited = True
directions:+"s"
End If

'west cell possible?
If choose_x - 1 >= 0 And temp_map[choose_x - 1, choose_y].visited = True
directions:+"w"
EndIf

'shuffle the string and take the firest digit
If directions.Length > 0
Local start_slice = Rand(0, directions.Length - 1)
Local end_slice = start_slice + 1

directions = directions[start_slice..end_slice]
Select directions
Case "n"
temp_map[choose_x, choose_y - 1].s = False
temp_map[choose_x, choose_y].n = False
Case "e"
temp_map[choose_x + 1, choose_y].w = False
temp_map[choose_x, choose_y].e = False
Case "s"
temp_map[choose_x, choose_y + 1].n = False
temp_map[choose_x, choose_y].s = False
Case "w"
temp_map[choose_x - 1, choose_y].e = False
temp_map[choose_x, choose_y].w = False
End Select
End If

End Function

' add non visited touching cells to the visited list
Function add_touching(choose_x:Float, choose_y:Float)
' set up a position to add to the list if need be

' add the neighbouring cells that have not been visited and are connected

' north cell possible?
If choose_y - 1 >= 0
If temp_map[choose_x, choose_y - 1].visited = False
Local n:position = New position
n.x = choose_x
n.y = choose_y - 1
ListAddFirst(visited_list, n)
EndIf
End If

' east cell possible?
If choose_x + 1 <= columns - 1
If temp_map[choose_x + 1, choose_y].visited = False
Local e:position = New position
e.x = choose_x + 1
e.y = choose_y
ListAddFirst(visited_list, e)
EndIf
End If

' south cell possible?
If choose_y + 1 <= rows - 1
If temp_map[choose_x, choose_y + 1].visited = False
Local s:position = New position
s.x = choose_x
s.y = choose_y + 1
ListAddFirst(visited_list, s)
EndIf
End If

'west cell possible?
If choose_x - 1 >= 0
If temp_map[choose_x - 1, choose_y].visited = False
Local w:position = New position
w.x = choose_x - 1
w.y = choose_y
ListAddFirst(visited_list, w)
EndIf
EndIf

End Function

' combind remove_wall and add_touching with logic
Function carve()
' start the first cell, set the visited to true and add to the unvisited list
While CountList(visited_list) > 0
' 1 visit a random cell from the unvisited list
' 2 knock down a wall connected from the chosen cell to a visited cell
' 3 set visited to true
' 4 add neighbours that are unvisited
' 5 remove chosen from unvisited list

Local chosen:position = position(visited_list.ValueAtIndex(Rand(0, CountList(visited_list) - 1)))
Local choose_x:Int = chosen.x
Local choose_y:Int = chosen.y

remove_wall(choose_x, choose_y)
temp_map[choose_x, choose_y].visited = True
add_touching(choose_x, choose_y)
For Local l:position = EachIn(visited_list)
If l.x = choose_x And l.y = choose_y
ListRemove(visited_list, l)
End If
Next
Wend
End Function


Graphics (800, 600)     ' start demo
Local a:position = New position
a.x = 0
a.y = 0
ListAddLast(visited_list, a)

carve()
draw()
visited_list.Clear()
Flip
WaitKey()

Also here is the .exe which makes a moderate sized maze. It uses the "hunt and kill" algorithm.