Results 1 to 31 of 31

Thread: [RESOLVED] Random Maze Generator

  1. #1

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Resolved [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
    Last edited by NinjaNic; Feb 21st, 2015 at 01:46 PM.

  2. #2
    Frenzied Member Bulldog's Avatar
    Join Date
    Jun 2005
    Location
    South UK
    Posts
    1,950

    Re: Random Maze Generator

    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


    • If my post helped you, please Rate it
    • If your problem is solved please also mark the thread resolved

    I use VS2015 (unless otherwise stated).
    _________________________________________________________________________________
    B.Sc(Hons), AUS.P, C.Eng, MIET, MIEEE, MBCS / MCSE+Sec, MCSA+Sec, MCP, A+, Net+, Sec+, MCIWD, CIWP, CIWA
    I wrote my very first program in 1979, using machine code on a mechanical Olivetti teletype connected to an 8-bit, 78 instruction, 1MHz, Motorola 6800 multi-user system with 2k of memory. Using Windows, I dont think my situation has improved.

  3. #3

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Re: Random Maze Generator

    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
    Last edited by NinjaNic; Feb 22nd, 2015 at 12:42 AM.

  4. #4
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    Re: Random Maze Generator

    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

  5. #5
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    25,458

    Re: Random Maze Generator

    Quote Originally Posted by boops boops View Post
    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

  6. #6
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    25,458

    Re: Random Maze Generator

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

  7. #7

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Re: Random Maze Generator

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

  8. #8
    Bad man! ident's Avatar
    Join Date
    Mar 2009
    Location
    Cambridge
    Posts
    5,398

    Re: Random Maze Generator

    Quote Originally Posted by NinjaNic View Post
    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.

  9. #9

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Re: Random Maze Generator

    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:
    1. Private Sub CreatePath()
    2.  
    3.         Dim Rn As Int32 = 0
    4.         Dim NextPt As New Point(0, 0)
    5.         Dim NextPt2 As New Point(0, 0)
    6.  
    7.         NextPt = Path(Path.Count - 1)
    8.         NextPt2 = Path(Path.Count - 1)
    9.         Rn = R.NewNumber(4)
    10.         Select Case Rn
    11.  
    12.             Case 0
    13.  
    14.                 If IsFree(Path.Count - 1, -2, 0) Then
    15.                     NextPt.X -= 1
    16.                     NextPt2.X -= 2
    17.                 End If
    18.  
    19.             Case 1
    20.  
    21.                 If IsFree(Path.Count - 1, 0, -2) Then
    22.                     NextPt.Y -= 1
    23.                     NextPt2.Y -= 2
    24.                 End If
    25.  
    26.             Case 2
    27.  
    28.                 If IsFree(Path.Count - 1, 2, 0) Then
    29.                     NextPt.X += 1
    30.                     NextPt2.X += 2
    31.                 End If
    32.  
    33.             Case 3
    34.  
    35.                 If IsFree(Path.Count - 1, 0, 2) Then
    36.                     NextPt.Y += 1
    37.                     NextPt2.Y += 2
    38.                 End If
    39.  
    40.         End Select
    41.  
    42.         Path.Add(NextPt)
    43.         Path.Add(NextPt2)
    44.  
    45.         Me.Invalidate()
    46.  
    47.     End Sub

    And this makes sure that 2 blocks ahead is free:

    vb Code:
    1. Private Function IsFree(ByRef i As Int32, ByRef NextX As Int32, ByRef NextY As Int32) As Boolean
    2.         Dim Free As Boolean = True
    3.         Dim CheckPoint As New Point(Path(Path.Count - 1).X + NextX, Path(Path.Count - 1).Y + NextY)
    4.         If CheckPoint.X < 0 Or CheckPoint.Y < 0 Or CheckPoint.X > 20 Or CheckPoint.Y > 20 Then
    5.             Free = False
    6.             Return Free
    7.             Exit Function
    8.         End If
    9.         For i_1 As Int32 = Path.Count - 1 To 0 Step -1
    10.             If Path(i_1) = CheckPoint Then
    11.                 Free = False
    12.                 Exit For
    13.             End If
    14.         Next
    15.         Return Free
    16.     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.)

  10. #10
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    25,458

    Re: Random Maze Generator

    Quote Originally Posted by NinjaNic View Post
    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

  11. #11

  12. #12
    Frenzied Member
    Join Date
    Jul 2011
    Location
    UK
    Posts
    1,335

    Re: Random Maze Generator

    @.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 ).

    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

    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

  13. #13
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    25,458

    Re: Random Maze Generator

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

  14. #14

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Re: Random Maze Generator

    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

  15. #15

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Re: Random Maze Generator

    For future reference, this is my backtrack code:
    vb Code:
    1. Private Sub Backtrack()
    2.  
    3.         FormMaze.CurrentBlock = FormMaze.Path.Count - 1
    4.         Dim ThisPoint As New Point(FormMaze.Path(FormMaze.CurrentBlock).Pt.X, FormMaze.Path(FormMaze.CurrentBlock).Pt.Y)
    5.  
    6.         Do Until FormMaze.CurrentBlock < 0
    7.  
    8.             If FormMaze.Path(FormMaze.CurrentBlock).Visit = True Then
    9.  
    10.                 FormMaze.CurrentBlock -= 1
    11.  
    12.             ElseIf IsFree(FormMaze.CurrentBlock, -2, 0) = False _
    13.                 And IsFree(FormMaze.CurrentBlock, 2, 0) = False _
    14.                 And IsFree(FormMaze.CurrentBlock, 0, -2) = False _
    15.                 And IsFree(FormMaze.CurrentBlock, 0, 2) = False Then
    16.  
    17.                 FormMaze.Path(FormMaze.CurrentBlock).Visit = True
    18.                 FormMaze.CurrentBlock -= 1
    19.  
    20.             Else
    21.  
    22.                 CreatePath()
    23.                 Exit Sub
    24.  
    25.             End If
    26.  
    27.         Loop
    28.  
    29.         If FormMaze.CurrentBlock < 0 Then
    30.             FormMaze.StopDrawing = True
    31.         End If
    32.  
    33.     End Sub

  16. #16
    Bad man! ident's Avatar
    Join Date
    Mar 2009
    Location
    Cambridge
    Posts
    5,398

    Re: Random Maze Generator

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

  17. #17
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    25,458

    Re: Random Maze Generator

    I just followed the algorithm in NinjaNic's original post

  18. #18
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    25,458

    Re: Random Maze Generator

    Quote Originally Posted by NinjaNic View Post
    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...

  19. #19

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Re: Random Maze Generator

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

  20. #20
    eXtreme Programmer .paul.'s Avatar
    Join Date
    May 2007
    Location
    Chelmsford UK
    Posts
    25,458

    Re: Random Maze Generator

    Quote Originally Posted by NinjaNic View Post
    You think you're so smart... Try solving this!
    Attachment 124047
    might need my glasses on for that one

  21. #21

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Re: Random Maze Generator

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

  22. #22
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,582

    Re: Random Maze Generator

    Quote Originally Posted by NinjaNic View Post
    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.
    Last edited by passel; Feb 23rd, 2015 at 06:39 AM.

  23. #23
    Frenzied Member
    Join Date
    Jul 2011
    Location
    UK
    Posts
    1,335

    Re: Random Maze Generator

    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.

    Name:  hugemaze2_solved_ .png
