ID:161242
 
Well, uh, I have a problem with my maze generator.

maze
var
lowerBounds = null
upperBounds = null

list/area = null

turf/wallType = /turf/wall
turf/floorType = /turf/floor

New(turf/_lowerBounds, turf/_upperBounds)
lowerBounds = _lowerBounds
upperBounds = _upperBounds
area = block(lowerBounds, upperBounds)

proc
generate(seed)
if(!seed)
seed = world.realtime

else
rand_seed(seed)

generateMaze()

generateMaze()
var
list/unvisited = area
list/visited = list()
turf/currentCell = pick(unvisited)

unvisited -= currentCell
visited += currentCell

while(length(unvisited))
var
randomDirs = list(1, 2, 4, 8)
randomDir = pick(randomDirs)
turf/C = null

while(!length(randomDirs) ||\
!get_step(currentCell, randomDir) ||\
!(get_step(currentCell, randomDir) in area) ||\
(get_step(currentCell, randomDir) in visited))
randomDirs -= randomDir

if(length(randomDirs))
randomDir = pick(randomDirs)

else
break

if(!length(randomDirs))
currentCell = pick(visited - currentCell)

continue

C = get_step(currentCell, randomDir)
new/turf/floor(C)

currentCell = C
unvisited -= currentCell
visited += currentCell


It's basically the hunt-and-kill algorithm. It works, but the problem is that there aren't any actual walls in between the passages that are created. It's actually making a maze because if you put a delay in the main while loop you can see it putting the maze together, there's just nothing in between each passage. I don't really know how to fix this. Anyone have any experience in random maze generation that can help me? =/
I've tried using the same algorithm you do, and have gotten exactly the same problem. I only skimmed briefly over your code, but if my suspicions are correct, the problem is that you are creating a floor on every cell you visit, and you are visiting all turfs in the maze (so every cell will be a floor.)

I'm a bit hazy right now, so it's likely that I'm wrong... I'll take some time reading/debugging this later.
In response to DivineO'peanut
Well, I tried reprogramming it.

world
view = "32x32"
turf = /turf/floor

client
perspective = EDGE_PERSPECTIVE

turf
text = " "
wall
text = "#"

floor
text = "."

matrix
New(w, h)
width = w
height = h
size = width * height
data = new/list(width * height)

var
width = 0
height = 0
size = 0
list/data = null

proc
read(x, y)
if(data)
return data[x + (y - 1) * width]

write(x, y, value)
if(data)
data[x + (y - 1) * width] = value

empty()
if(data)
data = new/list(size)

mob
verb
test()
var/maze/test = new(10, 10)
test.generate()

mazeCell
var
x = 0
y = 0
exits = 0

New(_x, _y)
x = _x
y = _y

maze
var
matrix/cells

list/unvisited
list/visited
mazeCell/currentCell

New(width, height)
cells = new/matrix(width, height)

for(var/x = 1, x <= width, x ++)
for(var/y = 1, y <= height, y ++)
cells.write(x, y, new/mazeCell(x, y))

proc
getCell(mazeCell/cell, dir, check = 0)
var
x = cell.x
y = cell.y

switch(dir)
if(NORTH) y ++
if(SOUTH) y --
if(EAST) x ++
if(WEST) x --

if((x < 1) || (x > cells.width) || (y < 1) || (y > cells.height))
return 0

if(check)
if(cells.read(x, y) in visited)
return 0

return 1

else
return cells.read(x, y)

generate()
unvisited = cells.data
visited = list()
currentCell = pick(unvisited)

unvisited -= currentCell
visited += currentCell

while(length(unvisited))
var
list/validDirs
validDir
mazeCell/C

for(var/dir in list(NORTH, SOUTH, EAST, WEST))
if(getCell(currentCell, dir, 1))
if(!validDirs)
validDirs = list()

validDirs += dir

if(!validDirs)
currentCell = pick(visited)

continue

validDir = pick(validDirs)

C = getCell(currentCell, validDir)

currentCell.exits |= validDir
C.exits |= turn(validDir, 180)

unvisited -= C
visited += C

currentCell = C


But of course, it doesn't work. ;/ It usually just freezes up. What the heck am I doing wrong? Someone please help. =/
In response to Koil
The solution is to start removing walls from the open list as you carve out paths next to them. There are two solutions I came up with off the top of my head:

