Pixel Spaceships 

Description Pixel Spaceships harken back to the olden days of video game sprites in the era of the Apple ][, MSDOS, fontbased graphics and monochrome monitors. They are algorithmically generated in the millions by combinatorial methods. The algorithm is explained in more detail below and is an outgrowth of the algorithm used for the Pixel Robots. Applets The demo applet uses a random box fitting strategy to fill the image with colored spaceships of varying sizes. Algorithm (much of this description is just borrowed from Pixel Robots and modifed as appropriate) The spaceships are generated within a grid of cells that is 12 columns wide by 12 rows tall. Each cell may be either on (black) or off (white). Without any further constraints this would allow for 2^144 combinations  a monstrously ridiculously impossibly huge number. Unfortunately, most of those combinations are not "interesting" in the context of this project. So the cells are constrained in several ways to limit the total number of combinations while focusing in on those that produce interesting spaceship shapes. The first constraint imposed is that the cells must be horizontally symetrical. This reduces the effective grid size to 6x12 cells, reducing the number of combinations to 2^72, which is still impossibly huge. The second constraint imposed comes about after flipping the problem on it's head. Instead of asking which cells to turn on in order to create spaceship shapes (which is a nontrivial problem) the question becomes which cells to avoid turning on because they constitute the "interior" of the ship. Then once the interior is defined, simply draw an outline around it, thus producing the desired spaceshiplike shapes. In the end, 32 cells are directly controlled, allowing 2^32, about 4 billion, unique spaceships. A single 32bit number is used to control the shape of the spaceship, with 26 bits controlling the main body portion, and the remaining 6 bits controlling the cockpit area. Or, if you prefer color, here are some more... Or, if you want LOTS of them, here are 7500 more in wallpaper form... Further Exploration For now, just see Pixel Robots and let that suggest possible ways that various 32bit values might encode for specific spaceships, and vice versa. There's a "Galaxian" or "Phoenix" clone just waiting to be born from this work. :D And here's a sneak peek at a higher resolution version I'm working on: 



© 2006 Dave Bollinger 