Views: 3236
Size:  33.3 KB

  24. #24

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Re: Random Maze Generator

    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??!!

  25. #25
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,582

    Re: Random Maze Generator

    Quote Originally Posted by Inferrd View Post
    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.

  26. #26
    Frenzied Member
    Join Date
    Jul 2011
    Location
    UK
    Posts
    1,335

    Re: Random Maze Generator

    @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 View Post
    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

  27. #27

    Thread Starter
    Addicted Member NinjaNic's Avatar
    Join Date
    Dec 2013
    Location
    Earth
    Posts
    230

    Re: Random Maze Generator

    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.

  28. #28
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    Re: [RESOLVED] Random Maze Generator

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

    Name:  Maze1.jpg
Views: 2965
Size:  106.8 KB

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

    BB

  29. #29
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,582

    Re: [RESOLVED] Random Maze Generator

    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.
    Attached Images Attached Images  
    Last edited by passel; Feb 27th, 2015 at 07:14 AM.

  30. #30
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    Re: [RESOLVED] Random Maze Generator

    Quote Originally Posted by passel View Post
    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:
    Name:  Maze2small.jpg
Views: 3067
Size:  314.0 KB
    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

  31. #31
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    Re: [RESOLVED] Random Maze Generator

    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. For now.

    Name:  Maze5.jpg
Views: 2653
Size:  78.2 KBName:  Maze6.jpg
Views: 3129
Size:  79.2 KB

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width