Random Numbers, Blue Noise vs White Noise

[RevEng]

 

Often random numbers are referred to as "noise", and sometimes we attach colors to refer to the different characteristics of that noise. 

 

I recently watched a very good video that covered the usefulness of blue noise in modern game dev. One of the relevant bits for us was that blue noise is a source of aesthetically pleasing random numbers. Most random noise sources, including our better LFSRs, have white noise characteristics. Humans tend to perceive white noise distribution as "clumpy", meaning that sometimes you get a run of neighbouring random values. This likely isn't desirable if you're using random numbers for enemy positions, loot drops, etc.

 

The traditional algorithms for generating blue noise from white noise involve generating a bunch of random values, and massaging the number distribution. That's approach isn't suitable for our small machines, so I came up with an alternative method of bluing white noise that's super-cheap and surprisingly effective. The comparison spectral analysis charts in that article were produced using the  bB/7800basic 16-bit LFSR as the random source.

 

Hopefully someone finds all of this interesting, if not useful.

[+Karl G]

This is pretty cool! I need a bit of help understanding your pseudocode, though:

 

	A=RAND ; any masking or range-reduction needs to be done here, or else
	B=RAND ; it will reintroduce clumpiness into the value distribution
	if ABS(B-C) > ABS(A-C) then A=B
	C=(C+A)/2 ; exponentially decaying running average
	; "A" is holding your next bluish noise value

Would "RAND" here be our call to the LFSR or whatever random generator so that A and B hold different randomly-generated values? If so, it doesn't appear that there's any saved state in the function for it to keep track of prior random values?

[RevEng]

53 minutes ago, Karl G said:

This is pretty cool! I need a bit of help understanding your pseudocode, though:

The assignments were meant to black box the random function, since the algorithm works with LFSR, Standard C library random calls, or any other white noise source. I'll change the pseudocode to a function call looking thing to make that point clearer. (A=GetRandom(),  B=GetRandom() )

 

[edit - done]

[+Karl G]

That's what I figured, but I somehow missed that C would end up keeping its state. So it sounds like only one new persistent byte would be needed to blue the randomization, in addition to what is needed for the random function itself. Pretty cool! 

[RevEng]

Yep, you got it - just the one additional persistent byte is needed.

[Eagle]

FYI,

SN² cart has Random Number Generator at address $43c/$43d (57MHz clock)

[+Karl G]

Just for fun, I made a bin to demonstrate the difference between the two algorithms with random audio output. Press fire to switch which random number generator that is in use, with the background color matching (regular rand having a white background, and "blue rand" having a blue background). My ear can't really hear the difference; probably the sounds change too quickly to notice any patterns. If nothing else, it shows a 7800basic implementation of this algorithm, however.

 

I may try to maybe a visual demo that may make the differences more obvious.

 

bluewhite.78b

 

[RevEng]

Yeah, it's a bit hard to tell. I want to say the blue is slightly less squiggly, but I don't know if that's just because I expect it to be so. The power of suggestion is pretty strong.

 

The algorithm definitely produces bluish sounding noise when directly played as sample data, with characteristic boosted highs, compared to white. I just think there are some areas where people aren't great at detecting those clumps or runs of numbers.

[+Karl G]

I made a visual version with two side-by-side 16x16 grids with fading squares. It's still difficult for me to get a sense of the difference in random distribution, but if nothing else, it looks cool, and could make for a good screensaver.  

 

 

bluewhite2.zip

[AtomicFear]

 

[+saxmeister]

Random number systems have always fascinated me, and I'm always looking for better options on these limited 8-bit systems. Thanks!!

[Synthpopalooza]

Correct me if I'm wrong, but wonder if POKEY's random number generator (at POKEYADDR+$0A) might come in useful.  It repeats a sequence every 131,000 cycles, or something on the order of 500 if 9-bit poly is selected.

[RevEng]

Pokey's RNG is a source of white noise and slightly cheaper than the 16-bit LFSRs we typically use, but other than that I don't see an immediate use here.