[RESOLVED] Random Maze Generator

Hi!
Good morning to you all. I had a random idea of making a random maze generator, but may need a bit of help. What I do is create wall "Blocks" (with properties of X, Y, and Type) through the whole maze. So first thing, every block in a grid is changed to a pathway "Block." (White is pathway, black is wall.)
Attachment 123991
Then, every block connecting to 2 walls has about a 20% chance of becoming a pathway.
Attachment 123993
After that, every block connecting to 3 or less walls will become a pathway.
Attachment 123995
Edit: When I say connect, that means diagonal as well.
(I don't think I need to put code here because I explained it pretty accurately.) Now, this code is pretty random (and inefficient.) There is no Start/End, there are some loops, and also some pathways aren't even connected to the rest. I found this: http://en.wikipedia.org/wiki/Maze_generation_algorithm but I was not sure how to put those into VB code.
Does anyone know how to do these things in VB 2010? I appreciate this.
Thanks
~Nic

Yes, many people know how to do these things in VB, but I think you're question was more than that.

I would first write out the algorithm on paper and make sure it works - Research

Then design the application, identify what controls do you need, what the forms look like, how to test it - Specification

Then it's time to start coding - Implementation

And onto testing - Verification

Well, I already have what is written on the first post. What I need to know is how to make sure it has a solution (start to finish) for the maze, and to make sure there are no stranded pathways.

Edit: This is what I mean by "stranded pathway." I manually highlighted some.Attachment 124005

To make sure there is a good pathway though the maze, I would start by trying to make a single pathway without branches. Start by selecting a random point on one side of the square. Then repeatedly break through a square next to that, disallowing squares already on the pathway. At each step, in other words, you would limit the next breakthrough to a randomly chosen square next to the present one. You continue this until (if you are lucky) you reach a point on another side, such as the opposite side to the starting point.

You will have to keep a count of the squares you have added to the path. If it's less than a certain number, it means the path is too short so you reject that attempt and start again. Probably you should also set an upper limit, to avoid a path which just spirals inwards.

Once you have found a single path, you continue by growing side branches. Select a random point on the existing path and break through to an adjacent square. Probably you probably need to disallow breaking back into the existing path, or only allow it once in so many times. You continue until all the possibilities for branching have been used up.

Would this produce a nice maze? I don't know without trying it:).

BB

Quote:

---

Originally Posted by boops boops

To make sure there is a good pathway though the maze, I would start by trying to make a single pathway without branches. Start by selecting a random point on one side of the square. Then repeatedly break through a square next to that, disallowing squares already on the pathway. At each step, in other words, you would limit the next breakthrough to a randomly chosen square next to the present one. You continue this until (if you are lucky) you reach a point on another side, such as the opposite side to the starting point.

You will have to keep a count of the squares you have added to the path. If it's less than a certain number, it means the path is too short so you reject that attempt and start again. Probably you should also set an upper limit, to avoid a path which just spirals inwards.

Once you have found a single path, you continue by growing side branches. Select a random point on the existing path and break through to an adjacent square. Probably you probably need to disallow breaking back into the existing path, or only allow it once in so many times. You continue until all the possibilities for branching have been used up.

Would this produce a nice maze? I don't know without trying it:).

BB

---

I tried the Recursive backtracker algorithm @ http://en.wikipedia.org/wiki/Maze_generation_algorithm and it doesn't create a solvable maze... just seems to be random walls, so I tried creating a random path across the grid, which I intended to amalgamate with the random walls created by the Recursive backtracker algorithm. I've just about given up on that idea now. Next i'll try Prim's algorithm

I stand corrected... the Recursive backtracker algorithm works well

Paul, can you help me code the Recursize Backtracker? I tried to do a different method but it made loops in the pathway.

Quote:

---

Originally Posted by NinjaNic

Paul, can you help me code the Recursize Backtracker? I tried to do a different method but it made loops in the pathway.

---

Help you code or write the code for you? Lets see what you tried.

Too late- I changed it. But here's what I have now. I made it so that when you press a button, a new block is added. (So you can see what's going on.)

2 blocks are added upon click: (Rn is a random number.)

vb Code:

