Push the green flag to generate a random 3x3 maze. Push one of the buttons to generate a differently size maze. Try finding the path from one corner to another corner!
This is a Scratch adaptation of http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking. The generator initializes all cells in the maze to have 4 walls. It then picks a random cell and recursively carves passages to neighboring cells (in random order) that have not yet been visited. The animation shows the progress of the maze generator. Purple cells have been visited, but have not yet examined all their neighbors. Green cells have been visited and all their neighbors have been examined. The "cell" widget has 15 costumes, one for each possible passage configuration (a costume for passages in all 4 walls is not needed). The original algorithm uses a 2-dimensional array to represent cells in the maze. I use a "grid" list and convert between cell coordinates and index into the list using the "convert x y position to index" block which sets "index = x + (y-1) * size". Index can be converted to coordinates using division and modulo, e.g. "x = (index - 1) mod size + 1" and "y = floor((index - 1) / size) + 1". The original algorithm uses a bitmask to keep track of which cell walls contain a passage. I use a string and letters (N,S,E,W) to indicate available passages to neighboring cells. The original algorithm uses a randomized list of directions when deciding the order in which to carve passages from a cell. Instead I use an "encoded directions" number variable which is initialized in the "randomize encoded directions" block. The variable is treated as a 4 digit number which each digit (1, 2, 3, 4) representing a cardinal direction (W, E, N, S). The "carve_passage_from" block makes a recursive call, and since Scratch does not support block-local variables, I use a list "encoded directions stack" to save and restore the value of the "encoded directions" variable around invocations.
