Pseudorandom generation

Ask anything your want about Megadrive/Genesis programming.

Moderator: BigEvilCorporation

Zontar
Very interested
Posts: 55
Joined: Fri Oct 21, 2011 8:58 pm

Pseudorandom generation

Post by Zontar » Thu Nov 24, 2011 6:36 am

I'm currently in the process of writing a puzzle game for the Genesis.

The puzzle depends on a two-dimensional map in memory of values ranging from one to four (zero is a blank space.) There are no blanks in an initialization. When I initialize the game, I use a for loop that iterates through the map and places a value from one to four in each cell. If the chosen value is zero, it simply substitutes the arbitrary constant of 3.

The problem is, the random() function in SGDK appears to generate the same results with every call. I've tried two different emulators, which do give differing results, but the same results every time I reset the console. Is this to be expected?

Here is a screenshot of the game so far. It's nothing more than a simple test board. These same values appear on the board with every bootup in the respective emulators.


My main question is if I'm using the random() function properly or if there were something else I was supposed to do beforehand, or if this is expected behavior. If so, how could I make a small pseudorandom routine that yields varied values on every board refresh?

Here is the relevant piece of code:

Code: Select all

	
	int x;
	int y;
	int c;
	for (x = 0; x != BOARD_X; x++) {
		for (y = 0; y != BOARD_Y; y++) {
			c = random() % 4;
			if (c != 0) { board[x][y].id = c; } else { board[x][y].id = 3; }
			board[x][y].selected = 0;
		}
	}
Last edited by Zontar on Sun May 18, 2014 10:29 pm, edited 1 time in total.

Zontar
Very interested
Posts: 55
Joined: Fri Oct 21, 2011 8:58 pm

Post by Zontar » Thu Nov 24, 2011 6:41 am

I just realized I could do the non-zero generation much better by putting c equal to (random() % 4) + 1. :p

Other than that, I still have the pseudorandom issue.

Chilly Willy
Very interested
Posts: 2984
Joined: Fri Aug 17, 2007 9:33 pm

Post by Chilly Willy » Thu Nov 24, 2011 4:46 pm

There is a LOT of theory behind pseudo-random numbers. I suggest you start with the wikipedia page on them, then follow some of the links at the bottom of the wiki page.

Shiru
Very interested
Posts: 786
Joined: Sat Apr 07, 2007 3:11 am
Location: Russia, Moscow
Contact:

Post by Shiru » Thu Nov 24, 2011 6:25 pm

All the software random generators are pseudorandom, they give exactly the same sequence every time. It does not matter which algorithm you will use, you still will have the problem. To fix it you need to introduce a real random. The most common source for it is user input. For example, the time that is passed after turning the game on and pressing Start to begin the game. I.e. just call random (without using the result) in a loop that awaits a keypress on the title screen or somewhere like this.

Zontar
Very interested
Posts: 55
Joined: Fri Oct 21, 2011 8:58 pm

Post by Zontar » Thu Nov 24, 2011 7:29 pm

I got it. :D

The problem was right in front of me. u16 random() involves the use of the Genesis VDP's HVCounter...a value that was the exact same amount with every launch of my program. I didn't have a title screen, but rather it went directly to the game board.

I implemented a thus-far rudimentary title screen that prompts the user to press start, after which the HVCounter should be some real random value. The board works great now. :D

Stef
Very interested
Posts: 3131
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Post by Stef » Fri Nov 25, 2011 9:46 am

Actually the random() function will produce the same number series on emulator but not on the real hardware as the HV counter can start from anywhere (not 100% certain but some genesis hardware guru could probably confirm that).

Nemesis
Very interested
Posts: 791
Joined: Wed Nov 07, 2007 1:09 am
Location: Sydney, Australia

Post by Nemesis » Sun Nov 27, 2011 2:42 am

Yeah, I can confirm that. On the real hardware, the VDP starts up at a random position, so the HV counter could be used as an effective random seed, on the early Mega Drive models at least. I'm not sure about models with the TMSS bios though. If the bios uses a wait loop that's based on VINT, the bios could do a good job of de-randomizing the HV counter by the time your code runs. I haven't looked at the disassembly of the TMSS bios though, so I don't know if this is an issue.

Jorge Nuno
Very interested
Posts: 374
Joined: Mon Jun 11, 2007 3:09 am
Location: Azeitão, PT

Post by Jorge Nuno » Sun Nov 27, 2011 3:33 am

Take z80 RAM contents on power up and do a Shift/XOR on a couple of addresses... I doubt TMSS clears the ZRam, so that could be a good seed. Or take advantage from the user like the time it takes him to press, hold and release the start button 8)

TmEE co.(TM)
Very interested
Posts: 2440
Joined: Tue Dec 05, 2006 1:37 pm
Location: Estonia, Rapla City
Contact:

Post by TmEE co.(TM) » Sun Nov 27, 2011 9:17 am

Yea, Z80 RAM is not touched by TMSS. However HV counter still is viable randomizer seed in TMSS models, I have never had problems on those systems
Mida sa loed ? Nagunii aru ei saa ;)
http://www.tmeeco.eu
Files of all broken links and images of mine are found here : http://www.tmeeco.eu/FileDen

