This article was originally written for Darren Hebden's RLNews
Frequently, in a roguelike game, the programmer will want to do various
pseudorandom things. As well as simply generating random numbers, they
may want to have subroutines for picking a random set of things from a
list, shuffling a list, picking an item fairly from a weighted list,
and so on.
Although it is easy to come up with "random" algorithms for doing this,
mere randomness and/or intricacy does not guarantee fairness. Moreover,
if the algorithms are used frequently, their efficiency can be an
important issue. The following algorithms are both reasonably efficient
and fair...
I have written the algorithms both in a Basicstyle pseudocode and in
native C. The C code for these algorithms is amazingly small.
The proofoffairness for these algorithms is available on request from:
londonien@hotmail.com
and illustrates the value of applied maths in even quite simple computer
science.
N.B. For the following algorithms, the function "random(x)" is assumed
to produce a fair random number between 0 and x1.
BAGPICK ALGORITHM
This algorithm picks a random subset of size "x" from the numbers "0"
to "n1". It is conceptually equivalent to picking a bunch of things
from a bag without replacement. It is not THE most efficient approach
for a static array, but has the edge because it can be applied to a
linked list instead of numbers, with very little modification.
***************
Pseudocode
***************
max:=n;
remaining:=x;
current:=0;
while (remaining > 0)
if (random(max) < remaining) then
ADD (current) TO OUTPUT LIST
remaining:=remaining1;
end if
max:=max1;
current:=current+1;
end while
***************
C Code
***************
void BagPick(int *dest, int n, int x)
{
int i;
for(i=0;x>0;i++) {
if (random(n) < x) *dest++=x;
}
}
SHUFFLE ALGORITHM
This algorithm shuffles a list "array" of length "n". Unlike more
complex and seeminglyrandom algorithms, it is truly random, and
optimally efficient.
***************
Pseudocode
***************
for f:=0 to n
SWAP array[f] WITH array[random(f)];
end for
***************
C Code
***************
void Shuffle(void *array, int n, size_t size)
// "size" is the size, in chars, of an array element
{
int f,g;
char *temp,*p;
temp=malloc(size);
p=array;
for(f=0;f<n;f++) {
g=random(f);
memcpy(temp,&p[g*size]);
memcpy(&p[g*size],&p[f*size]);
memcpy(&p[f*size],temp);
}
free(temp);
}
FOR FURTHER THOUGHT
Another useful randomiser technique is to be able to associate a
random seed with a "meaningful" text string, so that randomly generated
entities such as dungeons, levels, planets, NPCs, species and so on can
be given a name which completely specifies their generated
characteristics. This technique will feature heavily in Dimensions, and
hopefully I will find time later to post and comment on suitable
algorithms based on this idea.