1) when carving, for every wall adjacent to it (cardial directions), increase that wall's counter. If that counter reaches 2, then remove it from the open list.

2) when carving, for every wall in orange(1) of it, increase that wall's counter. If that counter reaches 3, then remove it from the open list.

Both will give you a maze, however in either one (moreso the first) you will find that it results in paths being connected diagonally. Additionally, there may be un-dug chunks of wall, as you can get a configuration where you have, for example, two paths parallel to each other with two spaces in between.

A better solution, I think, would be to initialize the maze as a bunch of individual carved segments surrounded by walls, then use a standard algorithm to dig through those walls. IE:

XXXXX
X X X
XXXXX
X X X
XXXXX
In response to Garthor
Your second solution (about initializing the maze with each floor tile surrounded by walls) is what I used, but the second time I reprogrammed the generator (found in my second post), I'm just using a matrix to hold the maze information instead of the map. It just keeps freezing and being stupid when I run it, though...
Typically maze generation is done by filling in the target area with walls, and carving out as you go. It looks like your algorithm here isn't starting with walls. It's also only taking one step at a time instead of two.

Here's one approach that will work well:

proc/RandomBit(n)
var/b = n
var/count = 0
for(b=n, b, b&=b-1) ++count
if(!count) return 0
count = rand(1, count)
for(b=n, b, b&=b-1)
if(!--count)
return b ^ (b & (b-1))
return 0

proc/Generate()
var/x1,x2,y1,x2
x1 = lowerBounds.x + 1
y1 = lowerBounds.y + 1
x2 = upperBounds.x - 1
y2 = upperBounds.y - 1

var/list/floorbits = new
var/list/region = new
var/list/next = new
var/list/prev = new
var/turf/T
var/turf/T2
var/turf/Tprev
var/turf/T2prev

for(T in block(lowerBounds, upperBounds))
if((T.x - x1) % 2 || (T.y - y1) % 2)
new wallType(T)
else
new floorType(T)
var/bits = 0
if(T.x-1 > x1) bits |= WEST
if(T.x+1 < x2) bits |= EAST
if(T.y-1 > y1) bits |= SOUTH
if(T.y+1 < y2) bits |= NORTH
floorbits[T] = bits
region[T] = T
next[T] = T
prev[T] = T

while(floorbits.len)
T = pick(floorbits)
var/dir = RandomBit(floorbits[T])
floorbits[T] &= ~dir
if(!floorbits[T]) floorbits -= T
for(T2 = get_step(T, dir); T2; T2 = get_step(T2, dir))
if(istype(T2, floorType)) break
if(!T2)
// this should never happen
continue
floorbits[T2] &= ~turn(dir, 180)
if(!floorbits[T2]) floorbits -= T2
// are these turfs in the same region?
if(region[T2] == region[T])
continue
// fill in floors
for(T2 = get_step(T, dir); T2; T2 = get_step(T2, dir))
if(istype(T2, floorType)) break
new floorType(T2)
// join the regions
T = region[T]
T2 = region[T2]
Tprev = prev[T]
T2prev = prev[T2]
prev[T2] = Tprev
prev[T] = T2prev
next[T2prev] = T
next[Tprev] = T2
while(T2 != T)
region[T2] = T
T2 = next[T2]


That approach should grow the maze by picking random available cells and joining them into larger and larger regions. The region, prev, and next lists all function as a set of circular doubly-linked lists; region is the "head" of each list, and prev/next join each turf to the next in the chain.

Lummox JR
In response to Lummox JR
An additional note: If the idea of using what is effectively a set of doubly-linked lists seems confusing, you can do this with a crapload of regular lists. The problem then is that you want to make sure you don't run out of them. Or, you can use a single list and just grow out from a specific region:

proc/Generate()
var/x1,x2,y1,x2
x1 = lowerBounds.x + 1
y1 = lowerBounds.y + 1
x2 = upperBounds.x - 1
y2 = upperBounds.y - 1

var/bits
var/list/floorbits = new
var/list/exploring = new
var/turf/T
var/turf/T2

for(T in block(lowerBounds, upperBounds))
if((T.x - x1) % 2 || (T.y - y1) % 2)
new wallType(T)
else
new floorType(T)
bits = 0
if(T.x-1 > x1) bits |= WEST
if(T.x+1 < x2) bits |= EAST
if(T.y-1 > y1) bits |= SOUTH
if(T.y+1 < y2) bits |= NORTH
floorbits[T] = bits

