Mazegenerator: the algorithm (alt)
211
Published 2012-07-31
About the video.
This is the first video dedicated to the maze generator. It explains the algorithm.
Feel free to ask any questions if it's not clear what it does at any given point.
This video was made due to comments I got on the Sudoku solver and should show you that backtracking is a generic solution to a lot of problems. It's very inefficient for Sudoku solvers, but for a maze, it's fairly decent.
Up next is the dedication to the source code of this algorithm (in python).
Explanation of the video content.
Colours.
The black squares are walls, illegal areas where you can't move when solving the maze.
The white squares are paths, legal areas where you can move when solving the maze.
The orange square carves hallways through the walls that are there by default.
The purple squares indicate legal moves for it to make.
The purple squares only appear on walls, never on paths.
The green squares are the points it keeps in it's memory (stack).
The blue square is it's endpoint when the algorithm is done.
Backtracking.
Whenever the orange square changes it's direction without being forced to, it will remember where it did so. This point is put on top of a stack. When it carves a dead end or whenever it is in a point where there are no legal moves left it will move back to the top-most point on the stack.
End condition.
When the stack is empty, the maze is complete.
Features of the maze.
This maze is fully and simply connected.
"Fully" means that you can get from any random point A to any other random point B, even these are both legal areas (i.e. white).
"Simply" means that there are no loops or multiple routes between any two given points.
See you guys in the next video.
Feel free to comment, rate and subscribe.
Regards,
FreeHomeBrew