  | MAIN | NEWS | FAQS | LINKS | ARTICLES | WORKSHOP | Send Mail To:Steve Register

 Randomiser Algorithms - Simon McGregor.
 This article was originally written for Darren Hebden's RLNews ```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