Push the green flag to generate a random 10x10 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 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 a "direction mask" number variable which is initialized in the "randomize direction mask" 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 "direction mask stack" to save and restore the value of the "direction mask" variable around invocations.
