Random number generation on a VIC

Basic and Machine Language

Moderator: Moderators

Post Reply
User avatar
Victragic
Frogger '07
Posts: 605
Joined: Tue Nov 14, 2006 5:56 pm
Location: South Australia

Random number generation on a VIC

Post by Victragic »

Hi,

apologies if this has been raised before...

I'm looking for a quick way to fill the screen with random characters between a certain limit.. say 0-7..

I find I can create 'randomness' if I slow things down and generate a number based on the Raster beam location, but surely there's a quicker and easier way? What is the internal random function RND based on?

If someone can help out, I'd be mighty obliged

-Glen
3^4 is 81.0000001
User avatar
Mike
Herr VC
Posts: 4901
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Re: Random number generation on a VIC

Post by Mike »

Victragic wrote:What is the internal random function RND based on?
RND(0) uses TI, RND(1) is based on a linear-congruential generator (seeded with RND(-x)). However, Commodore tried to "improve" upon that, by swapping some bytes, and thus broke the RND() function. It already loops after ~60000 calls, even though it would loop only after 4 billion numbers if it were not broken.
I'm looking for a quick way to fill the screen with random characters between a certain limit.. say 0-7.. [...] generate a number based on the Raster beam location, but surely there's a quicker and easier way?
In ML, you might try a linear-feedback-shift generator, something like:

Code: Select all

LSR $FA
ROR $FB
BCC skip
LDA $FA
EOR #$AA  ; most significant bit *must* be set
STA $FA
LDA $FB
EOR #$2B  ; least significant bit should be set
STA $FB
.skip
It gives single pseudo-random bits in the C flag, which you can rotate into another value. Use a non-0 value to seed.

Greetings,

Michael
Bacon
for breakfast
Posts: 578
Joined: Mon Apr 19, 2004 8:07 am

Post by Bacon »

The Fridge at Stephen L. Judd's ffd2.com site has some good stuff, like this random routine. And this.
Bacon
-------------------------------------------------------
Das rubbernecken Sichtseeren keepen das cotton-pickenen Hands in die Pockets muss; relaxen und watschen die Blinkenlichten.
User avatar
Victragic
Frogger '07
Posts: 605
Joined: Tue Nov 14, 2006 5:56 pm
Location: South Australia

Post by Victragic »

Very cool, that's exactly what I needed..
3^4 is 81.0000001
User avatar
nbla000
Salmon Run
Posts: 2582
Joined: Thu Oct 13, 2005 8:58 am
Location: Italy

Post by nbla000 »

Take a look to this old thread too.

I've used Carlsson/Nippur72 solutions for my works, the last was a random game selection inside the Mega-Cart Menu.
Mega-Cart: the cartridge you plug in once and for all.
User avatar
Jeff-20
Denial Founder
Posts: 5761
Joined: Wed Dec 31, 1969 6:00 pm

Post by Jeff-20 »

A random game is a great idea! It's like a Vic iPod. "Shuffle Games"
High Scores, Links, and Jeff's Basic Games page.
User avatar
Victragic
Frogger '07
Posts: 605
Joined: Tue Nov 14, 2006 5:56 pm
Location: South Australia

Post by Victragic »

Jeff-20 wrote:A random game is a great idea! It's like a Vic iPod. "Shuffle Games"
I had an MP3 player that couldn't manage to randomly shuffle the tunes -- selecting 'Random' made them play out of order, but it was always the same sequence..

-Good old Taiwanese knockoffs..
3^4 is 81.0000001
User avatar
Jeff-20
Denial Founder
Posts: 5761
Joined: Wed Dec 31, 1969 6:00 pm

Post by Jeff-20 »

