Frequently, in a roguelike game, the programmer will want to do various
pseudo-random 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 Basic-style pseudocode and in 
native C. The C code for these algorithms is amazingly small.

The proof-of-fairness 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 x-1.

BAG-PICK ALGORITHM

This algorithm picks a random subset of size "x" from the numbers "0" 
to "n-1". 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:=remaining-1;
    end if
    max:=max-1;
    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 seemingly-random 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.