Random Number Generation
Almost all game programs require a random number generator. When
implementing games for embedded systems, generating random numbers
raises certain interesting issues. While generation of random number
can be done using the rand() C library function, getting a suitable
seed is a challenge.
Seeding, the Random Number Generator
For the uninitiated, the rand() function is a pseudorandom number
generator. Wikipedia has a detailed article on
pseudorandom
number generators. In short, a pseudorandom number generator takes
the previous generated value, plugs it into a complex expression and
generates the next value. With this setup, we will have to specify the
start value for the random number generator, called the seed. For a
given seed, the sequence of generated random numbers will be the
same. The seed is specified using the srand() function.
To get a better idea of how these functions work, the implementation
of srand() and rand() in SDCC is shown below.
#include <stdlib.h>
static unsigned long int next = 1;
int rand(void)
{
next = next * 1103515245UL + 12345;
return (unsigned int)(next/65536) % (RAND_MAX + 1U);
}
void srand(unsigned int seed)
{
next = seed;
}
In a Unix system, the current time is generally used as the seed, as
shown below. The time() function returns the no. of seconds since
1st Jan 1970 (the Epoch).
srand(time(NULL));
Timer Ticks, The Problem
Not many embedded systems have an RTC. And the solution used in the PC cannot be replicated here. Most embedded systems though keep track of time using a periodic tick timer. In such embedded systems, the timer ticks since start of the program can be used as the seed.
But every time the user starts the game, by reset-ing the board, the
no. ticks from boot-up to the invocation of srand() function will be
the same, resulting in the same sequence of random numbers.
Using an EEPROM
In systems with an EEPROM, a simple solution to the problem is to have a reboot counter in the EEPROM. Every time the board boots up the counter is to be incremented by one. The reboot counter can be used as the seed. A sample implementation with ZDev is shown below.
static void eeprom_seed_init()
{
uint8_t seed;
/* Read the count. */
eeprom_init();
seed = eeprom_read(0);
/* Increment and writeback the count */
eeprom_write_protect(false);
eeprom_write(0, seed + 1);
eeprom_write_protect(true);
srand(seed);
}
Using a Key Press
In systems without an EEPROM, a little more effort is required. A element of randomity has to be introduced somehow. Here is a simple trick. When the system boots up, the program waits till the user presses a key. Since the time to key press will be random, the tick count obtained after the key press will change each time. The tick count can now be used as a seed.
This can be neatly hidden behind a start screen, saying "press any key to continue!" A sample implementation with ZDev is shown below.
static void keypress_seed_init()
{
/* Clear all keypresses first. */
while (button_tstc())
button_getc();
/* Wait for a key. */
button_getc();
srand(systick_get_ticks());
}
Using an ADC
In systems with an ADC, the noise on the analog signal can be used for creating the seed. A series of values is read from the ADC and the LSB of the values are merged together to form the seed. A sample implementation with ZDev, using channel 1 of the ADC is shown below.
static void adc_seed_init()
{
int i;
int seed;
unsigned lsb;
adc_enable(1);
/* Collect the LSB bits of 32 consecutive samples. */
seed = 0;
for (i = 0; i < 32; i++) {
lsb = adc_read16(1);
seed |= (lsb << i);
}
srand(seed);
}
Concluding Remarks
Hope this article has shown some neat techniques for generating the seed. If you have suggestions and improvements, please post them as comments to this article. In upcoming articles, we will show how to develop simple game programs using ZDev. In these game programs, we will be using one of the above techniques for generating the seed.
And by the way, some of ideas discussed in this article were triggered from this discussion on stackoverflow.com.