Language…
14 users online: Anas, Batata Douce, Darolac, DasFueller, eltiolavara9, Foxy_9000_, Gamet2004, Hammerer, jump_run_repeat, Mythundare,  Nanako, Necrotext, pzyko103, Rykon-V73 - Guests: 274 - Bots: 431
Users: 64,795 (2,377 active)
Latest user: mathew

Better Random Number Generator

SMW Patches → Better Random Number Generator

Submission Details

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

Screenshots

Comments (30)

crocodileman94 Link
While this patch did work at making vanilla sprites random, it caused the Masked Koopa boss sprite to only use a single attack over and over.
HammerBrother Link
Akaginite I know this is very late, but I deeply learned something of why this mistake occurred about the "Unequally appearance ratio" (as in, uneven distribution) when you convert a random integer range 0-255 to 0-max. When you take a random integer 0-255, multiply by max, divide by 256 and round (foor, ceiling, half up or down, etc.) this will result in having a range of inputs that results the same output. Each of these ranges must have equal or approximately equal lengths of ranges so that each input have even distribution. Thus the range sizes are the odds of them happening.

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:
Code
RandomNumberRange0_255: ConvertedRangeOutput (range size)
;Rand_Output = round(Random0_255 * Max / 255)
;round(Random0_255 * 5 / 255)
0-25: 0 (range size: 25)
26-77: 1 (range size: 51)
78-127: 2 (range size: 49)
128-179: 3 (range size: 51)
180-230: 4 (range size: 50)
230-255: 5 (range size: 25)

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:
Code
;Rand_Output = floor(Random0_255 * (Max+1) / 256)
;floor(Random0_255 * (5+1) / 256)
;Note: if you want max to not be included, then don't add max by 1
0-42: 0 (range size: 42)
43-85: 1 (range size: 42)
86-127: 2 (range size: 41)
128-170: 3 (range size: 42)
171-213: 4 (range size: 42)
214-255: 5 (range size: 41)

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:
Random number 0-255Output
00
12
24
......
253506
254508
255510


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.
 Erik Link
Tested with: Asar v1.71; SA-1 v1.32; Lunar Magic 3.04; bsnes-plus v073+3a
This patch is up to the standards and requires no remoderation.
john fortnite kennedy Link
Crashes on ZSNES. Works perfectly fine on any other emulator though.
HammerBrother Link
Thanks for updating the patch! I was worried that many spriters who make bosses couldn't use the good RNG due to the fact that the SA-1 patch modifies that as well as the RAM clearing routine.
HammerBrother From older version: Better Random Number Generator Link
I get how the ranged RNG works, because integer always truncate the value towards 0, add the fact that at user-defined max, (255*x)/256, would never land exactly at max (say 256), since it exploits the round-down. For example: a maximum of 4 would be (255*5)/256 gives 4.98046875, which truncates to 4, which is the intended maximum. The maximum in a fixed number of bits is 2n-1, while loading the higher bit/word (which is the same as LSR 8 or 16 times) divide by exactly 2n without the -1. The maximum and the division is really close to each other, therefore doing minimal impact to the result compare to my broken one.
Kiatus From older version: Better Random Number Generator Link
@bensalot see description
Bensalot From older version: Better Random Number Generator Link
I'm still really new to hacking. How do you get the custom range to apply to an SA1 rom? I keep getting error messages
HammerBrother From older version: Better Random Number Generator Link
Sorry about that.
Akaginite From older version: Better Random Number Generator Link
Thanks god Erik
HammerBrother From older version: Better Random Number Generator Link
Did i invade someone's else privacy about metioning someone's name?
 Erik From older version: Better Random Number Generator Link
horrable
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.
IanBoy From older version: Better Random Number Generator Link
I've lost the run to RNG dude, what!?
HammerBrother From older version: Better Random Number Generator Link
Dumb that nintendo cleared the RNG ram, which messes it up and not make it random.
HammerBrother From older version: Better Random Number Generator Link
@Akaginite

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.
Akaginite From older version: Better Random Number Generator Link
should remove sa-1 tag because this patch doesn't works on sa-1 rom.



... also please remove my name on authors.
HammerBrother From older version: Better Random Number Generator Link
Look at the gersion history included. It has better ranged RNG.
Klug From older version: Better Random Number Generator Link
What's the difference in this update?
HammerBrother From older version: Better Random Number Generator Link
Yep, my spelling is horrible.
 Erik From older version: Better Random Number Generator Link
horrable
HammerBrother From older version: Better Random Number Generator Link
@Akaginite

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).

Akaginite From older version: Better Random Number Generator Link
about RNG_Range.asm, I think your code has two problems...

-VEEEEEEEERRRRY SLOW
Your code require divide of 255, it is too slow. really too slow.
if calculated divide of 256, it can omitted.
Code
; int(rand*(max+1)/256)
RNG:	INC A
	BEQ .All
	STA $4202
	JSL $01ACF9
	STA $4203
	XBA : XBA : NOP		; Wait 8 cycles
	LDA $4217
	RTL

.All	JML $01ACF9


-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.
MV250 From older version: Better Random Number Generator Link
This patch is incompatible with the BRAM Plus Patch for whatever reason.
HammerBrother From older version: Better Random Number Generator Link
@anonimzwx

Quote
Result = MaxValue*Random/255


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)
Vitor Vilela From older version: Better Random Number Generator Link
LDA $2137 is the H/V counter LATCH. If you remove it the LDA $213C will generate null value instead.
anonimzwx From older version: Better Random Number Generator Link
Problems of rand.asm

-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

-
Code
Multiply:             ;\multiplication subroutine
        STA $04             ;|
    .Loop   LSR $02             ;
        BEQ .end            ;|
        BCC .Next           ;|
        CLC             ;|
        ADC $00             ;|
    .Next   ASL $00             ;
        BRA .Loop           ;|
    .end                    ;|
        CLC             ;|
        ADC $00             ;|
        SEC             ;|\remove 1-extra multiplication.
        SBC $04             ;//
        RTS


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
DiscoTheBat From older version: Better Random Number Generator Link
Well, looks a great addition to people who want to do a specific range for any desired number. I think the RNG_Range code could be improved but it is good and functional.

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.
Vitor Vilela From older version: Better Random Number Generator Link
It's used, for example, in the three question blocks bonus rooms. The '?' block that will contain the 1-up is determined by a random number generator.

It is also used to determine next boss move and/or where the boss will go, like lemmy/wendy in pipes.
MrMartley64 From older version: Better Random Number Generator Link
What would a number generator be doing in Smw? Can anyone show me?
yoshiatom From older version: Better Random Number Generator Link
Patch info: Requires Free Space: Yes

Description: "Requires no freespace"

Uh