Pitfall 2600 hack: Brand new map

[samiam]

Welcome everyone! I hope y'all enjoy my very first post to atariage.com

 

While there are a few hacks for the original 2600 Pitfall, I haven't seen one that changes the map Pitfall uses.

 

That in mind, using modern random number generation techniques that did not exist when David Crane wrote the original 2600 Pitfall in the early 1980s, I have created a version of Pitfall with a new map.

 

I have not fully play tested this map, but simulations indicate it should be possible to finish the map in under 20 minutes (just like in the original Pitfall).

 

A download is here:

 

http://samiam.org/pitfall/

 

I have also attached the files available there. This doesn't have the actual final rom; to play this new map, download the pitfall.xor file as well as the public domain xor.image (source code for Linux and Mac users) tool, and invoke the tool in the same directory as a ROM image of the original Pitfall game:

 

xor.image pitfall.rom pitfall.xor pitfallX.rom

 

(Note: pitfall.rom, the original Pitfall game ROM, may have the name pitfall.bin. If so: "xor.image pitfall.bin pitfall.xor pitfallX.rom")

 

This will create a ROM image—pitfallX.rom—that can be played in Stella or any other 2600 emulator (it is probably also possible to burn a EPROM and play it on a real 2600).

 

The resulting pitfallX.rom has the following cryptographic sums:

 

md5 5ed1d839f908f580220d6cf487633f90

sha1 fcb9b2068e05017e98c6502e0cb685f1aee3b6db

sha2-256 fe6be7879e58cc29e1fbbf6008a69244004c2b6b6c477d92a8b960d65503b7b7

 

All of the files attached to this post are donated to the public domain. I hope people enjoy this hack of Pitfall as much as I enjoyed seeing how much of a modern ranom number generator I could squeeze in to a 35-year-old 2600.

 

I am also working on a series of blogs looking at and exploring the pseudo random number generator (PRNG) Pitfall uses:

 

http://www.samiam.or...g/20130606.html

 

David Crane did agressively optimize the PRNG and made best use of the then state-of-the-art PRNG techniques of the early 1980s. While the generator I use is a little smaller and more flexible than the "LFSR" he uses, it does require more cycles to generate a decent map--cycles which Pitfall thankfully has during the vblank.

 

I hope to have time in the coming days to explain iin my blog just how clever Crane's optimizations were (the 16 bytes of 6502 code that is the core of his RNG is brilliant, taking me hours to fully understand), and to explain what PRNG I am using (it’s something called add-rotate-xor which, while used as early as 1987—five years after Pitfall—did not see widespread use until the late '00s).

Pitfall-newmap.zip

[Thomas Jentzsch]

David Crane did agressively optimize the PRNG and made best use of the then state-of-the-art PRNG techniques of the early 1980s. While the generator I use is a little smaller and more flexible than the "LFSR" he uses, it does require more cycles to generate a decent map--cycles which Pitfall thankfully has during the vblank.

 

I hope to have time in the coming days to explain iin my blog just how clever Crane's optimizations were (the 16 bytes of 6502 code that is the core of his RNG is brilliant, taking me hours to fully understand), and to explain what PRNG I am using (it’s something called add-rotate-xor which, while used as early as 1987—five years after Pitfall—did not see widespread use until the late '00s).

I am really interested into this.

 

BTW: I suppose your XOR works with NTSC and PAL versions, right?

[samiam]

Hey, Thomas...thanks so much for your disassembly of the 4k Pitfall rom. I would not have been able to study the PRNG used without your hard work.

 

I think it would be a good idea to make it possible to have this hack work in the PAL version. I have been having problems assembling your pitfall.asm file in DASM 2.20.11. A couple of questions:

• Which version of DASM should I use to assemble you pitfall.asm to get the exact same binary as David Crane's original pitfall ROM?
  
• Which are the exact command line switches with DASM to use?
  

Once I have that information, I will be able to make a version of this new map hack that's a diff against your pitfall.asm file, allowing it to easily compile for NTSC, PAL, and with whatever other hacks people have. In addition, it will allow me to remove the NOP padding the current hack uses (increasing the number of free "0" bytes at the bottom of the ROM from six to 11), and even have the two "magic numbers" in the new ARX code to be changed at the top of the file (note: of the 65,536 possible "magic numbers", only 40 make usable 256-screen Pitfall maps).

 

