Dampé writeup for ZFG

Alright, I'll start with the way Dampé uses the RNG, and then I can talk a bit
about the RNG itself.

First, a random 32-bit floating-point number is generated between 0 and 1.
Greater than or equal to zero, and less than one. I can talk about how floating
point numbers work if you want. This number is used to choose one out of four
possible rewards, numbered 0 to 3. If the random value is less than 0.4, the
reward is set to 0. Otherwise if it is less than 0.7, the reward is set to 1.
Otherwise if it is less than 0.9, it is set to 2. Otherwise, it is set to 3.
  0.0 - 0.4: 0 (green rupee)
  0.4 - 0.7: 1 (blue rupee)
  0.7 - 0.9: 2 (red rupee)
  0.9 - 1.0: 3 (purple rupee)
So the probabilities for each reward is 40%, 30%, 20%, and 10% respectively.

Next, the game checks how many times the randomly selected reward has been
awarded already. Each possible reward has a max number of times it can be
awarded.
  0 (green rupee): 8
  1 (blue rupee): 4
  2 (red rupee): 2
  3 (purple rupee): 1
If the randomized reward is not "saturated", the reward selection process
completes and the corresponding reward counter is incremented. If the randomized
reward is saturated, the random value is discarded and the selection process
continues to "phase two". At this point, each of the four possible rewards is
tested in order lowest to highest. When a reward is encountered that is not
saturated, that reward is selected and its counter is incremented. In other
words, the game chooses the worst possible reward that is left to give. If there
are no rewards left to give (all rewards are saturated), phase two fails, and
the selection process moves on to the final phase. That is where the "cycle
reset" happens, where all reward counters are reset to zero. But, instead of
starting the selection process over for this dig, at this point the game simply
selects reward 0 (green rupee). You'd think the first attempt in each 15 attempt
cycle would have an equal reward probability distribution, but actually, on
every 15th attempt starting on attempt 16, you're guaranteed to receive a green
rupee.

So, that's the reward selection process. The heart piece is not actually part of
the selection process itself. When the reward has been selected, the game checks
if the selected reward is 3 (purple rupee). If it is, and if the Dampé HP flag
is not set, the game sets the reward to 4 (heart piece), and sets the Dampé HP
flag. So for the purpose of reward selection, the purple rupee and the heart
piece are identical.

Alright, that's it for dampe I think. Now, on to the RNG.

OoT uses a very common type of RNG called a Linear Congruential Generator (LCG).
An RNG, as the name suggests, is just a thing that produces random numbers.
LCG's are common because they're fast, easy to implement, and produce pretty
good randomness, certainly good enough for videogames. An LCG has an internal
state, which consists of just a single number, which is the last number that was
produced in the random number sequence. Whenever the game needs some randomness,
it asks the RNG to produce the next number in the sequence, and then uses that
number to determine the outcome of some event, or to set some variable. The LCG
produces the next number in the sequence with a simple formula. I don't know how
much you care about the details and mathematics behind the RNG, but here's the
formula;
  (x * a + c) % m
x is the previous number in the sequence. a, c, m are some predetermined
constants, and % is the modulo operator (division remainder).

OoT's rng uses these constants;
  a = 1664525
  c = 1013904223
  m = 4294967296
You want your constants to satisfy certain conditions if you care about the
strength of your RNG. But if you just want some numbers that look random enough,
the choice of constants isn't that important. These particular constants come
from a 1986 book called Numerical Recipes. This m was chosen because it is the
numerical limit of a 32-bit value. As such, the modular arithmetic is implicit
in the way the cpu does its computations (if you increment a 32-bit number past
4294967295 it rolls over to zero). The formula can thus be simplified to
  x <- x * 1664525 + 1013904223,
And that's really all that the RNG does.

Now, obviously there's nothing random about this (which is why it's called a
pseudo-random number generator, it's not actually random). For any given x in
the sequence, the next x will always be the same. If you know the starting x,
any number further down the sequence is dead simple to predict. What's not so
easy to predict is the starting value of x, the seed. Assigning a starting value
of x is known as seeding, and this is done at every scene load (i.e. after
entering a new scene, voiding out, etc). The LCG is seeded with the CPU counter.
The CPU counter is simply a 32-bit number in the CPU that counts up at a
constant rate of 46875000 ticks per second. When it reaches its numerical limit,
it rolls over to zero and starts over. This happens roughly every 91.63 seconds.

Now, in order to predict the value of the RNG, you must know when the seeding
happened, to a precision of about 20 nanoseconds (in order to know what the
value of the CPU counter was at the time), and you must know exactly how many
times the RNG sequence has advanced since then. I'll stop here for now, let me
know if there's anything you want me to clarify or elaborate on, or if there's
something else in particular you want to know.

Addendum; Randomization of floating-point numbers.
The LCG produces 32-bit integers, but Dampé uses a floating-point number to
choose a reward. For this purpose, the LCG is not used directly, but instead a
different function which transforms a random integer from the LCG into a
floating-point number.

The floating-point random number function calls the LCG to produce a random
integer number. The lower 23 bits of this number are put in the significand of a
floating point number with an exponent of 0, and the rest are thrown away. The
resulting number is in the range 1 <= x < 2. One is subtracted from the number
to put it in the range 0 <= x < 1, and then it is returned to the user. It is
common practice for the user to multiply the number by n to produce a number in
the range 0 <= x < n, where n is the desired range, but Dampé does not do this
because the number is already in the desired range.

The exponent is not randomized, because the distribution of the resulting
numbers would not be uniform. If a random exponent in the range (-128) - (-1)
were used, the number would have a 1/128 chance of being in the range 0.5 - 1,
and a 127/128 chance of being in the range 0 - 0.5. Using an exponent of 0 and
then subtracting 1 is the easiest way of producing a uniform distribution with a
range of 1.