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.
There’s a cool program that’s been around for a few years made by the MIT Media Lab called Scratch. It’s an interface for creating basic animations with sprites and sounds. Rather than writing scripts using code, the user connects ‘blocks’ to program the sprites to move around the stage. It’s like being able to program without having to learn the syntax of a specific language. Not surprisingly, there’s a lot of interest from educators (both secondary and tertiary level) in the software, as it makes learning about computer programming much more accessible to students.
Enchanting is a modification of Scratch that allows you to program the Lego NXT robot using the same interface. I’ve been involved as a contributor over the past few months, and we’re using the software with the year 10 students this semester at the John Monash Science School. The reason that we’ve opted to use the Scratch-based interface for controlling the NXTs is that it more closely resembles a real programming language when compared to the Lego Mindstorms software.
Here’s a comparison showing the same program written in both interfaces… you can see that Mindstorms is quite blinged up with pretty pictures and symbols, but lacks any resemblance to a control structure that you’d find in a typical programming language.
The students took to it very well, and I’m currently working on another mod of Scratch that will allow the students to simulate natural systems using the same interface, similar to the core concepts of Star Logo TNG. The Enchanting team are currently porting the software to the BYOB mod of Scratch, which provides the functionality to create custom blocks (functions) and list data structures.