LoginLogin

Deterministic Pseudorandom Number Generator

Root / Submissions / [.]

ezmanCreated:
Random numbers are great for adding variety to games, but sometimes it's desirable to have these numbers come out in the same sequence every time. Deterministic generators are used in procedural generation techniques. For instance, a world in Minecraft is generated from a seed value. Here's a SmileBASIC implementation of a popular generator called the Mersenne Twister. You don't need to understand how it works, but look it up on Wikipedia to read about the algorithm if you're interested.
'MERSENNE TWISTER - PSEUDORANDOM NUMBERS
'IMPLEMENTATION FROM WIKIPEDIA
'DEFINE CONSTANTS
DIM F%=1812433253
DIM U%=11 'ADDITIONAL TEMPERING BIT SHIFT/MASK
DIM S%=7 'TEMPERING BIT SHIFT
DIM T%=15 'TEMPERING BITSHIFT
DIM L%=18 'ADDITIONAL TEMPERING BIT SHIFT MASK
DIM D%=&HFFFFFFFF 'ADDITIONAL TEMPERING BIT SHIFT MASK
DIM B%=&H9D2C5680 'TEMPERING BIT MASK
DIM C%=&HEFC60000 'TEMPERING BIT MASK
DIM A%=&H9908B0DF 'COEFFICIENTS OF THE RATIONAL NORMAL FORM TWIST MATRIX
DIM W%=32 'WORD LENGTH IN BITS
DIM N%=624 'LENGTH OF STATE ARRAY
DIM M%=397 'MIDDLE WORD 
DIM MT%[N%] 'MERSENNE TWISTER VALUE ARRAY
DIM R%=W%-1 'NUMBER OF BITS IN LOWER MASK
DIM LM%=(1<<R%)-1 'LOWER MASK
DIM UM%=((1<<W%)-1) 'UPPER MASK
DIM IDX%=N%+1
'SEED RANDOM NUMBER ARRAY
COMMON DEF SRAND S%
DIM I%=0
IDX%=N%
MT%[0]=S%
FOR I%=1 TO N%-1
 MT%[I%]=((1<<W%)-1) AND (F% * (MT%[I%-1] XOR (MT%[I%-1] >> (W%-2) ) ) + I%)
NEXT
END
'"TWIST" RANDOM NUMBER ARRAY
DEF TWIST
DIM X%=0
DIM XA%=0
DIM I%=0
FOR I%=0 TO N%-1
 X%=(MT%[I%] AND UM%)+(MT%[(I%+1) MOD N%] AND LM%)
 XA%=X% >> 1
 IF (X% MOD 2) != 0 THEN
  XA%=XA% XOR A%
 ENDIF
 MT%[I%]=MT%[((I%+M%) MOD N%)] XOR XA%
NEXT
IDX%=0
END
'RETURN RANDOM NUMBER OF LENGTH LEN% IN BITS
COMMON DEF RAND(LEN%)
IF IDX% >= N% THEN
 IF IDX% > N% THEN
  SRAND 5489 'SEED GENERATOR
 ENDIF
 TWIST
ENDIF
DIM Y%=MT%[IDX%]
Y%=Y% XOR ((Y% >> U%) AND D%)
Y%=Y% XOR ((Y% << S%) AND B%)
Y%=Y% XOR ((Y% << T%) AND C%)
Y%=Y% XOR (Y% >> 1)
INC IDX%
DIM O%=(Y% AND ((1<<LEN%)-1))
RETURN O%
END
'SOME HELPER FUNCTIONS
COMMON DEF RAND32()
 RETURN RAND(32)
END
COMMON DEF RAND16()
 RETURN RAND(16)
END
COMMON DEF RAND8()
 RETURN RAND(8)
