Emerald: Battle Tower RNG Manipulation

Summary

How RNG works in Emerald Battle Tower and how the Emerald Battle Tower RNG Manipulation Tool exploits it.

Table of Contents

1. First version of the RNG manipulation tool: Naive Approach

1.1 Opponent Team Generation Algorithm

By itself, the algorithm used to generate the opponent team is quite simple.

1.2 RNG Manipulation Basics

In Emerald, RNG updates every frame. Forcing a specific battle requires frame-perfect button presses, which is very difficult. Unlike wild Pokemon encounters that can be attempted multiple times, the Battle Frontier can only be attempted once. In short, RNG manipulation in Emerald Battle Frontier can't be used to force a specific battle.

A less risky and easier RNG manipulation is to be able to predict the entire opponent team, based on the trainer and their first Pokemon. With this extra knowledge, the battle becomes a lot easier.

In theory, there are only two unknown variables at play:

1.3 Estimating Frames Before Trainer

The trainer is selected upon entering the battle map. The number of frames before reaching the map depends on the time spent in the Battle Tower elevator, which depends on the current win streak. The more win streak you have, the higher up you go, and the more time you spend in the elevator.

Here's the number of frames in the elevator by win streak:

Considering this, we can accurately predict the frame when the trainer is selected with autofire (pressing A every frame). Without autofire (pressing A about 5 times per second), the additional frames is between 120 and 180 (~2-3 seconds slower than TAS).

1.4 Estimating Frames Between Trainer And 1st Pokemon

The first Pokemon is selected upon starting the battle, upon pressing A after the trainer greeting message. The number of frames for the greeting message depends on trainer. Every trainer has a different message, with variable length.

The shortest message is "FUFUFU..." by Joel which takes 17 frames. The longest is "MY SECRET POWER IS OVERWHELMING TO POKEMON" by Jamison which takes 49 frames. It's about 0.88 frames per letter.

1.5 Outcome

I applied each step of the generation algorithm perfectly. And the results were... totally wrong... For a mysterious reason, the Pokemon team predicted by the tool didn't match at all the ones when playing the game.

After debugging the assembly, I discovered that the Random() function was called way more often than expected. The reason: v-blank interrupts.


2. Second version of the RNG manipulation tool: V-Blanks by Section

2.1 What are V-Blank Interrupts?

A V-blank interrupt is the mechanism used by the GBA to refresh the screen. It is triggered every 1/60th of a second independently from regular game logic execution.

When a V-blank interrupt occurs, the regular game program execution is paused, v-blank associated code is executed, then the regular game program resumes.

In Pokemon Emerald, the v-blank associated code updates the RNG frame by 1. This means that every 1/60th of a second, the RNG frame updates by 1.

Every single program operation has an impact on v-blank interrupts. Two GBAs with different saves that boot the game and press the buttons at the same time will not result in the exact same outcome. This is because loading and saving the savefile take a variable number of operations.

In short, it's impossible to precisely determine when v-blank interrupts will occur in the context of the Battle Frontier.

2.2 RNG Manipulation considering V-Blank Interrupts

Here is the list of important RNG steps:

V-blanks can occur between steps, or during the retry attempts of a step.

For the tool to return accurate results, we need to estimate as accurately as possible the number of v-blanks occuring between and during each step.

The V-blanks occuring before 1st Pokemon Preset don't really matter, because it depends on the player input. We already add a buffer to take into consideration the variability.

According to my tests, the following is the range of V-blanks for each step:

StepV-Blank Count# of Possible Outcomes
During 1st Pokemon Preset retries: 0-1 2
Between 1st Pokemon Preset and 1st Pokemon Generation: 0-1 2
During 1st Pokemon Generation retries 0-1 ~100†
Between 1st Pokemon Generation and 2nd Pokemon Preset 0-16 17
During 2nd Pokemon Preset retries: 0-1 2
Between 2nd Pokemon Preset and 2nd Pokemon Generation: 0-1 2
During 2nd Pokemon Generation retries 0-1 ~100†
Between 2nd Pokemon Generation and 3rd Pokemon Preset 0-16 17
During 3rd Pokemon Preset retries: 0-1 2
Between 3rd Pokemon Preset and 3rd Pokemon Generation: 0-1 2
During 3rd Pokemon Generation retries 0-1 ~100†

The overall number of possibilities is: 2 * 2 * 100 * 17 * 2 * 2 * 100 * 17 * 2 * 2 * 100 = 18_496_000_000 !

Note † : The reason why Pokemon Generation retries generate so much possibilities will be explained later.

