Mercurial > vba-clojure

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