#### Archived

This topic is now archived and is closed to further replies.

# Generating a maze

This topic is 6101 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey, for my Visual Basic course at the college me and my friend were thinking of making a little random maze generator. I''ve been trying some stuff on paper, but I just can''t seem to figure out how a maze could be generated. Anyone have any resources or code that could help me out? Thanks -Doddler

##### Share on other sites
Here''s how I would create a random maze (first attempt):

#### Stage 1: primary path

1.) Determine the desired maze dimensions in terms of cells.
2.) If you want the maze to actually have a solution, determine the cell coordinates of the starting (A) and ending (B) points.

Declare a variable to be the eccentricity (the amount of divergence from the linear path to the end point).

3.) Starting from the begin point (A), select a random direction to advance. Wall off the path. Increment your eccentricity as a function of the selected direction. If eccentricity hits or goes over 1, move directly towards the end point and reset it.

4.) Are we at the end point (B) yet? If yes, skip to Stage 2. If not, go back to 3.

#### Stage 2: alternate paths

Create the alternate paths in a manner similar to the primary path, but without the eccentricity.

Alternatively, you could define a bunch of geometric connections (left turn, right turn, circular loop) and randomly (or logically) connect segments.

Hmm, I think I''ll go write that this weekend.

##### Share on other sites
I created a little random maze generator for a game programming contest a while back. Won first place too. I''m not going to give you the source because it would be better for you to work it out yourself since this is for your course. I will however describe the algorithm that I used.

1. Setup the entire maze so that each cell is fully closed. Each cell is considered to be in a set with itself as the one member.

2. Pick a random cell from the grid. Now pick a random wall. If the cell on the other side of that wall is in a different set than the first cell, ie. the set that contains cell 1 does not contain cell 2, then remove the wall and join the sets.

3. Repeat step 2 until you have one set.

This one remaining set will contain all cells and it is guaranteed that for any two cells, there is one and only one path between them. If you want more than one solution, then remove a couple of random walls after you have one set.

I have successfully used this algorithm to produce large multi-level mazes. Very large mazes may take a while to produce due to the random nature of cell selection.

My contest entry was also able to solve the maze. I wrote an article about the maze solving algorithm for the Unofficial Newsletter of Delphi Users.

Steve ''Sly'' Williams  Monkey Wrangler  Krome Studios

