Please put a good PRNG in 0.8.1

General discussion about LÖVE, Lua, game development, puns, and unicorns.
User avatar
Hexenhammer
Party member
Posts: 175
Joined: Sun Feb 17, 2013 8:19 am

Please put a good PRNG in 0.8.1

Post by Hexenhammer »

You really want a decent PRNG for many kinds of games. I suggest xorshift, it is very small and fast yet perfectly fine for typical game programming. A quality PRNG can really make a difference. My procedurally generated level maps started looking a lot better when I switched from a poor PRNG to xorshift (in C).

Unfortunately the LÖVE version of Lua does not support direct bit manipulation and thus cannot be used to reasonably implement a good PRNG, thus one should be bundled.

Here is a Public Domain version of 32-bit xorshift in ISO C99 written by me:

Code: Select all

#include <stdint.h>


// PRNG state type
typedef struct { uint32_t x; uint32_t y; } RandomState;

// Current PRNG state
static RandomState State = {2282008U, 362436069U};


// Seeds the RNG
void RandomSeed(uint32_t seed)
{
  State.x = seed;
}


// Returns a random unsigned integer
uint32_t RandomUint32(void)
{
  State.x = 69069U * State.x + 123U;
  State.y ^= State.y << 13U;
  State.y ^= State.y >> 17U;
  State.y ^= State.y << 5U;

  return State.x + State.y;
}


// Returns a random double [0, 1) interval
double RandomDouble(void)
{
  return RandomUint32() * (1.0 / 4294967296.0);
}


// Returns a random integer [0, n) interval
int32_t RandomMod(int32_t n)
{
  return RandomDouble() * n;
}


// Returns a random integer [lb, ub] interval
int32_t Random(int32_t lb, int32_t ub)
{
  return lb + (int32_t)(RandomDouble() * (ub - lb + 1));
}

// Demo
#include <time.h>
#include <stdio.h>

int main(void)
{
  RandomSeed(time(NULL));

  for (int i = 0; i < 20; ++i)
    printf("%d\n", Random(1,3));

  return 0;
}
You can use the 32-bit version for both the 32-bit and the 64-bit build of LÖVE. I think it would be good if the random() functions of all versions of LÖVE showed identical behavior. The current situation where the exact behavior of random depends on the underlying platform is certainly not optimal.

I do not think it is necessary to implement more than one RNG (as someone suggested elsewhere). LÖVE is not Java or C++ and hopefully never will be. More than one PRNG would be bloat for a platform like this IMO. Even if the binary size impact would be fairly minimal API bloat is a problem in itself.

You don't have to use xorshift but please do not rely on the platform's random for LÖVE's random functions.

Oh, and please add functions to get/set the PRNG state. They are useful for many things. With xorshift those functions are trivial and easy to understand because the state is just two integers.
User avatar
micha
Inner party member
Posts: 1083
Joined: Wed Sep 26, 2012 5:13 pm

Re: Please put a good PRNG in 0.8.1

Post by micha »

Thanks for your post. Until now I assumed that lua used the mersenne twister. After reading your post and some online reading, I found that lua uses the c rand() function, which is just a linear congruential generator. That is good to know.

And now I am curious: How did you see that your procedurally generated level maps are better, if you are using xorshift? How do you define "better" here? I am aware that xorshift has better proberties as a linear congruential generator, concerning randomness. But I didn't expect that this is already visible in simple applications. I thought, that only matters in scientific applications.

One last thing:
For people who don't want to recompile löve, here is a lua library for generating numbers with the mersenne twister:
http://www.tecgraf.puc-rio.br/~lhf/ftp/lua/
scroll down to "lrandom". I am a fan of the mersenne twister and it is used in python, r and matlab, which are used by a large scientific audience. (Also I like the name mersenne twister)
User avatar
Hexenhammer
Party member
Posts: 175
Joined: Sun Feb 17, 2013 8:19 am

Re: Please put a good PRNG in 0.8.1

Post by Hexenhammer »

