Jump to content
IGNORED

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

## Recommended Posts

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:

The publication from John Aycock and Tara Copplestone

Edited by The Historian
Attchached publication.
##### Share on other sites

Yeah I just saw that article.  Very cool.

##### Share on other sites

Any idea where the code can be located?

##### Share on other sites

```
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?

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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

##### Share on other sites

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! ???

##### Share on other sites

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.

##### Share on other sites

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```

##### Share on other sites

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.

##### Share on other sites

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```

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

• 2 years later...

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.

##### Share on other sites

• 7 months later...

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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
• ### Recently Browsing   0 members

• No registered users viewing this page.
×
×
• Create New...