##### Share on other sites

  char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);-- E; J[ E] =T[E ]= E) printf("._"); for(;(A-=Z=!Z) || (printf("\n|") , A = 39 ,C --) ; Z || printf (M ))M[Z]=Z[A-(E =A[J-Z])&&!C& A == T[ A]|6<<27

The code is much easier to understand if you read the page itself

##### Share on other sites
Well it just so happens I have an old VB project that did just that. It used the simplest maze algo there is

Here is how the maze was created: (excuse very bad code, I did this when I was about 11.... ) ive moved on to greater things (C++)

'ResetMaze()'-----------Public Sub ResetMaze(ByVal pl_Width As Long, pl_Height As Long)    Dim i As Long 'Define temporary loop var    Dim j As Long 'Define temporary loop var    ml_Width = pl_Width   'Assign new maze width    ml_Height = pl_Height 'Assign new maze height    ReDim ml_Cells(1 To ml_Width, 1 To ml_Height) As Long 'Reset the Cells array    'Cycle through all cells and put up all walls    For i = 1 To ml_Width        For j = 1 To ml_Height            ml_Cells(i, j) = 3 'Put up right and bottom wall        Next    NextEnd Sub 'ResetMaze'CreateMaze()'------------Public Sub CreateMaze()    Dim pl_VisitedCells As Long 'Number of cells been to    Dim pl_CurrentCellX As Long 'Current cell X value    Dim pl_CurrentCellY As Long 'Current cell Y value    ReDim pt_cellstack(ml_Width * ml_Height) As Cell 'Stack of cells been done and their positions    Dim pb_CellBottom   As Boolean 'Whether the current cell has a bottom side    Dim pb_CellLeft     As Boolean 'Whether the current cell has a left side    Dim pb_CellRight    As Boolean 'Whether the current cell has a right side    Dim pb_CellTop      As Boolean 'Whether the current cell has a top side    Dim pl_SideChosen   As Long 'The side of the cell that was chosen to be knocked down    Dim pl_CurrentCellStackPosition As Long 'The current cell number in the stack    Dim pl_NumberOfSides As Long 'The number of sides in the current cell that can be knocked down    ReDim pb_cellvisited(ml_Width + 1, ml_Height + 1) As Boolean 'Whether each cell has been visited    Dim Sides(1 To 4)   As String    Call Randomize 'Initialise random number generator    pl_CurrentCellX = Int(ml_Width * Rnd + 1)    pl_CurrentCellY = Int(ml_Height * Rnd + 1)    pb_cellvisited(pl_CurrentCellX, pl_CurrentCellY) = True    pl_VisitedCells = 1    Do While pl_VisitedCells < ml_Width * ml_Height        pb_CellBottom = False        pb_CellTop = False        pb_CellRight = False        pb_CellLeft = False        If ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 1 Or ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 3 Then            If pl_CurrentCellY > 1 Then                If Not pb_cellvisited(pl_CurrentCellX, pl_CurrentCellY - 1) Then                    pb_CellBottom = True                End If            End If        End If        If ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 2 Or ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 3 Then            If pl_CurrentCellX < ml_Width Then                If Not pb_cellvisited(pl_CurrentCellX + 1, pl_CurrentCellY) Then                    pb_CellRight = True                End If            End If        End If        If pl_CurrentCellY < ml_Height Then            If ml_Cells(pl_CurrentCellX, pl_CurrentCellY + 1) = 1 Or ml_Cells(pl_CurrentCellX, pl_CurrentCellY + 1) = 3 Then                If Not pb_cellvisited(pl_CurrentCellX, pl_CurrentCellY + 1) Then                    pb_CellTop = True                End If            End If        End If        If pl_CurrentCellX > 1 Then            If ml_Cells(pl_CurrentCellX - 1, pl_CurrentCellY) = 1 Or ml_Cells(pl_CurrentCellX - 1, pl_CurrentCellY) = 3 Then                If Not pb_cellvisited(pl_CurrentCellX - 1, pl_CurrentCellY) Then                    pb_CellLeft = True                End If            End If        End If        pl_NumberOfSides = 0        If pb_CellRight Then            pl_NumberOfSides = pl_NumberOfSides + 1            Sides(pl_NumberOfSides) = "R"        End If        If pb_CellLeft Then            pl_NumberOfSides = pl_NumberOfSides + 1            Sides(pl_NumberOfSides) = "L"        End If        If pb_CellTop Then            pl_NumberOfSides = pl_NumberOfSides + 1            Sides(pl_NumberOfSides) = "T"        End If        If pb_CellBottom Then            pl_NumberOfSides = pl_NumberOfSides + 1            Sides(pl_NumberOfSides) = "B"        End If        If (pb_CellRight Or pb_CellLeft Or pb_CellTop Or pb_CellBottom) Thengetrand:            pl_SideChosen = Int(pl_NumberOfSides * Rnd + 1)            If pl_SideChosen < 0 Or pl_SideChosen > pl_NumberOfSides Then                GoTo getrand            End If            If Sides(pl_SideChosen) = "R" Then                If ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 3 Then                    ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 1                ElseIf ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 2 Then                    ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 0                End If                pl_CurrentCellX = pl_CurrentCellX + 1            End If            If Sides(pl_SideChosen) = "B" Then                If ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 3 Then                    ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 2                ElseIf ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 1 Then                    ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 0                End If                pl_CurrentCellY = pl_CurrentCellY - 1            End If            If Sides(pl_SideChosen) = "T" Then                If ml_Cells(pl_CurrentCellX, pl_CurrentCellY + 1) = 3 Then                    ml_Cells(pl_CurrentCellX, pl_CurrentCellY + 1) = 2                ElseIf ml_Cells(pl_CurrentCellX, pl_CurrentCellY + 1) = 1 Then                    ml_Cells(pl_CurrentCellX, pl_CurrentCellY) = 0                End If                pl_CurrentCellY = pl_CurrentCellY + 1            End If            If Sides(pl_SideChosen) = "L" Then                If ml_Cells(pl_CurrentCellX - 1, pl_CurrentCellY) = 3 Then                    ml_Cells(pl_CurrentCellX - 1, pl_CurrentCellY) = 1                ElseIf ml_Cells(pl_CurrentCellX - 1, pl_CurrentCellY) = 2 Then                    ml_Cells(pl_CurrentCellX - 1, pl_CurrentCellY) = 0                End If                pl_CurrentCellX = pl_CurrentCellX - 1            End If            pl_CurrentCellStackPosition = pl_CurrentCellStackPosition + 1            pt_cellstack(pl_CurrentCellStackPosition).x = pl_CurrentCellX            pt_cellstack(pl_CurrentCellStackPosition).y = pl_CurrentCellY            pl_VisitedCells = pl_VisitedCells + 1            pb_cellvisited(pl_CurrentCellX, pl_CurrentCellY) = True        Else            pl_CurrentCellStackPosition = pl_CurrentCellStackPosition - 1            pl_CurrentCellX = pt_cellstack(pl_CurrentCellStackPosition).x            pl_CurrentCellY = pt_cellstack(pl_CurrentCellStackPosition).y        End If        Me.Label1.Caption = Int((pl_VisitedCells / (ml_Width * ml_Height)) * 100) & "%"        Me.Label1.Refresh    LoopEnd Sub 'CreateMaze() `

OK, that is very messy, but basically there is a 2d array of cells, each with a value, this was before i really knew about flags if the value is 1 the cell has a bottom wall, 2 the cell has a right wall, 3 means the cell has both walls. The algo starts in a random place and chooses a wall to knock down, pushes the current cell onto the stack, then moves into the cell that it just knocked a wall down from. Once no walls can be removed, it pops the stack and goes back down.... until the stack is empty, also no cell can be visited more than once, except on your way back down the stack. This creates a perfect maze, that is from any two cells there is only one route. Finding a solution for the maze can be done in a similar way.

Hope thats what you needed,

Richard

Edited by - FatalXC on October 30, 2001 2:29:45 AM

##### Share on other sites
Hey thanks! I fully understand your idea there sly. BTW I do do alot of coding in C++ and DirectX, but I''m back to VB for the first simester of my computer information processing course. FatalXC, thanks for the code, but I plan on writing my own since it is for my course project. Anyways, thanks everyone!

-Doddler

##### Share on other sites
quote:
Original post by Sly
I have successfully used this algorithm to produce large multi-level mazes. Very large mazes may take a while to produce due to the random nature of cell selection.

after reading your post, i toyed with this... i found that you can iterate through the array of squares in a loop, rather than randomly picking a cell to manipulate, and still get a pretty good maze. just go across each column row-by-row and pick which wall (if any) to remove. when it is done with the whole grid, check to see if all the squares are connected; if not do it again.
when i programmed this in it still generated "good looking" random mazes, and it only took like 1/10th the time.

--- krez (krezisback@aol.com)

##### Share on other sites
Interesting approach. I''d never actually thought of that. Sometimes I miss the simplest ideas.

Steve ''Sly'' Williams  Monkey Wrangler  Krome Studios

##### Share on other sites
Ok, after searching around, I found a really easy algorithm called the Depth First Search, which is summerized like so:

1) Start at a random cell in the grid.
2) Look for a random neighbor cell you haven''t been to yet.
3) If you find one, move there, knocking down the wall between the cells. If you don''t find one, back up to the previous cell.
4) Repeat steps 2 and 3 until you''ve been to every cell in the grid.

The question is, I can do this all fine in C++, but how would I generate a stack of moves in VB? I don''t know how you use pointers in VB, or if it''s even possible. Anyone?

##### Share on other sites
Besides, DFS is for finding a path through the maze, not for generating one. As for your VB question, I only use VB if I have to (read: under duress by my employer).

I wanna work for Microsoft!

1. 1
2. 2
Rutin
22
3. 3
4. 4
JoeJ
16
5. 5

• 14
• 29
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
631775
• Total Posts
3002278
×