Post subject: Learning ASM (assembly) for TASing; any advice?
Joined: 6/16/2009
Posts: 30
Well not just for TASing, cause I've been meaning to learn ASM for a while now. But anyway, I've been wanting to use ASM for TAS projects (because I have some free time now; and you may know me as the guy who bailed on the Golden Sun TAS... twice... >_>) because I think it would be really beneficial to look into the code and look at glitches and stuff. All of this comes with the assumptions that ASM is actually the language that's used to look into and decipher the hex in the RAM and of the ROM, look into programming errors and whatnot. So my question are: -Should I learn ASM for TASing? -If so, which architecture? -If not, which language am I looking for? Also, slightly unrelated, but what language are route optimizing and glitch finding programs in? I was thinking anywhere from Lua to C, but I could be wrong... Thanks guys.
Joined: 2/19/2010
Posts: 248
Learn the assembly language of the system you want to TAS on. For example, GBA uses ARM Thumb instructions. ARM Thumb has the advantage that it's a rather nicely designed assembly language -- orthogonal instructions, no implicit arguments, general-purpose registers. Having said that, the most important thing is that you're TASing a game you love, and that will drive your desire to learn the assembly language on that platform. It will also help to get a copy of an emulator with an assembly debugger in it, so you can actually step through the assembly code as it executes. I have done this with GBA before; I don't have time right now to find the version of VBA which allows this, but remind me and I'll do it later.
Skilled player (1636)
Joined: 11/15/2004
Posts: 2202
Location: Killjoy
Looking at the ROM to find an RNG is difficult, looking at the ROM to understand glitches is many levels of difficulty of that. To date, I believe final fighter is the only person who has directly explored a glitch in a ROM, and figured out how to exploit it. I think this path will find you very discouraged, as a warning. Attempt to TAS the game with just ram watch, and at most lua.
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
MESHUGGAH
Other
Skilled player (1888)
Joined: 11/14/2009
Posts: 1349
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
DarkKobold is correct. First thing you should think about is your actual goals. Please read this Post #261693. So here's your choices: If you want to make a 100% perfect TAS, you should know everything about that specific game. You will need to learn the console's language, disassemble the game with an emulator step-by-step, rewrite your results/code to make it easier to read for humans after figuring out the variables, understand the code execution, writing down ALL possible glitches/bugs that leads you faster to the desired end game state and don't forget that possible memory corruption holes are a bit harder to figure out just by watching the code for 1 time. You should also play the game normally and explore everything in the game to know the possibilities of the memory values and gamestates. If you want to make an impressive TAS, you can ignore disassembling. There are many games where common game design/programming code flaws exists, therefore it's easy to abuse it without knowing the exact code behind it. As DarkKobold mentioned, you will have to figure out memory addresses, also LUA helps you to make various actions automatized (generating pseudo-random input to get the desired RNG value), drawing/showing useful values you needed from frame by frame (subpixel values, specific state values, etc) and other. I'm strongly advice you to consider about the time you want to "waste" for a specific TAS. Also I recommend to try disassembling "easy" games where there are no many objects/levels/data, not to mention the console choice.
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
Joined: 6/16/2009
Posts: 30
rhebus wrote:
Learn the assembly language of the system you want to TAS on. For example, GBA uses ARM Thumb instructions.
Thanks, rhebus. I've never programmed in ASM before, so would ARM Thumb be a good start, or should I start with PC architecture and then shift over after I know it?
DarkKobold wrote:
I think this path will find you very discouraged, as a warning. Attempt to TAS the game with just ram watch, and at most lua.
Warning heeded. I just wanted to have the abilities as resources, as supplements to the normal TAS methods; I've noticed that most major publications have game-breaking glitches (such as Yoshi's Island (30 second, iirc) run), that I assume to be found by looking into the game coding; otherwise, how else would they be found out?
MESHUGGAH wrote:
I'm strongly advice you to consider about the time you want to "waste" for a specific TAS. Also I recommend to try disassembling "easy" games where there are no many objects/levels/data, not to mention the console choice.
Advice taken. And thanks for the links, will read now. Again, I want to use ASM and RAM stepping as supplements, maybe not necessarily as the main tools (unless I really love the game) Btw, I'd just like to say that while I am a newbie to TASing, I'm no newbie to coding and programming, (2.5 year programmer), so don't be afraid to recommend me some more advanced stuff. Also, what language are bots usually written in? But thanks for all of your help so far, guys.
Joined: 7/2/2007
Posts: 3960
My impression is that most game-breaking glitches are found through a combination of experimentation and intuition. An experienced programmer or TASer will know about a large variety of potential bugs and the general situations required to trigger them. For example, most TASers know about trying L+R or U+D in various scenarios (on the ground, in the air, climbing a ladder, etc.). Less well-known is corner boosting, but anyone who's ever implemented their own bounding box-based "physics engine" will know that the direction you get pushed out of a bit of scenery is not always the direction you entered from; combine that knowledge with TASing and the application becomes reasonably clear. I shouldn't deprecate the amount of time spent on experimentation, though. Plenty of time is spent with memory watch open, just manually figuring out the fastest way to move. The Aria of Sorrow TASers went through four or five iterations of "Ah! This sequence of button presses is 11% faster on slopes than the old method!" for example. I also can't count the number if times I've seen "I was just playing the game normally, and something bizarre happened, so I went back and figured out how to replicate it" on these forums. On that note, always be recording your gameplay if you intend to TAS a game; I also can't count the number of times I've seen "I was playing the game normally, and something bizarre happened, but I wasn't recording and now I can't replicate it. :(" on these forums. Honestly I suspect that if you really want to improve your TASing through programming knowledge, you'd be better off trying to write your own game in the genre you want to TAS. That seems more likely to give you insight into the potential bug types than learning to read the ASM of a specific game will, at least in terms of results per time invested.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
MESHUGGAH
Other
Skilled player (1888)
Joined: 11/14/2009
Posts: 1349
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
Sorry if my post sounded too "easy". I'm glad that you know programming. Here are more advanced links you should watch: http://www.romhacking.net/ - You can download various disassemblers for various platforms (left side menu Utilities, "Debuggers/Special emulators" for category). Most of them comes with technical documentation. Also you could search for your desired consoles disassembler websites, for example NES: http://nesdev.parodius.com/ (very detailed informations and useful utilites and many other things regarding NES) I don't know famous GBA disassemblers. As mentioned above, I heard of a SDL version of VBA that let's you disassemble games. Maybe romhacking.net has information about it. edit:
Zero100 wrote:
Also, what language are bots usually written in?
Lua is far enough for it. You can easily retrieve memory values and write different algorithms to do various tasks like pressing A if you have 3 lives and there's a mushroom 24 pixels away.
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
Joined: 2/19/2010
Posts: 248
Zero100 wrote:
rhebus wrote:
Learn the assembly language of the system you want to TAS on. For example, GBA uses ARM Thumb instructions.
Thanks, rhebus. I've never programmed in ASM before, so would ARM Thumb be a good start, or should I start with PC architecture and then shift over after I know it?
The first asm you learn should be the first asm you want to use. If you have no reason to use PC asm, don't learn it. Find a game you want to TAS, and learn the asm for that platform.
DarkKobold wrote:
I think this path will find you very discouraged, as a warning. Attempt to TAS the game with just ram watch, and at most lua.
I partly agree with this viewpoint, because reading disassembly is not for the faint of heart. However, if you have a specific goal, and you have either good skills or good support (by asking questions here) or both, then you can get quite far by trying to investigate specific questions. For example, I recently discovered the algorithms for item drops and soul drops from Castlevania: Aria of Sorrow; this was entirely done by disassembling the code, using vba-sdl. It took bloody ages, but it was worth it. Having a specific goal - the soul drop code - helped keep me focussed and keep my mind on the task at hand. Most of my AoS discoveries, however, are by RAM search rather than by disassembly. RAM search is far, far easier, and can tell you much about the game.
Skilled player (1636)
Joined: 11/15/2004
Posts: 2202
Location: Killjoy
rhebus wrote:
I partly agree with this viewpoint, because reading disassembly is not for the faint of heart. However, if you have a specific goal, and you have either good skills or good support (by asking questions here) or both, then you can get quite far by trying to investigate specific questions. For example, I recently discovered the algorithms for item drops and soul drops from Castlevania: Aria of Sorrow; this was entirely done by disassembling the code, using vba-sdl. It took bloody ages, but it was worth it. Having a specific goal - the soul drop code - helped keep me focussed and keep my mind on the task at hand..
Yeah, I did a similar thing with Shining Force... You had better LOVE the game, because you will be spending countless hours on one game, with information that will only really be worthwhile for one TAS. I think the sum total hours I spent on SF is equal to the sum total hours I've spent on every other TAS I've worked on. (tangent).
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
Banned User, Former player
Joined: 3/10/2004
Posts: 7698
Location: Finland
I agree with the sentiment that learning a console's assembly language just to be able to find out how the game works, find exploitable glitches and so on, is the really, really hard way of doing it. Understanding someone else's code, regardless of the programming language, is often very laborious. Imagine that you are trying to understand someone else's code, and that there are no comments whatsoever, and all the variables and functions have been named with numbers (indicating memory addresses) instead of descriptive names. Add to that the fact that the "language" itself is as primitive and nondescriptive as you can possibly get, and that the programs are often extremely large (especially because pure asm is quite verbose). In many cases the asm will not have been written by a human, but generated with a compiler, making understanding it even harder, as the human design element has been removed. (I don't know if NES games were primarily written in asm or a higher-level language, although back in those days, in the mid-80's, writing games directly in asm was pretty common, but the more modern the console, the less likely that they were written in asm directly.) Not that it's impossible, though. People have deciphered the inner workings of RNGs, password codes, and made even patches and hacks by purely studying the asm dumps of games. However, this is far from easy, especially if you are learning asm for the first time. Not that I want to discourage you, but it would indeed be much easier to find glitches and bugs the "traditional" way.
Editor, Active player (296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Warp wrote:
In many cases the asm will not have been written by a human, but generated with a compiler, making understanding it even harder, as the human design element has been removed.
On the other hand, compiler-generated code is often mechanical enough that you can depict the original control structures, or even the original expressions in case of simpler compilers, with relative ease. Human-generated code tends to be full of "clever tricks" that just aren't worth it for compiler-designers to implement.
Joined: 10/20/2006
Posts: 1248
I'd recommend looking into a game's code only for a very specific goal. F.e. if you've found a glitch, but don't know exactly what causes that glitch to occur, you can do a RAM search to find at least one related memory address. Then, you can disassemble the game and try your best at finding all lines of code that modify that address (this isn't as easy as it sounds). If you're lucky, you're going to get some very valuable information from that. If the disassembler is integrated into an emulator, it'll hopefully let you define break points, which means that once the game has reached a certain line of code, the emulation will come to a halt. This way, you'll be quicker at finding out what the area of code around your break point actually does. I have so far only disassembled/debugged [URL=http://www.zophar.net/snes/geiger-s-snes9x-debugger.html]SNES[/URL] and [URL=http://www.zophar.net/gb/no-gmb.html]GB[/URL] games, using these tools.
Editor, Skilled player (1938)
Joined: 6/15/2005
Posts: 3246
I've only worked disassembly of any kind with two games, NES Monopoly and FDS Backgammon. Both times were to understand the RNG and how the game uses it. It wasn't particularly difficult (making 40-minute-long TASes generally takes up a lot more time) but it wasn't easy either. I would only ever consider disassembly for RNG purposes. This is mostly because RNGs are one of the least intuitive things during normal TASing, and are highly procedural in code. Tricks and glitches, on the other hand, are the opposite: highly intuitive during normal TASing, effectively non-procedural in code. Computers don't understand tricks, glitches, or intuition. They just do what they are told to do. Looking at code is much the same way. Even for RNGs, it is sometimes possible to determine behavior just from trial and observation of its memory address, in which case disassembly is not needed. In Pokemon Sapphire, for which I have created a page on RNG mechanics, I only used existing knowledge (fortunately there is a lot), RNG observation, and pattern-finding to obtain the results. They may not be perfect information (only full RNG disassembly can do that) but they are good enough for my purposes. Another example is the infamous cannon launch event in Mega Man X5, which at the time, no one knew when the launch without parts would succeed or fail, or even its exact probability (rumors of about 1/100 were frequent). It seemed like something that would require disassembly, but through testing in a more ideal setting (a couple parts rather than no parts, which raises the probability), I noticed that on a couple instances of success, one byte of the RNG memory address, normally some number from 0-255, was 6 and 7 at the time of decision. I cracked the code a few hours later. As an aside, the reason for the 1/100 rumors (the actual probability is 1/16) is because players on the PSX version would keep resetting for the event, but it always used the same RNG value.
Banned User, Former player
Joined: 3/10/2004
Posts: 7698
Location: Finland
FractalFusion wrote:
I would only ever consider disassembly for RNG purposes.
Given that, I wonder how feasible it would be to create a tutorial on how to find (and interpret) the randon number generator code for a game. It might help many people get started. (I know that most games have their own custom RNGs and there are approximately as many different implementations as there are games with RNGs, but perhaps there still are common ways to finding and understanding them.)
MESHUGGAH
Other
Skilled player (1888)
Joined: 11/14/2009
Posts: 1349
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
Warp wrote:
create a tutorial on how to find (and interpret) the randon number generator code for a game.
I actually planned to make a newbie-friendly RAM search video-tutorial similar to CheatEngine's 1st time tutorial. Mostly for avoiding motivated and interested players making TASes without optimizations and knowledge.
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
Skilled player (1636)
Joined: 11/15/2004
Posts: 2202
Location: Killjoy
It also depends on the RNG. In the case of sequential RNGs, (fire emblem, Shining Force 2, Alien Hominid, Shining Soul 2, and numerous others) there is a much easier way to track the RNG, without knowing the formula. Once you figure out it sequential, and you've isolated a frame in which you know only a single RNG execution happens, a quick lua script can dump all the RNGs to a file. That is what I do, when I don't want to dig into a game's ASM.
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
Site Admin, Skilled player (1236)
Joined: 4/17/2010
Posts: 11264
Location: RU
The video-tutorial on RAM Searching already exists. http://www.ustream.tv/recorded/8547343
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Joined: 6/16/2009
Posts: 30
Woah, all of the vets are posting in my humble topic... I feel so honored ;_; So this was my game plan, thanks to you guys: -Finish reading all of the great resources that you guys have helped me find -Find a game (that I love) -Learn how to use that game's console emulator inside and out -Play through the game non-TAS (and record it) -Learn Lua, and get a feel for RAM searching by picking up a bit of asm -TAS the game -Hopefully publish :D For the actual TASing, now that I think of it, I don't know how to hex/splice in new input (like if an improvement is found in a part that I've already done, the improvement can be grafted in, without disturbing any other parts of the run, I forget what this is called). If there's no tutorial in the resources section, could someone please give me a brief rundown of how to do this?
Joined: 7/2/2007
Posts: 3960
Some of the consoles are supported by the TAS movie editor which should be able to help you with hex-editing. Otherwise, you can do it manually. The movie files are basically sequences of button presses (and, with more advanced consoles, analog stick positions). Hexing is "merely" inserting the newly-desired input into the middle of the previous input. This does require you to be able to read the input file, though, which can be more or less complicated depending on the file format. Also, hexing isn't always possible. Let's say that there's a platform in the game whose position is dependent on a global timer. If you hex an earlier part of the run to be faster, then when you get to that platform it's not where it was the first time you encountered it. Think of hex-editing as time travel: you went back in time and changed things, so now in the present the game world is different. Depending on the game, things may change more or less drastically.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
MESHUGGAH
Other
Skilled player (1888)
Joined: 11/14/2009
Posts: 1349
Location: 𝔐𝔞𝔤𝑦𝔞𝔯
Zero100 wrote:
I don't know how to hex/splice in new input (like if an improvement is found in a part that I've already done, the improvement can be grafted in)
http://code.google.com/p/tastools/wiki/QuickHex - Open your improved movie file for the 1st slot - Open your original movie file for the 2nd slot - Fill in the starting frame and ending frame (the improvement part) You can also try http://code.google.com/p/tastools/wiki/TASMovieEditor if the improvement is only some bytes/frames. Or download a free hex editor and do it manually.
PhD in TASing 🎓 speedrun enthusiast ❤🚷🔥 white hat hacker ▓ black box tester ░ censorships and rules...
Joined: 6/16/2009
Posts: 30
o_O Wow, that was fast. Seriously, thanks a bunch for all of the help, guys. I'll update this when I find a game, for your guys' approval, hopefully.
Joined: 6/16/2009
Posts: 30
Alright, so I'm going to be doing Pokemon Crystal. I'm in the middle of watching FractalFusions's (what a cool username) Gold run, and I'm playing the game through myself the first time. I'm also gonna be looking at the resources and other things available. I hate to ask again, but does anyone have any advice?