Process
For generating levels, I came up with an interesting solution involving pentominos. Pentominos are like Tetris pieces, only they use five blocks instead of four. Like tetris pieces, they can also be rotated. There are 12 unique block configurations:
All twelve pentominos can be packed into a 5x12 grid. Depending on the difficulty of the level, we can use all 12 unique pieces, or anywhere from 1 to 11 unique pieces multiple times.
Packing pentominos is an example of the exact cover problem, which is solved here with an implementation of Donald Knuthâs Algorithm X. This algorithm was selected for both its speed and its awesome name.
After picking a start and end point of the maze, several randomized paths are cut out of the level. The width, number of turns, and number of cutting paths vary according to the difficulty of the level, but only one path is allowed to cut through the start and end points.
Easier levels have wider cutting paths and less variety of pentomino pieces. Computing the boolean subtraction of initial pentomino borders and the cutting paths gives us the finished level:
A game made for fun during the summer of 2009 at Luxurious Animals. How far will one pixel go to defend the galaxy?!
In addition to design tweaks and a new arcade cabinet model, I developed a novel maze-generating algorithm, which I explain in the process section below.