FF7 in-battle RNG (algorithm) ?

[antd]

Does anyone know which addresses are responsible for the in-battle RNG?

I have found that these seem to be look-up tables. And 0x00062E18 cycles 0 through 7. Then it looks up the other addresss (assigned 0 - 7) and reads that value to determine whether a critical hit (etc) is possible.

Code: [Select]

0x00062E10
0x00062E11
0x00062E12
0x00062E13
0x00062E14
0x00062E15
0x00062E16
0x00062E17
*
0x00062E18
This is not all of the addresses though. This is what happens when I lock 0x00062E18 and its corresponding look-up:
http://pastebin.com/NXJcCgmF
(trying an attack on each frame)

As you can see, it doesn't result in a critical hit (>1000) every time.

Anyone know what the other in-battle RNG address is? Or how I could go about finding it?

The reason is because I'm working on this:
http://www.youtube.com/watch?v=bnEjQxwDnNA

and it will be easier if I can make an algorithm for easier luck manipulation testing

[nfitc1]

FFVII doesn't use a RNG. Rather it uses a RNLUT (Random Number Look-Up Table). These are 256 pre-determined values that the game uses for pretty much anything "random". I've confirmed at least that this involves encounter rate, battle formation, random target acquisition, critical rate, and random damage variance (for applicable actions, of course). That's pretty much anything you'd need for a TAS. I haven't confirmed Evasion rate, but that's likely there too.

You can see the look up table using this program:

http://forums.qhimm.com/index.php?topic=7928.0

It's under Initial Data -> Random Numbers (changing these would be considered cheating in a TAS btw ).

As you've noticed, there are seven pointers to this table. I don't know the initial values to these tables, but what I think happens is there's a pointer to one of those seven pointers. When a random number is requested it looks at the value pointed to by the specified pointer. Then that pointer and the pointer pointer are both increased by one. You'll have to watch their behavior in a debugger, but that seems pretty reasonable.

[syntax error]

Adding real random numbers and encounters?

[Bosola]

No, it's not really randomized. It's just that the stepping process makes it harder to spot patterns.

It's fair to say there are circumstances where [Save, Reset, Reload, Run through next area] will be faster than [Run through next area].

[antd]

As you've noticed, there are seven pointers to this table. I don't know the initial values to these tables, but what I think happens is there's a pointer to one of those seven pointers. When a random number is requested it looks at the value pointed to by the specified pointer. Then that pointer and the pointer pointer are both increased by one. You'll have to watch their behavior in a debugger, but that seems pretty reasonable.

Hmm, the thing is I have the pointer and the "pointer to the pointer". But while freezing those values results in a critical hit 90% of the time, it doesn't result in a critical hit 100% of the time.

So this means there is another piece to the puzzle? I just know that the 'randomness' repeats after 65536 frames. Eg, if I get a critical on frame 1. I'll be able to get exactly the same critical on frame 65537, and on frame 131073 and so forth...

The pointer and the other pointer are only one byte, so I would guess that there is something else that is responsible and is 2 bytes.

Can anyone else shed any more information on this?

[dziugo]

If by freezing you mean using some external program to write into those locations constantly - maybe FF7 is quicker than that (sometimes)?

[nfitc1]

If by freezing you mean using some external program to write into those locations constantly - maybe FF7 is quicker than that (sometimes)?

No doubt that most programs are "faster". By the time something like Cheat Machine reads the data has changed and re-saves it, the program has already read the new value and moves on. I'm not certain that's what's happening here though. Most of the time, the value is read first THEN written to. It's possible that the value just gets updated several times in a second and Cheat Machine doesn't re-set it in time for the next read.

Here's what I can tell about the Random Number system. On the PC it DOES call an RNG quite often (in 2559 different places as a matter of fact). The battle-related random number set is "Seeded" in this way:

Code: [Select]

word RNG()
{
     value = _getptd(); //not sure what this does. Could be timer related
     long toreturn = 214013 * (*DWORD)(value + 5) + 2531011;
     return (toreturn >> 16) AND 7FFFh;
}

void something( args[] )
{
     .....
     _rand = RNG();
     Seed( _rand );
     .....
}

void Seed( int16 _rand )
{
     int seed = _rand;
     For (byte x = 0; byte < 8; x++)
     {
          RandomNumberSet(x) = seed;
          seed = seed >> 1;  (bit-shift 1 to the right [divide by 2, truncate remainder])
     }
     CurrentRandomSet = 0;
}
It's possible this seeding takes place before each battle at least.
Then there are three important functions after that. One is ReturnRandomByte, then ReturnRandomWord and IncrementRandomNumberSet:

Code: [Select]

byte ReturnRandomByte()
{
     byte toReturn = Random_Number_Tbl( RandomNumberSet( CurrentRandomSet ) );
     RandomNumberSet( CurrentRandomSet ) = RandomNumberSet( CurrentRandomSet ) + 1;  //the result of this is a byte so it never goes above 255
     return toReturn;
}

word ReturnRandomWord()
{
     byte lowerrand = ReturnRandomByte();
     if (UpperRandomSet AND 7 == 0)  //this is a global and is only used to determine if the set should be incremented. It's a 32-bit value so it could possibly overflow. I've never heard of this happening though.
     {
          IncrementRandomSet();
     }
     UpperRandomSet = ( UpperRandomSet ) + 1;
     byte upperrand = ReturnRandomByte();
     word toReturn = (upperrand << 8) + lowerrand;
     return toReturn;
}

void IncrementRandomNumberSet
{
     CurrentRandomSet = CurrentRandomSet + 1;
     CurrentRandomSet = CurrentRandomSet AND 7;
}
The associated pointers to each of these values are as follows:

