Is there a general approach to generating a random maze? - One with a guareenteed exit?
I've seen games in the past with random mazes (at least I think they were random..) and have always been interested in how it's done. Not so much the actual code, but at least the steps involved.
In my opinion, random mazes are done at the above way:
Say, the map is a map of blocks. Every X,Y of the map is set True/False. Like block or not block.
At first step, you run through the map using For loops and set randomly every block: True/False.
After that step, there might be a way out of the random maze.
"Might be" is not good for us, so we got to make sure that there is a way out.
This maze is a simple one, so let us say that we start at (1,1) block point and end the maze at the right-bottom block.
Now comes the hard part, make the way from the start to the end.
It's something like this:
Run a visual player the runs through the maze.
You run a while loop. The while stops when the visual player gets to the end.
At each point in the maze, ask the following questions in that certain order:
Am I blocked?
If not, choose randomly which way to go and remove the block.
If yes, ask the next question:
Can I go in a diagonal way?
If yes, choose randomly which way to go and remove the necessary blocks.
If not, choose randomly which way to go.
Well, I didn't check that theory.
Maybe it's missing some parts, but in general, that's the idea.
You know, with that question, you got me trying it.
Thank you.
I hope you'll get great results from that plan.
Arie.
I haven't written this code and I'm not sure I understand how it works... But it does work very well.
It's written by "David Brebner, Unlimited Realities"
VB Code:
Private Sub create_maze()
'clear maze
For a% = 1 To 29
For b% = 1 To 29
mz%(a%, b%) = 0
Next
Next
'make border
For a% = 0 To 30
mz%(a%, 0) = 1
mz%(a%, 30) = 1
mz%(0, a%) = 1
mz%(30, a%) = 1
Next
'generate vertices
For x% = 2 To 28 Step 2
For y% = 2 To 28 Step 2
vertsx%(x%, y%) = x%
vertsy%(x%, y%) = y%
Next
Next
'mix up the order to draw verticies
For X1% = 2 To 28 Step 2
For Y1% = 2 To 28 Step 2
X2% = (Int(Rnd(1) * 13) + 1) * 2
Y2% = (Int(Rnd(1) * 13) + 1) * 2
tmpx% = vertsx%(X1%, Y1%)
tmpy% = vertsy%(X1%, Y1%)
vertsx%(X1%, Y1%) = vertsx%(X2%, Y2%)
vertsy%(X1%, Y1%) = vertsy%(X2%, Y2%)
vertsx%(X2%, Y2%) = tmpx%
vertsy%(X2%, Y2%) = tmpy%
Next
Next
'now draw walls
'draw a wall from each verticies in a random direction
'until another wall is reached
For x% = 2 To 28 Step 2
For y% = 2 To 28 Step 2
xx% = vertsx%(x%, y%)
yy% = vertsy%(x%, y%)
If mz%(xx%, yy%) = 0 Then
Do
cnt% = 0
xx% = vertsx%(x%, y%)
yy% = vertsy%(x%, y%)
dirn% = Int(Rnd(1) * 4)
Do
cnt% = cnt% + 1
Select Case dirn%
Case 0: xx% = xx% - 1
Case 1: xx% = xx% + 1
Case 2: yy% = yy% + 1
Case Else: yy% = yy% - 1
End Select
Loop Until mz%(xx%, yy%) = 1
Loop Until cnt% < 26
xx% = vertsx%(x%, y%)
yy% = vertsy%(x%, y%)
Do
mz%(xx%, yy%) = 1
Select Case dirn%
Case 0: xx% = xx% - 1
Case 1: xx% = xx% + 1
Case 2: yy% = yy% + 1
Case Else: yy% = yy% - 1
End Select
Loop Until mz%(xx%, yy%) = 1
End If
Next
Next
End Sub
Never argue with fools, they will only drag you down to their level, and beat you with experience.
Q: How do you tell an experienced hacker from a novice?
A: The latter thinks there's 1000 bytes in a kilobyte, while the former is sure there's 1024 meters in a kilometer
This is a differnt way to generate a maze, it shares a similarity with Arie's method but I think its different enough to methion. So Arie if you think Im restating your method, you have my appologise.
You start with a rectangular array X by Y (squares are rectangles).
Each cell of the maze has these attributes: (I'd use a Type definition)
VISITED as Boolean
NORTHWALL as Boolean
SOUTHWALL as Boolean
EASTWALL as Boolean
WESTWALL as Boolean
I'm gonna assume that a True value for a wall means the wall exists and blocks the path.
Now initially set your array with VISITED = FALSE and all the others TRUE. This will result in a grid with no way to get anywhere (Can you visualize it?)
So make a function that can 'see' (in scope) the array. And is passed the current position in the array. Something like this:
Public Function MakeMaze(ByVal ROW as Integer, ByVal COL as Integer)
The function will mark the position it is given as VISTED (VISITED = True) Then it will check if any of its neighboring cells are unvisited (VISITED = False) if even one is then RANDOMLY choose an unvisited cell. And then set the appropriate wall to be false (take away the wall) and recursively call your function (in my case MakeMaze) with the neighbors cell coords. If all the neighbors are already visited then exit the function.
The recursiveness of this function will make it work.
If you want a code sample you'll have to pay me
I hope I made this clear enough. Ask me if you have any questions.
Originally posted by Arie Can someone explain this code??
I'd like to know how it works...
Thank you,
Arie.
I've rewritten it using more more standard VB. I've also removed a big chunc of unnessesarry (sp?) code. And I changed the maze-size to 61x61. Here's the code:
VB Code:
Private Sub CreateMaze()
Dim intA As Integer
Dim intX As Integer
Dim intY As Integer
Dim intX2 As Integer
Dim intY2 As Integer
Dim intTmpX As Integer
Dim intTmpY As Integer
Dim intDirn As Integer
'clear maze
For intX = 1 To 59
For intY = 1 To 59
intMz(intX, intY) = 0
Next
Next
'make border
For intA = 0 To 60
intMz(intA, 0) = 1
intMz(intA, 60) = 1
intMz(0, intA) = 1
intMz(60, intA) = 1
Next
'generate vertices
For intX = 2 To 58 Step 2
For intY = 2 To 58 Step 2
intVertsX(intX, intY) = intX
intVertsY(intX, intY) = intY
Next
Next
'mix up the order to draw verticies
For intX = 2 To 58 Step 2
For intY = 2 To 58 Step 2
'Int(Rnd * 29) returns a value between 0 and 28. (Int(Rnd * 29) + 1)
'returns a value between 1 and 29. 1 * 2 = 2 and 29 * 2 = 58. So the
'entire function (Int(Rnd * 29) + 1) * 2 returns a value between 2
'and 58.
intX2 = (Int(Rnd * 29) + 1) * 2
intY2 = (Int(Rnd * 29) + 1) * 2
'To swap two variables you save the first (A) then you replace (A) with
'the other variable (B) and then you replace (B) with the saved (A)-
'variable
intTmpX = intVertsX(intX, intY)
intTmpY = intVertsY(intX, intY)
intVertsX(intX, intY) = intVertsX(intX2, intY2)
intVertsY(intX, intY) = intVertsY(intX2, intY2)
intVertsX(intX2, intY2) = intTmpX
intVertsY(intX2, intY2) = intTmpY
Next
Next
'now draw walls
'draw a wall from each of the verticies in a random direction until another wall
Last edited by McCain; Oct 20th, 2003 at 12:15 AM.
Never argue with fools, they will only drag you down to their level, and beat you with experience.
Q: How do you tell an experienced hacker from a novice?
A: The latter thinks there's 1000 bytes in a kilobyte, while the former is sure there's 1024 meters in a kilometer
Back to mine, I neglected to state WHY mine works.
Since the recursive function starts at the beginning and visits every square that means any square is accessible from any other include the start and end.
Something else I may have glossed over, when you're in the recursive function you should have a while loop that loops until all neighbors have been visited. But make sure to do it randomly or the maze will look the same each time
I made a few changes to the code to produce better looking mazes...
VB Code:
Private Sub CreateMaze()
Dim intX As Integer
Dim intY As Integer
Dim intX2 As Integer
Dim intY2 As Integer
Dim intTmpX As Integer
Dim intTmpY As Integer
Dim intDirn As Integer
Dim intTmpDirn As Integer
Dim intVertsX(sizeX, sizeY) As Integer
Dim intVertsY(sizeX, sizeY) As Integer
'clear maze
For intX = 1 To sizeX - 1
For intY = 1 To sizeY - 1
intMz(intX, intY) = 0
Next
Next
'make border
For intX = 0 To sizeX
intMz(intX, 0) = 1
intMz(intX, sizeY) = 1
Next
For intY = 0 To sizeY
intMz(0, intY) = 1
intMz(sizeX, intY) = 1
Next
'generate vertices
For intX = 2 To sizeX - 2 Step 2
For intY = 2 To sizeY - 2 Step 2
intVertsX(intX, intY) = intX
intVertsY(intX, intY) = intY
Next
Next
'mix up the order to draw verticies
For intX = 2 To sizeX - 2 Step 2
For intY = 2 To sizeY - 2 Step 2
'Let's say that sizeX and sizeY are both 60, then is
'(sizeX / 2 - 1) = 29 and (sizeY / 2 - 1) = 29 as well.
' Int(Rnd * 29) returns a value between 0 and 28. (Int(Rnd * 29) + 1)
'returns a value between 1 and 29. 1 * 2 = 2 and 29 * 2 = 58. So the
'entire function (Int(Rnd * 29) + 1) * 2 returns a value between 2
'and 58.
intX2 = (Int(Rnd * (sizeX / 2 - 1)) + 1) * 2
intY2 = (Int(Rnd * (sizeY / 2 - 1)) + 1) * 2
'To swap two variables you save the first (A) then you replace (A) with
'the other variable (B) and then you replace (B) with the saved (A)-
'variable
intTmpX = intVertsX(intX, intY)
intTmpY = intVertsY(intX, intY)
intVertsX(intX, intY) = intVertsX(intX2, intY2)
intVertsY(intX, intY) = intVertsY(intX2, intY2)
intVertsX(intX2, intY2) = intTmpX
intVertsY(intX2, intY2) = intTmpY
Next
Next
'Now draw walls.
'Draw a wall from each of the verticies in a random direction until another wall
'is reached.
' For the best looking maze we don't want any walls going all the way across
'the maze, so if we're close to an edge, we make it more likely for the wall to
'go to that closest wall.
For intX = 2 To sizeX - 2 Step 2
For intY = 2 To sizeY - 2 Step 2
intTmpX = intVertsX(intX, intY)
intTmpY = intVertsY(intX, intY)
If intMz(intTmpX, intTmpY) = 0 Then
' Top Left ----------
If intX < sizeX / 3 And intY < sizeY / 3 Then
intTmpDirn = Int(Rnd * 11)
If intTmpDirn <= 4 Then
intDirn = 0
ElseIf intTmpDirn >= 5 And intTmpDirn <= 8 Then
intDirn = 3
ElseIf intTmpDirn = 9 Then
intDirn = 2
Else
intDirn = 1
End If
' Left --------------
ElseIf intX < sizeX / 3 And intY >= sizeY / 3 And intY <= sizeY / 3 Then
intTmpDirn = Int(Rnd * 8)
If intTmpDirn <= 4 Then
intDirn = 0
ElseIf intTmpDirn = 5 Then
intDirn = 1
ElseIf intTmpDirn = 6 Then
intDirn = 2
Else
intDirn = 3
End If ' = 40 if sizeY = 60
' Bottom Left ----------- /------^------\
ElseIf intX < sizeX / 3 And intY > sizeY * (2 / 3) Then
intTmpDirn = Int(Rnd * 11)
If intTmpDirn <= 4 Then
intDirn = 0
ElseIf intTmpDirn >= 5 And intTmpDirn <= 8 Then
intDirn = 2
ElseIf intTmpDirn = 9 Then
intDirn = 1
Else
intDirn = 3
End If
' Bottom ------------
ElseIf intX >= sizeX / 3 And intX <= sizeX * (2 / 3) And intY > sizeY * (2 / 3) Then
intTmpDirn = Int(Rnd * 8)
If intTmpDirn <= 4 Then
intDirn = 2
ElseIf intTmpDirn = 5 Then
intDirn = 0
ElseIf intTmpDirn = 6 Then
intDirn = 1
Else
intDirn = 3
End If
' Bottom Right ---------
ElseIf intX > sizeX * (2 / 3) And intY > sizeY * (2 / 3) Then
intTmpDirn = Int(Rnd * 11)
If intTmpDirn <= 4 Then
intDirn = 1
ElseIf intTmpDirn >= 5 And intTmpDirn <= 8 Then
intDirn = 2
ElseIf intTmpDirn = 9 Then
intDirn = 0
Else
intDirn = 3
End If
' Right ----------
ElseIf intX > sizeX * (2 / 3) And intY >= sizeY / 3 And intY <= sizeY * (2 / 3) Then
intTmpDirn = Int(Rnd * 8)
If intTmpDirn <= 4 Then
intDirn = 1
ElseIf intTmpDirn = 5 Then
intDirn = 0
ElseIf intTmpDirn = 6 Then
intDirn = 2
Else
intDirn = 3
End If
' Top Right ----------
ElseIf intX > sizeX * (2 / 3) And intY < sizeY / 3 Then
intTmpDirn = Int(Rnd * 11)
If intTmpDirn <= 4 Then
intDirn = 1
ElseIf intTmpDirn >= 5 And intTmpDirn <= 8 Then
intDirn = 3
ElseIf intTmpDirn = 9 Then
intDirn = 0
Else
intDirn = 2
End If
' Top -------------
ElseIf intX >= sizeX / 3 And intX <= sizeX * (2 / 3) And intY < sizeY / 3 Then
intTmpDirn = Int(Rnd * 8)
If intTmpDirn <= 4 Then
intDirn = 3
ElseIf intTmpDirn = 5 Then
intDirn = 0
ElseIf intTmpDirn = 6 Then
intDirn = 1
Else
intDirn = 2
End If
' Middle -----------
Else
intDirn = Int(Rnd * 4)
End If
Do
intMz(intTmpX, intTmpY) = 1
Select Case intDirn
Case 0: intTmpX = intTmpX - 1
Case 1: intTmpX = intTmpX + 1
Case 2: intTmpY = intTmpY + 1
Case Else: intTmpY = intTmpY - 1
End Select
Loop Until intMz(intTmpX, intTmpY) = 1
End If
Next
Next
End Sub
Never argue with fools, they will only drag you down to their level, and beat you with experience.
Q: How do you tell an experienced hacker from a novice?
A: The latter thinks there's 1000 bytes in a kilobyte, while the former is sure there's 1024 meters in a kilometer
I've been looking at links to maze generation.
I had no idea there was so much stuff out there. It's all pretty good to.
Here's a couple of links I've found to be very interesting. I'm not sure I'm up to tackeling them in VB, but it looks to interesting to ignore.
Reply With Quote
