Random numbers generation

[Shiru]

What source can be used as initial state for pseudo-random generator on SMD (to make generator produce different sequences at each power-up)?

[ob1]

wait for an input ?
eg : print "press an key to continue" and the time elapsed from the power on to any key pressed is your seed.

[TmEE co.(TM)]

I've used mixture of default seed(usually my phone number ) and HBL counter... always different results.

[Shiru]

wait for an input ?

Thanks for reminder, I knew this method, but completely forgot about it.

I've used mixture of default seed(usually my phone number ) and HBL counter... always different results.

Do you read HBL before setting up video mode? I.e., is that counter resets after mode change or not?

On Z80-based systems I used register R (memory refresh counter), but I thought it will be too complex for SMD, so I asked here. HBL counter seems to be enough.

[Eke]

I can think of 2 games (X-Men 2 & Eternal Champons) that read HV counter to display a random character at power-up

on emulators, since VDP and 68k executions are generally synchronized, this is generally not working properly, the same counter value being always returned at a given CPU cycle

[TulioAdriano]

Regarding to X-Men, when you power up the character is always the same. Only when you hit Reset the character is changed. This is a question I made for Stef years ago... I said there was a timer problem when reseting the emulator but he explained that MD has no timer... anyway... Because emulators usually have the "hard reset" they always return the same character. Only after they implement the soft reset, we could start having the proper reset behaviour on Mega Drive. Obviously because when you reset MD those counters are not reset.

[Eke]

That's right, on a soft reset, the VDP and the main RAM are not reseted ...

I wonder what a real soft-reset precisely do: is it only a simple 68000 reset ? Maybe it also resets the Z80/YM2612 or only the Zbus arbitration logic ?

[TmEE co.(TM)]

soft reset resets only 68K, Z80 and YM2612 (and PSG I think, though VDP is not reset)... In CA when you hit reset, you don't have to watch SEGA and TµEE and other screens... goes straight to intro screen, BUT well, SRAMs keep their data to some extent even after power off (for a few minutes), so you'll not see the screens after a quick power off...

[Chilly Willy]

Well, according to the schematics, the reset switch goes to the control chip, which then generates a reset signal to the 68000, the VDP, and Z80/YM2612. The Z80 and YM2612 use the same reset line, so anytime the Z80 is reset, so is the YM2612.

[Stef]

On real hardware, taking the V or H counter value before any synchronisation operation (as waiting for V int) is ok to get a random number generator as the V/H counter never starts at the same value.
Emulator doesn't care about that feature so it just doesn't work on them...
But still the best "randomiser" is human, waiting for an input (as ob1 said) is a good solution then

[Shiru]

But still the best "randomiser" is human, waiting for an input (as ob1 said) is a good solution then ;)

Can't say it best because it has two flaws. Small one: it needs human to work (unacceptable if random needs before any input, needed rarely). Bigger one: if human hold key(s) from power-up, he be able to always get same random sequences. It good method for most cases though.

Generally, emulators must care about random V/H counters state at power-up, as well as about garbage in RAM and other things. They doesn't care just because all (most) of known games works fine without that anyway.

[KanedaFr]

Bigger one: if human hold key(s) from power-up, he be able to always get same random sequences. It good method for most cases though.

unless you check it on keyup not keydown
hehe!

I fought a long time to find "the best randomizer for Genny" and finally found the human factor's the best...mainly because I wanted my works to be playable on emulators also

[Shiru]

unless you check it on keyup not keydown ;)
hehe!

Some radioactive mutants may release key on exact frame then;) OK, that better idea.

I fought a long time to find "the best randomizer for Genny" and finally found the human factor's the best...mainly because I wanted my works to be playable on emulators also

How about random algorithms, which one you found most suitable? I though about these two:

Mitchell-Moore: X[n]=(X[n-24]+X[n-55]) mod m (needs buffer to work)

Don't know name: Rand=Rand*N+M, where N and M some constant values (needs multiply)

[8bitwizard]

What source can be used as initial state for pseudo-random generator on SMD (to make generator produce different sequences at each power-up)?

