The software I’m currently working on is a mod for the very popular animation-creating tool called Scratch, developed by MIT. Our mod, tentatively named Cellular, extends the capabilities of Scratch by allowing the sprites to not just interact with each other, but also the environment beneath them.
The environment (known as the stage in Scratch), is divided up into cells that can have attributes assigned to them, which can then be read from and written to by the sprites as they move about.
Here’s an example of what can be achieved with Cellular…
So what’s happening here? Well, the cat is creating a maze using a well known algorithm based on a depth-first search. In brief, the algorithm goes:
- Mark all cells as unvisited, and place the cat in a random cell, which will be the exit.
- Get a list of neighbour cells, and for each neighbour, starting with a randomly selected one:
- Move to the chosen cell and remove the wall separating the two
- Recurse the algorithm, using the new as the current cell
- Move back to the previous cell
The cat will eventually fill all available space on the stage with paths, and an entry to the maze can be chosen at will (obviously a good choice of entry will be suitably far from the exit).
There’s guaranteed to be only one correct path out of the maze, as the algorithm will neven create any loops or circuits.
What I find particularly cool about maze generation algorithms is that they expose students to the concept of recursion in a fun and practical way. Also, maze generators are typically just modified search algorithms, which form part of the fundamentals of Computer Science education.
*