Private Sub CreatePath()
 
        Dim Rn As Int32 = 0
        Dim NextPt As New Point(0, 0)
        Dim NextPt2 As New Point(0, 0)
 
        NextPt = Path(Path.Count - 1)
        NextPt2 = Path(Path.Count - 1)
        Rn = R.NewNumber(4)
        Select Case Rn
 
            Case 0
 
                If IsFree(Path.Count - 1, -2, 0) Then
                    NextPt.X -= 1
                    NextPt2.X -= 2
                End If
 
            Case 1
 
                If IsFree(Path.Count - 1, 0, -2) Then
                    NextPt.Y -= 1
                    NextPt2.Y -= 2
                End If
 
            Case 2
 
                If IsFree(Path.Count - 1, 2, 0) Then
                    NextPt.X += 1
                    NextPt2.X += 2
                End If
 
            Case 3
 
                If IsFree(Path.Count - 1, 0, 2) Then
                    NextPt.Y += 1
                    NextPt2.Y += 2
                End If
 
        End Select
 
        Path.Add(NextPt)
        Path.Add(NextPt2)
 
        Me.Invalidate()
 
    End Sub

And this makes sure that 2 blocks ahead is free:

vb Code:

Private Function IsFree(ByRef i As Int32, ByRef NextX As Int32, ByRef NextY As Int32) As Boolean
        Dim Free As Boolean = True
        Dim CheckPoint As New Point(Path(Path.Count - 1).X + NextX, Path(Path.Count - 1).Y + NextY)
        If CheckPoint.X < 0 Or CheckPoint.Y < 0 Or CheckPoint.X > 20 Or CheckPoint.Y > 20 Then
            Free = False
            Return Free
            Exit Function
        End If
        For i_1 As Int32 = Path.Count - 1 To 0 Step -1
            If Path(i_1) = CheckPoint Then
                Free = False
                Exit For
            End If
        Next
        Return Free
    End Function

Now, no loops are made. But I still need a way to back track. (That's why I added the i as int32 in the IsFree function.)

Quote:

---

Originally Posted by NinjaNic

Paul, can you help me code the Recursize Backtracker? I tried to do a different method but it made loops in the pathway.

---

No warranties or explanations here, either explicit or implied:

Code:

---

Public Class Form1

    Dim unvisited As New List(Of cell)
    Dim visited As New List(Of cell)

    Dim current As cell
    Dim r As New Random

    Dim passages As New List(Of Rectangle)

    Private Sub PictureBox1_Paint(ByVal sender As Object, ByVal e As System.Windows.Forms.PaintEventArgs) Handles PictureBox1.Paint
        For r As Integer = 20 To PictureBox1.Height Step 20
            e.Graphics.DrawLine(New Pen(Color.Silver, 3), 0, r, PictureBox1.Width, r)
        Next
        For c As Integer = 20 To PictureBox1.Width Step 20
            e.Graphics.DrawLine(New Pen(Color.Silver, 3), c, 0, c, PictureBox1.Height)
        Next

        For x As Integer = 0 To passages.Count - 1
            If passages(x).Y < 10 Then passages(x) = New Rectangle(passages(x).Left, 0, passages(x).Width, passages(x).Height + 2)
            If passages(x).X < 10 Then passages(x) = New Rectangle(0, passages(x).Top, passages(x).Width + 2, passages(x).Height)

            e.Graphics.FillRectangle(Brushes.Black, passages(x))
        Next
    End Sub

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Me.SetClientSizeCore(405, 465)
    End Sub

    Private Sub Form1_Paint(ByVal sender As Object, ByVal e As System.Windows.Forms.PaintEventArgs) Handles Me.Paint
        e.Graphics.FillRectangle(Brushes.Black, New Rectangle(0, 406, 406, 60))
    End Sub

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        'create new maze
        unvisited.Clear()
        visited.Clear()
        passages.Clear()


        For r As Integer = 0 To 20
            For c As Integer = 0 To 20
                unvisited.Add(New cell With {.x = c, .y = r, .visited = False})
            Next
        Next

        visited.Add(unvisited.First)
        unvisited.RemoveAt(0)
        current = visited.First
        current.visited = True

        Dim backTrack As Integer = 1

        While unvisited.Count > 0
            Dim indices As New List(Of Integer)

            indices.Add(unvisited.FindIndex(Function(c) c.x = current.x And c.y = current.y - 1)) 'above
            indices.Add(unvisited.FindIndex(Function(c) c.x = current.x + 1 And c.y = current.y)) 'to the right
            indices.Add(unvisited.FindIndex(Function(c) c.x = current.x And c.y = current.y + 1)) 'below
            indices.Add(unvisited.FindIndex(Function(c) c.x = current.x - 1 And c.y = current.y)) 'to the left
            indices.RemoveAll(Function(x) x = -1)

            If indices.Count > 0 Then
                Dim index As Integer = indices(r.Next(0, indices.Count))

                If current.x > unvisited(index).x Then 'to the left
                    passages.Add(New Rectangle(current.x * 20 - 1, current.y * 20 + 2, 3, 17))
                ElseIf current.x < unvisited(index).x Then 'to the right
                    passages.Add(New Rectangle(unvisited(index).x * 20 - 1, current.y * 20 + 2, 3, 17))
                ElseIf current.x = unvisited(index).x Then
                    If current.y > unvisited(index).y Then 'above
                        passages.Add(New Rectangle(current.x * 20 + 2, current.y * 20 - 1, 17, 3))
                    ElseIf current.y < unvisited(index).y Then 'below
                        passages.Add(New Rectangle(current.x * 20 + 2, unvisited(index).y * 20 - 1, 17, 3))
                    End If
                End If

                visited.Add(unvisited(index))
                unvisited.RemoveAt(index)
                current = visited.Last
                current.visited = True
                backTrack = 1
            Else

                current = visited(visited.Count - (1 + backTrack))
                backTrack += 1
            End If
        End While

        PictureBox1.Invalidate()
    End Sub
End Class

Public Class cell
    Public x As Integer
    Public y As Integer
    Public visited As Boolean
End Class

---

Paul you are too generous

@.paul.

Very nice :)

