Pseudorandom Number Generator

Blitz3D Forums/Blitz3D Programming/Pseudorandom Number Generator

ClayPigeon(Posted 2011) [#1]
I am creating a game that greatly relies on random numbers. I cannot use the random functions build into B3D because:
- I have no control over the internal system of the B3D RNG
- If I want to use a seed twice, it disrupts the randomness of anything else I use the RNG for
- I need to supply the RNG with and x and y (maybe z) value to get my random number

The problem is that I have searched all over the internet for a good, yet simple random number generator, and have come across many. But, when I convert them to Blitz, the don't function correctly due to the differences in variable types that other languages use (eg. double-precision float). Does anyone know of a good PRNG for use with B3D that meets these criteria?


Yasha(Posted 2011) [#2]
If I want to use a seed twice, it disrupts the randomness of anything else I use the RNG for

One thing you can do is get the current state of the RNG with RndSeed, and put that in a temporary variable. Set the seed to the value you want to get your set of predictable results, then once that's done, you can restore the RNG to the state extracted with RndSeed (by setting it as the new seed, with SeedRnd). The RNG will then continue exactly as it would have done, had you never executed the middle step.

I don't see what other control you could need over an RNG than to set and extract its state (any more than that and it's no longer generating random numbers...?). However, here's a recent thread on the same subject with a B3D code algorithm courtesy of Warpy (incidentally, it's still on the first forum page): http://www.blitzbasic.com/Community/posts.php?topic=93780

As for your third criterion... I don't understand what you mean, sorry.