Obviously, it's impossible to brute force this number of possibilities. There's no point in having a tool that displays 18_496_000_000 possible trainer teams. We need to optimize certain sections by understanding why the v-blank varies so much.

2.3 Optimizing V-Blanks During Pokemon Generation Retries

Pokemon Generation has a very variable number of RNG calls. In Generation 3, the nature is determined by using the formula (PID modulo 25) where PID is the personality ID. To create a Pokemon with a specific nature, the game generates a random PID until it results in the wanted nature. In average, it takes 25 attempts to create a valid PID. In some cases, it can take many many more (100+).

A v-blank can occur at any time during those RNG calls. If there are 100 RNG calls, then there are 100 possible outcomes (v-blank at 1st retry, v-blank at 2nd retry, v-blank at 3rd retry etc.)

Fortunately, in most cases, the exact moment when the v-blank occurs doesn't impact the end result. We need to take advantage of that fact to optimize the RNG manipulation.

2.3.1 Determining the Different Outcomes for Pokemon Generation

We want determine the list of different outcomes for the nature generation. Note that each nature generation attempt calls RNG twice (PID has 32 bits, and Random() returns 16 random bits).

For example, nature generation starts at RNG frame 1000 and the wanted nature is Brave. We make the list of all frames after 1000 that result in the Brave nature, for example frames 1005, 1015, 1018, 1027, 1039, and 1050.

From those values, we can determine the following:

As you can notice, v-blank occuring after RNG frame 1018 doesn't matter, because the valid PID would already be found at this point.

The number of different outcomes is 2 + (the number of odd RNG frames resulting in valid PID before the first valid even RNG frame). With the example above (1005, 1015, 1018, 1027, 1039, 1050), we get 4 different outcomes (1000 to 1004 for 1005, 1006 to 1014 for 1015, 1016 to 1018 for 1027, later than 1018 for 1018).

2.3.2 How Helpful That Pokemon Generation Optimization Is

In average, the average number of different outcomes for nature generation is 3. (The average the number of odd RNG frames resulting in valid PID before the first valid even RNG frame is 1.)

Another easy optimization is to ignore nature generation for the 3rd Pokemon, because it only impacts its ability and gender, which are not that important.

In short, with this optimization, the average number of possible outcomes caused by Nature Generation retries was reduced from 100^3 (1_000_000) to 3^2 (9).

2.4 Optimizing V-Blank After Pokemon Generation

The number of v-blanks between selecting the PID of the 1st Pokemon and selecting the Pokemon preset of the 2nd Pokemon is also very variable. It ranges between 0 to 16 v-blanks.

Unlike v-blanks occuring during Pokemon Generation, every v-blank after Pokemon Generation results in a different outcome.

Reminder: The number of v-blanks is directly related to the number of processor cycles which is related to the instructions performed. For some reasons, the number of instructions performed greatly vary depending on the Pokemon generated.

The number of cycles (instructions) during Pokemon Generation depends on:

2.4.1 Impact of PID on Cycle Count

The reason why PID has an impact on cycle count is because Pokemon Emerald was compiled with a compiler that has a poorly-optimized modulo operator code. The modulo operator takes between 10 and 900 cycles.

In theory, taking 10 or 900 cycles shouldn't have a big impact on v-blank count. Reminder: V-blanks occur every 280_896 cycles. To cause a difference of 16 v-blanks, you would need to call the modulo function on the PID thousands of times! It makes no sense to call the modulo operator that many times when creating a Pokemon, right?!

Well, it turns out that the game does indeed call the modulo operator thousands of times (x2924 times to be exact for Level 100 Roselia 1).

The reason it is being called so much is because the Pokemon data structure is always encrypted in the RAM. Every access to read or write a Pokemon attribute must decrypt the data structure. And to decrypt the data structure, 4 calls to (PID % 24) are performed.

This means the number of times Pokemon attributes are accessed impacts the number of cycles. The number of accesses depends on the Pokemon preset.

2.4.2 Impact of Pokemon Preset on Cycle Count

The Pokemon preset in the Battle Frontier includes:

The number of accesses to Pokemon attributes depend on:

I was able to extract the number of modulo calls and cycle count for each Pokemon preset. Using this data, the tool can determine the number of cycles of a Pokemon generation for a given PID and level.

Let say that the number of cycles for Level 50 Jynx with a given PID is 2_500_000. (2_500_000 cycles) / (280_896 cycles / vblank) = 8.9 vblanks. This means generating that Pokemon will cause 8 or 9 v-blanks. If the current cycle when Pokemon generation starts is below 28_089 (90% of 280_896), there will be 8 v-blanks. If it is above or equal to 28_089, there will be 9 v-blanks.

