# HG changeset patch # User Robert McIntyre # Date 1353611541 21600 # Node ID b531d490859cf9c8866d63cc3083d129f0890f2d # Parent e1dcad3ce9675033b89cae9c0576fc7387035589 submitting to TAS... diff -r e1dcad3ce967 -r b531d490859c .hgignore --- a/.hgignore Thu Nov 22 11:36:07 2012 -0600 +++ b/.hgignore Thu Nov 22 13:12:21 2012 -0600 @@ -18,4 +18,5 @@ html/* java/lib/* render/* -zophar/* \ No newline at end of file +zophar/* +video/* diff -r e1dcad3ce967 -r b531d490859c org/tas-submission.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/org/tas-submission.txt Thu Nov 22 13:12:21 2012 -0600 @@ -0,0 +1,287 @@ +Pokemon Yellow Total Control Hack. Reprogramming the game from the inside! + +!! Game objectives + +* Emulator used: vba-rerecording 23.5 +* Reprogram the Game from the inside + +!! Comments + +I've included a detailed writeup here: +http://aurellem.org/vba-clojure/html/total-control.html + +There is a video at: +http://www.youtube.com/watch?v=p5T81yHkHtI with keypress visualizations + +The following are the highlights: + +! Introduction + +Think of pokemon yellow as creating a little universe with certain +rules. Inside that universe, you can buy items, defeat rival trainers, +and raise your pokemon. But within that universe, you are bound by the +rules of pokemon. You can't build new buildings, or change the music, +or change your clothes.. There are some games (like chess), where it +is not possible to alter the rules of the game from within the +game. No matter what moves you make in chess, you can never change the +rules of the game so that it becomes checkers or basketball. The point +of this run is to show that you CAN change the rules in pokemon +yellow. There is a certain sequence of valid actions (like walking +from one place to another or buying items) that will allow you to +transform pokemon yellow into Pacman, or Tetris, or Pong, or a MIDI +player, or anything else you can imagine. + + +! Background + +The speedrun (http://tasvideos.org/2913S.html) by Felipe Lopes de +Freitas (p4wn3r), beats pokemon yellow in only 1 minute and 36 +seconds. It does it by corrupting the in-game item list so that he can +advance the list past its normal limit of 20 items. The memory +immediately after the item list includes the warp points for the +current map, and by treating that data as items and switching and +dropping them, he can make the door from his house take him directly +to the end of the game. + +When I first saw that speedrun, I was amazed at how fast pokemon +yellow could be beaten, and that it was possible to manipulate the +game from the inside, using only the item list. I wondered how far I +could extend the techniques found in p4wn3r's run. + +The gameboy is an 8 bit computer. That means that ultimately, anything +that happens in pokemon is a result of the gameboy's CPU reading a +stream of 8 bit numbers and doing whatever those numbers mean. For +example, in the gameboy, the numbers: + +62 16 37 224 47 240 37 230 15 55 + +mean to check which buttons are currently pressed and copy that result +into the "A" register. With enough numbers, you can spell out an +interactive program that reads input from the buttons and allows you +to write any program you want to the gameboy. Once you have assembled +such a program and forced the game to run it, you have won, since you +can use that program to write any other program (like Tetris or +Pacman) over pokemon yellow's code. I call a program that allows you +to write any other program a "bootstrapping program". So, the goal is +to somehow get a bootstrapping program into pokemon yellow and then +force yellow to run that program instead of its own. + +How can we spell out such a program? Everything in the game is +ultimately numbers, including all items, pokemon, levels, etc. In +particular, the item list looks like: + + + item-one-id (0-255) + item-one-quantity (0-255) + item-two-id (0-255) + item-two-quantity (0-255) + . + . + . + + +Let's consider the button measuring program [37 62 16 37 224 37 240 +37 230 15 55] from before. Interpreted as items and item quantities, it is + + lemonade x16 + guard spec. x224 + leaf stone x240 + guard spec. x230 + parlyz heal x55 + +So, if we can get the right items in the right quantities, we can +spell out a bootstrapping program. Likewise, when writing the +bootstrapping program, we must be careful to only use numbers that are +also valid items and quantities. This is hard because there aren't +many different items to work with, and many machine instructions +actually take 2 or even 3 numbers in a row, which severely restricts +the types of items you can use. I ended up needing about 92 numbers to +implement a bootstrap program. Half of those numbers were elaborate +ways of doing nothing and were just there so that the entire program +was also a valid item list. + +The final part of the hack is getting pokemon yellow to execute the +new program after it has been assembled with items. Fortunately, +pokemon keeps a number called a function pointer within easy reach of +the corrupted item list. This function pointer is the starting point +(address) of a program which the game runs every so often to check for +poison and do general maintenance. By shifting an item over this +function pointer, I can rewrite that address to point to the +bootstrapping program, and make the game execute it. Without this +function pointer, it would not be possible to take over the game. + +!! The Run + +! Pallet + +I start off and name my rival Lp/k. These characters will eventually be +treated as items and shifted over the function pointer, causing it to +execute the bootstrapping program that will soon be constructed. I +start the run the same as p4wn3r's and restart the game while saving, +so that the pokemon list is corrupted. By switching the 8th and 10th +pokemon, I corrupt the item list and can now scroll down past the 20th +item. I shift items around to increase the text speed to maximum and +rewrite the warp point of my house to Celadon Dept. Store. (p4wn3r +used this to go directly to the hall of fame and win the game in his +run.) I deposit many 0x00 glitch items into the PC from my corrupted +inventory for later use. Then, I withdraw the potion from the +PC. This repairs my item list by overflowing the item counter from +0xFF back to 0x00, though the potion is obliterated in the process. I +then take 255 glitch items with ID 0x00 from the computer into my +personal items. + +! Celadon Dept. Store + +Leaving my house takes me directly to Celadon Dept. store, where I +sell two 0x00 items for 414925 each, giving myself essentially max +money. I hit every floor of the department store, gathering the +following items: + + +-------------------+----------+ + |##| Item | Quantity | + +--+----------------+----------+ + |1 | TM02 | 98 | + |2 | TM37 | 71 | + |3 | TM05 | 1 | + |4 | TM09 | 1 | + |5 | burn-heal | 12 | + |6 | ice-heal | 55 | + |7 | parlyz-heal | 99 | + |8 | parlyz-heal | 55 | + |9 | TM18 | 1 | + |10| fire-stone | 23 | + |11| water-stone | 29 | + |12| x-accuracy | 58 | + |13| guard-spec | 99 | + |14| guard-spec | 24 | + |15| lemonade | 16 | + |16| TM13 | 1 | + +--+----------------+----------+ + + +After gathering these items, I deposit them in the appropriate order +into the item PC to spell out my bootstrapping program. Writing a full +bootstrap program in one go using only items turned out to be too +hard, so I split the process up into three parts. The program that I +actually construct using items is very limited. It reads only from the +A, B, start, and select buttons, and writes 4 bits each frame starting +at a fixed point in memory. After it writes 200 or so bytes, it jumps +directly to what it just wrote. In my run, I use this program to write +another bootstrapping program that can write any number of bytes to +any location in memory, and then jump to any location in memory. This +new program also can write 8 bits per frame by using all the +buttons. Using this new bootstrap program, I write a final +bootstrapping program that does everything the previous bootstrapping +program does except it also displays the bytes it is writing to memory +on the screen. + +! Finale + +After completing this bootstrapping program, I go to the Celadon +mansion, because I find the metaness of that building to be +sufficiently high to serve as an exit point for the pokemon +universe. I corrupt my item list again by switching corrupted pokemon, +scroll down to my rival's name and discard until it is equal to the +address of my bootstrapping program, and then swap it with the +function pointer. Once the menu is closed, the bootstrapping program +takes over, and I write the payload.... + +!! Other comments + +The entire video was played by the computer using bots. I used +functional programming to write search programs over different +possible game states to find the most efficient way of performing +general actions. Some interesting things I developed but didn't use +were pretty printing functions to display the game's internal data +structures, and an "improbability drive" that forces improbable events +to happen automatically using search. + +Here are a few example scripts: + + + (defn-memo viridian-store->oaks-lab + ([] (viridian-store->oaks-lab + (get-oaks-parcel) ) ) + ([ script \] + (->> script + (walk [↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ + ← ← ← ← ← ← ← ← ← + ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ + ← ← + ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ + ↓ ↓ ↓ ↓ ↓ ↓ ↓ + → → → → → → → → + ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ + ← ← ← ← ← + ↓ ↓ ↓ ↓ + ]) + (walk-thru-grass + [↓ ↓ ↓ ↓ ↓ ↓ ↓]) + (walk [↓ ↓ ← ↓ ↓ ↓ ← + ↓ ↓ ↓ ↓ ↓ ↓ + → → → ↑]) + + (do-nothing 1) ) ) ) + + +This script walks from the Viridian City pokemon store to Oak's +Lab in the most efficient way possible. The walk-thru-grass function +guarantees that no wild battles will happen by manipulating the game's +random number generator. + + + (defn-memo hacking-10 + ([] (hacking-10 (hacking-9) ) ) + ([ script \] + (->> script + begin-deposit + (deposit-held-item 17 230) + (deposit-held-item-named :parlyz-heal 55) + (deposit-held-item 14 178) + (deposit-held-item-named :water-stone 29) + (deposit-held-item 14 32) + (deposit-held-item-named :TM18 1) + (deposit-held-item 13 1) + (deposit-held-item 13 191) + (deposit-held-item-named :TM02 98) + (deposit-held-item-named :TM09 1) + close-menu) ) ) + + +This script calculates the fastest sequence of key presses to deposit +the requested items into a PC, assuming that the character starts out +in front of a computer. + +!! Other Comments + +The final payload program is multiple programs. I created a reduced +form of MIDI and implemented it in gameboy machine language. Then I +translated a midi file from http://www.everyponysings.com/ into this +reduced MIDI language. The payload program contains both the music +data and the MIDI interpreter to play that data. The picture works in +a similar way. There is code to translate a png file into a form that +can be displayed on a gameboy, and other code to actually display that +image. Both the image and the display code are also written by the +final bootstrapping program. Even though my final payload is rather +simple, you can write any program at all as the payload. The source +for the sound and image displaying code is at +http://hg.bortreb.com/vba-clojure. + +This entire project is open source and I encourage anyone who wants to +take the code and play around! + + +!! Suggested Screenshots + +* http://aurellem.org/pokemon-hack/code.png +* http://aurellem.org/pokemon-hack/code2.png +* http://aurellem.org/pokemon-hack/matrix.png +* http://aurellem.org/pokemon-hack/matrix2.png +* http://aurellem.org/pokemon-hack/pinkie-pie.png + +Or whatever you all think would be best. + +I encoded the video with/without button visualization here: + +* http://aurellem.org/pokemon-hack/rlm-yellow-hack.avi +* http://aurellem.org/pokemon-hack/rlm-yellow-hack-no-buttons.avi diff -r e1dcad3ce967 -r b531d490859c org/total-control.org --- a/org/total-control.org Thu Nov 22 11:36:07 2012 -0600 +++ b/org/total-control.org Thu Nov 22 13:12:21 2012 -0600 @@ -168,8 +168,8 @@ bootstrap program in one go using only items turned out to be too hard, so I split the process up into three parts. The program that I actually construct using items is very limited. It reads only from the -A, B, start, and select buttons, and writes 4 bits each frame to a -fixed point in memory. After it writes 200 or so bytes, it jumps +A, B, start, and select buttons, and writes 4 bits each frame starting +at a fixed point in memory. After it writes 200 or so bytes, it jumps directly to what it just wrote. In my run, I use this program to write another bootstrapping program that can write any number of bytes to any location in memory, and then jump to any location in memory. This @@ -462,17 +462,17 @@ in with impunity. At the end, I toss the 0xFF away to reveal the completed bootstrap program. -The final payload program is actually multiple programs. I created a -reduced form of MIDI and implemented it in gameboy machine -language. Then I translated a midi file from -http://www.everyponysings.com/ into this reduced MIDI language. The -payload program contains both the music data and the MIDI interpreter -to play that data. The picture works in a similar way. There is code -to translate a png file into a form that can be displayed on a -gameboy, and other code to actually display that image. Both the image -and the display code are also written by the final bootstrapping -program. Even though my final payload is rather simple, you can write -any program at all as the payload. The source for the sound and image -displaying code is at http://hg.bortreb.com/vba-clojure. +The final payload program is multiple programs. I created a reduced +form of MIDI and implemented it in gameboy machine language. Then I +translated a midi file from http://www.everyponysings.com/ into this +reduced MIDI language. The payload program contains both the music +data and the MIDI interpreter to play that data. The picture works in +a similar way. There is code to translate a png file into a form that +can be displayed on a gameboy, and other code to actually display that +image. Both the image and the display code are also written by the +final bootstrapping program. Even though my final payload is rather +simple, you can write any program at all as the payload. The source +for the sound and image displaying code is at +http://hg.bortreb.com/vba-clojure.