Matty(Posted 2011) [#3]
http://en.wikipedia.org/wiki/Linear_congruential_generator

This one is similar to the one used in VBA (for older versions of Excel).

Very simple:

Xn+1 = (a * Xn + c) mod m

X(n=0) is the seed, and value from 0 to m-1
a is a multipler - typically some value between 1 and m
c is an increment - typically some value between 1 and m

Very easy to use, and found from first google search.


ClayPigeon(Posted 2011) [#4]
Since 'n' is inside of the equation it's being set to, doesn't that make it an iterative equation? I want to be able to just give it the XY coords and it will return the same random number every time. Also I gave it a shot at implementing your equation and I couldn't get it to work. I get the feeling I missing something really obvious...


Matty(Posted 2011) [#5]
"n" refers to the "nth" iteration. "n" is not a variable...I'll write some code..hang on a moment...

Graphics 512,512,0,2

Xn = 1 ;the seed
a = 120938 ;some number arbitrarily picked
c = 2430958 ;some other number abitrarily picked
m = 16777216 ;a large number - this is the range the values can be for


For n=1 To 10

Xn = (a * Xn + c) Mod m
Text 0,n*15,Xn

Next

Flip
WaitKey
End




ClayPigeon(Posted 2011) [#6]
But still, isn't that iterative? Meaning that if I want a number further into the sequence, I have to iterate it more times?


Warpy(Posted 2011) [#7]
Yes, it's an iterative algorithm. The thread Yasha linked to contains a long explanation of why this has to be the case for any reasonable pseudorandom number algorithm.

In fact, you want to do exactly the same thing as Sacha wanted to do.


ClayPigeon(Posted 2011) [#8]
The thread Yasha linked to contains a long explanation of why this has to be the case for any reasonable pseudorandom number algorithm.


Yes, I understand that iterative algorithms heed more true random numbers, but that means the further I get away from the origin, the more recursive iterations must be carried out, which is obviously not acceptable. Is there really no way to get a unique number for virtually any combination of x and y? I had something going a while back that worked okay, but it used B3D's built-in RNG:

Function Noise#(x%,y%,seed%)
	Local n = x+(y+512)*64
	n = n*(n)+24*(y)
	SeedRnd seed+n
	Return Rnd(-1,1)
End Function


This also is obviously not acceptable, because it reseeds the RNG for every call, making its iterative-ness useless.

Last edited 2011


Axel Wheeler(Posted 2011) [#9]
Using Yasha's method (in his first post) you would add a couple of lines:

Function Noise#(x%,y%,seed%)
	Local n = x+(y+512)*64
	n = n*(n)+24*(y)
        rs=RndSeed() ; Save the previous seed
	SeedRnd seed+n
	Result# = Rnd(-1,1)
        SeedRnd(rs) ; Set it back to that previous seed, like nothing ever happened
        Return Result#
End Function


Actually, if you just want to go back to uncontrolled random numbers after generating your controlled one, just use SeedRnd(millisecs()) again (assuming you did this at program start). For ordinary use it doesn't really need to be the "next" random number.

However, that doesn't solve the problem of passing two or more seeds to get a unique result (especially as it appears from your code that you want these seeds to be floats)

What is the range of x and y?

I would think it would be better to use integers if at all possible and if there is a reasonable limit to these values, then your general approach should work (I haven't checked your math, though). Basically, if you can combine the two values into a unique single value that fits into an int, then you are good to go.

On the other hand, if these are large ints, could you maybe...

SeedRnd(x)
ySeed=rand(y)
SeedRnd(ySeed)
Return Rnd(-1,1)


... and again you can restore the old seed at the end, or SeedRnd(millisecs()).

Are you really only looking for a single result for each x and y? Or are you trying to produce a whole region of complexity filling each gridpoint? I'm not sure it matters, but somehow it seems important.

In any event, see the following post (zoom in on a 500 million star galaxy), which may be one of the few (perhaps only?) successful attempts to do what (I think) you are talking about (in Blitz). Anyway, it's really cool. Uses an actual image as it's base, then seeds the rng with data from a given pixel. Generates the star names too!

http://www.blitzbasic.com/Community/posts.php?topic=78086


ClayPigeon(Posted 2011) [#10]
I've created an infinite terrain generator using the code I posted above. It seems to work just fine, but it uses the B3D RNG, and I want one that is self-contained (meaning it IS a RNG, not using one). I tried that equation:

Xn+1 = (a * Xn + c) mod m

But, it generated an oscillating, repeating pattern that resembled a sawtooth wave. I really don't see how this could work..


Krischan(Posted 2011) [#11]
Hmm I coded an improved perlin noise landscape generator, perhaps you can use this generation code:





It is using a predictable pseudorandom number generator I derived from my elite planet name generator, very simple:



You should always get these values

0.304706
-0.595686
0.42549
0.13451
-0.0301961
0.529804
0.634118
-0.277255
-0.518824
-0.167451
0.441961
-0.244314
0.0356863
0.233333
0.0192157
0.288235
0.540784
-0.557255
0.266275
0.244314
-0.0466667

Last edited 2011


Axel Wheeler(Posted 2011) [#12]
For some reason I thought the Blitz3D rng was posted at some point. If so I can't find it now.

Keep in mind though that the Blitz3D rng is compiled right into your binary, so there's no risk of it not working right on some processors or whatever. The only thing that would break it is if Mark were to change it in an update and you were to recompile with that update, then you'd have a different terrain. However, many other programs would break too so Mark is unlikely to do that.


_PJ_(Posted 2011) [#13]
Keep in mind though that the Blitz3D rng is compiled right into your binary, so there's no risk of it not working right on some processors or whatever.

If I'd klnown that a while ago it would have saved me having to ask a lot of people what the results of a Rnd were XD

--

Personally, I find the blitz generator good enough.


MCP(Posted 2011) [#14]
An alternative to creating your own random number generator (and much faster in terms of compution time) would be to create a table of random numbers (say 4k's worth) either in the range
that your interested in or using floats in the range of 0.0 - 1.0 then scale the result to the range you want.
Your 'Seed' then would simply be an index into this array (modulo array size) to fetch the next number in sequence.

You could write a small program in Blitz to generate this table easily using the native functions or if you prefer 'true' randomness you could visit...

www.random.org and use their free random number generation service.


Krischan(Posted 2011) [#15]
Another example, this time with unique numbers: