(Nice read! Table-driven maze generation in the Atari 2600 game ‘Entombed’ - paper here.)
Now I’m intrigued: usually, you’d use a LFSR (linear feedback shift register) for procedural generation, but, for rooms a linked list may be preferable. Maybe some combination of the two? I might have a look at it, once I’m prepared to lose my mind over it…
Edit: The part with the five-squares-tiles is at least counterintuitive. On the VCS (Atari 2600), you’d typically use background graphics for walls, etc. (There’s actually no other way to do this.) These are 40 fat pixels (each pixel is 4 normal pixels or color clocks wide) for a scanline and have to be updated, while the screen is drawn. But there are only registers for half of the playfield, which is either mirrored or repeated for the right side. These are stored in 3 registers: a 4-bit high-nibble and 2 full, byte-width registers for a total of 20 bits.
It may seem counterintuitive to store this in a format of five chunks. Having a look at the screenshot provided in the instruction manual, there are passages and walls, each 4 bits/fat pixels wide, displayed in a mirrored playfield. So, we’re talking probably about 5 nibbles being encoded by a single bit each, which would still do for a runtime efficient format.
As it turns out, the walls on either side are fixed, so there are just 4 segments to be encoded for each row, which is done in a somewhat curious fashion:
(Progressive rendering in Entombed. From the paper, see below.)
Apparently, having a cursory look at the paper, there’s in deed a mix of table and RNG, since bit “e” isn’t effective in terms of the playfield display, but rather instructs the RNG. The value of “X”, the value actually sent to the video chip (TIA) for a given segment, apparently depends on the values of a-e and involves a 32-byte lookup table.
It may be worth noting that the display chip of the VCS, the TIA, is mapping distinctive write-only and read-only registers to its addresses. So there’s no way to read previously set values and we’re talking about an in-memory model exclusively.
For a closer look on how playfield graphics work, you may want to experiment with this online-editor:
BTW, here’s the paper in question:
Entombed: An archaeological examination of an Atari 2600 game (2018)
John Aycock (University of Calgary, Canada), Tara Copplestone (University of York, United Kingdom)