Do emulators nullify randomization routines?

[accousticguitar]

Since they often get their seed from the 2600 hardware chips.

[+batari]

Since they often get their seed from the 2600 hardware chips.

I don't know what z26 does. But Stella works in some cases and not in others. I've tried to read INTIM on startup and it doesn't get a random value in Stella. On real hardware, it seems to work, however.

 

But Berzerk (which also reads the RIOT on startup) works in Stella.

[accousticguitar]

Sounds like I will have to try it out on real hardware to know for sure if it works or not. Thanks for the reply.

[TROGDOR]

The best way I've found to keep a random number generator truly random (or at least make it non-deterministic from the perspective of the user) is to incorporate user input as a seed.

 

For example, in Hunt the Wumpus, I pull a bit out of the random number generator every frame, whether I need it or not. This changes the state of the random number buffer every frame. Then, when the user finally presses the button to start the first game, the game will essentially be seeded by how long the user took to start the game from when the system powered up. So if the user waited 600 frames to start the game, the maze will be completely different than if the user waited 601 frames to start the game. If I didn't do this, the first game would always have the same "random" maze.

 

This has the added benefit that the game will behave exactly the same on an emulator as it does on the real hardware, since nothing in the code is dependent on the initial state of the hardware.

 

The user could potentially cheat this system by holding down the button to start the game immediately on the first frame as the game starts up, but even that can be prevented by only allowing the game to start on the transition of the joystick button (where the previous frame the button is up and the current frame the button is down), rather than just checking if the button is down.

Edited January 25, 2008 by TROGDOR

[supercat]

The best way I've found to keep a random number generator truly random (or at least make it non-deterministic from the perspective of the user) is to incorporate user input as a seed.

 

On a real system, it's possible to read a joystick button with fine timing granularity if one has time within the kernel. On Z26, however, it seems the button is only sampled once per emulated frame.

[TROGDOR]

The best way I've found to keep a random number generator truly random (or at least make it non-deterministic from the perspective of the user) is to incorporate user input as a seed.

 

On a real system, it's possible to read a joystick button with fine timing granularity if one has time within the kernel. On Z26, however, it seems the button is only sampled once per emulated frame.

This seeding technique doesn't require intra-frame joystick reading granularity. Joystick polling is done normally, once per frame. The main idea is that a random number of frames will pass before the user starts the game, so it's a great way to seed the random number generator. 60Hz granularity is fine enough that a human won't be able to reliably "pick" a particular starting frame.

Edited January 25, 2008 by TROGDOR

[supercat]

60Hz granularity is fine enough that a human won't be able to reliably "pick" a particular starting frame.

 

If the person hits the start button sometime between 1/10 and 1/5 second after launching the game, there are only going to be about six different starting values with granularity 1/60. On a real system, sampling at the beginning and end of each displayed frame will double the number of possible starting mazes.

[TROGDOR]

60Hz granularity is fine enough that a human won't be able to reliably "pick" a particular starting frame.

 

If the person hits the start button sometime between 1/10 and 1/5 second after launching the game, there are only going to be about six different starting values with granularity 1/60. On a real system, sampling at the beginning and end of each displayed frame will double the number of possible starting mazes.

That's assuming they only want to play level 1. It takes a couple seconds to select any of the other levels. If someone really wants to twitch and start the game on level 1 in the first 1/10 of a second, I'm not going to stop them.

 

Under normal use, there will be a very wide window of start times, depending on the mood of the player. Sometimes I want to play right when I start up, in the first few seconds. Usually though, I will languidly start up the system and poke around on the title screen, taking anywhere from 5 to 20 seconds to start a game, which provides hundreds of possible starting games.

 

Also, this issue only applies to the first maze on the first game after power up. All subsequent mazes will have a completely random seed.

 

I tested this on Hunt the Wumpus, and I can get the same maze every time on level 1 if I hold down the button when the game starts up. I'll have to add the previously mentioned transition check to the button to prevent immediate start up. (But I'm not going to do that now. I'm still working on Stellar Fortress. Honest!)

Edited January 25, 2008 by TROGDOR

[Rybags]

You could also use incorporate "button up" delay into a seed.

 

Then, the chances of duplicate seeding would be reduced even further.

[accousticguitar]

The best way I've found to keep a random number generator truly random (or at least make it non-deterministic from the perspective of the user) is to incorporate user input as a seed.

 

