Editor, Experienced Forum User, Experienced player (631)
Joined: 5/2/2015
Posts: 670
Location: France
In this post I will describe how I found the RNG and implemented it in Lua on a game I was working on. This post is written in this way, and not in an authoritarian tone because first of all, this is the first time I did this and I don't pretend to dictate others with what little knowledge I have, and second because this is hardly the sort of thing where you can follow a manual and have it work out with streamlined instructions. Also, please note that this does not really require intense programming skills: I had no actual experience with programming before I started this, and I only started writing Lua when working on the script for my game. I think the only things that would be required for this is a strong sense of intution (as in, to be able to figure things out easily), good willpower and some familiarity with concepts of how a computer works. Shoutouts to people who helped me along this two-day endeavor: Masterjun, Warepire, ThunderAxe31, feos, Scum, Scepheo, etc. Also, I want to give a link to the Reverse Engineering page here, which is quite helpful for an introduction to a few concepts. Part I: Figuring out the RNG's adress So I was working on a GBA game, Shaman King 2, and I was kind of in a rut; I was in the third boss fight, but, unlike the first two that I had manipulated perfectly, this one required much more precise manipulation. Then I thought: Why not try to figure out the RNG? This way, I would be able to predict it, and as such, predict and manipulate boss attacks. The first thing is figuring out where the RNG is actually predicted. To do this, I used cross-branch RAM search, using BizHawk. How does it actually work? First, find an action that will seem to change the outcome of what happens next (thus manipulating the RNG): in my case, it was attacking. Then, make two branches using TAStudio, that are the exact same in movement, etc, except for one branch where you insert the action that advances RNG and one branch where you don't. Now, set your two branches at the same frame (after the action that advances RNG), open RAM search, set the search to "not equal to" and "previous value", then switch between the two branches. Now, you should have a list of adresses that differ between the two branches of the same frame. Finally, select all those adresses, then click Search > Add to RAM watch. You should have quite a few adresses now: we will do a bisect to find the correct one(s). What you want to do is switch to a branch, then freeze half the adresses in RAM watch. Switch to the other branch. If the game behaves the same way as it did on the other branch (eg. boss behaves the same way) then you've frozen the RNG adress(es) and can delete the other half. If not, delete the half you've frozen. Repeat until you find the adresses. Using this method, I was able to find the good adress: 0x16C0. But, how does it actually work? Time to disassemble! Part II: Disassembly of the game Sounds scary? Well, it kind of is; we're basically going to the "lowest level" just above machine language: assembly language (which I'll abbreviate as asm for the rest of the post). Assembly is, from my understanding, basically a glorified macro language. To do this, you will need an emulator that supports disassembly: I used no$gba. (Note: you can do all of this in a much easier way, in the case of the GBA, simply by switching to the vba-next core in Bizhawk and using the provided debugger and trace logger.) Because the platform of the game is GBA, these instructions are gonna be biased towards it. In any case, you will need a lot of information about your platform. The main ones I used for this part were gbatek, along with the ARM reference center whenever I needed more info about an instruction. Now, I already had my adress, so in no$gba's disassembler I put a breakpoint at that adress: first rightclick the bottom window, go to break/watch window, then Define Breakpoint and set the breakpoint. A breakpoint will halt execution whenever the condition is reached: here I set a breakpoint whenever the adress 0x16C0 was written to in IWRAM, so: "[030016C0]!" will trigger on write. You might be saying that my adress was 0x16C0, so why was the value I specified 0x030016C0? That's because the IWRAM section starts at 0x03000000 in memory:
  00000000-00003FFF   BIOS - System ROM         (16 KBytes)
  00004000-01FFFFFF   Not used
  02000000-0203FFFF   WRAM - On-board Work RAM  (256 KBytes) 2 Wait
  02040000-02FFFFFF   Not used
  03000000-03007FFF   WRAM - On-chip Work RAM   (32 KBytes)  
  03008000-03FFFFFF   Not used
  04000000-040003FE   I/O Registers
  04000400-04FFFFFF   Not used
Then after that, I made the RNG advance to trigger the breakpoint (by attacking, since that advanced RNG.) After some time, I found this subroutine (note that subroutine=function):
Language: armasm

ROM:0800F904 PUSH {LR} ; Link register is register 14 ROM:0800F906 MOV R1, R0 ROM:0800F908 LDR R3, =0x30016C0 ; IWRAM 0x16C0 into r3 (adress of RNG) ROM:0800F90A LDR R2, [R3] ; Loads the previous value of the RNG into R2 ROM:0800F90C LDR R0, =0x41C64E6D ; Multiply by 0x41C63E6D ROM:0800F90E MUL R0, R2 ; stores only the least significant bits; modulo 32 ROM:0800F910 LDR R2, =0x3039 ROM:0800F912 ADD R0, R0, R2 ; Add 0x3039 ROM:0800F914 STR R0, [R3] ; Store result into adress of r3, 0x16C0
I commented it a bit here, so it should be easy to understand, and it's a pretty simple RNG. In english, what this subroutine does is that it first reads the previous value of the RNG, multiplies it by 0x41C64E6D and only keeps the least 32 significant bits; modulo 32 (if the value after multiplying was 0x273219DA6F3, then the value of r0 would be 0x219DA6F3), then adds 0x3039 to it, and writes it to the RNG adress. If it sounds familiar, that's because it is a linear congruential generator. (Bonus: this is actually the most common RNG in history! Try converting 0x41C64E6D to decimal..) If you want to check that your analysis of the RNG is correct, then, open up your emulator with RAM watch on the RNG adress, then try predicting the next RNG value (using a hex calculator.) If your result matches up with the next RNG value, then you've grasped it. Note that even if it doens't match, the RNG can advance multiple times per frame! So, at some times your first calculation may not match up with the actual RNG value. This is why it's convenient to have an RNG table of values, so that we can check how much the RNG advances per frame, and also to get the next RNG values. Part III: Lua implementation Since we now understand how the RNG works, we can reimplement it in a simpler programming language. Lua is the standard scripting language for the entirety of TAS emulators, including BizHawk. Since you can interact with the emulator with it, we'ill be using it in order to reimplement this subroutine in Lua. Unfortunately, I ran into a roadblock here, which was that Lua numbers in 5.1, the version in Bizhawk, are double precision floating point and can only represent numbers accurately up to 53 bits, after which they were rounded: see this post and the following. After solving this, I had a nice implementation:
Language: lua

-- SK2 rng re-implementation in Lua --############################################################################# local function RngLua(value) --############################################################################# local high = (value * 0x41C6) % 0x10000 local low = (value * 0x4E6D) % 0x100000000 return ((low + high * 0x10000) % 0x100000000) + 0x3039 end
This was a function that calculates the next RNG value based on the current one. Mission complete! The only thing left is to expose that to the TASer (me) in a friendly way, and so I wrote a function which would display the next RNG values, as well as a counter (to see how much the RNG changed per frame, if it changed) and a visual indicator (to see where was the position of the rng was in the table before)
Language: lua

-- Displays a table of the next X rng values, based on current RNG --############################################################################# local function RngPredict(x,y,number) --############################################################################# local RNG = memory.read_u32_le(0x16C0, "IWRAM") -- Display the number of steps the RNG has advanced, if it advanced pastRNG[2]= pastRNG[1] pastRNG[1]= RNG if pastRNG[2] ~= pastRNG[1] then for i=1,number do if RNG == rngResults[i] then gui.pixelText(x+33,y, i, 0xFFFFFFFF, color.trans[6]) gui.pixelText(x+33,y+i*7, "!", 0xFFFFFFFF, color.trans[2]) end end end gui.pixelText(x,y, string.format("%08X", RNG)) rngResults[1] = RngLua(RNG) for i=1,number do rngResults[i+1] = RngLua(rngResults[i]) gui.pixelText(x,y+i*7, string.format("%08X", rngResults[i])) end end
And what the result looked like, because this post is severely lacking in cool images - RNG predictor on the left: And that's it. I hope this can help anyone who is trying to find RNG in their games. Please point out if there is misinformation in this post (there probably is).
Editor, Experienced Forum User, Player (131)
Joined: 4/7/2015
Posts: 316
Location: Porto Alegre, RS, Brazil
Good guide for beginners! A few weeks ago I was searching the RNG address for The Flintstones (SNES), and apparently it doesn't exist! The only "random" moments are boss fights, but they seem hardcoded
Games are basically math with a visual representation of this math, that's why I make the scripts, to re-see games as math. My things: YouTube, GitHub, Pastebin, Twitter
Editor, Experienced Forum User, Player (42)
Joined: 7/11/2010
Posts: 1017
I'm beginning to wonder in how many games you could find the RNG routine simply by searching the ROM for 0x41C64E6D. It's not a very commonly used number in most contexts, but it *is* very commonly used in RNG algorithms. Obviously, this wouldn't work for every game, but it wouldn't surprise me if it worked in a fairly large proportion of them. 64-bit RNGs are becoming more popular, but unlike 32-bit RNGs, there isn't a consensus value for a yet (which is normally the most distinctive value in an LCRNG algorithm). So unfortunately, those may be harder to find by this method.
Dragos-san
Other
Experienced Forum User
Joined: 11/4/2019
Posts: 21
Location: Apple Macbook Pro (Early 2015)
Can't you just command-f or similar while deconstructing the game for the RNG lines? IE we know that there are certain words attached to the RNG values, so we search up those words. I have no experience in programming, so I apologise if I'm wrong. ... I wish that game devs released their RNG code as a long list of numbers for our convenience. But that doesn't happen, even when pi is the most random number we know.
Thank you and have a nice week! :)
Experienced Forum User, Skilled player (1593)
Joined: 9/17/2009
Posts: 4899
Location: ̶C̶a̶n̶a̶d̶a̶ "Kanatah"
Since the RNG mentioned is the LCG, I think this post may help: Post #394464
In practice, them using LCG very often means you're going to have an incredibly easy time figuring out the algorithm. Most of the time, you don't even need to disassemble those. For LCG, the formula for advancing through seeds is (oldSeed*x+y)%z. (Will keep calling each iteration "seed", even though that might not be technically correct) Most of the time, the %z part is just dropping the highest bits and will occur naturally in older systems. F.e., z would be 65536 for 16bit values. 1) Find the address they store the last seed at 2) Find a way to advance this seed by exactly one iteration. 3) Set this address to 0, advance once. (0*x+y)%z will give you y. 4) Set this address to 1, advance once. (1*x+y)%z will either give you x+y or (x+y)%z (They might also use XOR) And you're usually just about done at this point. When analyzing the RNG of older games, I usually first try this procedure. Only if it fails, I'll disassemble. It can often save you lots of time. (If you already have a disassembler open, it might still be faster to just disassemble though) 5) For each random event, they'll usually take either a portion of the last seed or the seed they have just advanced to (they'll either advance the seed before or after getting the actual random number they'll use), and take that portion % the number of possible outcomes for the random event in question. By "portion", I mean any number of consecutive bits of the seed. You should be able to work things out from there. Maybe without disassembling again. (Though disassembling would generally save time with this step) Please go easy on me when pointing out everything that's wrong with this post. I know straight-up disassembling is actually the proper way, and I don't recommend anyone should follow my advice.
In case anyone wonders how does one come up with X,Y, mod Z in the lua script. If it doesn't work, it's probably some other generator, and you might need to just code the instructions shown in the disassembler directly. Edit: And sometimes, it can be a slightly different form: Post #394484
AWDS: (x+1)(4x+1) % 2^30
Editor, Experienced Forum User, Experienced player (631)
Joined: 5/2/2015
Posts: 670
Location: France
I made a more comprehensive version of this post in my blog: https://xy2.dev/article/re-skgba/re-skgba.html
Experienced Forum User, Skilled player (1593)
Joined: 9/17/2009
Posts: 4899
Location: ̶C̶a̶n̶a̶d̶a̶ "Kanatah"
xy2_ wrote:
I made a more comprehensive version of this post in my blog: https://xy2.dev/article/re-skgba/re-skgba.html
Nice post and visuals. If you ever make a sequel post to that, I hope you also make a rough guide on how would one determine how the RNG is actually used (eg. How is 0x3039 related to the NPC's movement pattern?) Right now, I'm just looking at thousands of lines of assembly, and have no clue how the RNG is even used after figuring how how said RNG is advanced.
Active player, Experienced Forum User (256)
Joined: 9/1/2008
Posts: 900
I've tried looking at pretty much all addresses for BOF 3 to find the battle byte, to no avail. Any suggestions to find it quickly? I've tried highlighting non-zero addresses...
Experienced Forum User, Site Admin, Skilled player (1168)
Joined: 4/17/2010
Posts: 10856
Location: RU
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. If TASing is meta-play, TASVideos Movie Rules are meta-meta-play!