view org/total-control.org @ 614:b531d490859c

submitting to TAS...
author Robert McIntyre <rlm@mit.edu>
date Thu, 22 Nov 2012 13:12:21 -0600
parents e1dcad3ce967
children a79e5a852347 90575d3a64d1
line wrap: on
line source
1 #+title: Pokemon Yellow Total Control Hack
2 #+author: Robert McIntyre
3 #+email: rlm@mit.edu
4 #+description: Taking over Pokemon Yellow from the inside.
5 #+keywords: pokemon, pokemon yellow, rom, gameboy, assembly, hex, pointers, clojure
6 #+SETUPFILE: ../../aurellem/org/setup.org
7 #+INCLUDE: ../../aurellem/org/level-0.org
8 #+BABEL: :exports both :noweb yes :cache no :mkdirp yes
9 #+OPTIONS: num:2
12 Full Source : http://hg.bortreb.com/vba-clojure
14 Youtube Video w/ Visual Keypresses: http://www.youtube.com/watch?v=p5T81yHkHtI
16 Special Thanks to:
18 - http://tasvideos.org/2913S.html for the save corruption hack which
19 is used at the start of this run.
20 - http://www.everyponysings.com/ for providing the midi file I used
21 to create the song at the end.
22 - http://www.zophar.net/ for the terminal font.
25 * Introduction
27 Think of pokemon yellow as creating a little universe with certain
28 rules. Inside that universe, you can buy items, defeat rival trainers,
29 and raise your pokemon. But within that universe, you are bound by the
30 rules of pokemon. You can't build new buildings, or change the music,
31 or change your clothes.. There are some games (like chess), where it
32 is not possible to alter the rules of the game from within the
33 game. No matter what moves you make in chess, you can never change the
34 rules of the game so that it becomes checkers or basketball. The point
35 of this run is to show that you CAN change the rules in pokemon
36 yellow. There is a certain sequence of valid actions (like walking
37 from one place to another or buying items) that will allow you to
38 transform pokemon yellow into Pacman, or Tetris, or Pong, or a MIDI
39 player, or anything else you can imagine.
41 * Background
43 [[http://tasvideos.org/2913S.html][This speedrun]] by Felipe Lopes de Freitas (p4wn3r), beats pokemon
44 yellow in only 1 minute and 36 seconds. It does it by corrupting the
45 in-game item list so that he can advance the list past its normal
46 limit of 20 items. The memory immediately after the item list includes
47 the warp points for the current map, and by treating that data as
48 items and switching and dropping them, he can make the door from his
49 house take him directly to the end of the game.
51 When I first saw that speedrun, I was amazed at how fast pokemon
52 yellow could be beaten, and that it was possible to manipulate the
53 game from the inside, using only the item list. I wondered how far I
54 could extend the techniques found in p4wn3r's run.
56 The gameboy is an 8 bit computer. That means that ultimately, anything
57 that happens in pokemon is a result of the gameboy's CPU reading a
58 stream of 8 bit numbers and doing whatever those numbers mean. For
59 example, in the gameboy, the numbers:
61 [62 16 37 224 47 240 37 230 15 55]
63 mean to check which buttons are currently pressed and copy that result
64 into the "A" register. With enough numbers, you can spell out an
65 interactive program that reads input from the buttons and allows you
66 to write any program you want to the gameboy. Once you have assembled
67 such a program and forced the game to run it, you have won, since you
68 can use that program to write any other program (like Tetris or
69 Pacman) over pokemon yellow's code. I call a program that allows you
70 to write any other program a "bootstrapping program". So, the goal is
71 to somehow get a bootstrapping program into pokemon yellow and then
72 force yellow to run that program instead of its own.
74 How can we spell out such a program? Everything in the game is
75 ultimately numbers, including all items, pokemon, levels, etc. In
76 particular, the item list looks like:
78 #+begin_example
79 item-one-id (0-255)
80 item-one-quantity (0-255)
81 item-two-id (0-255)
82 item-two-quantity (0-255)
83 .
84 .
85 .
86 #+end_example
88 Let's consider the button measuring program [37 62 16 37 224 37 240
89 37 230 15 55] from before. Interpreted as items and item quantities, it is
91 #+begin_example
92 lemonade x16
93 guard spec. x224
94 leaf stone x240
95 guard spec. x230
96 parlyz heal x55
97 #+end_example
99 So, if we can get the right items in the right quantities, we can
100 spell out a bootstrapping program. Likewise, when writing the
101 bootstrapping program, we must be careful to only use numbers that are
102 also valid items and quantities. This is hard because there aren't
103 many different items to work with, and many machine instructions
104 actually take 2 or even 3 numbers in a row, which severely restricts
105 the types of items you can use. I ended up needing about 92 numbers to
106 implement a bootstrap program. Half of those numbers were elaborate
107 ways of doing nothing and were just there so that the entire program
108 was also a valid item list.
110 The final part of the hack is getting pokemon yellow to execute the
111 new program after it has been assembled with items. Fortunately,
112 pokemon keeps a number called a function pointer within easy reach of
113 the corrupted item list. This function pointer is the starting point
114 (address) of a program which the game runs every so often to check for
115 poison and do general maintenance. By shifting an item over this
116 function pointer, I can rewrite that address to point to the
117 bootstrapping program, and make the game execute it. Without this
118 function pointer, it would not be possible to take over the game.
120 * The Run
122 I start off and name my rival Lp/k. These characters will eventually be
123 treated as items and shifted over the function pointer, causing it to
124 execute the bootstrapping program that will soon be constructed. I
125 start the run the same as p4wn3r's and restart the game while saving,
126 so that the pokemon list is corrupted. By switching the 8th and 10th
127 pokemon, I corrupt the item list and can now scroll down past the 20th
128 item. I shift items around to increase the text speed to maximum and
129 rewrite the warp point of my house to Celadon Dept. Store. (p4wn3r
130 used this to go directly to the hall of fame and win the game in his
131 run.) I deposit many 0x00 glitch items into the PC from my corrupted
132 inventory for later use. Then, I withdraw the potion from the
133 PC. This repairs my item list by overflowing the item counter from
134 0xFF back to 0x00, though the potion is obliterated in the process. I
135 then take 255 glitch items with ID 0x00 from the computer into my
136 personal items.
138 Leaving my house takes me directly to Celadon Dept. store, where I
139 sell two 0x00 items for 414925 each, giving myself essentially max
140 money. I hit every floor of the department store, gathering the
141 following items:
143 #+begin_example
144 +-------------------+----------+
145 |##| Item | Quantity |
146 +--+----------------+----------+
147 |1 | TM02 | 98 |
148 |2 | TM37 | 71 |
149 |3 | TM05 | 1 |
150 |4 | TM09 | 1 |
151 |5 | burn-heal | 12 |
152 |6 | ice-heal | 55 |
153 |7 | parlyz-heal | 99 |
154 |8 | parlyz-heal | 55 |
155 |9 | TM18 | 1 |
156 |10| fire-stone | 23 |
157 |11| water-stone | 29 |
158 |12| x-accuracy | 58 |
159 |13| guard-spec | 99 |
160 |14| guard-spec | 24 |
161 |15| lemonade | 16 |
162 |16| TM13 | 1 |
163 +--+----------------+----------+
164 #+end_example
166 After gathering these items, I deposit them in the appropriate order
167 into the item PC to spell out my bootstrapping program. Writing a full
168 bootstrap program in one go using only items turned out to be too
169 hard, so I split the process up into three parts. The program that I
170 actually construct using items is very limited. It reads only from the
171 A, B, start, and select buttons, and writes 4 bits each frame starting
172 at a fixed point in memory. After it writes 200 or so bytes, it jumps
173 directly to what it just wrote. In my run, I use this program to write
174 another bootstrapping program that can write any number of bytes to
175 any location in memory, and then jump to any location in memory. This
176 new program also can write 8 bits per frame by using all the
177 buttons. Using this new bootstrap program, I write a final
178 bootstrapping program that does everything the previous bootstrapping
179 program does except it also displays the bytes it is writing to memory
180 on the screen.
182 After completing this bootstrapping program, I go to the Celadon
183 mansion, because I find the metaness of that building to be
184 sufficiently high to serve as an exit point for the pokemon
185 universe. I corrupt my item list again by switching corrupted pokemon,
186 scroll down to my rival's name and discard until it is equal to the
187 address of my bootstrapping program, and then swap it with the
188 function pointer. Once the menu is closed, the bootstrapping program
189 takes over, and I write the payload....
191 * Infrastructure
193 The entire video was completely produced by bots --- I didn't manually
194 play the game at all to produce this speedrun. Here is a brief account
195 of the infrastructure I build to make the video. The entire source of
196 the project is available at http://hg.bortreb.com/vba-clojure
198 The first step was to build a programmatic interface to pokemon
199 yellow. So, I downloaded vba-rerecording from
200 http://code.google.com/p/vba-rerecording/. After repairing their
201 broken auto-tools scripts so that it would compile on GNU/Linux, I
202 added a low level C interface that I could call from Java via
203 JNI. This C interface gives me basic control over the emulator: I can
204 step the emulator either one clock cycle or one frame, and I can get
205 the contents of any memory location or register. The interface also
206 allows me to freeze the state of the emulator, save it to a Java
207 object, and reload that state again at any time.
209 I built a layer of [[http://clojure.org/][clojure]] code on top of the JNI bindings to get an
210 entirely functional interface to vba-rerecording. This interface
211 treats state of the emulator as an immutable object, and allows me to
212 do everything I could do with the lower level C interface in a
213 functional manner. Using this functional code, I wrote search programs
214 that take a particular game-state and try out different combinations
215 of button presses to get any desired effect. By combining different
216 styles of search with different initial conditions, I created high
217 level functions that could each accomplish a certain general task,
218 like walking and buying items. For example, here is some actual code:
220 #+begin_src clojure
221 (defn-memo viridian-store->oaks-lab
222 ([] (viridian-store->oaks-lab
223 (get-oaks-parcel)))
224 ([script]
225 (->> script
226 (walk [↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
227 ← ← ← ← ← ← ← ← ←
228 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
229 ← ←
230 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
231 ↓ ↓ ↓ ↓ ↓ ↓ ↓
232 → → → → → → → →
233 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
234 ← ← ← ← ←
235 ↓ ↓ ↓ ↓
236 ])
237 (walk-thru-grass
238 [↓ ↓ ↓ ↓ ↓ ↓ ↓])
239 (walk [↓ ↓ ← ↓ ↓ ↓ ←
240 ↓ ↓ ↓ ↓ ↓ ↓
241 → → → ↑])
243 (do-nothing 1))))
244 #+end_src
246 This script walks from the Viridian City pokemon store to Oak's
247 Lab in the most efficient way possible. The walk-thru-grass function
248 guarantees that no wild battles will happen by manipulating the game's
249 random number generator.
251 #+begin_src clojure
252 (defn-memo hacking-10
253 ([] (hacking-10 (hacking-9)))
254 ([script]
255 (->> script
256 begin-deposit
257 (deposit-held-item 17 230)
258 (deposit-held-item-named :parlyz-heal 55)
259 (deposit-held-item 14 178)
260 (deposit-held-item-named :water-stone 29)
261 (deposit-held-item 14 32)
262 (deposit-held-item-named :TM18 1)
263 (deposit-held-item 13 1)
264 (deposit-held-item 13 191)
265 (deposit-held-item-named :TM02 98)
266 (deposit-held-item-named :TM09 1)
267 close-menu)))
268 #+end_src
270 This script calculates the fastest sequence of key presses to deposit
271 the requested items into a PC, assuming that the character starts out
272 in front of a computer.
274 I also wrote functions that could grovel through the game's memory and
275 present the internal data structures in usable ways. For example, the
276 function =print-inventory= returns the current inventory in a human
277 readable format.
279 #+begin_src clojure :results output :exports both
280 (com.aurellem.gb.items/print-inventory)
281 #+end_src
283 #+results:
284 #+begin_example
285 +-------------------+----------+
286 |##| Item | Quantity |
287 +--+----------------+----------+
288 |0 | poke-ball | 14 |
289 |1 | TM28 | 1 |
290 |2 | TM11 | 1 |
291 |3 | TM45 | 1 |
292 |4 | nugget | 1 |
293 |5 | s.s.ticket | 1 |
294 |6 | helix-fossil | 1 |
295 |7 | moon-stone | 1 |
296 +--+----------------+----------+
298 #+end_example
301 Armed with these functions, I constructed a bootstrapping program that
302 could be expressed as items. This is particularly hard, since many
303 useful opcodes do not correspond any item, and the item quantities
304 must all be less than 99.
306 Here is the first bootstrapping program in all its glory.
308 #+begin_src clojure
309 (defn pc-item-writer-program
310 []
311 (let [;;limit 75
312 limit 201 ;; (item-hack 201 is the smallest I could make this.)
313 [target-high target-low] (disect-bytes-2 pokemon-list-start)]
314 (flatten
315 [[0x00 ;; (item-hack) no-op (can't buy repel (1E) at celadon)
316 0x1E ;; load limit into E
317 limit
318 0x3F ;; (item-hack) set carry flag no-op
320 ;; load 2 into C.
321 0x0E ;; C == 1 means input-first nybble
322 0x04 ;; C == 0 means input-second nybble
324 0x21 ;; load target into HL
325 target-low
326 target-high
327 0x37 ;; (item-hack) set carry flag no-op
329 0x00 ;; (item-hack) no-op
330 0x37 ;; (item-hack) set carry flag no-op
332 0x00 ;; (item-hack) no-op
333 0xF3 ;; disable interrupts
334 ;; Input Section
336 0x3E ;; load 0x20 into A, to measure buttons
337 0x10
339 0x00 ;; (item-hack) no-op
340 0xE0 ;; load A into [FF00]
341 0x00
343 0xF0 ;; load 0xFF00 into A to get
344 0x00 ;; button presses
346 0xE6
347 0x0F ;; select bottom four bits of A
348 0x37 ;; (item-hack) set carry flag no-op
350 0x00 ;; (item-hack) no-op
351 0xB8 ;; see if input is different (CP A B)
353 0x00 ;; (item-hack) (INC SP)
354 0x28 ;; repeat above steps if input is not different
355 ;; (jump relative backwards if B != A)
356 0xED ;; (literal -19) (item-hack) -19 == egg bomb (TM37)
358 0x47 ;; load A into B
360 0x0D ;; dec C
361 0x37 ;; (item-hack) set-carry flag
362 ;; branch based on C:
363 0x20 ;; JR NZ
364 23 ;; skip "input second nybble" and "jump to target" below
366 ;; input second nybble
368 0x0C ;; inc C
369 0x0C ;; inc C
371 0x00 ;; (item-hack) no-op
372 0xE6 ;; select bottom bits
373 0x0F
374 0x37 ;; (item-hack) set-carry flag no-op
376 0x00 ;; (item-hack) no-op
377 0xB2 ;; (OR A D) -> A
379 0x22 ;; (do (A -> (HL)) (INC HL))
381 0x1D ;; (DEC E)
383 0x00 ;; (item-hack)
384 0x20 ;; jump back to input section if not done
385 0xDA ;; literal -36 == TM 18 (counter)
386 0x01 ;; (item-hack) set BC to literal (no-op)
388 ;; jump to target
389 0x00 ;; (item-hack) these two bytes can be anything.
390 0x01
392 0x00 ;; (item-hack) no-op
393 0xBF ;; (CP A A) ensures Z
395 0xCA ;; (item-hack) jump if Z
396 target-low
397 target-high
398 0x01 ;; (item-hack) will never be reached.
400 ;; input first nybble
401 0x00
402 0xCB
403 0x37 ;; swap nybbles on A
405 0x57 ;; A -> D
407 0x37 ;; (item-hack) set carry flag no-op
408 0x18 ;; relative jump backwards
409 0xCD ;; literal -51 == TM05; go back to input section
410 0x01 ;; (item-hack) will never reach this instruction
412 ]
413 (repeat 8 [0x00 0x01]);; these can be anything
415 [;; jump to actual program
416 0x00
417 0x37 ;; (item-hack) set carry flag no-op
419 0x2E ;; 0x3A -> L
420 0x3A
423 0x00 ;; (item-hack) no-op
424 0x26 ;; 0xD5 -> L
425 0xD5
426 0x01 ;; (item-hack) set-carry BC
428 0x00 ;; (item-hack) these can be anything
429 0x01
431 0x00
432 0xE9 ;; jump to (HL)
433 ]])))
435 #+end_src
437 I use the glitch items 0x00 and 0xFF to great effect in my run. 0x00
438 sells for almost half of maximum money --- I use just 3 of them to
439 finance the purchase of all the other items I need. 0x00 is also a
440 NO-OP in the gameboy's machine language, which means that I can stick
441 them anywhere where I need to break up an other wise illegal pair of
442 opcodes. 0xFF is also extremely useful because it is the end-of-list
443 sentinel. Normally, the game will "compact" your items whenever you
444 make a purchase or deposit. For example, if you deposit a pokeball,
445 then deposit another pokeball, the item list looks like:
447 #+begin_example
448 pokeball x2
449 #+end_example
451 instead of:
453 #+begin_example
454 pokeball x1
455 pokeball x1
456 #+end_example
458 However, the compaction stops after the first 0xFF item, so if there
459 is an 0xFF item at the beginning of the list, it will "shield" all the
460 items below it from compaction. It the beginning of the run, I stick
461 an 0xFF item at the top of the PC item list, allowing me to put items
462 in with impunity. At the end, I toss the 0xFF away to reveal the
463 completed bootstrap program.
465 The final payload program is multiple programs. I created a reduced
466 form of MIDI and implemented it in gameboy machine language. Then I
467 translated a midi file from http://www.everyponysings.com/ into this
468 reduced MIDI language. The payload program contains both the music
469 data and the MIDI interpreter to play that data. The picture works in
470 a similar way. There is code to translate a png file into a form that
471 can be displayed on a gameboy, and other code to actually display that
472 image. Both the image and the display code are also written by the
473 final bootstrapping program. Even though my final payload is rather
474 simple, you can write any program at all as the payload. The source
475 for the sound and image displaying code is at
476 http://hg.bortreb.com/vba-clojure.