Mercurial > vba-clojure

annotate org/tas-submission.txt @ 614:b531d490859c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
submitting to TAS...
author Robert McIntyre <rlm@mit.edu>
date Thu, 22 Nov 2012 13:12:21 -0600
parents
children
rev   line source
rlm@614 1 Pokemon Yellow Total Control Hack. Reprogramming the game from the inside!
rlm@614 2
rlm@614 3 !! Game objectives
rlm@614 4
rlm@614 5 * Emulator used: vba-rerecording 23.5
rlm@614 6 * Reprogram the Game from the inside
rlm@614 7
rlm@614 8 !! Comments
rlm@614 9
rlm@614 10 I've included a detailed writeup here:
rlm@614 11 http://aurellem.org/vba-clojure/html/total-control.html
rlm@614 12
rlm@614 13 There is a video at:
rlm@614 14 http://www.youtube.com/watch?v=p5T81yHkHtI with keypress visualizations
rlm@614 15
rlm@614 16 The following are the highlights:
rlm@614 17
rlm@614 18 ! Introduction
rlm@614 19
rlm@614 20 Think of pokemon yellow as creating a little universe with certain
rlm@614 21 rules. Inside that universe, you can buy items, defeat rival trainers,
rlm@614 22 and raise your pokemon. But within that universe, you are bound by the
rlm@614 23 rules of pokemon. You can't build new buildings, or change the music,
rlm@614 24 or change your clothes.. There are some games (like chess), where it
rlm@614 25 is not possible to alter the rules of the game from within the
rlm@614 26 game. No matter what moves you make in chess, you can never change the
rlm@614 27 rules of the game so that it becomes checkers or basketball. The point
rlm@614 28 of this run is to show that you CAN change the rules in pokemon
rlm@614 29 yellow. There is a certain sequence of valid actions (like walking
rlm@614 30 from one place to another or buying items) that will allow you to
rlm@614 31 transform pokemon yellow into Pacman, or Tetris, or Pong, or a MIDI
rlm@614 32 player, or anything else you can imagine.
rlm@614 33
rlm@614 34
rlm@614 35 ! Background
rlm@614 36
rlm@614 37 The speedrun (http://tasvideos.org/2913S.html) by Felipe Lopes de
rlm@614 38 Freitas (p4wn3r), beats pokemon yellow in only 1 minute and 36
rlm@614 39 seconds. It does it by corrupting the in-game item list so that he can
rlm@614 40 advance the list past its normal limit of 20 items. The memory
rlm@614 41 immediately after the item list includes the warp points for the
rlm@614 42 current map, and by treating that data as items and switching and
rlm@614 43 dropping them, he can make the door from his house take him directly
rlm@614 44 to the end of the game.
rlm@614 45
rlm@614 46 When I first saw that speedrun, I was amazed at how fast pokemon
rlm@614 47 yellow could be beaten, and that it was possible to manipulate the
rlm@614 48 game from the inside, using only the item list. I wondered how far I
rlm@614 49 could extend the techniques found in p4wn3r's run.
rlm@614 50
rlm@614 51 The gameboy is an 8 bit computer. That means that ultimately, anything
rlm@614 52 that happens in pokemon is a result of the gameboy's CPU reading a
rlm@614 53 stream of 8 bit numbers and doing whatever those numbers mean. For
rlm@614 54 example, in the gameboy, the numbers:
rlm@614 55
rlm@614 56 62 16 37 224 47 240 37 230 15 55
rlm@614 57
rlm@614 58 mean to check which buttons are currently pressed and copy that result
rlm@614 59 into the "A" register. With enough numbers, you can spell out an
rlm@614 60 interactive program that reads input from the buttons and allows you
rlm@614 61 to write any program you want to the gameboy. Once you have assembled
rlm@614 62 such a program and forced the game to run it, you have won, since you
rlm@614 63 can use that program to write any other program (like Tetris or
rlm@614 64 Pacman) over pokemon yellow's code. I call a program that allows you
rlm@614 65 to write any other program a "bootstrapping program". So, the goal is
rlm@614 66 to somehow get a bootstrapping program into pokemon yellow and then
rlm@614 67 force yellow to run that program instead of its own.
rlm@614 68
rlm@614 69 How can we spell out such a program? Everything in the game is
rlm@614 70 ultimately numbers, including all items, pokemon, levels, etc. In
rlm@614 71 particular, the item list looks like:
rlm@614 72
rlm@614 73
rlm@614 74 item-one-id (0-255)
rlm@614 75 item-one-quantity (0-255)
rlm@614 76 item-two-id (0-255)
rlm@614 77 item-two-quantity (0-255)
rlm@614 78 .
rlm@614 79 .
rlm@614 80 .
rlm@614 81
rlm@614 82
rlm@614 83 Let's consider the button measuring program [37 62 16 37 224 37 240
rlm@614 84 37 230 15 55] from before. Interpreted as items and item quantities, it is
rlm@614 85
rlm@614 86 lemonade x16
rlm@614 87 guard spec. x224
rlm@614 88 leaf stone x240
rlm@614 89 guard spec. x230
rlm@614 90 parlyz heal x55
rlm@614 91
rlm@614 92 So, if we can get the right items in the right quantities, we can
rlm@614 93 spell out a bootstrapping program. Likewise, when writing the
rlm@614 94 bootstrapping program, we must be careful to only use numbers that are
rlm@614 95 also valid items and quantities. This is hard because there aren't
rlm@614 96 many different items to work with, and many machine instructions
rlm@614 97 actually take 2 or even 3 numbers in a row, which severely restricts
rlm@614 98 the types of items you can use. I ended up needing about 92 numbers to
rlm@614 99 implement a bootstrap program. Half of those numbers were elaborate
rlm@614 100 ways of doing nothing and were just there so that the entire program
rlm@614 101 was also a valid item list.
rlm@614 102
rlm@614 103 The final part of the hack is getting pokemon yellow to execute the
rlm@614 104 new program after it has been assembled with items. Fortunately,
rlm@614 105 pokemon keeps a number called a function pointer within easy reach of
rlm@614 106 the corrupted item list. This function pointer is the starting point
rlm@614 107 (address) of a program which the game runs every so often to check for
rlm@614 108 poison and do general maintenance. By shifting an item over this
rlm@614 109 function pointer, I can rewrite that address to point to the
rlm@614 110 bootstrapping program, and make the game execute it. Without this
rlm@614 111 function pointer, it would not be possible to take over the game.
rlm@614 112
rlm@614 113 !! The Run
rlm@614 114
rlm@614 115 ! Pallet
rlm@614 116
rlm@614 117 I start off and name my rival Lp/k. These characters will eventually be
rlm@614 118 treated as items and shifted over the function pointer, causing it to
rlm@614 119 execute the bootstrapping program that will soon be constructed. I
rlm@614 120 start the run the same as p4wn3r's and restart the game while saving,
rlm@614 121 so that the pokemon list is corrupted. By switching the 8th and 10th
rlm@614 122 pokemon, I corrupt the item list and can now scroll down past the 20th
rlm@614 123 item. I shift items around to increase the text speed to maximum and
rlm@614 124 rewrite the warp point of my house to Celadon Dept. Store. (p4wn3r
rlm@614 125 used this to go directly to the hall of fame and win the game in his
rlm@614 126 run.) I deposit many 0x00 glitch items into the PC from my corrupted
rlm@614 127 inventory for later use. Then, I withdraw the potion from the
rlm@614 128 PC. This repairs my item list by overflowing the item counter from
rlm@614 129 0xFF back to 0x00, though the potion is obliterated in the process. I
rlm@614 130 then take 255 glitch items with ID 0x00 from the computer into my
rlm@614 131 personal items.
rlm@614 132
rlm@614 133 ! Celadon Dept. Store
rlm@614 134
rlm@614 135 Leaving my house takes me directly to Celadon Dept. store, where I
rlm@614 136 sell two 0x00 items for 414925 each, giving myself essentially max
rlm@614 137 money. I hit every floor of the department store, gathering the
rlm@614 138 following items:
rlm@614 139
rlm@614 140 +-------------------+----------+
rlm@614 141 |##| Item | Quantity |
rlm@614 142 +--+----------------+----------+
rlm@614 143 |1 | TM02 | 98 |
rlm@614 144 |2 | TM37 | 71 |
rlm@614 145 |3 | TM05 | 1 |
rlm@614 146 |4 | TM09 | 1 |
rlm@614 147 |5 | burn-heal | 12 |
rlm@614 148 |6 | ice-heal | 55 |
rlm@614 149 |7 | parlyz-heal | 99 |
rlm@614 150 |8 | parlyz-heal | 55 |
rlm@614 151 |9 | TM18 | 1 |
rlm@614 152 |10| fire-stone | 23 |
rlm@614 153 |11| water-stone | 29 |
rlm@614 154 |12| x-accuracy | 58 |
rlm@614 155 |13| guard-spec | 99 |
rlm@614 156 |14| guard-spec | 24 |
rlm@614 157 |15| lemonade | 16 |
rlm@614 158 |16| TM13 | 1 |
rlm@614 159 +--+----------------+----------+
rlm@614 160
rlm@614 161
rlm@614 162 After gathering these items, I deposit them in the appropriate order
rlm@614 163 into the item PC to spell out my bootstrapping program. Writing a full
rlm@614 164 bootstrap program in one go using only items turned out to be too
rlm@614 165 hard, so I split the process up into three parts. The program that I
rlm@614 166 actually construct using items is very limited. It reads only from the
rlm@614 167 A, B, start, and select buttons, and writes 4 bits each frame starting
rlm@614 168 at a fixed point in memory. After it writes 200 or so bytes, it jumps
rlm@614 169 directly to what it just wrote. In my run, I use this program to write
rlm@614 170 another bootstrapping program that can write any number of bytes to
rlm@614 171 any location in memory, and then jump to any location in memory. This
rlm@614 172 new program also can write 8 bits per frame by using all the
rlm@614 173 buttons. Using this new bootstrap program, I write a final
rlm@614 174 bootstrapping program that does everything the previous bootstrapping
rlm@614 175 program does except it also displays the bytes it is writing to memory
rlm@614 176 on the screen.
rlm@614 177
rlm@614 178 ! Finale
rlm@614 179
rlm@614 180 After completing this bootstrapping program, I go to the Celadon
rlm@614 181 mansion, because I find the metaness of that building to be
rlm@614 182 sufficiently high to serve as an exit point for the pokemon
rlm@614 183 universe. I corrupt my item list again by switching corrupted pokemon,
rlm@614 184 scroll down to my rival's name and discard until it is equal to the
rlm@614 185 address of my bootstrapping program, and then swap it with the
rlm@614 186 function pointer. Once the menu is closed, the bootstrapping program
rlm@614 187 takes over, and I write the payload....
rlm@614 188
rlm@614 189 !! Other comments
rlm@614 190
rlm@614 191 The entire video was played by the computer using bots. I used
rlm@614 192 functional programming to write search programs over different
rlm@614 193 possible game states to find the most efficient way of performing
rlm@614 194 general actions. Some interesting things I developed but didn't use
rlm@614 195 were pretty printing functions to display the game's internal data
rlm@614 196 structures, and an "improbability drive" that forces improbable events
rlm@614 197 to happen automatically using search.
rlm@614 198
rlm@614 199 Here are a few example scripts:
rlm@614 200
rlm@614 201
rlm@614 202 (defn-memo viridian-store->oaks-lab
rlm@614 203 ([] (viridian-store->oaks-lab
rlm@614 204 (get-oaks-parcel) ) )
rlm@614 205 ([ script \]
rlm@614 206 (->> script
rlm@614 207 (walk [↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
rlm@614 208 ← ← ← ← ← ← ← ← ←
rlm@614 209 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
rlm@614 210 ← ←
rlm@614 211 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
rlm@614 212 ↓ ↓ ↓ ↓ ↓ ↓ ↓
rlm@614 213 → → → → → → → →
rlm@614 214 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
rlm@614 215 ← ← ← ← ←
rlm@614 216 ↓ ↓ ↓ ↓
rlm@614 217 ])
rlm@614 218 (walk-thru-grass
rlm@614 219 [↓ ↓ ↓ ↓ ↓ ↓ ↓])
rlm@614 220 (walk [↓ ↓ ← ↓ ↓ ↓ ←
rlm@614 221 ↓ ↓ ↓ ↓ ↓ ↓
rlm@614 222 → → → ↑])
rlm@614 223
rlm@614 224 (do-nothing 1) ) ) )
rlm@614 225
rlm@614 226
rlm@614 227 This script walks from the Viridian City pokemon store to Oak's
rlm@614 228 Lab in the most efficient way possible. The walk-thru-grass function
rlm@614 229 guarantees that no wild battles will happen by manipulating the game's
rlm@614 230 random number generator.
rlm@614 231
rlm@614 232
rlm@614 233 (defn-memo hacking-10
rlm@614 234 ([] (hacking-10 (hacking-9) ) )
rlm@614 235 ([ script \]
rlm@614 236 (->> script
rlm@614 237 begin-deposit
rlm@614 238 (deposit-held-item 17 230)
rlm@614 239 (deposit-held-item-named :parlyz-heal 55)
rlm@614 240 (deposit-held-item 14 178)
rlm@614 241 (deposit-held-item-named :water-stone 29)
rlm@614 242 (deposit-held-item 14 32)
rlm@614 243 (deposit-held-item-named :TM18 1)
rlm@614 244 (deposit-held-item 13 1)
rlm@614 245 (deposit-held-item 13 191)
rlm@614 246 (deposit-held-item-named :TM02 98)
rlm@614 247 (deposit-held-item-named :TM09 1)
rlm@614 248 close-menu) ) )
rlm@614 249
rlm@614 250
rlm@614 251 This script calculates the fastest sequence of key presses to deposit
rlm@614 252 the requested items into a PC, assuming that the character starts out
rlm@614 253 in front of a computer.
rlm@614 254
rlm@614 255 !! Other Comments
rlm@614 256
rlm@614 257 The final payload program is multiple programs. I created a reduced
rlm@614 258 form of MIDI and implemented it in gameboy machine language. Then I
rlm@614 259 translated a midi file from http://www.everyponysings.com/ into this
rlm@614 260 reduced MIDI language. The payload program contains both the music
rlm@614 261 data and the MIDI interpreter to play that data. The picture works in
rlm@614 262 a similar way. There is code to translate a png file into a form that
rlm@614 263 can be displayed on a gameboy, and other code to actually display that
rlm@614 264 image. Both the image and the display code are also written by the
rlm@614 265 final bootstrapping program. Even though my final payload is rather
rlm@614 266 simple, you can write any program at all as the payload. The source
rlm@614 267 for the sound and image displaying code is at
rlm@614 268 http://hg.bortreb.com/vba-clojure.
rlm@614 269
rlm@614 270 This entire project is open source and I encourage anyone who wants to
rlm@614 271 take the code and play around!
rlm@614 272
rlm@614 273
rlm@614 274 !! Suggested Screenshots
rlm@614 275
rlm@614 276 * http://aurellem.org/pokemon-hack/code.png
rlm@614 277 * http://aurellem.org/pokemon-hack/code2.png
rlm@614 278 * http://aurellem.org/pokemon-hack/matrix.png
rlm@614 279 * http://aurellem.org/pokemon-hack/matrix2.png
rlm@614 280 * http://aurellem.org/pokemon-hack/pinkie-pie.png
rlm@614 281
rlm@614 282 Or whatever you all think would be best.
rlm@614 283
rlm@614 284 I encoded the video with/without button visualization here:
rlm@614 285
rlm@614 286 * http://aurellem.org/pokemon-hack/rlm-yellow-hack.avi
rlm@614 287 * http://aurellem.org/pokemon-hack/rlm-yellow-hack-no-buttons.avi