Generating a maze
Author
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
Here''s how I would create a random maze (first attempt):
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.
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.
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.
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
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
From this page:
The code is much easier to understand if you read the page itself
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
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++)
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
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
Author
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
-Doddler
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)
Interesting approach. I''d never actually thought of that. Sometimes I miss the simplest ideas.
Steve ''Sly'' Williams Monkey Wrangler Krome Studios
Steve ''Sly'' Williams Monkey Wrangler Krome Studios
Author
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?
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?
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!
I wanna work for Microsoft!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