micha wrote:Thanks for your post. Until now I assumed that lua used the mersenne twister. After reading your post and some online reading, I found that lua uses the c rand() function, which is just a linear congruential generator.
AFAIK there is no standard for C's rand() except the interface i.e. it is not guaranteed to be a LCG. IIRC the rand() on Linux actually uses a better PRNG but it's platform specific for sure and thus no good.
How did you see that your procedurally generated level maps are better, if you are using xorshift? How do you define "better" here?
Hard to describe. My level generator (for a roguelike) basically dug out rooms and connected them and when I switched from a LCG to xorshift the generated levels became a lot more varied i.e. the selection of room and connection types was more random. Or to put it differently, a PRNG which repeats certain patterns will also lead to repeated patterns in procedurally generated content. I was honestly surprised myself about the strength of this effect.

I think it only becomes obvious if you directly compare against a poor PRNG, though. I used a primitive LCG before switching to xorshift. In contrast, I doubt that there is any perceivable difference between xorshift and MT in such cases for example.
User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Please put a good PRNG in 0.8.1

Post by vrld »

LÖVE 0.9 will have a custom PRNG and it will indeed be XORSHIFT. This has been on the to-do list for a long time now (see the issue tracker) and has also been implemented in love-experiments (sort of a staging area/playground to test new features).

However, I feel the need to point out a few things, because this topic pops up way too often:
  • tl;dr: Random numbers, probability theory and statistics are very tricky things.
  • C's rand() - as bad as it may be suited for encryption, etc. - is often more than enough for video games. Just look at what Elite, FTL and other rougelikes out there achieve.
  • Humans are very, very bad at assessing random events. Or rather, humans are too eager to assume patterns in everything (that's why you can see faces in dirt and animals in clouds). In fact, "random numbers" produced by humans tend to include more patterns than "true" random numbers (humans will produce less clusters than true random events would).
  • Unwanted patterns can also be the result of unfortunate computation of random numbers. For example, the sum of two or more uniformly distributed random numbers will be biased towards the lower bound, i.e.

    Code: Select all

    x = (math.random() + math.random()) / 2 -- random number in [0:1]
    will be (close to) 0.5 twice as often as it will be close to 1 or 0.
  • "Better" in the context of randomness is a very dangerous statements. Unless you have a way of quantifying this statement (using statistic metrics) it's pretty much worthless because everyone has a different definition of "better" - Although in your case you explained what you meant really well in the second post.
  • The same goes for "more random" and "less random" - this doesn't even make sense, unless we are talking about entropy. Then, "more random" would mean "higher entropy" (or "uniformly distributed", i.e. each number has the same probability of occurrence) and "less random" would mean "lower entropy" (i.e. certain numbers occur more often than others, e.g. in a normal distribution). Note that "less random" does not mean worse in this context - sometimes a normal distribution is just what we want. Again, you didn't write "more" or "less random", but as I said, this pops up way too often.
Last edited by vrld on Mon Feb 25, 2013 3:05 pm, edited 1 time in total.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
User avatar
Hexenhammer
Party member
Posts: 175
Joined: Sun Feb 17, 2013 8:19 am

Re: Please put a good PRNG in 0.8.1

Post by Hexenhammer »

vrld wrote:LÖVE 0.9 will have a custom PRNG and it will indeed be XORSHIFT.
Cool! :ultrahappy:
[*]"Better" in the context of randomness is a very dangerous statements. Unless you have a way of quantifying this statement (using statistic metrics)
The mathematics professor who gave us xorshift and many other PRNGs - George Marsaglia (RIP) - also developed tests to measure the quality of PRNGs: http://en.wikipedia.org/wiki/Diehard_tests
According to these tests traditional implementations of C's rand are pretty horrible and xorshift is a lot better.
[*]The same goes for "more random" and "less random" - this doesn't even make sense
Actually it does. Even if two PRNGs both return uniformly distributed numbers one can be called "more random" if the sequence of numbers it returns is closer to a truly random sequence as opposed to say repeating certain patterns. The Diehard tests I mentioned above test these things.

It is actually more questionable to call a function which simply returns a potentially endless stream of numbers uniformly distributed within a specified range "random number generator". If you really want to be pedantic they are "uniformly distributed numbers generators", the sequence of numbers returned does not have to be random at all. And indeed C's rand() implementations are/were infamously non-random uniformly distributed numbers generators.
User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Please put a good PRNG in 0.8.1

Post by vrld »

Hexenhammer wrote:
[*]"Better" in the context of randomness is a very dangerous statements. Unless you have a way of quantifying this statement (using statistic metrics)
The mathematics professor who gave us xorshift and many other PRNGs - George Marsaglia (RIP) - also developed tests to measure the quality of PRNGs: http://en.wikipedia.org/wiki/Diehard_tests
According to these tests traditional implementations of C's rand are pretty horrible and xorshift is a lot better.
As I wrote: As long as you write what you mean by "better", it's ok. If you don't, it's not. But you did.
Anyway, C's rand() can also be better than xorshift when "better" refers to how fast the algorithm is.
Hexenhammer wrote:
[*]The same goes for "more random" and "less random" - this doesn't even make sense
Actually it does. Even if two PRNGs both return uniformly distributed numbers one can be called "more random" if the sequence of numbers it returns is closer to a truly random sequence as opposed to say repeating certain patterns.
And by "truly random" sequence you probably mean "high entropy", which is what I wrote in the part you kindly omitted... ;)
Hexenhammer wrote:It is actually more questionable to call a function which simply returns a potentially endless stream of numbers uniformly distributed within a specified range "random number generator". If you really want to be pedantic they are "uniformly distributed numbers generators", the sequence of numbers returned does not have to be random at all. And indeed C's rand() implementations are/were infamously non-random uniformly distributed numbers generators.
Yes, I agree. Relevant Dilbert:
Image
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
User avatar
Hexenhammer
Party member
Posts: 175
Joined: Sun Feb 17, 2013 8:19 am