For example, in Hunt the Wumpus, I pull a bit out of the random number generator every frame, whether I need it or not. This changes the state of the random number buffer every frame. Then, when the user finally presses the button to start the first game, the game will essentially be seeded by how long the user took to start the game from when the system powered up. So if the user waited 600 frames to start the game, the maze will be completely different than if the user waited 601 frames to start the game. If I didn't do this, the first game would always have the same "random" maze.

 

This has the added benefit that the game will behave exactly the same on an emulator as it does on the real hardware, since nothing in the code is dependent on the initial state of the hardware.

How do you "pull a bit out of the random number generator?" Could you could post some example code?

[TROGDOR]

How do you "pull a bit out of the random number generator?" Could you could post some example code?

Here's the subroutine I use to generate random numbers:

 

RandomBits

LDA Rand4
ASL
ASL
ASL
EOR Rand4		;new bit is now in bit 6 of A
ASL
ASL			;new bit is now in carry
ROL Rand1 		;shift new bit into bit 0 of register; bit 7 goes into carry
ROL Rand2 		;shift old bit 7 into bit 8, etc.
ROL Rand3
ROL Rand4

DEX
BNE RandomBits
LDA Rand1
RTS

This isn't the most efficient random number generator. A 3, or possibly 2 byte buffer would be faster and use less RAM, and I will likely be switching to a smaller buffer. But this will work as an example.

 

The subroutine is called as follows:

 

LDX #6

JSR RandomBits

 

This will return a 6 bit random number in A. (The 2 high bits can be masked off.)

 

By pulling a bit, I mean running:

 

LDX #1

JSR RandomBits

 

This modifies the contents of the random number generator. If I do this every frame, it makes time a factor for the state of the random number generator. This has worked well as a hardware-independent seeding system. In all the play testing I've done on my games, I haven't had a problem with repetitious patterns showing up.

 

As stated in the previous discussion, the only concern is preventing the player from starting the game on the first frame after power up. This can be solved by forcing the user to make a full button press (or reset switch press), transitioning down and then back up, before the game will start.

Edited January 27, 2008 by TROGDOR

[supercat]

I like to use, (posting from memory)

  lda rand1
 asl
 ror rand2
 bcc noEor1
 eor #$DB
noEor1:
 asl
 ror rand2
 bcc noEor2
 eor #$DB
noEor2:
 sta rand1
 eor rand2

This requires that rand1 and rand2 not both be zero (if they are, it will always return zero). The pattern it produces will repeat once every 65,535 calls. During that time, pairs of consecutive calls will yield all pairs of values 0-255 except for (0,0).

 

Note that having rand1 shift left while rand2 shifts right, and eor'ing them together, yields much better results than would be obtained if they both shifted the same direction. In that case, any given return value could only be followed by one of four other values.

[accousticguitar]

Trogdor, are you using Rand1 as the seed for the randomizing routine when the button is pressed? And what is the X register doing? It doesn't seem like it needs to be involved.

 

Supercat, should I load a nonzero number into Rand1 (or Rand2) at the start of the game to make sure both numbers are not zero?

 

Thanks guys for the info. I think I might understand enough to try it out.

[TROGDOR]

You could also use incorporate "button up" delay into a seed.

 

Then, the chances of duplicate seeding would be reduced even further.

Yes, this will help scramble the random buffer even more. Any user input, including joystick presses and control switch presses, both on the downward and upward transitions, can be used to add a timed factor to the random number buffer. The extent that you need to scramble the random numbers will depend on how the random numbers are used in your game. For maze games and card games it's particularly important to not allow a predictable pattern in the buffer.

Edited January 27, 2008 by TROGDOR

[TROGDOR]

Trogdor, are you using Rand1 as the seed for the randomizing routine when the button is pressed? And what is the X register doing? It doesn't seem like it needs to be involved.

 

Supercat, should I load a nonzero number into Rand1 (or Rand2) at the start of the game to make sure both numbers are not zero?

 

Thanks guys for the info. I think I might understand enough to try it out.

Here's the seed I use at power up:

 

;Initialize the random number generator.

 

LDA #$D6

STA Rand1

STA Rand2

STA Rand3

STA Rand4

 

Any seed can be used, as long as it's not all zeros. As supercat mentioned, all zeros will lock up the generator, producing infinite zeros.

 

