Random Mazes?

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.


Thanks!

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.

Right after I wrote my last post, I wrote this program.
It's a little sloppy and leaves lots of open areas in the map, yet does its work very well..

When you run it, press Random map, then press Way out.

Anyone who sees this post may help to code it better.
Please post if you have Improved projects.

Arie.

One little change here.. One big improvement...

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

Can someone explain this code??
I'd like to know how it works...

Thank you,
Arie.

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 :p
I hope I made this clear enough. Ask me if you have any questions.

NOMAD

Quote:

---

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
    'is reached
    For intX = 2 To 58 Step 2
        For intY = 2 To 58 Step 2
            intTmpX = intVertsX(intX, intY)
            intTmpY = intVertsY(intX, intY)
            If intX = 2 And intY < 10 Then
                MsgBox intVertsX(intX, intY) & " " & intVertsY(intX, intY)
            End If
            If intMz(intTmpX, intTmpY) = 0 Then
                intDirn = Int(Rnd * 4)
                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

Globals:

VB Code:

Option Explicit
Dim intMz(60, 60) As Integer
Dim intVertsX(60, 60) As Integer
Dim intVertsY(60, 60) As Integer
Dim intCnt As Integer 'intCount
Dim intWdt As Integer
Dim intHgt As Integer
Dim lngTimer As Long

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 :p

NOMAD

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

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.

http://www.mazeworks.com/mazegen/index.htm

http://www.astrolog.org/labyrnth/algrithm.htm