I remember Dday was messing with maze solving a couple of years back, and I was inspired to write an implementataion of that backtracking algorithm. I was going to post it here, but it's way, waaay longer than your code and more confusing too, so I'll not bother (even though longer obviously means better :p :p).

Couple of points though:
You might like to mention the size of your picturebox (400x400?)

Also, I'm thinking your picturebox has a Black background? With a normal coloured background, your passages look like black walls (which is the way I normally draw mazes: white background, black walls), but those "walls" form lots of enclosed islands. Basically, I was confused again ... happens a lot these days :cry:

Finally, your maze size is 20x20? If so, shouldn't you be looping to 19 in both loops here:

Code:

---

For r As Integer = 0 To 20
    For c As Integer = 0 To 20
        unvisited.Add(New cell With {.x = c, .y = r, .visited = False})
    Next
Next

---

oh yeah the loops...
your other assumptions are correct too

I did it! I didn't copy your code though; I organize mine differently. But thanks, you opened my eyes to use a class for the cell with the visited property. Thank you all for the help.

Code:

---

Public Class cell
    Public x As Integer
    Public y As Integer
    Public visited As Boolean
End Class

---

...Can you solve this? (Well, of course, you're geniuses.)
Attachment 124039

For future reference, this is my backtrack code:

vb Code:

Private Sub Backtrack()
 
        FormMaze.CurrentBlock = FormMaze.Path.Count - 1
        Dim ThisPoint As New Point(FormMaze.Path(FormMaze.CurrentBlock).Pt.X, FormMaze.Path(FormMaze.CurrentBlock).Pt.Y)
 
        Do Until FormMaze.CurrentBlock < 0
 
            If FormMaze.Path(FormMaze.CurrentBlock).Visit = True Then
 
                FormMaze.CurrentBlock -= 1
 
            ElseIf IsFree(FormMaze.CurrentBlock, -2, 0) = False _
                And IsFree(FormMaze.CurrentBlock, 2, 0) = False _
                And IsFree(FormMaze.CurrentBlock, 0, -2) = False _
                And IsFree(FormMaze.CurrentBlock, 0, 2) = False Then
 
                FormMaze.Path(FormMaze.CurrentBlock).Visit = True
                FormMaze.CurrentBlock -= 1
 
            Else
 
                CreatePath()
                Exit Sub
 
            End If
 
        Loop
 
        If FormMaze.CurrentBlock < 0 Then
            FormMaze.StopDrawing = True
        End If
 
    End Sub

Paul will you please write my whole program for me. Then i can claim to others i wrote it.

I just followed the algorithm in NinjaNic's original post

Quote:

---

Originally Posted by NinjaNic

I did it! I didn't copy your code though; I organize mine differently. But thanks, you opened my eyes to use a class for the cell with the visited property. Thank you all for the help.

Code:

---

Public Class cell
    Public x As Integer
    Public y As Integer
    Public visited As Boolean
End Class

---

...Can you solve this? (Well, of course, you're geniuses.)
Attachment 124039

---

I can solve it by eye.
Going to write a maze solver as part of this random maze generator, when i get some free time...

You think you're so smart... Try solving this!
Attachment 124047

Quote:

---

Originally Posted by NinjaNic

You think you're so smart... Try solving this!
Attachment 124047

---

might need my glasses on for that one:D

Here is my Maze Game downloadable EXE file, if anyone was interested:
http://gamejolt.com/games/puzzle/ran...ze-game/50855/

Quote:

---

Originally Posted by NinjaNic

You think you're so smart... Try solving this!

---

Actually, other than being large, it is an easy Maze to solve (green to red) as there are not a lot of branches to mislead you. Dead end branches are either fairly short, or obviously inside a walled off area you've already traversed.
That said, not so easy to do by eye since traversed areas are harder to "see" with the large puzzle.
Actually, if you tried to solve if from red to green, then that is a more difficult because you're presented with two long paths fairly quickly, which only one should be correct, so you'll have to choose one and won't know if it was the wrong one for quite awhile.
I wonder if that is always true with this type of maze generation, in which case it would seem you should generate it then make the end point the entrance, and entrance the exit so the maze is more challenging.

Personally, I would like a "wall" around the maze for visualization, otherwise, when you come to the edge of the maze halfway along the wall, you might traverse outsize the maze to go around a wall if not observant.

If you've created code that implements the recursive backtracker algorithm as outlined in the link given in the first post, and use it to build a maze starting from the entrance (green) cell, then once the "current cell" is the exit (red) cell, you'll find a solution is contained on the stack (in reverse order, i.e. the path from red to green).

With that in mind, very minor modifications to the existing code will enable it to solve any similar maze, such as the HugeMaze above, assuming that you can map the cells properly from a good picture of the maze that hasn't been mangled by jpeg compression and forum resizing. :sick:

Attachment 124107

By using the Recursive Backtracker method, you are bound to have a very long path directly to the end. The only reason it would "backtrack" is if the path get's itself stuck. (For example, when the snake eats its tail in the classic arcade game, Snake.)
Usually the dead ends are very short, but some of the dead ends can be very lengthy passages depending on how the first pass was set.

Now, how did you make that maze solver??!!

Quote:

---

Originally Posted by Inferrd

If you've created code that implements the recursive backtracker algorithm as outlined in the link given in the first post, and use it to build a maze starting from the entrance (green) cell, then once the "current cell" is the exit (red) cell, you'll find a solution is contained on the stack (in reverse order, i.e. the path from red to green)...

---

I realize that once you solve from green to red, then you also have the red to green.
I was just saying that solving the maze by hand, rather than algorithm, was fairly easy in this particular case, as the correct way to go was fairly obvious without large potential side trips when going from green to red. That makes the puzzle an "easy" one, although time consuming.
On the other hand, if you were solving it by hand and were going from red to green, that point a few cells up on the right bottom where the solution heads to the left, you also had the choice of continuing up into that vast area of the right side, which doesn't lead to a solution. Even if you used an algorithm, if it started at red, and was following the right walls, it would have taken much longer to solve going from red to green, than green to red because of the side trip into that vast wasteland, that is avoided going green to red.

@passel: my remarks in post #23 weren't aimed at you or anyone else in particular :). They were just my observations on the way the recursive backtracker seemed to be behaving when I was playing with it a couple of years ago. In fact, it took me a while to twig that the solution from the start cell to any cell marked as "current cell" (in the algorithm from the wikipedia page) was contained on the stack at that moment in the code's execution (I'm getting slow in my old age :(), but as it's a stack, the path data would be popped off in the reverse order.

I was also making that post as a hint to NinjaNic that the recursive backtracker algorithm might be worth investigating as one possible method for solving his maze, given that that algorithm had been discussed several times in earlier posts.

Quote:

---

Originally Posted by NinjaNic

By using the Recursive Backtracker method, you are bound to have a very long path directly to the end. The only reason it would "backtrack" is if the path get's itself stuck. (For example, when the snake eats its tail in the classic arcade game, Snake.)
Usually the dead ends are very short, but some of the dead ends can be very lengthy passages depending on how the first pass was set.

Now, how did you make that maze solver??!!

---

I totally agree with what you and passel are saying about that algorithm. It does appear to produce mazes that have a minimal number of solution paths, which I think makes them less interesting, but it was the first algorithm I tried, it worked, and that was enough for me ;).

It's also the algorithm I used to solve the maze, using almost exactly the same code as I made that creates mazes.

If you were to create code that follows all the steps at http://en.wikipedia.org/wiki/Maze_ge...ve_backtracker verbatim, then to solve your maze, all you would need to do would be to ignore step 2.1.3 "Remove the wall..", and when searching for the next neighbour cell, only consider cells that are path cells (I added a .IsWhiteCell boolean property to the Cell Class) and haven't been visited yet. Then when the current cell reaches the exit cell, examine the contents of the stack to find the solution path.

There are bound to be better approaches, but I had the code already written, so I used it :)

