How levels are generated in Spaceman 8
All levels in Spaceman 8 are procedurally generated and get larger and more complicated as the game progresses. PICO-8 has technical limitations so the map generator has to be relatively simple. The level generator works in two steps: first by generating the general structure of the level and then adding superficial details on the map that is eventually drawn on the screen. The map contains randomly placed objects that are often found in the ends of the map corridors.
The seed map
The seed map has two types of cells: “open” and “closed” cells. Map is initialized with closed cells.
All level objects (the collectables and the exits) are treated similarly.
- Start with single open cell in the center of the map
- Position all objects in the starting cell
- Pick a random cell on the map using these rules:
- The cell has to be closed
- Zero to one diagonal (NW, NE, SE, SW) neighbors have to be open
- 1 or 2 cardinal (N, E, S, W) neighbors have to be open
- Change the cell type open and move an object from any of the neighboring cells or a randomly picked object in the new open cell
- Repeat from step 3 until map is large enough
You now have a branching, mazelike map that has all open cells connected at least from one direction. The objects should be positioned (mostly) in the ends of the corridors, further from the starting position (this of course depends on luck and you should fiddle with it if you want to make sure the object locations are always challenging).
Making it pretty
The map is upscaled so that each cell now takes twice the cells vertically and horizontally. There is a random change that a cell flips its state if the neighboring cell is of the opposite type. The resizing is done again and again so that the level corridors are suitably wide (at first they are only one tile wide, then two, four etc.). The randomness from the resizing steps carries over and adds first large and then (relatively) smaller random variation to the edges.
The visible map is built from the data using a tileset that has tiles for different edge/side combinations.
The seed map is scanned cell-by-cell and if the current tile is closed, a bitmask is built from the four neighboring seed tiles in the cardinal directions (see the linked cart for working code). The bitmask tells us the tile we want on the visible map. E.g. if all neighboring seed tiles are closed, the bitmask will be binary) 1111b = 15, we know we want to use tile 15 which is a fully filled tile. If one of the sides is open, let’s say to the east, the mask will be 1101b = 13 and we will use tile 13.
If the current seed tile is empty, the visible map will simply have an empty cell. All of this is very easy to implement when just following instructions (basically just make sure the tile order is the same and it will work) but here is a good article about the technique in case you want more details.
Finally, the visible map has some random variations added on it: empty cells have a random change to have a non-black background tile and the fully filled tiles have a random change to have a pebble tile and so on. This randomness doesn’t change the level geometry.
I saved the best for last. Richard’s Evolving Sprite Tool, as the name implies, evolves sprites. The main idea is that the program generates a grid of mutated sprites and you can choose the one that looks good. The selected sprite then spawns mutated offspring. This continues until you decide the sprite is good enough. On the left, there’s an example of an evolved and hand-colored sprite (grabbed from the Retro Remakes forum thread). 
Note: Since this tool has gone AWOL, here’s something similar: 