In short, with this optimization, the number of average number of possible outcomes caused by Pokemon Generation was reduced from 17^3 (4913) to 2^3 (8).

The total number of possible teams is now relatively small, but we can do even better by simulating cycles!


3. Third version of the RNG manipulation tool: Cycle Simulator

3.1 How to Reduce Possibilities Even More

So far, we only tried to reduce possibilities of each step taken individually. We can reduce it even further by considering how the steps interact with eachother.

For example, generating the Pokemon Nature has taken 100 retries without any v-blank occuring. Afterwards, the number of v-blanks for Pokemon generation is estimated at ~8.9.

So far, we assumed that Pokemon generation would result in 8 or 9 v-blanks. (If the current cycle is below 28_089, there will be 8 v-blanks. If it is above 28_089, there will be 9 v-blanks.)

In reality, it's impossible for the current cycle to be below 28_089 cycle when Pokemon generation starts, because in the previous step, generating the Pokemon Nature has taken 100 retries without any v-blank occuring. Those 100 retries already rose the current cycles far above 28_089.

To improve the accuracy, we need a new RNG manipulation algorithm that simulates cycle count for all steps.

3.2 Data Required

For this new algorithm, we need the number of cycles of every step and each of its outcomes. Some steps have many possible outcomes. Here's the list of steps and outcomes:

For the same outcome, the number of cycles also depends on the RNG state at the time of the call. For example, the number of cycles for "Failure because invalid nature" depends on the cycles for the operation (PID % 25) which depends on the value of the last Random() call. Fortunately, we are able to accurately calculate it.

3.3 Cycles Per V-blanks

The v-blank interrupt function occurs every 280_896 cycles. In the v-blank function, two main things occur: updating what's displayed on the screen and updating the audio. In the case of Battle Tower, there's nothing to update visually, so that duration is constant. But the number of cycles to update the sound is highly variable (between 35_000 and 65_000 cycles depending on where the audio track is).

When the cycle counter reaches 280_896, the cyle counter is reset, regular program execution is stopped, and the v-blank function is called. Once the v-blank function is done, regular program execution resumes. The cycle counter when the regular program execution resumes is between a 35_000 and 65_000 range.

In the previous sections, I simplified the problem when calculating the number of v-blanks for Pokemon generation. If generating a Pokemon takes 2_500_000 cycles excluding v-blanks, the number of v-blanks is actually between 10 and 12 (not between 8 and 9) because of the cycles taken by the v-blank themselves. This extra variability makes it even harder to accurately determine the outcome.

Additionally, v-blank interrupts are not the only possible interrupts. There are also Vcount interrupts which work similarly, but they only run for 120 cycles in the Battle Frontier.

3.4 Algo Summary

With all the data collected, we need an algorithm to simulate cycles and calculate possible teams.

In short, for every starting state possible, the algo applies the generation steps. When a v-blank occurs, it takes into consideration all possible v-blank durations.

A starting state is composed of three values:

3.5 Algo Execution Example

For example, the starting state is {RNG_Trainer=2050, RNG_1st_Pokemon=2132, Cycle_Count_1st_Pokemon=250_000}. RNG_Trainer=2050 results in the trainer Dev being selected. RNG_1st_Pokemon=2132 results in the Pokemon Nidoking 1 being selected. The selection took 10_000 cycles. We are now at {RNG=2133,cycle=260_000}.

We attempt to generate a PID that results in the Adamant nature. The first attempt is a failure (nature was Brave) and took 5_000 cycles. The state is now {RNG=2135,cycle=265_000}. The second attempt is also a failure (nature was Modest) and took 20_896 cycles. The state is now {RNG=2137,cycle=285_896}.

Because the cycle is above 280_896, a v-blank occurs. The v-blank takes between 35_000 and 65_000 cycles. The tool selects a random number in that range, for example 40_000 cycles. The state is now {RNG=2138,cycle=45_000}.

A 3rd attempt for nature generation is a success (nature is Adamant). The generation of the Pokemon takes 2_500_000 cycles. The state is now {RNG=2140,cycle=2_545_000}. Because the cycle is above 280_896, v-blanks occur (x9 times). The state is now {RNG=2140,cycle=16_936 + 9 v-blanks}. The tool selects a random number of cycles that the x9 v-blanks took themselves to update the screen/audio, for example 375_000 cycles. The state is now {RNG=2149,cycle=386_936}. Because the cycle is above 280_896, an additional v-blank occurs {RNG=2149,cycle=106_040 + 1 v-blank}. The tool selects a random number of cycles for the v-blank (ex: 43_960 cycles). The state becomes {RNG=2150,cycle=150_000}.

We repeat this process until all 3 Pokemon are generated.

