0:26 and 0:36, assuming the solver knew the boundaries of the maze, it should have also known that the directions it headed were dead ends. Euclidean distance checks at T intersections are the key here :)
When I did a maze generator a long time ago, I had a parameter telling the chanse of continuing to dig straight forward or to turn left or right. That way I could set how wriggly the maze would be.
Another parameter I would introduce if I did this today is a random chanse to stop digging and start a new branch. This way I could set if there will be few or many dead ends.
@metabog Yes it is. Both the generator and solver are depth-first search algorithms that will track back when they find themselves in a dead end that will not lead to a solution.
You can also improve the maze solving algorithm by making it try squares that reduce the euclidean distance to the end in most-to-least order, since solutions are more often direct than not.
You can improve the maze-generating algorithm by starting at the end and generating towards the start. This means the start square will likely have two paths, one of which will always be a dead end. If you generating starting at the start, the end square will have two paths, one of which will never be traversed.
Where can I get more info on the "Caver" algorithm? I've written code that generates a maze using the Depth First algorithm but the results are mazes with very little branching and consequently very easy to solve. The Prim algorithm has ample branching (perhaps too much) because it results in lots of very short corridors. I don't have the stomach to implement the Kruskal algorithm.
@deefstes Dig out a square, look at the 4 adjacent squares in random order, for each of them that is not dug out you dig in that direction and repeat. When there are no adjacent squares to dig into you fall back to the previous square and look at the remaining adjacent squares. You can implement this as a very short recursive function.
Thanks @RJLeffmann. That sounds exactly like the Depth First Search algorithm though. How come your maze looks so much better than mazes created with DFS then?
Just to be clear, you write "look at the 4 adjacent squares in random order, for each of them that is not dug out you dig in that direction and repeat". I assume you meant, choose one of the 4 adjacent squares that is not dug out and dig in that direction (ie. not for all four - or as many as are not dug out)?
I would assume this to be a simple program, since all it should need to do is, record the position and possible choices at each intersection, and explore each option... usually I would assume with a bias... like clockwise from up... and once it reaches the end of the possibility tree, it goes back to a previous decision, and increases the value...so assuming that 0 is up, 1 is right, down is 2 and left is 3... and ignoring reverse directions, and non-choices, it would narrow the possibilities
@TheReasonWhyGuy Yes very simple. The recursive function that traverses the maze is only 10 or so lines of code, and it pretty much works like you said.
@RJLeffmann lol... oddly enough, I've never made this before... XD... I just thought of the simplest way I'd make it a vuala XD
Though I'm curious, would it be faster to have both finish and start path find towards each other, and if the start path finder hits a space that any of the finish path finder has, then the path is found... Or perhaps that would take more code, and result in the same level of efficiency :|
question, i like your video i was wondering if u can help me with a question i came up with an idea lets say there are two pc's ,in pc 1 there are three box's that are out putting letter from a-z box=f box=r box=w the next set of boxs box=h box=l box=x box 2 a-z box-3 a-z is it possible to see what pc 1 is out puting then take that info and manually in put it into pc 2 then could pc 2 know where pc 1 is going and what pc 1s next out put would be before it comes out
MarcusHab: Check out OpenGL if you want some hardware-accelerated graphics fun.
Conradhw: Maze algorithms and dungeon generators are two very different things. Maze algorithms solve mazes, usually obtaining the shortest route if more than one is available.
The workings of the algorithm have been visualised for you here, but the algorithm itself is unaware of any graphics. All it cares about is the data involved. It therefore makes no sense to make graphical demands of the algorithm itself.
I'm still waiting for the day that maze algorithms (dungeon generators) generate realisic corridors/rooms/interiors for 3D exploration (buildings/spaceships etc). There's so much you can do with maze algorithms & simple logic, in combination with defined geometry.
I get the concept of logic and algorithms (kinda), but how do you actually produce something you can see? The only thing I've ever been able do was in a run/command box. Whatever that's called.
C/C++ has no support for graphics, so you have to make use of an existing graphics library, or use whatever graphics support you have in the operating system you're on. For doing graphics on Windows and OS X you can find information on MSDN and Apple Developer Center.
In this case it was just a console application (a run/command box) and I generated each image frame in memory and wrote it to disk in the BMP format, batch loaded all frames into VirtualDub and saved back as an AVI animation.
That's is pretty cool. Can you tall me more, or give me some links, how to do something like that ? ... I mean generate frames to memory and write it to disk in bmp ? I suppose it won't be easy for me, however, I would like to know more about this.
If you're looking for general information on programming you can probably type your favorite language into Google along with words like free book, tutorial, guide etc., and you can find a good article with everything you need to know about the BMP image format on Wikipedia.
Cool! So out of curiosity, when the caver is "digging" the maze and he has more than one direction to dig in, does he simply choose from the available directions randomly?
Yes he does, and in addition you can have him dig several steps in the same direction, when possible, to vary between longer straight tunnels and shorter jittery ones.
0:26 and 0:36, assuming the solver knew the boundaries of the maze, it should have also known that the directions it headed were dead ends. Euclidean distance checks at T intersections are the key here :)
trjnz 2 months ago
@trjnz Yes - given that it's trying to reach a known coordinate. If you're trapped in a maze then you probably don't know where the actual exit is :)
RJLeffmann 2 months ago
When I did a maze generator a long time ago, I had a parameter telling the chanse of continuing to dig straight forward or to turn left or right. That way I could set how wriggly the maze would be.
Another parameter I would introduce if I did this today is a random chanse to stop digging and start a new branch. This way I could set if there will be few or many dead ends.
AngeCord 3 months ago
Is this an example of backtracking?
metabog 4 months ago
@metabog Yes it is. Both the generator and solver are depth-first search algorithms that will track back when they find themselves in a dead end that will not lead to a solution.
RJLeffmann 4 months ago 3
This is very similar to Trémaux's algorithm.
BitwiseRSBuddy 7 months ago
what's the maze generation algorithm?
halfaheartbongobongo 1 year ago
You can also improve the maze solving algorithm by making it try squares that reduce the euclidean distance to the end in most-to-least order, since solutions are more often direct than not.
domokato 1 year ago 2
@domokato Good thinking, and I agree on the heuristic for solving the maze, it would probably make it a lot quicker. I'll try it out some day.
RJLeffmann 1 year ago 2
I did this in college.
You can improve the maze-generating algorithm by starting at the end and generating towards the start. This means the start square will likely have two paths, one of which will always be a dead end. If you generating starting at the start, the end square will have two paths, one of which will never be traversed.
(continued)
domokato 1 year ago
Where can I get more info on the "Caver" algorithm? I've written code that generates a maze using the Depth First algorithm but the results are mazes with very little branching and consequently very easy to solve. The Prim algorithm has ample branching (perhaps too much) because it results in lots of very short corridors. I don't have the stomach to implement the Kruskal algorithm.
deefstes 1 year ago 2
@deefstes Dig out a square, look at the 4 adjacent squares in random order, for each of them that is not dug out you dig in that direction and repeat. When there are no adjacent squares to dig into you fall back to the previous square and look at the remaining adjacent squares. You can implement this as a very short recursive function.
RJLeffmann 1 year ago
This has been flagged as spam show
Thanks @RJLeffmann. That sounds exactly like the Depth First Search algorithm though. How come your maze looks so much better than mazes created with DFS then?
Just to be clear, you write "look at the 4 adjacent squares in random order, for each of them that is not dug out you dig in that direction and repeat". I assume you meant, choose one of the 4 adjacent squares that is not dug out and dig in that direction (ie. not for all four - or as many as are not dug out)?
deefstes 1 year ago
I would assume this to be a simple program, since all it should need to do is, record the position and possible choices at each intersection, and explore each option... usually I would assume with a bias... like clockwise from up... and once it reaches the end of the possibility tree, it goes back to a previous decision, and increases the value...so assuming that 0 is up, 1 is right, down is 2 and left is 3... and ignoring reverse directions, and non-choices, it would narrow the possibilities
TheReasonWhyGuy 1 year ago
@TheReasonWhyGuy Yes very simple. The recursive function that traverses the maze is only 10 or so lines of code, and it pretty much works like you said.
RJLeffmann 1 year ago
@RJLeffmann lol... oddly enough, I've never made this before... XD... I just thought of the simplest way I'd make it a vuala XD
Though I'm curious, would it be faster to have both finish and start path find towards each other, and if the start path finder hits a space that any of the finish path finder has, then the path is found... Or perhaps that would take more code, and result in the same level of efficiency :|
idk... I should try it :)
TheReasonWhyGuy 1 year ago
manattan342 1 year ago
doing so with recursion would be easier then any algorithm.
Udayanverma 2 years ago
MarcusHab: Check out OpenGL if you want some hardware-accelerated graphics fun.
Conradhw: Maze algorithms and dungeon generators are two very different things. Maze algorithms solve mazes, usually obtaining the shortest route if more than one is available.
The workings of the algorithm have been visualised for you here, but the algorithm itself is unaware of any graphics. All it cares about is the data involved. It therefore makes no sense to make graphical demands of the algorithm itself.
superscatboy 2 years ago
looks great!
zengrz 2 years ago
I'm still waiting for the day that maze algorithms (dungeon generators) generate realisic corridors/rooms/interiors for 3D exploration (buildings/spaceships etc). There's so much you can do with maze algorithms & simple logic, in combination with defined geometry.
conradhw 3 years ago
prolog ?
gnubboleso 3 years ago
It is a short C/C++ program.
RJLeffmann 3 years ago
I get the concept of logic and algorithms (kinda), but how do you actually produce something you can see? The only thing I've ever been able do was in a run/command box. Whatever that's called.
MarcusHab 2 years ago
C/C++ has no support for graphics, so you have to make use of an existing graphics library, or use whatever graphics support you have in the operating system you're on. For doing graphics on Windows and OS X you can find information on MSDN and Apple Developer Center.
In this case it was just a console application (a run/command box) and I generated each image frame in memory and wrote it to disk in the BMP format, batch loaded all frames into VirtualDub and saved back as an AVI animation.
RJLeffmann 2 years ago
That's is pretty cool. Can you tall me more, or give me some links, how to do something like that ? ... I mean generate frames to memory and write it to disk in bmp ? I suppose it won't be easy for me, however, I would like to know more about this.
7h3k1ng 2 years ago
If you're looking for general information on programming you can probably type your favorite language into Google along with words like free book, tutorial, guide etc., and you can find a good article with everything you need to know about the BMP image format on Wikipedia.
RJLeffmann 2 years ago
flood fill?
ddrmasterdude 3 years ago
It is a depth first searching algorithm, but a graphical flood fill works after the same principle.
RJLeffmann 3 years ago
Cool! So out of curiosity, when the caver is "digging" the maze and he has more than one direction to dig in, does he simply choose from the available directions randomly?
TheMathGuy 4 years ago
Yes he does, and in addition you can have him dig several steps in the same direction, when possible, to vary between longer straight tunnels and shorter jittery ones.
RJLeffmann 4 years ago
nice
mishafe 4 years ago