Technically, I'm not reseeding the number generator. But since the state of the random number generator is constantly changing, the time that the game is started will affect the set of random numbers generated. Another possible technique is to grab the frame byte (most games have a byte that keeps track of the frame count), and drop that value into one of the bytes of the random number generator. As long as the number is not zero.

 

The X in my routine is the number of bits desired. If you want a byte (i.e. 8 bits), you have to set X to 8. With each pass in RandomBits, (where X is used for looping,) a new "random" bit is generated and shifted into the random number buffer. So 8 passes will shift in 8 new bits. This is slow, but it is also genuinely random. If you only set X to 1 and then try to use the result in A as an entire byte, you'll be reusing 7 bits from the previous random number, which really isn't random.

 

Supercat, how do you handle this problem in your algorithm?

Edited January 27, 2008 by TROGDOR

[accousticguitar]

I see, it must have been too late for me to think last night. It cycles through until the X register is at 0. Here is the code for Adventure.

RandomizeLevel3:
   LDY	#RndNum		;For each of the eleven objects..			;2

RandomizeLevel3_2:
   LDA	LoCnt			 ;Get the low input counter as seed.		  ;3
   LSR					  ;											;2
   LSR					  ;											;2
   LSR					  ;Generate a psudo-random					 ;2
   LSR					  ;room number.								;2
   LSR					  ;											;2
   SEC					  ;											;2
   ADC	LoCnt			 ;Store the low input counter.				;3
   STA	LoCnt			 ;											;3
   AND	#RndMax		;Trim so represents a room value.			;2
   CMP	Loc_2,Y		;If it is less than the					  ;4
   BCC	RandomizeLevel3_2 ;lower bound for object then get another.	;2
   CMP	Loc_3,Y		;If it equals or is						  ;4
   BEQ	RandomizeLevel3_3 ;Less than the higher bound for object	;2
   BCS	RandomizeLevel3_2 ;Then continue (branch if higher)			;2
RandomizeLevel3_3:
   LDX	Loc_1,Y		;Get the dynamic data index for this object  ;4
   STA	VSYNC,X		;Store the new room value.				;4
   DEY					  ;											;2
   DEY					  ;Goto the next object.					;2
   DEY					  ;											;2
   BPL	RandomizeLevel3_2 ;Untill all done							 ;2
   RTS					  ;

And also

;Check for input.
CheckInput:
   INC	LoCnt			 ;Increment low count.						;5
   BNE	GetJoystick	;											;2
   INC	HiCnt			 ;Increment hight count if					;5
   BNE	GetJoystick	;	  needed.							;2
   LDA	#$80			  ;Wrap the high count (indicating			 ;2
   STA	HiCnt			 ;	  timeout) if needed.

I'm not sure how often it increments LoCnt though. If I wanted to incorporate your routine, I could just do something like this couldn't I?

DEX
BNE RandomBits
LDA Rand1
STA LoCnt
RTS

(Adding "STA LoCnt" at the end of the RandomBits routine.) Of course, I would have to make sure Rand1, Rand2, Rand3, and Rand4 had locations in RAM and then stick a JSR to RandomBits in one of the main game loops. I could do something similar with Supercat's routine too I think. The Missadventure Revised routine has been working okay, though sometimes when I first start the game I will get a familiar object placement pattern. I wonder if I will recognize patterns more and more as I get to know the game better. Of course, the bat moves things around, so sometimes it's hard to tell. Thanks for your input.

Edited January 27, 2008 by accousticguitar

[supercat]

Supercat, how do you handle this problem in your algorithm?

 

Returning the xor of the left-shifted and right-shifted halves of the generator will yield values that are essentially independent. Every return value can be generated 256 ways, except zero which can be generated 255. For example, a return value of $AA can result from rand1 holding $AA and rand2 holding $00, or rand1 holding $AB and rand2 holding $01, or rand1 holding $A8 and rand2 holding $02, etc. Each of those 256 (or 255) combinations of rand1 and rand2 will yield a different result on the next random call.

 

You'll notice my code invokes its generator function twice. The one reason I do this is to slightly mask the one bit of bad behavior in the generator, which occurs when it generates the sequence $01 $02 $04 $08 $10 $20 $40 $80 $40 $20 $10 $08 $04 $02 $01. Depending upon what the generator is used for, that could be a little bit ugly. Running through the sequence twice as fast makes it a little less ugly.