Patterns with Random Numbers
by Deozaan · in Torque Game Builder · 05/20/2008 (5:27 pm) · 10 replies
I'm a complete beginner/noob when it comes to pseudo random numbers and procedurally generated content, so if I'm doing something that painfully obviously wrong, please let me know.
I made a very small scale pseudo random number generator with code like this:
And I've noticed a scary trend: Smaller MAX numbers cause results to repeat very frequently. I know this is pretty much a "Well duh! Using a smaller MAX reduces the pool from which to pick random numbers! Of course there will be repeats!" I'm aware of that, but I never expected the repeats to happen every 3-4 numbers!
For example:
Now at 2500 I don't see a repeat (within the ten matches it displays) but the numbers still have a very eerie pattern.
Interestingly enough, just generating one more random value before setting the new seed seems to almost eliminate the problem completely:
New Function
Example Results:
Everything looks good until you get down to a max of 50, and the result becomes 32 for the first time.
Anyway, I'm not really sure what my point is in all this except to say that it's very interesting.
I made a very small scale pseudo random number generator with code like this:
function randStuff(%seed, %max)
{
setRandomSeed(%seed);
for(%i = 0; %i < 10; %i++)
{
%num = getRandom(1,%max);
echo(%num);
setRandomSeed(%num);
}
}And I've noticed a scary trend: Smaller MAX numbers cause results to repeat very frequently. I know this is pretty much a "Well duh! Using a smaller MAX reduces the pool from which to pick random numbers! Of course there will be repeats!" I'm aware of that, but I never expected the repeats to happen every 3-4 numbers!
For example:
Quote:==>randStuff(50, 100);
51
58
7
50
51
58
7
50
51
58
==>randStuff(900, 500);
301
408
257
400
301
408
257
400
301
408
==>randstuff(354, 1000);
679
954
879
354
679
954
879
354
679
954
==> randstuff(993548, 2500);
708
1857
600
1701
1208
357
100
701
1708
1357
Now at 2500 I don't see a repeat (within the ten matches it displays) but the numbers still have a very eerie pattern.
Interestingly enough, just generating one more random value before setting the new seed seems to almost eliminate the problem completely:
New Function
function randStuff(%seed, %max)
{
setRandomSeed(%seed);
for(%i = 0; %i < 10; %i++)
{
%num = getRandom(1, %max);
echo("Random Value " @ %num);
%num = getRandom(1, %max);
echo("New Seed " @ %num);
setRandomSeed(%num);
}
}Example Results:
Quote:==>randStuff(50,1000);
Random Value 351
New Seed 569
Random Value 184
New Seed 804
Random Value 829
New Seed 262
Random Value 435
New Seed 241
Random Value 488
New Seed 953
Random Value 72
New Seed 423
Random Value 362
New Seed 743
Random Value 602
New Seed 249
Random Value 944
New Seed 298
Random Value 487
New Seed 970
==>randStuff(50,500);
Random Value 351
New Seed 69
Random Value 184
New Seed 359
Random Value 214
New Seed 483
Random Value 282
New Seed 7
Random Value 150
New Seed 244
Random Value 409
New Seed 53
Random Value 272
New Seed 316
Random Value 13
New Seed 158
Random Value 7
New Seed 403
Random Value 222
New Seed 57
==>randStuff(50,100);
Random Value 51
New Seed 69
Random Value 84
New Seed 59
Random Value 14
New Seed 63
Random Value 42
New Seed 12
Random Value 85
New Seed 42
Random Value 95
New Seed 24
Random Value 69
New Seed 36
Random Value 53
New Seed 77
Random Value 40
New Seed 4
Random Value 29
New Seed 97
==>randStuff(50,50);
Random Value 1
New Seed 19
Random Value 34
New Seed 38
Random Value 17
New Seed 25
Random Value 26
New Seed 35
Random Value 46
New Seed 28
Random Value 47
New Seed 32
Random Value 25
New Seed 31
Random Value 18
New Seed 32
Random Value 25
New Seed 31
Random Value 18
New Seed 32
Everything looks good until you get down to a max of 50, and the result becomes 32 for the first time.
Anyway, I'm not really sure what my point is in all this except to say that it's very interesting.
#2
Here's some example code:
First we have a function to initialize a universe with some basic parameters:
Then we make a function to find out if there's a galaxy at a certain coordinate:
FYI: debugEcho is just a function I wrote that will echo the argument if a certain debug variable is set.
And just for testing purposes, some code that will check out every possible coordinate to see if a galaxy is there or not.
So here I test it, by using a seed of 101, a 10x10 universe with a 100% population rate, meaning every (x,y) coordinate pair will contain a galaxy. So I should get 100 results.
If you look at (0,0) which has a unique seed of 87 and (2,1) which has a seed of 79, you can see that the numbers are just 8 digits apart. Every 12 numbers are 8 digits apart. This is common between them all until we get through 50 of them. At which point the difference becomes 2121. If the difference of 2121 would put the number in the negatives, it wraps back to the max 10,000 (see (8,6): 553 and (0,8): 8432 for what I mean) And then towards the end they seem to vary with some of them keeping a difference of 2121 and some having a difference of 8. (I haven't compared them all.)
This post is too long... Continued on next post.
05/21/2008 (11:39 pm)
I'm still not liking the patterns I'm finding...Here's some example code:
First we have a function to initialize a universe with some basic parameters:
function createUniverse(%baseSeed, %width, %height, %popPercent)
{
%uni = new scriptObject()
{
class = "universeClass";
canSaveDynamicFields = true;
};
%uni.baseSeed = %baseSeed;
%uni.popPercent = %popPercent; // percentage of universe to be populated with galaxies
%uni.width = %width; // the percentage should become smaller as
%uni.height = %height; // width and height become larger
$universe = %uni;
}Then we make a function to find out if there's a galaxy at a certain coordinate:
function universeClass::galaxyAt(%this, %x, %y)
{
%tempSeed = %x @ %this.baseSeed @ %y; // make a unique seed for these coordinates
setRandomSeed(%tempSeed); // and use it to determine if there is a galaxy here
%num = getRandom(0,100);
if (%num <= %this.popPercent) // Houston, we have a galaxy!
{
%newMax = %this.width * %this.height;
%newMax = %newMax * %newMax;
%galSeed = getRandom(1, %newMax); // give each galaxy a unique baseSeed
debugEcho("Galaxy Found at: (" @ %x @ "," @ %y @ ") Unique Seed is: " @ %galSeed);
return (%galSeed);
} else {
// debugEcho("No Galaxy here!");
return false;
}
}FYI: debugEcho is just a function I wrote that will echo the argument if a certain debug variable is set.
And just for testing purposes, some code that will check out every possible coordinate to see if a galaxy is there or not.
function universeClass::allGalaxies(%this)
{
for (%y = 0; %y < %this.height; %y++)
{
for (%x = 0; %x < %this.width; %x++)
{
%this.galaxyAt(%x, %y);
}
}
}So here I test it, by using a seed of 101, a 10x10 universe with a 100% population rate, meaning every (x,y) coordinate pair will contain a galaxy. So I should get 100 results.
==>createUniverse(101,10,10,100); ==>$universe.allGalaxies(); Galaxy Found at: (0,0) Unique Seed is: 87 Galaxy Found at: (1,0) Unique Seed is: 635 Galaxy Found at: (2,0) Unique Seed is: 4830 Galaxy Found at: (3,0) Unique Seed is: 9025 Galaxy Found at: (4,0) Unique Seed is: 9573 Galaxy Found at: (5,0) Unique Seed is: 3768 Galaxy Found at: (6,0) Unique Seed is: 4316 Galaxy Found at: (7,0) Unique Seed is: 8511 Galaxy Found at: (8,0) Unique Seed is: 2706 Galaxy Found at: (9,0) Unique Seed is: 3254 Galaxy Found at: (0,1) Unique Seed is: 5336 Galaxy Found at: (1,1) Unique Seed is: 5884 Galaxy Found at: (2,1) Unique Seed is: 79 Galaxy Found at: (3,1) Unique Seed is: 627 Galaxy Found at: (4,1) Unique Seed is: 4822 Galaxy Found at: (5,1) Unique Seed is: 9017 Galaxy Found at: (6,1) Unique Seed is: 9565 Galaxy Found at: (7,1) Unique Seed is: 3760 Galaxy Found at: (8,1) Unique Seed is: 4308 Galaxy Found at: (9,1) Unique Seed is: 8503 Galaxy Found at: (0,2) Unique Seed is: 6938 Galaxy Found at: (1,2) Unique Seed is: 1133 Galaxy Found at: (2,2) Unique Seed is: 5328 Galaxy Found at: (3,2) Unique Seed is: 5876 Galaxy Found at: (4,2) Unique Seed is: 71 Galaxy Found at: (5,2) Unique Seed is: 619 Galaxy Found at: (6,2) Unique Seed is: 4814 Galaxy Found at: (7,2) Unique Seed is: 9009 Galaxy Found at: (8,2) Unique Seed is: 9557 Galaxy Found at: (9,2) Unique Seed is: 3752 Galaxy Found at: (0,3) Unique Seed is: 2187 Galaxy Found at: (1,3) Unique Seed is: 6382 Galaxy Found at: (2,3) Unique Seed is: 6930 Galaxy Found at: (3,3) Unique Seed is: 1125 Galaxy Found at: (4,3) Unique Seed is: 5320 Galaxy Found at: (5,3) Unique Seed is: 5868 Galaxy Found at: (6,3) Unique Seed is: 63 Galaxy Found at: (7,3) Unique Seed is: 4258 Galaxy Found at: (8,3) Unique Seed is: 4806 Galaxy Found at: (9,3) Unique Seed is: 9001 Galaxy Found at: (0,4) Unique Seed is: 7436 Galaxy Found at: (1,4) Unique Seed is: 1631 Galaxy Found at: (2,4) Unique Seed is: 2179 Galaxy Found at: (3,4) Unique Seed is: 6374 Galaxy Found at: (4,4) Unique Seed is: 569 Galaxy Found at: (5,4) Unique Seed is: 1117 Galaxy Found at: (6,4) Unique Seed is: 5312 Galaxy Found at: (7,4) Unique Seed is: 5860 Galaxy Found at: (8,4) Unique Seed is: 55 Galaxy Found at: (9,4) Unique Seed is: 4250 Galaxy Found at: (0,5) Unique Seed is: 2685 Galaxy Found at: (1,5) Unique Seed is: 6880 Galaxy Found at: (2,5) Unique Seed is: 7428 Galaxy Found at: (3,5) Unique Seed is: 1623 Galaxy Found at: (4,5) Unique Seed is: 2171 Galaxy Found at: (5,5) Unique Seed is: 6366 Galaxy Found at: (6,5) Unique Seed is: 561 Galaxy Found at: (7,5) Unique Seed is: 1109 Galaxy Found at: (8,5) Unique Seed is: 5304 Galaxy Found at: (9,5) Unique Seed is: 9499 Galaxy Found at: (0,6) Unique Seed is: 7934 Galaxy Found at: (1,6) Unique Seed is: 8482 Galaxy Found at: (2,6) Unique Seed is: 2677 Galaxy Found at: (3,6) Unique Seed is: 6872 Galaxy Found at: (4,6) Unique Seed is: 7420 Galaxy Found at: (5,6) Unique Seed is: 1615 Galaxy Found at: (6,6) Unique Seed is: 5810 Galaxy Found at: (7,6) Unique Seed is: 6358 Galaxy Found at: (8,6) Unique Seed is: 553 Galaxy Found at: (9,6) Unique Seed is: 1101 Galaxy Found at: (0,7) Unique Seed is: 3183 Galaxy Found at: (1,7) Unique Seed is: 3731 Galaxy Found at: (2,7) Unique Seed is: 7926 Galaxy Found at: (3,7) Unique Seed is: 2121 Galaxy Found at: (4,7) Unique Seed is: 2669 Galaxy Found at: (5,7) Unique Seed is: 6864 Galaxy Found at: (6,7) Unique Seed is: 7412 Galaxy Found at: (7,7) Unique Seed is: 1607 Galaxy Found at: (8,7) Unique Seed is: 5802 Galaxy Found at: (9,7) Unique Seed is: 6350 Galaxy Found at: (0,8) Unique Seed is: 8432 Galaxy Found at: (1,8) Unique Seed is: 8980 Galaxy Found at: (2,8) Unique Seed is: 3175 Galaxy Found at: (3,8) Unique Seed is: 3723 Galaxy Found at: (4,8) Unique Seed is: 7918 Galaxy Found at: (5,8) Unique Seed is: 2113 Galaxy Found at: (6,8) Unique Seed is: 2661 Galaxy Found at: (7,8) Unique Seed is: 6856 Galaxy Found at: (8,8) Unique Seed is: 1051 Galaxy Found at: (9,8) Unique Seed is: 1599 Galaxy Found at: (0,9) Unique Seed is: 34 Galaxy Found at: (1,9) Unique Seed is: 4229 Galaxy Found at: (2,9) Unique Seed is: 8424 Galaxy Found at: (3,9) Unique Seed is: 8972 Galaxy Found at: (4,9) Unique Seed is: 3167 Galaxy Found at: (5,9) Unique Seed is: 7362 Galaxy Found at: (6,9) Unique Seed is: 7910 Galaxy Found at: (7,9) Unique Seed is: 2105 Galaxy Found at: (8,9) Unique Seed is: 2653 Galaxy Found at: (9,9) Unique Seed is: 6848
If you look at (0,0) which has a unique seed of 87 and (2,1) which has a seed of 79, you can see that the numbers are just 8 digits apart. Every 12 numbers are 8 digits apart. This is common between them all until we get through 50 of them. At which point the difference becomes 2121. If the difference of 2121 would put the number in the negatives, it wraps back to the max 10,000 (see (8,6): 553 and (0,8): 8432 for what I mean) And then towards the end they seem to vary with some of them keeping a difference of 2121 and some having a difference of 8. (I haven't compared them all.)
This post is too long... Continued on next post.
#3
Something about these patterns just makes me uncomfortable. The funny thing is that I'm trying to use pseudo-random numbers to create a pattern so I can make the universe the exact same way every time given the same seed, but theoretically, these unique seeds given to each galaxy should not have a pattern to them. Or at least if they do, it shouldn't show up quite so easily. If any of these "unique" seeds end up being the same in a real environment, that would mean duplicate galaxies, since they will be generated completely based on the seed.
Of course, you could take into account the probability of something like this happening. For instance, I'm expecting that in a real case only 1% of the universe would be populated with galaxies. So even if the universe was 1,000x1,000 that's "only" 10,000 galaxies. And what are the chances that, given such a large pool of numbers to randomly choose from (1,000^4) that any of these galaxies would have the same seed? I guess you could say that it would be a 1 in 1,000,000,000,000 chance. At least, that is, if the numbers are very close to truly random and if it can even keep track of numbers that large. But if there's a pattern, which seems to be the case, maybe the chance of that happening would be significantly larger.
05/21/2008 (11:39 pm)
Continued from previous post...Something about these patterns just makes me uncomfortable. The funny thing is that I'm trying to use pseudo-random numbers to create a pattern so I can make the universe the exact same way every time given the same seed, but theoretically, these unique seeds given to each galaxy should not have a pattern to them. Or at least if they do, it shouldn't show up quite so easily. If any of these "unique" seeds end up being the same in a real environment, that would mean duplicate galaxies, since they will be generated completely based on the seed.
Of course, you could take into account the probability of something like this happening. For instance, I'm expecting that in a real case only 1% of the universe would be populated with galaxies. So even if the universe was 1,000x1,000 that's "only" 10,000 galaxies. And what are the chances that, given such a large pool of numbers to randomly choose from (1,000^4) that any of these galaxies would have the same seed? I guess you could say that it would be a 1 in 1,000,000,000,000 chance. At least, that is, if the numbers are very close to truly random and if it can even keep track of numbers that large. But if there's a pattern, which seems to be the case, maybe the chance of that happening would be significantly larger.
#4
Generally speaking, for most OS-level random generators is really just a string of floats(not sure how deep) ranging from 0.0~ to 1.0 and seeding just tells the random generator where to start in the string and what sequence to use as it steps through the string. The patterns you find are basically harmonics in the noise if you will.
When it comes to seeding with a weak random system, the argument is generally, "Seed once, seed well". The easiest and usually adequate seed method is just to seed with the system time. If you must seed more than once, as long as you don't seed twice in the same time slice, your numbers will be different.
This weakness is the argument of the ages and there are people dedicated with coming up with reasonable solutions (and no, photon emission is not a reasonable solution, at least not until it can be put on a $0.50 chip for future motherboards). But there needs to be a solotion. The more complexed software comes, the more obvious the psuedo-ness becomes.
There are countless resources on the web for better systems for seeding ranging in languages from python, to ruby, to c/c++, to turtle (j/k). I doubt the math capabilites of Torquescript can handle most of them, but it shouldn't be too hard to add a few of them to source to run the above tests against and see which you like.
Until that quantum-on-a-chip solution comes out, you can always write a function that grabs a seed from here: http://random.irb.hr/ at launch, and if it times out, seed with systemtime.
05/22/2008 (12:13 am)
Assuming Torque random works like most random functions, setting the seed to a specific static number will always yeild the same results. So in your first example where your first seed is 51, the first number always returned will be 58. Seeding with simple procedural math(which is a pattern) will yield pattern randoms. This isn't unique to Torque.Generally speaking, for most OS-level random generators is really just a string of floats(not sure how deep) ranging from 0.0~ to 1.0 and seeding just tells the random generator where to start in the string and what sequence to use as it steps through the string. The patterns you find are basically harmonics in the noise if you will.
When it comes to seeding with a weak random system, the argument is generally, "Seed once, seed well". The easiest and usually adequate seed method is just to seed with the system time. If you must seed more than once, as long as you don't seed twice in the same time slice, your numbers will be different.
This weakness is the argument of the ages and there are people dedicated with coming up with reasonable solutions (and no, photon emission is not a reasonable solution, at least not until it can be put on a $0.50 chip for future motherboards). But there needs to be a solotion. The more complexed software comes, the more obvious the psuedo-ness becomes.
There are countless resources on the web for better systems for seeding ranging in languages from python, to ruby, to c/c++, to turtle (j/k). I doubt the math capabilites of Torquescript can handle most of them, but it shouldn't be too hard to add a few of them to source to run the above tests against and see which you like.
Until that quantum-on-a-chip solution comes out, you can always write a function that grabs a seed from here: http://random.irb.hr/ at launch, and if it times out, seed with systemtime.
#5
as Brian said, "Seed once, seed well".
in your case i think the more pressing part of that is "seed once": stop calling setRandomSeed() every iteration.
try removing all your calls to setRandomSeed() and i think you'll see more satisfying numbers.
05/22/2008 (12:58 am)
Deozaan,as Brian said, "Seed once, seed well".
in your case i think the more pressing part of that is "seed once": stop calling setRandomSeed() every iteration.
try removing all your calls to setRandomSeed() and i think you'll see more satisfying numbers.
#6
You're right. If I never call setRandomSeed() again, it will indeed be more satisfying from a non-pattern perspective. But I need to be able to generate specific numbers each time, but in a non-specific order. As such, I need to use many different seeds based on the perhaps 100 million different solar systems that will be in the game.
Obviously with 100 million different solar systems, I don't want to generate them all at once and store the information in a database. So I'm trying to figure out a method in which I can generate only the ones I need, on the fly, and on a need-to-know basis.
As such, I honestly can't see how I can just "seed once, seed well" for this particular instance. As I said, I'm a complete noob in this area so what better methods may be obvious to you are apparently not obvious to me.
However, I think I've come up with a solution (that I haven't implemented yet and am not quite sure how to implement) that would work at least where my algorithm is concerned.
But I need to know what is the max value I can use for a seed? Is it an unsigned 32bit integer? 4,294,967,295?
If so, then my idea is to create a hash using the CRC-32 method, which happens to produce results (in HEX) that are unsigned 32bit integers.
So if those numbers are compatible with each other, I just need to figure out how to get a CRC-32 hash in TGB. :)
05/22/2008 (1:07 am)
Thank you both for your willingness to provide suggestions and help.You're right. If I never call setRandomSeed() again, it will indeed be more satisfying from a non-pattern perspective. But I need to be able to generate specific numbers each time, but in a non-specific order. As such, I need to use many different seeds based on the perhaps 100 million different solar systems that will be in the game.
Obviously with 100 million different solar systems, I don't want to generate them all at once and store the information in a database. So I'm trying to figure out a method in which I can generate only the ones I need, on the fly, and on a need-to-know basis.
As such, I honestly can't see how I can just "seed once, seed well" for this particular instance. As I said, I'm a complete noob in this area so what better methods may be obvious to you are apparently not obvious to me.
However, I think I've come up with a solution (that I haven't implemented yet and am not quite sure how to implement) that would work at least where my algorithm is concerned.
But I need to know what is the max value I can use for a seed? Is it an unsigned 32bit integer? 4,294,967,295?
If so, then my idea is to create a hash using the CRC-32 method, which happens to produce results (in HEX) that are unsigned 32bit integers.
So if those numbers are compatible with each other, I just need to figure out how to get a CRC-32 hash in TGB. :)
#7
I do see what you are trying to do here, but without knowing exactly why you care about the pattern, I don't know how to help much better.
From what I see in your example, theoretically, you shouldn't care if two adjacent galaxies have an off-by-one seed, as the string provided by the random sequence based off of each seed will be quite different from each other, even if the seed numerically adjacent.
One note though, use a static number for your master seed that can be referenced as a seed for generating seeds for each new galaxy, that way the results are the same every time you run the game (assuming that's what you want).
On another note... test on all platforms... if Torque uses the OS random fuctions, you will have different results on different OS's.
If you are releasing multi-platform and you want consistancy between the platforms, you are going to have to step away from random and go with hashing algo and pre-genned key table.
05/22/2008 (1:50 am)
@DeozaanI do see what you are trying to do here, but without knowing exactly why you care about the pattern, I don't know how to help much better.
From what I see in your example, theoretically, you shouldn't care if two adjacent galaxies have an off-by-one seed, as the string provided by the random sequence based off of each seed will be quite different from each other, even if the seed numerically adjacent.
One note though, use a static number for your master seed that can be referenced as a seed for generating seeds for each new galaxy, that way the results are the same every time you run the game (assuming that's what you want).
On another note... test on all platforms... if Torque uses the OS random fuctions, you will have different results on different OS's.
If you are releasing multi-platform and you want consistancy between the platforms, you are going to have to step away from random and go with hashing algo and pre-genned key table.
#8
I don't really care about the pattern as long as they're all unique.
I guess I just question how unique they would truly be, because the pattern is so easily visible in a small scale test, when you've got 1 million of them to go through. If they're off-by-one, how many iterations does it have to go through before there are duplicates?
Just kind of a what-if. But it makes me nervous just the same. :-)
The master seed does have a static number that is referenced. It's the baseSeed when the universe is created.
Yeah, I considered the possibility of different results for cross-platform compatibility. Not sure what to do with that. Unless my CRC-32 hash idea is consistent on all platforms.
05/22/2008 (2:02 am)
Brian,I don't really care about the pattern as long as they're all unique.
I guess I just question how unique they would truly be, because the pattern is so easily visible in a small scale test, when you've got 1 million of them to go through. If they're off-by-one, how many iterations does it have to go through before there are duplicates?
Just kind of a what-if. But it makes me nervous just the same. :-)
The master seed does have a static number that is referenced. It's the baseSeed when the universe is created.
Yeah, I considered the possibility of different results for cross-platform compatibility. Not sure what to do with that. Unless my CRC-32 hash idea is consistent on all platforms.
#9
I was skimming through my copy of the 1st volume of the Game Programming Gems and it actually has a decent chapter that analyses concepts quite close to what you are wanting to do with a retrospecive look back to Elite. I know it doesn't help with the patern issue you are seeing but it still might be worth a skim if you can find a copy. (I love that book series, but they are pricey).
06/05/2008 (7:27 am)
Deozaan,I was skimming through my copy of the 1st volume of the Game Programming Gems and it actually has a decent chapter that analyses concepts quite close to what you are wanting to do with a retrospecive look back to Elite. I know it doesn't help with the patern issue you are seeing but it still might be worth a skim if you can find a copy. (I love that book series, but they are pricey).
Associate Orion Elenzil
Real Life Plus
i think this might be happening because you're reducing the range of the seed to the range of the output.
if you don't re-seed the generator with the previous output, you should be good.
internally the generator is letting the seed wander through all of 32 bits worth of space,
so resetting it really hurts that.
consider the case where your output range is only two numbers: 1 and 2.
now say the first number generated from the seed 1 is 1 itself (it's got to be either 1 or 2).
then clearly when you re-seed with 1 you will never get a 2.
the best you can do in that situation is a cycle of period 2: 1, 2, 1, 2, 1, 2, ...
generally you only seed a random number generator once during the entire session of your application.