END
You can now get a random number of up to 32 bits in length by calling RAND(length), RAND8(), RAND16(), or RAND32(). You can re-seed the generator by passing an integer to SRAND. Example usage: A 'random' name generator. Maybe you're making a big RPG with lots of NPC characters populating your world. Each NPC has a name, and you'd like that name to be the same every time the game is run. Here's a function that will return a string which should be pronounceable.
COMMON DEF REALNAME()
DIM A$="abcdefghijklmnpqrstuvwxyz"
DIM B$="abeloruy"
DIM C$="acehloru"
DIM D$="aehioruy"
DIM E$="abcdefghjklmnpqrstuvwxyz"
DIM F$="aefiloru"
DIM G$="aeghiloruy"
DIM H$="aeiou"
DIM I$="abcdefgjklmnopqrstuvwxyz"
DIM J$="aeoiu"
DIM K$="aeoiuy"
DIM L$="aeilouy"
DIM M$="aeiouy"
DIM N$="aeinouy"
DIM O$="abcdfghiklmnopqrstuvwxyz"
DIM P$="aehiloprstuy"
DIM Q$="u"
DIM R$="aeioruy"
DIM S$="acehiklmnopqstuvwyz"
DIM T$="aehiortuwyz"
DIM U$="bcdfghklmnpqrstvxz"
DIM V$="aeilou"
DIM W$="aehioru"
DIM X$="ae"
DIM Y$="aeiou"
DIM Z$="aeiou"
DIM A%=(RAND(5) MOD 25) 'PICK A RANDOM LETTER OF THE ALPHABET
DIM A1$=CHR$(97+A%) 'ADD 97 TO GET ASCII A
DIM I%=0 'LOOP COUNTER
DIM O%=0 'ANTI-TRIPLE-LETTER OVERFLOW COUNTER
DIM LST$="" 'ANTI-TRIPLE-LETTER LAST CHARACTER
DIM LST2$="" 'ANTI-TRIPLE-LETTER SECOND LAST CHARACTER
DIM TMP$="" 'TEMPORARY STRING
DIM OUT$="" 'OUTPUT
DIM NL%=RAND(3)+2 'LENGTH OF NAME BETWEEN 2 TO 9 CHARACTERS
PUSH OUT$,A1$ 'FIRST LETTER OF NAME
FOR I%=0 TO NL%
 LST2$=LST$
 LST$=A1$
 TMP%=VAR(CHR$((ASC(LST$)-32))+"$")
 O%=0
 REPEAT
  A1$=TMP$[(RAND(6) MOD LEN(TMP$))]
  INC O%
 UNTIL (O%>100) OR ((A1$ != LST2$) AND (LST$ != A1$)) 'DON'T ALLOW THE SAME LETTER THREE TIMES IN A ROW UNLESS NO OTHER OPTION
 PUSH OUT$,A1$
NEXT
OUT$[0]=CHR$(ASC(OUT$[0])-32) 'UPPERCASE THE FIRST LETTER OF THE NAME
RETURN OUT$
END
It works by having a string of characters for each letter of the alphabet, which specify the characters which are allowed to come after that letter. One is chosen at random and appended to the name. It's not as short as a simpler function based on vowels and consonants, but produces better output, and is easily tailored by adding/removing characters from the letter strings. If you want to make a certain letter more likely to appear then simply repeat that letter in the character string. Test it out in direct mode by printing a list of ten names:
SRAND 4321:FOR I=1 TO 10:?REALNAME()+" "+REALNAME():NEXT
You should see the same ten names each time.

Are you aware of the RANDOMIZE command?

I am, but when I tested it I didn't get the same sequence of numbers from RND after calling RANDOMIZE, which is why I knocked this together :-)

Replying to:ezman
I am, but when I tested it I didn't get the same sequence of numbers from RND after calling RANDOMIZE, which is why I knocked this together :-)
RANDOMIZE 0,4321:FOR A=1 TO 10:?RND(0,10);" ";:NEXT 6 6 1 2 8 0 2 9 8 5 consistently.

So it does! Brilliant. I must have messed up while testing it :-D Maybe I should change this to a "Random Name Generator" tutorial?