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.
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.
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.
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.
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
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
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
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 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...
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.
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.
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.
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.
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):
Of course, you only have to click that button to see the solution ... when you have the code. Maybe I'll post that soon.
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.
Last edited by passel; Feb 27th, 2015 at 07:14 AM.
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:
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.
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.