(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)
I am intrigued by the state of mind of the programmer. I remember working on very little sleep on an original nineties 3D video game and I’d spent a month on this tough problem of optimizing the BSP collision system for fast particle updates and I’d finally cracked the problem and it was beautiful. It was an order of magnitude faster than what the previous programmer had come up with. I was dreaming in a type of abstract space where I’d never be able to communicate it in words. But it was all so clear to me… Lack of sleep is like not being sober. A very curious state of mind that perhaps can help sometimes navigate some fruitful patterns. What is creativity?
I read somewhere that back around 1978 Woz couldn’t quite get the Disk ][ interface design done, because every time he got tired and went to sleep he would lose ground. His solution was to go sleep-deprived for that extra amount of time he needed to complete everything, and the rest is history.