2600 USGames Entombed - The mysterious origins of an uncrackable video game

[The Historian]

An interesting article from the BBC on the maze generation of the game Entombed. It seems the researchers just don't understand how it works. 

Quote

As I dug into this maze algorithm, it became clear that this was something that seemed to be fairly unique to this maze game – John Aycock

I wonder if anyone here has looked into the code for this game?

 

BBC Article here: 

http://www.bbc.com/future/story/20190919-the-maze-puzzle-hidden-within-an-early-video-game

The publication from John Aycock and Tara Copplestone

https://arxiv.org/ftp/arxiv/papers/1811/1811.02035.pdf

 

 

Entombed - An archaeological examination of an Atari 2600 game.pdf

Edited September 23, 2019 by The Historian
Attchached publication.

[Tempest]

Yeah I just saw that article.  Very cool.

[+Psionic]

Also being discussed here...

https://atariage.com/forums/topic/296385-atari-in-the-news-cool-bbc-article/

 

[Tensor]

Any idea where the code can be located?

[Nukey Shay]

  lda ram_87   ;3 rnd
  sta ram_82   ;3
  sta ram_84   ;3
  ldx #$04     ;2
LB46C
  lsr          ;2
  rol ram_A0   ;5
  lsr ram_82   ;5
  rol ram_A0   ;5
  asl ram_84   ;5
  rol ram_90   ;5
  asl ram_87   ;5
  rol ram_90   ;5
  dex          ;2
  bne LB46C    ;2
  ldx #$1F     ;2
LB480
  lda ram_8F,x ;4
  sta ram_90,x ;4
  dex          ;2
  bne LB480    ;2

$90-$9F = PF1

$A0-$AF = PF2

 

Simple, but effective.  I wonder if this is the same method used in Diggerbonk?

[+Cafeman]

Nukey, what is the difference between using LSR and ROR,   Or ASL and ROL?

[+Andrew Davie]

12 minutes ago, Cafeman said:

Nukey, what is the difference between using LSR and ROR,   Or ASL and ROL?

I'm not Nukey, but...
LSR and ASL shift a zero bit onto the "end"
ROR and ROL shift the carry bit onto the "end"
If you're shifting/rolling right, then the bit goes into D7.
If you're shifting/rolling left, then the bit goes into D0.
 

[+Cafeman]

Ok, thanks. Do you know of an example where one is preferable to the other?

[+Omegamatrix]

3 hours ago, Andrew Davie said:

I'm not Nukey, but...
 

Hmmmm. I feel the conspiracy theories have already started Mr Davie, or should I say Andrew Shay! ???

[+Karl G]

1 hour ago, Cafeman said:

Ok, thanks. Do you know of an example where one is preferable to the other?

if you are bit-shifting for the purpose of multiplying or dividing by two, then you don't want to have carry shifted in, so you would prefer LSR and ASL. 

 

ROR and ROL can be used e.g. if you want to shift the bits from one variable to another, like for a scrolling playfield.  The bit that falls off the end would go into carry, and would be shifted in for the second operation.

[+Andrew Davie]

2 hours ago, Cafeman said:

Ok, thanks. Do you know of an example where one is preferable to the other?

double a 16-bit value uses both...

	asl value			; lo byte
	rol value+1			; hi byte

 

[Nukey Shay]

Without rol/ror, that would be 3x longer:

  lda value+1

  asl

  asl value

  bcc NoCarry

  ora #$01

NoCarry

  sta value+1

 

Not getting how Entombed has these "archaeologists" stumped, tho.  It's just using the separate nybbles of rnd for PF1 and PF2...each bit position corresponds to 2 bit positions of PF to make the passages wide enough for the player character to move though.

 

[+Andrew Davie]

7 hours ago, Nukey Shay said:

Without rol/ror, that would be 3x longer:

 

 

Not quite! I think this would work...

		lda value+1
		asl
		asl value
		adc #0
		sta value+1

 

[+Omegamatrix]

    asl Value+1
    asl Value
    bcc .finish
    inc Value+1
.finish:

 

[+Omegamatrix]

19 hours ago, Nukey Shay said:

Not getting how Entombed has these "archaeologists" stumped, tho.  It's just using the separate nybbles of rnd for PF1 and PF2...each bit position corresponds to 2 bit positions of PF to make the passages wide enough for the player character to move though.

 

You're right. This part of the code looks straight forward. So really the magic is in the pattern of numbers from the pseudo random generator, and how that corresponds to D7 and D0.

 

I have not looked at the rest of the code at all, but I am wondering if this random generator is only called for this routine? It would be more interesting if it wasn't. If it is not called only by this routine I would want to know if it is called every nth time, repeatedly.

[+SpiceWare]

The story continues: Still Entombed After All These Years: The continuing twists and turns of a maze game

 

For this followup they were able to get ahold of one of the two inventors of the maze algorithm, Paul Allen Newell.

 

Quote

The logic behind how the 32-byte table mapped abcde values into X values was an open question. Why, for example, did 01101 produce 0, an empty passage, as opposed to a wall or a random selection between the two options? Aycock and Copplestone (2019, 4:11) took a conservative stance given all the available evidence, concluding that 'the table values were manually chosen, or manually tuned, by the maze algorithm designer', while others sought deeper meaning in the table (e.g., Brüning nd; colinbeveridge 2019; Mächler and Naccache 2021); it was an interesting puzzle.

 

The table, as it turned out, was a red herring. Note the reverse engineering performed was not incorrect, but the use of the table reflected an intermediate step rather than the algorithm's true design; there would have been no way to non-speculatively infer the actual design from what remained in Entombed. However, since Newell extensively documented the algorithm when it was developed (Figure 4), we need not speculate.

 

emphasis added.

[+Psionic]

Crazy how a mostly unknown game has suddenly attracted so much attention after all these years.  Not a bad thing though, especially since the attention resulted in the programmer finally releasing a number of artifacts related to the game's development that he's had in his possession.

 

https://www.atariprotos.com/2600/software/entombed/entombed.htm