Name: | Better Random Number Generator |
Author: | wiiqwertyuiop |
Added: | |
Version History: | View |
Tool: | Asar |
Requires Free Space: | No |
Bug Fix: | No |
Featured: | No |
Description: | This patch will replace SMW's RNG with a faster, shorter, and more random number generator. It will also let you use $148B and $148C as freeram. Requires no freespace. There are a few things different in this version: - Now fully works with the SA-1 after I was made aware the SA-1 has it's own latch counter (thanks Vitor Vilela) - I fixed it so the RNG values aren't cleared when you exit a level - I also made the outputs a bit more random Note: If using the SA-1, it won't work as well (won't be as random, but otherwise will be fine), in emulators that don't properly emulate the SA-1. |
Tags: | lorom random rng sa-1 |
Comments: | 30 (jump to comments) |
Download
3.89 KiB | 672 downloads
Comments (30)
When rounding half-up, creates this problem: The range of inputs for 0 and max are half because the range boundaries are positioned (by the rounding) so that the range of min and max get cut halfway. Using the same example (convert 0-255 to 0-5; ), this results:
The average odds of each output of 1-4 are averaging about 50 units (50.25 more precisely), for the min and max, that is 25. This is extremely biased, a non-uniform distribution. When using a floor function and dividing by 256 instead of 255, and have the input max added by 1, results in this:
Causes each range to have an average size of 42 (41.67 more precisely).
I also leaned that in a lot of programming languages, when a interval is expressed, it is a half-open interval, meaning a range that includes all numbers except the max. If you want 100 numbers starting at 0, then it shall be 0 ≤ X < 100, which is 0-99, not 0-100, that would be 101 values instead of 100. In javascript, arrays, string, when taking a slice or copy within, and substring, all have the "up to but not including".
Upon further inspection, I noticed that it is interpreted that the RNG ranges from 0 (inclusive) to 256 (exclusive), to be treated as a fraction - Random0_255 / 256 (a fixed point arithmetic with a scaling of 1/256), the equivalent to most floating point random number ranging between 0 (inclusive) and 1 (exclusive). As learned in JS, you multiply Random (0 ≤ Random > 1) by an integer to scale this number to be this size, from 0 to size-1.*
*But be careful not to scale it to a size bigger than 256 in this case, since there are only 256 possible values from Random, that means up to 256 outcomes, and also have an unexpected shorter range than it should've been. Example: scaling it to a range of, say 0-511 via multiplying by 512 (doubled size), will only produce 256 values, all being even numbers, and despite 511 is the max, 510 is the highest output value:
The same also applies with a 16-bit RNG range, but with a range of 0 (inclusive) 65536 to (exclusive), you can't have a scaled range greater than 65535, but very unlikely you would need that many outcomes.
This limitation of how many outcomes also applies even if this was done all in floating point, and that is depending on precision that determines how many representable values there are between 0 and 1, as well as if subnormal numbers are allowed or not, and the fact that representable values aren't evenly distributed, with numbers closer to 0 being more dense than numbers further away.
This patch is up to the standards and requires no remoderation.
Seems okay, however I made some modifications, namely changed ORA to AND, which should allow for lower ranges in some occassions too. Functionality wise it's okay and allows for making manipulation harder, however the only reason this is better than SMW's is because you'll still get a random value even when you enter a new level (the random seeds still get cleared in level load, but by using the latch/HV counters this really has no effect).
Removed Akaginite's name by request.
Oh, thanks for telling me that, I often don't look at the already filled entries. The custom range now works with SA-1. If you look in the sa-1 patch, there are multiplication registers you can replace the ppu.
... also please remove my name on authors.
I realized before I even saw your post, there is a flaw that it rounds 1/2 up, meaning that the chance of getting minimum or maximum will be halved, since non-zero and non-maximum numbers have a range from -0.5 to +0.4 (so if the result is 3, it ranges from 2.5 to 3.4), while:
*0 only have a range from 0.0 to 0.4.
*The maximum will have it from x to x-0.5 (example: if the max is 5, then the only possible range to get a 5 is 4.5 to 5.0 rather than 4.5 to 5.4).
-VEEEEEEEERRRRY SLOW
Your code require divide of 255, it is too slow. really too slow.
if calculated divide of 256, it can omitted.
-Unequally appearance ratio
Diagram link
Originally, your formula does not include maximum value. (0 <= rand < max)
so you has get the maximum value forcefully by doing multiplication of 256/255. (0 <= rand <= max)
then you did rounding a value. as a result, the maximum and minimum value appearance ratio became half of other values.
Diagram link
...
about Rand.asm
-Doesn't work on SA-1
This code requires access to PPU register, but SA-1 can't do it.
as a result, when called this routine by SA-1 side, it will return an invalid value.
-This is not better
this RNG is like a Hardware-RNG, it doesn't have reproducibility.
probably this RNG behavior is different in each emulator.
...
I tnink SMW's RNG is great, it has used two types RNG algorithm. (LFSR + LCG)
but those algorithm has weak point, so SMW has absorb it by combining them.
but random seed will be reset at Overworld loading. spoil it all.
Its a cross multiply to have a custom range rather than a base-2 maximum (maximum restricted by a power of 2; max is either 1, 3, 7, 15, 31, 63, 127, 255)
-LDA $2137 & LDA $213C at the start, the first LDA is useless.
-ORA $14 can destroy the normal distribution, must be replaced by EOR $14
-It is of 8bit vs original smw random that is of 16 bits.
-I am pretty sure that $213c have not normal distribution. Try with $210f
Problems of rng_range.asm
I undestand that you try to make something like Result = MaxValue*Random/255
-
I am pretty sure that this multiply routine doesn't work as you want.
-LDA $148D+!Base2 ;\Random number...
!Base2 doesn't exist on the .asm
EDIT: The multiply code looks wonky and the original RNG routine is 16-bit while this (and wii's) one is 8-bit, not a quirk but something to be noted on. Also, I believe that routine could be optimized by changing some ORAs to EORs and so on.
It is also used to determine next boss move and/or where the boss will go, like lemmy/wendy in pipes.
Description: "Requires no freespace"
Uh