Random_Number_Tbl = 0x99DC2C
CurrentRandomSet = 0xC06738
RandomSet( 8 ) = 0xC06740
UpperRandomSet = 0xC06748

The actual look-up to the table is in ReturnRandomByte. So if you freeze CurrentRandomSet and all eight bytes of RandomSet then any deviation that occurs is due to the RNG() above.

I did, at one time, set the entire Random_Number_Tbl to the same value and tried the effects in-game. The enemies always targeted one player; the players, when performing something that chose a random target like comet2 or various limits, always targeted the same enemy; all attacks did the same amount of damage, depending on the attack (the random variance was the same). It may not have an effect on critical hits.

[dziugo]

Yeah, just shooting in dark - even if it's first being read from, then written into, it might do that multiple times in each frame, and that would be often.

[syntax error]

Speed may be a reason for this often used simplification.
Make a patch using slower but real random values.

[nfitc1]

Speed may be a reason for this often used simplification.
Make a patch using slower but real random values.

I think it was used in the PSX version because either a: the RNG on the PSX is costly to use, or b: it's always the same each time. Having eight pointers to a look-up table seems more "random" I guess.

[antd]

The actual look-up to the table is in ReturnRandomByte. So if you freeze CurrentRandomSet and all eight bytes of RandomSet then any deviation that occurs is due to the RNG() above.

Yes, I froze those mentioned bytes and deviation did occur. Actually, I've found that the deviations occur every 32nd frame. So it seems something is coming in every 32nd frame to mess with randomness?

What exactly is causing the deviation? I was a bit lost there as I'm not a coder.

Could you give any advice on how to find the relevant addresses in RAM which are causing the deviations? (I'm using an emulator which allows frame by frame playback and lua scripts)

[antd]

Well.... better late than never, I suppose!

Code: [Select]

Random = [Rnd(0..65535) * 99 / 65535] + 1This post investigates the rnd part of the critical hit formula.

Code: [Select]

crit% = chance of critical       # (luck + level - enemy level) / 4
Here is how the randomness in critical hits is determined (Bad comments show PSX addresses ;p):

Code: [Select]

##Random Function##

lw r3,0x00d4(r28) # load word from 80062e18 = offset1
lui r2, 0x8006
addiu r2,r2,0x2e10 # 80062e10
addu r3,r3,r2 # 80062e10 + (word from 80062e18 as offset)
lbu r2,0x0(r3) # load byte from 80062e10(offset1) = offset2
nop

addiu r4,r2,0x01
andi r2,r2,0xff
sb r4,0x0(r3) # increment by 1 and store

lui r1,0x8008
addu r1,r1,r2 # 80083084
lbu r2,0x3084(r1) # load byte from 80083084(offset2) = rnd1
jr r31
nop

lw r3,0x0008(r28) # load word from 80062d4c
nop

addiu r4,r3,0x01 # increment by 1

andi r3,r3,0x07 # AND 7 (check that value < 8)
sw r4,0x08(r28) # store incremented value back to 8062d4c


beq r3,r0,0x14c18 # if crit% = 0 then no critical
addu r16,r2,r0 # move rnd1
jal 0x14b54
nop

lw r2,0xd4(r28) # load word from 80062e18
nop
addiu r2,r2,0x01 # increment by 1
andi r2,r2,0x07 # AND with 7 (check that value < 8) = offset2
sw r2,0xd4(r28) # store in 80026e18
jr r31
nop

jal 0x14b70
nop

lw r3,0xd4(r28) # load word from 80062e18 = offset3
lui r2,0x8006
addiu r2,r2,0x2e10
addu r3,r3,r2
lbu r2,0x0(r3) # load byte from 80062e10(offset3) = offset4
nop

addiu r4,r2,0x01
andi r2,r2,0xff
sb r4,0x0(r3) # increment byte by 1 and store in 80062e11

lui r1,0x8008
addu r1,r1,r2
lbu r2,0x3084(r1) # load byte from 80083084(offset4) = rnd2
jr r31
nop

andi r2,r2,0xff
sll r2,r2,0x08 # rnd2 * 256
andi r3,r16,0xff
or r2,r3,r2 # rnd1 OR rnd2 (combine rnd1 and rnd2) = rnd0
lw r31,0x14(r29)
lw r16,0x10(r29)
addiu r29,r29,0x18
jr r31
nop

lw r31,0x10(r29)
andi r2,r2,0xffff # take 2 bytes of rnd0
jr r31
addiu r29,r29,0x18


## calculate crit_rnd for which to compare against crit% ##

lui r4,0x8000
ori r4,r4,0x8001
andi r2,r2,0xffff
sll r3,r2,0x01 ## This section is actually simple, but compiler
addu r3,r3,r2 ## optimised for MIPS
sll r2,r3,0x05 ## Just: crit_rnd = ((rnd0 * 99) / 65535) + 1
addu r3,r3,r2
mult r3,r4
addu r2,r5,r3
sra r2,r2,0x0f
sra r3,r3,0x1f
subu r2,r2,r3
lw r31,0x10(r29)
addiu r2,r2,0x01
jr r31
addiu r29,r29,0x0018

slt r2,r16,r2
bne r2,r0,0xb0888 # if crit% >= crit_rnd then critical hit success
nop


[nfitc1]

http://wiki.qhimm.com/view/FF7/DamageFormula#Accuracy_Functions

Function 2 is the critical hit chance calculator. That's from the PC asm. The randomness factor is based on the ReturnRandomWord function that I mentioned way back. I think you just showed the PSX equiv of it.

[antd]

I just needed to know all of the memory addresses for PSX and there exact interaction for the TAS, hence the post!

[nfitc1]

Oh yeah. That was your first question, wasn't it? Sorry, can't help you there.

Hope your TAS goes well!