Done! (I feel so accomplished right now...)
Attachment 124171
I guess I should stop posting to this thread. It is solved and I will mark it as so. Thanks again for the help.

Hi nic, you are not finished with this thread yet (unless you ignore this post). When I replied in post #2, I didn't realize there was a whole community of maze experts on the forum. But I decided to make my own maze generator anyway, partly because I wanted to develop random fill patterns for other purposes.

The main features of my maze generator are:
1. It starts by generating a solution pathway ("trunk") in the code. The pathway runs from the center top of the frame to a random point on the bottom, and is made using the backtracking method.
2. Side branches are added, starting from both ends of the main pathway simultaneously. These do not backtrack but continue until they reach a dead end.
3. Secondary branches are added in a similar way to fill any remaining empty cells.

Here's an example of the output (50 x 50 cells):

Attachment 124193

Of course, you only have to click that button to see the solution ... when you have the code:D. Maybe I'll post that soon.

BB

Not bad. Still not too hard to do by hand, as you can follow most side passages to a termination by eye,or follow the blue walls and see that they don't have a break so there is not a path in that direction, but I don't know how you go about making it trickier. There were a good number of side paths that went a reasonable distance. I should have timed myself. I just copied the image into paint and use the pencil tool to trace the path.

Quote:

---

Originally Posted by passel