Fonzie
Genny lover
Posts: 323
Joined: Tue Aug 29, 2006 11:17 am
Contact:

Post by Fonzie » Mon Mar 26, 2012 8:20 am

One rule I learnt is to not make "random of a random", see.

I used to have :
1- A "precalculated" random numbers table (3 7 8 6 4 2 0 ....)
2- The initial pointer was set by timing user inputs (joypad delay to press start at titlescreen).
3- Everytime I wanted a random value, jump "randomely" (using some game code vars) in this table & read value...

Guess what... It got MORE random, and by far, if either dropped the step 1 (a random table) or step 3 (a random jump every read)...
Best way was to either use a linear table (1 2 3 4 5 6 7 8 9) OR just scan a table made of precalculated random numbers.

So my lame conclusion is, do not combine random thinking it would make things "more" random, its actually making things "less random" :P
This apply for cryptography as well, doh.

-------
Another point is... In games, true random is sometimes not wished at all. A true randomization can make same event happen X times in a row... But, if the player gets his ass kicked X times in a row, he gonna ask for a refund! You get the idea, its the art of making the player think its "random" while in your game code, its not :P

fdarkangel
Interested
Posts: 24
Joined: Sun Dec 17, 2006 8:28 pm
Location: Osaka, Japan

Post by fdarkangel » Mon Mar 26, 2012 12:12 pm

Fonzie wrote:One rule I learnt is to not make "random of a random", see.

I used to have :
1- A "precalculated" random numbers table (3 7 8 6 4 2 0 ....)
2- The initial pointer was set by timing user inputs (joypad delay to press start at titlescreen).
3- Everytime I wanted a random value, jump "randomely" (using some game code vars) in this table & read value...

Guess what... It got MORE random, and by far, if either dropped the step 1 (a random table) or step 3 (a random jump every read)...
Best way was to either use a linear table (1 2 3 4 5 6 7 8 9) OR just scan a table made of precalculated random numbers.

So my lame conclusion is, do not combine random thinking it would make things "more" random, its actually making things "less random" :P
This apply for cryptography as well, doh.

-------
Another point is... In games, true random is sometimes not wished at all. A true randomization can make same event happen X times in a row... But, if the player gets his ass kicked X times in a row, he gonna ask for a refund! You get the idea, its the art of making the player think its "random" while in your game code, its not :P
That reminds me of Knuth (The Art of Computer Programming, Vol II, Chapter 3.1):
The moral of this story is that random numbers should not be generated with a method chosen at random. Some theory should be used.
It's a classic, and lists several working examples.

If you don't want randomness (which is not the case in this thread), why use a random number generator (RNG) at all?
A RNG is normally a uniform one, meaning the chances of getting the same event decreases exponentially with X as (1/N)^X, where N is the number of possible distinct numbers the RNG can yield. You only need to worry about such a thing when both N and X of consideration are small (i.e., integers little bit bigger than 1), which is unlikely to be a realistic situation. But even in this case you can count the occurrences of the event manually, and check whether the threshold is reached each time.

fdarkangel
Interested
Posts: 24
Joined: Sun Dec 17, 2006 8:28 pm
Location: Osaka, Japan

Post by fdarkangel » Sat Apr 07, 2012 9:44 am

At the beginning of X-Men 2 Clone Wars, the player is assigned to a random character. And this happens without any user input, there are no menus whatsoever.
Using Gens/GS r7 you always start with Beast whereas Kega Fusion 3.63x gives you a random character.
Apparently Kega zeroes out the Z80 RAM initially, so the game must be using a different method. Has anyone studied this ROM?

TmEE co.(TM)
Very interested
Posts: 2440
Joined: Tue Dec 05, 2006 1:37 pm
Location: Estonia, Rapla City
Contact:

Post by TmEE co.(TM) » Sat Apr 07, 2012 11:41 am

Fusion randomizes HV counter on startup IIRC, so games using it will work right.
Mida sa loed ? Nagunii aru ei saa ;)
http://www.tmeeco.eu
Files of all broken links and images of mine are found here : http://www.tmeeco.eu/FileDen

Eke
Very interested
Posts: 884
Joined: Wed Feb 28, 2007 2:57 pm
Contact:

Post by Eke » Sat Apr 07, 2012 12:14 pm

Some other games do the same thing on sega logo: Eternal Champions, Bonkers,...

Like for X-Men 2, random seed is issued from HV counter read before any synchronization is done with VDP (like waiting for interrupt or specific status flag)

fdarkangel
Interested
Posts: 24
Joined: Sun Dec 17, 2006 8:28 pm
Location: Osaka, Japan

Post by fdarkangel » Sat Apr 07, 2012 12:57 pm

TmEE co.(TM) wrote:Fusion randomizes HV counter on startup IIRC, so games using it will work right.
Which would amount to adding a random offset to H and V counters. Thanks! It indeed fixed the problem. I've patched Gens/GS accordingly. I'm surprised this hasn't been fixed so far.

Post Reply