Other than not re-initializing the seed after reset, there really isn't any way. The circuitry is the same every time, with esentially no non-determinstic parts. Even the RAM can be counted on to start up mostly the same on power-up, though I suppose a CRC or checksum of RAM at power-on could get you a little randomness.

But if there is user interaction involved, you can use the fractional time between user inputs as a source of randomness. The simplest way is to simply call your random number generator on every Vsync interrupt, or use the vsync counter to randomize your seed.

Code: Select all

RndSeed	DS	4		; random number seed

. . .

	BSR	Randomize		; initialize random number generator

. . .

;-----------------------------------------------------------------------
;	_Random from Mac Plus, returns a 16-bit random number
;
;	EXIT:	D0.W = random number 0..65535
;
;	* the use of the constant 16807 means this is a
;	  linear congruential generator (seed * 16807 mod (2^31 - 1))
;	* note that the seed must be in the range [1 .. 2^31-1] !!!
;	* also note that 2^31-1 is a Mersenne prime
;	* for more information, google for: 16807 random
;	* this page has a lot of info: http://www.firstpr.com.au/dsp/rand31/
;-----------------------------------------------------------------------

Random
	MOVEM.L	D1/D2,-(A7)

	; this multiplies the 32-bit seed by 16807
	MOVE.W  #16807,D0	; D0,D2 = multiplication constant
	MOVE.W  D0,D2
	MULU    RndSeed+2,D0	; multiply low word
	MOVE.L  D0,D1		; D1 = high word of product
	CLR.W   D1
	SWAP    D1
	MULU    RndSeed,D2	; multiply high word
	ADD.L   D1,D2		; add high of first multiply to result of second multiply

	; this does the mod (2^31-1)
	MOVE.L  D2,D1		; save in both D1 and D2
	ADD.L   D1,D1		; multiply high word of result by 2
	CLR.W   D1
	SWAP    D1
	ANDI.L  #$0000FFFF,D0
	SUBI.L  #$7FFFFFFF,D0	; =2^31-1
	ANDI.L  #$00007FFF,D2
	SWAP    D2
	ADD.L   D1,D2
	ADD.L   D2,D0
	BPL.B   .10		; add 2^31-1 once more if bit 31 is set
	ADDI.L  #$7FFFFFFF,D0	; =2^31-1
.10
	MOVE.L  D0,RndSeed	; save result as new random number seed
	MOVEM.L	(A7)+,D1/D2
	RTS

;-----------------------------------------------------------------------
;	Generate a new random number seed using the current frame counter
;-----------------------------------------------------------------------

Randomize
	MOVE.L	RndSeed,D0	; start with previous random seed
	MOVE.L	VTimer,D1	; XOR with current frame counter
	EOR	D1,D0
	BCLR	#31,D0		; clear high bit to ensure <= 2^31-1
	BNE.S	.10
	ADDQ.L	#1,D0		; don't allow a seed of zero
.10
	MOVE.L	D0,RndSeed	; save new seed
	ADDQ.L	#1,D0		; see if it was == 2^31-1
	BPL.S	.20
	SUBQ.L	#1,RndSeed	; don't allow a seed of 2^31-1
.20
	RTS

[Shiru]

8bitwizard, I not understand you.

Other than not re-initializing the seed after reset, there really isn't any way.

There is ways, TmEE and I already mentioned two of them (HBL counter, register R of Z80).

The circuitry is the same every time, with esentially no non-determinstic parts.

States of logic elements like triggers on power-up usually is non-determined.

Even the RAM can be counted on to start up mostly the same on power-up

It must be different, although garbage pattern always similar (but not exact). I'm not take that way because counting of CRC is long and more complex than other possible ways.

The simplest way is to simply call your random number generator on every Vsync interrupt

Why I must call random generator every VSync? I need only one random value at start of whole program to use it as initial state of RNG. Generator then called each time when I need random number, and that can be many times per frame.

Thanks anyway, at least I now know about Park-Miller algorithm which used in code example which you gave.