// keep one region and expand from there
T = pick(floorbits)
exploring[T] = floorbits[T]
floorbits -= T

while(floorbits.len) // done when the last turf has been explored
T = pick(exploring)
var/dir = RandomBit(exploring[T])
exploring[T] &= ~dir
if(!exploring[T]) exploring -= T
for(T2 = get_step(T, dir); T2; T2 = get_step(T2, dir))
if(istype(T2, floorType)) break
if(!T2)
// this should never happen
continue
dir = turn(dir, 180)
// was the new turf already found?
bits = floorbits[T2]
if(!bits)
bits = exploring[T2] & ~dir
if(bits) exploring[T2] = bits
else exploring -= T2
continue
bits &= ~dir;
if(bits) exploring[T2] = bits
// fill in floors
for(T2 = get_step(T2, dir); T2 != T; T2 = get_step(T2, dir))
if(istype(T2, floorType)) break
new floorType(T2)


This code is a lot simpler than what I posted before. Any unexplored turfs are in the floorbits list, while the exploring list contains any turfs that are part of the maze structure and may be able to branch off into new passages. The exploring list will grow at first, then start to shrink down, while the floorbits list should shrink every time a new piece is added to the maze.

The maze this algorithm creates should be functionally equivalent to the last one. Complexity of this algorithm should be roughly O(n), n being the number of nodal points in the maze, because it has approximately 2n possible connections it can make (less when you account for the edges), and it will consider every one of them once and only once.

Lummox JR
In response to Lummox JR
Hm, I appreciate the help alot. I've been trying to get a maze generator working for a while now. Anyway, there appears to be a problem with this.

mob
verb
test()
Generate(locate(2, 2, 1), locate(14, 14, 1))

proc
RandomBit(n)
var
b = n
count = 0

for(b = n, b, b &= b - 1)
++ count

if(!count)
return 0

count = rand(1, count)

for(b = n, b, b &= b - 1)
if(!-- count)
return b ^ (b & (b - 1))

return 0

Generate(turf/lowerBounds, turf/upperBounds)
var
x1 = lowerBounds.x + 1
y1 = lowerBounds.y + 1
x2 = upperBounds.x - 1
y2 = upperBounds.y - 1

bits
list/floorbits = new
list/exploring = new

turf/T
turf/T2

for(T in block(lowerBounds, upperBounds))
if((T.x - x1) % 2 || (T.y - y1) % 2)
new/turf/wall(T)

else
new/turf/floor(T)

bits = 0
if(T.x-1 > x1)
bits |= WEST

if(T.x+1 < x2)
bits |= EAST

if(T.y-1 > y1)
bits |= SOUTH

if(T.y+1 < y2)
bits |= NORTH

floorbits[T] = bits

// keep one region and expand from there
T = pick(floorbits)
exploring[T] = floorbits[T]
floorbits -= T

while(floorbits.len) // done when the last turf has been explored
T = pick(exploring)
var/dir = RandomBit(exploring[T])
exploring[T] &= ~dir

if(!exploring[T])
exploring -= T

for(T2 = get_step(T, dir), T2, T2 = get_step(T2, dir))
if(istype(T2, /turf/floor))
break

if(!T2)
// this should never happen
continue

dir = turn(dir, 180)

// was the new turf already found?
bits = floorbits[T2]
if(!bits)
bits = exploring[T2] & ~dir
if(bits)
exploring[T2] = bits

else
exploring -= T2

continue

bits &= ~dir
if(bits)
exploring[T2] = bits

// fill in floors
for(T2 = get_step(T2, dir), T2 != T, T2 = get_step(T2, dir))
if(istype(T2, /turf/floor))
break

new/turf/floor(T2)


(please excuse the fact that I rewrote it because I like more whitespace in my code. <_<)

Anyway, when I test generate a maze, I get a <code>pick() from empty list</code> runtime for the line <code>T = pick(exploring)</code> just under the <code>while(floorbits.len)</code>. I thought maybe making the while loop <code>while(floorbits.len && exploring.len)</code> would fix it, and it did stop the runtime error, however, a maze is not actually generated. It gives me this:



Again, I appreciate your help. However, could you elaborate a tad more on how this works? I don't quite understand it.
In response to Koil
I realize it hasn't been 24 hours yet or whatever the time limit is, but this post got 2 pages back so quick so I was afraid you might of missed my previous post...