Not bad. Still not too hard to do by hand, as you can follow most side passages to a termination by eye,or follow the blue walls and see that they don't have a break so there is not a path in that direction, but I don't know how you go about making it trickier. There were a good number of side paths that went a reasonable distance. I should have timed myself. I just copied the image into paint and use the pencil tool to trace the path.

---

Well done! Here's how the above maze looked with the solution marked by the program:
Attachment 124205
I'm pleased with my "can of worms" look but the rounded tips make it easier to spot dead ends, compared to NinjaNic's square style. Of course any maze can be made more difficult by increasing the number of cells so I don't see that as a problem. My program automatically scales the maze to fit the form.

I am going to try letting the branches backtrack too, so that longer false paths can arise. It would reduce the total number of branches, but the very short branches are mostly filling anyway. It would be nice if the difficulty level turns out to be scalable. Maybe this weekend.

BB

Here's a new "square" style maze, staying at 50*50 cells for comparison purposes. It's a bit more challenging, isn't it? To swap, I simply change the LineJoin and EndCap properties of the pen used to widen a GraphicsPath.

I decided not to bother with backtracking the branches. Why should a backtracked branch be longer than one that isn't? It would of course allow me to try each branch a given number of times and select the longest. But with fast maze generation you can easily loop through multiple mazes and select the best result on various criteria (solution pathway length, side branch lengths etc.)

The length of the solution pathway probably has more impact on difficulty. The longest pathways wind to and fro across the whole maze area so you lose your sense of direction. In this program, the solution length also varies much more widely than the maximum branch length. Finally, if it matters, backtracking is much slower.

Here are two mazes in the new style. One has the longest solution pathway I found in about 20 tries, and the other has the longest side branch. But I'm not going to tell you which is which:D. For now.

Attachment 124249Attachment 124251