3.6 Supporting Uncommon Results

A problem with the implementation above is that only 1 final outcome is generated, based on the random number of cycles per v-blank used. To generate multiple possible outcomes, the algo must be ran multiple times. It's unclear how many times the algo must be ran to ensure that all possible outcomes have been found.

To overcome this problem, the strategy is to always explore two branches: the lower bound and the upper bound. For example, if v-blank cycles are between 35_000 and 65_000, we will explore the outcome given that v-blank cycles is 35_000, then explore the outcome for 65_000. This ensures all possible outcomes are explored. Note: Additional tweaks were also added to explore different outcomes for cycles in-between the bounds.

3.7 Calculating Probabilities

So far, we were only interested in knowning the possible teams. In most cases, there are over 100 possible teams, but some of them are a lot more probable then others (often one with 50%+ chance). It is a lot more useful to players if we can identify the most probable teams.

For accurate probabilities, we need the distribution probabilities for all randomized ranges.

3.7.1 Probability Distribution for V-Blanks from Player Inputs

This covers v-blanks before selecting the trainer and before the 1st Pokemon.

Assuming the player presses A every 12 frames (x5 times per second), the average frame delay per press is between 0 and 12 (average of ~6). It takes 9 A-presses from the game booting to selecting the trainer.

In reality, it's a bit more complex than that, because there's a fixed delay between optimal inputs. Having a slower but better tuned mashing speed may result in better results. For example, in a text transition, a minimal delay of 15 frames is required between two inputs. Mashing once every 14 frames will trigger the text after 28 frames. Mashing once every 16 frames (slower than before) will trigger the text after 16 frames. In short, it's hard to estimate the real delay based on calculations alone. Actual in-game testing was required. Note: This is a simplified example with made-up numbers.

Still, we can make some assumptions. The probability distribution of the frame delay should follow a pyramid-like curve, with the average case being a lot more probable than the extremity. It is similar to the probability distribution when summing two random dices (obtaining 7 is a lot more common than obtaining 12).

The distribution can be approximated as 1,1,3,8,8,3,1,1. A value near the average region is about x8 more like than in the extremity region.

The same logic can be applied for estimating the frame delay for the trainer greeting message, before selecting the 1st Pokemon.

3.7.2 Probability Distribution for Current Cycle At 1st Pokemon Selection

The current cycle count is the number of cycles since the last v-blank. It is a value between 0 and 280_895. It impacts when the next v-blank will occur and can greatly change the end result.

According to my tests, its value range between 185_000 and 235_000, with the range 210_000 to 215_000 being the most likely.

3.7.3 Probability Distribution for Cycles Per V-blank

Even though a v-blank takes between 35_000 and 65_000 cycles, not all values have the same chance of occuring. For example, a v-blank taking between [50_000, 55_000] cycles is x5 more likely than a v-blank taking between [35_000, 40_000] cycles.

Furthermore, the range of x10 consecutive v-blanks is a lot smaller than 10 times the range of a single v-blank (350_000 to 650_000). The reason is that multiple consecutive "long" v-blanks are impossible.

For example, the v-blank takes 65_000 cycles only when the audio reaches the end of the song and loops back to the beginning of the song. This means it's impossible to reach 130_000 cycles in 2 consecutive v-blanks, because the audio can't loop twice consecutively. Note: Audio looping is not the real reason for long v-blanks. This is only a supposition to illustrate the idea.

By collecting data of many consecutive v-blanks, it is possible to have a better approximation when multiple consecutive v-blanks occur. For example, the actual range for x10 consecutive v-blank is between 374_000 and 574_000.

Additional research could be done to better understand the number of cycles of the function SoundMain() called in the v-blank interrupt function.

3.8 Apply Probabilities

The easiest way to simulate probabilities in complex multi-step logic is to run simulations. The more simulations, the better the accuracy.

Even though we could simply run simulations of the entire Pokemon team generation, it wouldn't be very efficient. This is because about 99% of teams generated are invalid because they don't match the trainer and Pokemon the player is facing in-game.

A better way is to split the algorithm in two parts: determining the possible valid team outcomes, then calculating probabilities only on the "paths" that lead to valid outcomes.

3.9 Useful Scripts

Those scripts must be used on the latest dev version of the mGBA emulator.

4. Final Result

Here's the Emerald Battle Tower RNG Manipulation Tool.

Here's the Emerald Battle Frontier Assistant which fills the input for the RNG Manipulation tool automatically.

5. Credits

Author: RainingChain

Special thanks to Shao for support and providing the functions to calculate cycle count for the modulo operator.

Special thanks to mGBA team for the mGBA emulator.