(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.