Did I mention that the jungle in the hacked Pitfall is bigger than the jungle in the original Pitfall, and there is no "Mobil Ave" location like there is if $81/random is set to 0 in the original Pitfall (such as when "frying" the game)?

Edited June 10, 2013 by samiam

[Thomas Jentzsch]

Add

 

TIA_BASE_READ_ADDRESS = $30

 

at the very beginning of the file. My code uses something like "CXP0FB-$30" because the DASM TIA read address was hardwired to $30 back then.

 

Regarding the parameters, only -f3 is really relevant.

 

BTW: What got you interested into Pitfall!

Edited June 10, 2013 by Thomas Jentzsch

[samiam]

Add

 

TIA_BASE_READ_ADDRESS = $30

 

at the very beginning of the file.

 

That fixed it. I was able to assemble pitfall.asm with that line added to the top. Attached is the "diff" file which takes you pitfall.asm file, updates it to compile in dasm-2.20.11, and changes the map generated.

 

For people not familiar with diff files: A '-' at the beginning of a line means "remove this line". A '+' at the beginning of a line means "add this line".

 

Regarding the parameters, only -f3 is really relevant.

 

Here's the incantation I use to assemble it with dasm-2.20.11: ./bin/dasm.exe pitfall-with-tia-line.asm -f3 -opitfall.rom -Imachines/atari2600/

 

BTW: What got you interested into Pitfall!

 

I'm very impressed at how David Crane was able to fit a huge 255-location jungle in only 31 bytes of code. Whenever I look at a modern crypto algorithm, I always ask myself "can you run this in a 2600?" so wanted to see how pieces of modern crypto technology can be used with classic tech like the 2600. And, they help: Modern crypto makes it possible for me to fit an even bigger 256-location jungle in less code (26 instead of 31 bytes), albeit using more cycles.

 

As an aside, does anyone know of a way in Stella or another emulator to know exactly how many cycles are left in the vblank interval?

 

pitfall-arx.diff.txt

 

Here is the core of the random number generator:

 

; add-xor-rotate: a=5; b=11; r = (r >> 1) | (r << 7); r -= a; r ^= b (0xb);

lda random ; ?

lsr ; 2

ror random ; 3

lda random ; 3

sec ; 2

sbc #$03 ; 3

eor #$0b ; 3

sta random ; ?

 

And the inverse function (Pitfall requires an invertible function, which rules out otherwise promising PRNGs like an 8-bit version of XORshift):

 

; ARX-style code: a=3; b=11 (0xb); r ^= b; r += a; r = (r << 1) | (r >> 7);

lda random ; ?

eor #$0b ; ?

clc ; ?

adc #$03 ; ?

sta random ; 3

asl ; 2

rol random ; 5

 

The above routines are run three times to get decent "diffusion" (nine times when traveling underground to retain Pitfall's property of a single move underground being like three moves on the surface). "A" and "B" can not be chosen at random; only 40 values of "A" and "B" (out of 65,536 possible values) are a permutation (when run repeatedly, a=3 and b=11 cause the function to go through all 256 possible values).

Edited June 10, 2013 by samiam

[roland p]

As an aside, does anyone know of a way in Stella or another emulator to know exactly how many cycles are left in the vblank interval?

 

pitfall-arx.diff.txt

 

I just did a quick look at the pitfall code and added some echo's:

echo "LAST VBLANK INSTRUCTION",*
nop

.waitTim:
lda INTIM ; 4
bne .waitTim ; 2³

echo "START SCREEN",*

sta WSYNC ; 3
;---------------------------------------
sta HMOVE ; 3
sta VBLANK ; 3
sta CXCLR ; 3
sta temp3 ; 3 don't show anything before score
jsr ShowDigits ; 6 draw score

(This is my clumsy way of calculating free cycles)

If you compile the code, you will see the addresses of the echo's. If you add those addresses in Stella as breakpoints (type 'break $ffff' in the debugger (press ~, above the tab), replace $ffff with the right address) stella will stop the next time those addresses are reached. In the debugger you can see 'f. cyc'. The first break will have a lower f cyc than the second break. substract the low f cyc from the high f cyc and you have your amount of cycles that are left.

[Chuck D. Head]

 

Once I have that information, I will be able to make a version of this new map hack that's a diff against your pitfall.asm file, allowing it to easily compile for NTSC, PAL, and with whatever other hacks people have. In addition, it will allow me to remove the NOP padding the current hack uses (increasing the number of free "0" bytes at the bottom of the ROM from six to 11), and even have the two "magic numbers" in the new ARX code to be changed at the top of the file (note: of the 65,536 possible "magic numbers", only 40 make usable 256-screen Pitfall maps).

 

 

I always hesitate to post in this kind of thread, as I am pretty ignorant when it comes to this level of programming, but..... with what you have done and learned so far, would it be possible to create a version of the rom that "randomly" generated one of the 40 possible screen configurations? I also justed wanted to post ahead of the inevitable Random Terrain "controlled randomness post", which is coming in 3, 2, 1.......... :-)