Re: Please put a good PRNG in 0.8.1

Post by Hexenhammer »

To make the issue here more clear to the general audience, here is a simplified example. Imagine three functions.

randomA(1, 10)
Always returns this sequence: 1,2,3,4,5,6,7,8,9,10 repeated endlessly
It returns uniformly distributed numbers but we wouldn't call it a "RNG"

randomB(1, 10)
May return: 3,6,7,1,1,3,4,8,9.. and if we call it often enough and measure we find that it returns as many 3s as it return 4s etc.
I.e. another uniformly distributed numbers generator but people start calling it an "RNG" now because they don't immediately notice any pattern. However, this "RNG" actually has the characteristic that a 7 is followed by a 1 much more often than by any other number. The patterns are usually more complex than that but you get the idea. Any non-random pattern within the returned sequence of numbers will have an effect on procedural content generation routines. To stick with our simplified example and my roguelike level generation issues: randomB() would cause room type 7 to be connected with connection type 1 more often than with any other connection type thus making the levels less random than intended.

randomC(1, 10)
A hypothetical, perfect RNG. The returned sequence looks like the sequence returned by randomB() to the casual observer, again it is uniformly distributed.. but it is also perfectly random. That means in my example room type 7 will no longer be more likely to get connection type 1 than say connection type 2.
Last edited by Hexenhammer on Fri Feb 22, 2013 4:20 pm, edited 1 time in total.
User avatar
Hexenhammer
Party member
Posts: 175
Joined: Sun Feb 17, 2013 8:19 am

Re: Please put a good PRNG in 0.8.1

Post by Hexenhammer »

vrld wrote: And by "truly random" sequence you probably mean "high entropy", which is what I wrote in the part you kindly omitted... ;)
No, I thought I made it clear that I wasn't talking about distribution issues at all. You can easily transform uniform to normal distribution etc. That is not the issue here.
User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Please put a good PRNG in 0.8.1

Post by kikito »

Code: Select all

math.rand = function()
  return 4 -- produced with a real dice
end
Sorry guys I could not resist. :ultraglee:
When I write def I mean function.
User avatar
Nixola
Inner party member
Posts: 1949
Joined: Tue Dec 06, 2011 7:11 pm
Location: Italy

Re: Please put a good PRNG in 0.8.1

Post by Nixola »

lf = love.filesystem
ls = love.sound
la = love.audio
lp = love.physics
lt = love.thread
li = love.image
lg = love.graphics
Post Reply

Who is online

Users browsing this forum: No registered users and 5 guests