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).
A few seconds before this, I am on the orange spot circled on the map, and I want to reach Silva in area 5. Now, the intended order is to clear the whole zone (going through 2,3,4 before reaching area 5, marked with red.). But a quirk of this game is that it offers "shortcut" areas to avoid going back through the entire zone, after beating a boss. In this case, it's the area 6, marked here with a blue road.
Now, these "shortcuts" areas are usually impossible to pass through until you complete the area, and this is ensured in various ways- missing soul (that you get by beating the boss of that area), or one-way passthrough. But, if it was possible to pass through these shortcuts areas, then we could skip the entire zone and get almost directly to the boss. In this skip, this is exactly what happens.
The way this particular zone is blocked off is a combinaison of both. There's a jump here that's supposed to be impossible until you get Mic, which allows to make jumps with much higher speed. But if you take the area in the intended way (from left to right, as opposed to from right to left in the skip) you can also fall down and be unable to get back up, but have succesfully taken the shortcut; a one-way passage.
But, what if I tried to do a normal jump, instead of the boosted jump that you're supposed to do? Well, it would turn out that I was off by a few hundred subpixels. So, as I said in IRC:
In terms of actual route and discoveries, what changed?
* I picked up Magnescope (soul), by far the biggest route improvement. I am ashamed of myself for missing this one; it allows to cancel effectively every state (except backdashing), which is extremely useful for combat. With Magnescope, you can pump enemies without even letting them one frame of non-invinicibilty in the best-case scenario.
* I pick up Vodianoi later on, which allows unrestricted movement in water (instead of more than halving your speed, keeps it as-is). Useful for Area 2 backtracks and for the area just before Lee-Pai Long which is filled with water.
* Strategies on the Rio fight: thanks to Magnescope, we can keep up a decent combo without getting hit: three slash > Magnescope > single slash > magnescope > crouch slash when Rio attacks. Crouching allows us to lower our hitbox enough, and attacking on the first frame we crouch brings us to the crouch slash state instantly, giving us greater flexibility.
* Thanks to my hitbox script, I noticed that Rio hitbox will extend towards us a significant amount when he does his crouch attack. If we need to take damage to manipulate RNG, this is very useful (as hits from contact damage with Rio do 7 damage, instead of 9 from the sword.) Taking damage wastes a frame for every health lost, as there's a refill after each boss that takes an extra frame for every health point it has to refill.
* I noticed that the 1-frame state lag affects everything in this game. This is easily the most important [glitch/bug] in the game. To explain it more clearly than my previous post, every slot in this game (enemy, Yoh himself, even objects) have a state which is changed depending on their actions. Getting on a floating platform will change its state, attacking will change Yoh's state, and so on. However; when states are changed, there is a one-frame lag during which the state will apply, but not the effects of that state. For example, if we are groundsliding with large speed, and then walk to 1 frame, we change to the walking state, but the effects itself of the walking state (changing our speed) are not applied. This applies to bosses as well (as well as every other thing which has a slot); if you interrupt them during this lag, then they will take different actions.
There are a few new things I discovered about the mechanics of the game as well as in general, see the new numbers on the Lua script, but I'll keep these for once I have a WIP to show alongside it. (And once I get past Rio again..)