[Thomas Jentzsch]

Why not using Stella debugger? The timer values are displayed in I/O tab.

[samiam]

If you compile the code, you will see the addresses of the echo's.

 

Hmmm...dasm-2.20 doesn't seem to have that feature. Never mind, I can look at the Distella output with the raw addresses:

 

STX $E0 ;3

LF658: LDA INTIM ;4

BNE LF658 ;2

STA AUDC1 ;3

 

OK, the last pre-vblank instruction is at $F658 (The page zero STX instruction is 2 bytes long) and the next one after the "wait for vblank to end" busy look starts at $F65D.

 

Let's debug that...

 

Load ROM in Stella, hit '~' to enter debug console, then type in "break $F658" followed by "break $F65D".

OK, we first hit the vblank on cycle 17736 and end it on cycle 19618...that gives us 1882 cycles.

 

Next, count the cycles in the most expensive form of the ARX core:

 

lda page 0 3 cycles + lsr 2 cycles + ror page 0 5 cycles (!!) + lda page 0 3 more cycles + sec 2 cycles + sbc immediate 2 cycles + eor immediate 2 cycles + sta page 0 3 cycles + dex 2 cycles + 4 cycles for branch (I'm not bothering to see if it crosses a page boundary and will just assume it does) 3 + 2 + 5 + 3 + 2 + 2 + 2 + 3 + 2 + 4 = 28 cycles per round. We easily have 1500 cycles to play with, so there should not be a problem running this for up to 49 rounds. So, if I wanted to, we could run the ARX cycle for 15 rounds, 45 rounds when going underground. Or even have something like 7 rounds for above-ground moves and and 49 rounds (7 screens) for underground moves.

 

The reason I wanted to count this is because a single round of ARX gives really bad diffusion; ARX gets its strength from being very cheap to run and running with as many rounds as possible. 1 round of an ARX gave me maps so bad as to be, IMHO, unusable (I think there was one with 7 treasure locations next to each other); three rounds gives us a decent map; it's nice to know I could easily add more rounds if needed.

[samiam]

Would it be possible to create a version of the rom that "randomly" generated one of the 40 possible screen configurations? I also justed wanted to post ahead of the inevitable Random Terrain "controlled randomness post", which is coming in 3, 2, 1.......... :-)

 

For someone to pull this off, we would probably have to extend Pitfall to use bank switching. Right now, Pitfall has six—make that 11—bytes free. For us to pull off having "game select", with 40 different games (one for each set of working "magic constants"), not only will we will have to write all the code to process "game select" being pressed, we also need to have 80 or 120 bytes to store the table of magic constants.

 

There's also the issue that different maps have different lengths (number of screens to travel through to get all treasures), so we will either have to disable the timer, or have different maps have different time limits. I actually chose the constants I did because it appears, based on my simulations, to have about the same optimum solution length as the original Pitfall (I also had to modify the code for placing walls underground a bit to pull it off).

Edited June 10, 2013 by samiam

[samiam]

Talking to myself, but further research in to these ARX pseudo-random sequences shows that there are actually some 2,176 possible jungles where once can, from the starting screen (0xc4), obtain all 32 treasures. In more detail:

SizeCount

125 2

165 2

169 2

177 6

191 4

197 10

201 4

204 4

207 2

209 18

217 16

219 8

220 8

223 6

224 6

225 16

226 2

228 4

229 4

230 12

233 22

234 16

235 24

236 16

237 4

238 10

239 36

240 16

241 22

242 10

243 26

244 22

245 32

246 20

247 26

248 36

249 80

250 144

251 72

252 244

253 76

254 88

255 958

256 40

 