I once had an MP3 player with a "Random" mode and no Shuffle mode. This meant that the songs could be played in any order, but it could play the same song two or three times in a row and never get to another song for days. :( I hated that.
High Scores, Links, and Jeff's Basic Games page.
carlsson
Class of '6502
Posts: 5516
Joined: Wed Mar 10, 2004 1:41 am

Post by carlsson »

Yep, I call the broken ROM routine for a random number, but implementing your own small integer RNG seems like a better approach!
Anders Carlsson

Image Image Image Image Image
WillKemp
Vic 20 Drifter
Posts: 25
Joined: Thu Dec 27, 2007 4:19 pm

Post by WillKemp »

This thread's a bit old, but i thought i'd add a comment from what i've rediscovered disassembling River Rescue (which i wrote 25 years ago).

If there's no human intervention, random number generation is fairly tricky, but once human input comes into it, it becomes quite easy, i think.

After a bit of experimenting (in the 80s), the way i implemented a random number generator was with three counters - one incremented every time the NMI handler was called, one incremented by the IRQ handler, and one which was incremented every time round the main control loop.

The random number generator takes the raster value and XORs it with each of those counters, one after the other. The result's returned as the "random" number.

That random number generator is used in the intro routine and in demo mode - but it's certainly not very random in the intro or the first run of the demo mode. In fact, if it's allowed to run into the demo mode after start up, it repeats the same pattern each time. I'm using Vice, so the raster scan timing's probably rock solid, but the raster timing of the Vic hardware might be a different matter altogether. Athough i guess the timing of everything would fluctuate together. However, i can't remember it being so predictable in the pre-play state when i wrote it.

As soon as you hit a key though, it starts to become a lot more random. That's because a fraction of a second difference in the time you hit the start key, or move the joystick, press the fire button, etc, makes a significant difference to the generated random number.

It's pretty random, i think, but it must respond to the way it's played - in some intangible way - i reckon!
User avatar
Kweepa
Vic 20 Scientist
Posts: 1316
Joined: Fri Jan 04, 2008 5:11 pm
Location: Austin, Texas
Occupation: Game maker

Post by Kweepa »

Bacon wrote:The Fridge at Stephen L. Judd's ffd2.com site has some good stuff, like this random routine.
I found a bug in the LCG in rand1.s (by comparing with the output from a C version): the carry bit should be cleared before adding $3611. So the code should be:

Code: Select all

GETRAND                   
         LDA RANDOM+1     
         STA TEMP1        
         LDA RANDOM       
         ASL              
         ROL TEMP1        
         ASL              
         ROL TEMP1        
         CLC              
         ADC RANDOM       
         PHA              
         LDA TEMP1        
         ADC RANDOM+1     
         STA RANDOM+1     
         PLA              
         CLC             ; added this instruction - kweepa
         ADC #$11         
         STA RANDOM       
         LDA RANDOM+1     
         ADC #$36         
         STA RANDOM+1     
         RTS 
This should make the generator cycle through all 65536 values without repeats. Sorry about adding a byte!

[EDIT]
I ran some tests on the old code vs. the new code using "ent" to ensure correct behaviour. For the statistical tests, I used the top 8 bits.

Code: Select all

TEST                  NEW       OLD
Entropy              8.00      6.35  bits per byte - good random # generator should be 8
ChiSquare Dist       0.00      2.36  value - good random # generator should be 0
ChiSquare rand      50.00      0.96  % - good random # generator should be 50
Mean               127.50    124.78  good random # generator should be 127.5
Monte Carlo pi       3.13      3.12  good random # generator will approach 3.14 slowly
Serial correlation   0.00     -0.03  good random # generator will be 0
I also checked for premature looping. The new code looped after 65536 numbers as expected. The old code when seeded with 0 looped after 358 numbers to the 263rd number and repeated this 95 number sequence.
carlsson
Class of '6502
Posts: 5516
Joined: Wed Mar 10, 2004 1:41 am

Post by carlsson »

Nice spotted! Did you message Steve, in case he still maintains The Fridge actively?
Anders Carlsson

Image Image Image Image Image
User avatar
Kweepa
Vic 20 Scientist
Posts: 1316
Joined: Fri Jan 04, 2008 5:11 pm
Location: Austin, Texas
Occupation: Game maker

Post by Kweepa »

My randomly wandering creatures were behaving distinctly non-randomly, so it was easy to see :)

It doesn't look like he's updated his website in a couple of years, but I'll send him an email.
Post Reply