Archived

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

Generating a maze

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
From this page:

  
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<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];}


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

Share this post


Link to post
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
Next
End 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) Then
getrand:
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
Loop
End 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Did you read the steps I gave? Of course it''s used as a path searching algorithm, hence the name, but if you read it clearly it can be used to make the maze as well. I forgot the link to the site which I read that from. The only problem I''m having is tracing the path back through the list of moves.

Share this post


Link to post
Share on other sites