In the above table, the left column is the size of the jungle and the right column is the number of possible jungles with that size. I have already mentioned the 40 256-location jungles. There are nearly 1,000 jungles the same size as Pitfall's jungle (with only a single location in a "Mobil Ave" trap) and jungles as small as 125 locations (a=16 b=10 and a=144 b=138, where "a" is the ADC/SBC constant and "b" is the EOR constant). I really should make a (16, 10) "trainer" jungle.

Edited June 11, 2013 by samiam

[samiam]

I really should make a (16, 10) "trainer" jungle.

 

Done. See the attached file, which includes directions on how to make a 125-location "trainer" version of Pitfall. I have also given the player unlimited lives (albeit with a one-minute penalty every time the player dies), 60 minutes to finish the map, and there are no frustrating underground walls.

 

To play this map, download the attached file an invoke the xor.image tool in the same directory as both the pitfallT.xor file and a ROM image of the original Pitfall game:

 

xor.image pitfall.rom pitfallT.xor pitfallT.rom

 

(Note: pitfall.rom, the original Pitfall game ROM, may have the name pitfall.bin. If so: "xor.image pitfall.bin pitfallT.xor pitfallT.rom")

 

This will create a ROM image--pitfallT.rom--that can be played in Stella or any other 2600 emulator. It is probably also possible to download it to a Harmony Cartridge (or even burn an EPROM) to play it on a real 2600.

 

The resulting pitfallT.rom has the following cryptographic sums:

 

md5 85a5a15f921b06e7acf7a08826dcf963

sha-2-256 b649d9f3f542b8f8dff44553bdb726ce3cf32ea87fdeb07371b4d7bb732431c1

 

All of my modifications are donated to the public domain.

small-jungle.zip

Edited June 11, 2013 by samiam

[samiam]

One final note: In the easy "16, 10" Jungle, which only has 125 locations, the other 131 places still exist--but in 19 other mini-jungles. Taking a debugger, it's possible to change the Jungle one starts in by changing address $FAA9 (set by default to "c4"), then hitting "game reset" to go to one of the other 19 jungles: 01 03 05 07 42 46 47 4a 86 87 c0 c1 c2 c3 c5 c7 c8 cb d3

 

The most interesting mini-jungle is jungle "46"; the most annoying jungles are jungles "c3", "cb", and the one-location "Mobil Ave" "d3" jungle. Note that none of these 19 other jungles have any treasure.

[Thomas Jentzsch]

Hm, why are you using not a more simple LFSR? Just XOR the values, but do not subtract anything. There are quite a lot of XOR values which generate 255 different random numbers values before repeating.

 

 lda random ; 3
 lsr ; 2
 bcc .skipEor ; 2³
 eor #RAND_EOR_8 ; 2
.skipEor: ;
 sta random ; 3

 

For RAND_EOR_8 you can use the 8 bit values you find here.

Edited June 11, 2013 by Thomas Jentzsch

[samiam]

Hm, why are you using not a more simple LFSR?

 

Ahh, yes, I didn't think to use a Galois Linear Feedback Shift Register (LFSR) instead of the Fibonacci LFSR David Crane used (for people wondering what the heck Thomas and I are talking about, http://en.wikipedia.org/wiki/LFSR ). Very clever and more compact than an add-rotate-XOR (ARX; EOR is sometimes called XOR).

 

I still prefer an ARX random number generator because it gives us a lot more solvable jungles (2,176 instead of 16) including smaller "training" jungles--alas, none of the non-255-period 8-bit Galois LFSRs gives us a jungle with all 32 treasures.

 

My simulations show that the tap sequence "d4" (#RAND_EOR_8 with the value "d4") generates a Pitfall map that may or may not be solvable in 20 minutes; all of the other tap sequences appear to be impossible to solve in 20 (increasing the initial time over 20 minutes require either using two more bytes or increasing the player's initial score).

 

For the record, here's the inverse of the "d4" tap sequence:

 

lda random

asl

bcc .skipEor

eor #a9

.skipEor:

sta random

 

- Sam

Edited June 11, 2013 by samiam

[Thomas Jentzsch]

Ah, so you are doing a simulation. I figure you have a map generator and some mapping algorithm, right?

[Mr SQL]

Great thread! Interesting stuff

[Thomas Jentzsch]

Hmmm...dasm-2.20 doesn't seem to have that feature.

Use -v4, this makes DASM really verbose.

[samiam]

Ah, so you are doing a simulation. I figure you have a map generator and some mapping algorithm, right?

 

Exactly. I have a number of programs to help me find a good Pitfall random number generator:

• The first program, written in C, shows me a text Pitfall map for a given random number generator. Every time there is a ladder room, the map goes down the ladder and sees if it is a dead end or an exit; if it's an exit, it shows where the exit is and how many caves one must go through to get to the exit.
  
• The second program, written in Python, sees how long it takes to get all of the treasures on a map. The Python program first figures out how many locations Harry must walk to go from any given location on the map to a given treasure; this is calculated for all 32 treasures. The program then, from the starting location (which I just keep at "c4"), goes to the closest treasure and grabs it, noting how many locations Harry had to walk to get to the treasure. It then goes to the closest remaining treasure and grabs it; this is repeated until no treasures remain. This may not give us an optimal solution (to find an optimal solution is an extremely hard problem called the "travelling salesman problem"), but it does give us the same solution experienced Pitfall players use to finish the game. The program tells us how many locations Harry had to walk through to get all of the treasures (205 for the stock Pitfall game).
  
• I have a third program which gives me detailed information about how many "mini jungles" a given random number generator makes, telling me how many different jungles (cycles) a given RNG sequence has, and finding out if there is a jungle that has both the stock player start (c4) and all 32 treasures. Stock Pitfall, for example, has two jungles: The 255-location main jungle, and a 1-location "Mobil Ave" (This name comes from the third Matrix movie) looping jungle (the "00" location with a ladder, a wall on the left, and a single rolling log) which one can enter by hacking the ROM, by setting memory location $81 to 00 in an emulator and then walking either left or right to the next jungle location, or sometimes by "frying" the console.
  

The pathfinder is not as good as of a simulation as Thomas' "Perfect Pitfall" simulation ( http://atariage.com/...ct-pitfall-142/ ); it only counts the number of locations one walks through to get all of the treasures and doesn't talk in to account some kinds of locations take longer to walk through than other locations.

 

For people with a UNIX-like development environment (gcc, make, and Python), attached are a copy of the tools I have been using for this research.

 

Mapping-tools.zip includes basic documentation in a "README" file.

 

The "xar-8" tool I have been using to evaluate potential Jungles to see if they can be finished is used by doing something like this in a UNIX clone (Cygwin, Linux, MAC OS X with developer tools, etc.)

 

mv xar-8.c.txt xar-8.c

gcc -O3 -o xar-8 xar-8.c

./xar-8.exe | grep start | awk '{print $11 " " $1 " " $2}' | sort -n | head

 

The output is three columns: Jungle size, a (additive constant) value, b (EOR/XOR constant) value. Note: xar-8 has a bug where, if the jungle with all of the treasures is not the largest possible Jungle for a given set of constants, it will give us an incorrect Jungle size. I don't think this happens with the add-rotate-XOR code I'm using.

mapping-tools.zip

xar-8.c.txt

Edited June 11, 2013 by samiam

[Thomas Jentzsch]

Did David Crane ever explain how he found a working setup for Pitfall! ?

[samiam]

We should ask him. Looking at his code, it looks like he went to a lot of thinking to find the map, and that, back in 1980-1982, Galois (as opposed to Fibonacci) LFSRs were not around. Even if add-rotate-XOR was around back then, I think Crane would have used a Galois LFSR instead (fewer bytes, fewer cycles). I will send him an email and ask him; his address is in his rarely used Twitter feed at https://twitter.com/pitfallcreator

 

Edit: I sent him an email and a tweet pointing to this thread.

Edited June 11, 2013 by samiam

[+Gemintronic]

Did David Crane ever explain how he found a working setup for Pitfall! ?

 

Yup. Somewhere in this vid:

http://www.youtube.com/watch?v=MBT1OK6VAIU

 

Basically, it sounds like trial and error.

[Nukey Shay]

For someone to pull this off, we would probably have to extend Pitfall to use bank switching. Right now, Pitfall has six~make that 11~bytes free. For us to pull off having "game select", with 40 different games (one for each set of working "magic constants"), not only will we will have to write all the code to process "game select" being pressed, we also need to have 80 or 120 bytes to store the table of magic constants.

Plenty of areas that can be edited or rewritten to save space. The hack I did of this game is still only 4k.

[Brian O]