Random values gives a pattern ...
Blitz3D Forums/Blitz3D Programming/Random values gives a pattern ...
| ||
| I need some help in understanding this : - I have a table with cells. - Using the cells coordinates, I generate a unique RndSeed (no other cell can have the same). - Using the unique cell RndSeed, I decide if the cell has a value, and what is that value - I draw the results. Running the following simplified code, as you can see there's a pattern appearing. Not only that but the values in the cells also arent random. I dont understand how this could happen since all RndSeed are uniques, and both the fact a cell has a value or not and the value itself are 'randomly' decided. Also, the pattern is clear but not perfectly regular. Can someone bring me light on this problem ? Graphics 600,600,16,2 Type cell Field x,y Field seed Field value End Type Function add_cell(x,y) c.cell = New cell c\x = x : c\y = y ;set seed / cumulate cell coordinate so no pair of coordinates will ever have the same seed sx$ = Str(x) sy$ = Str(y) While Len(Str(Abs(x))) > Len(Str(Abs(x))) sy = "0"+sy Wend ; making sure the x and y strings are the same length to avoid generating possible duplicates seeds While Len(Str(Abs(y))) > Len(Str(Abs(y))) sx = "0"+sx Wend ; If x >= 0 sx = "1"+sx Else sx = Replace (sx,"-","2") If y >= 0 sy = "1"+sy Else sy = Replace (sy,"-","2") my_seed = seed_biome + Int(sx+sy) c\seed = my_seed ;db "x y " + x + ","+ y + " m " + my_seed ;1 chance out of 4 assign a value to the cell SeedRnd my_seed ; using the unique cell seed k = Int(Rnd(3)) If k = 1 k = Int(Rnd(100)) ; still using the unique cell seed c\value = k End If End Function ; create the cells For x = -20 To 20 For y = -20 To 20 add_cell(x,y) Next Next ; draw the cells SetBuffer BackBuffer() For c.cell = Each cell Color 0,150,0 Rect (c\x*15)+300,(c\y*15)+300,14,14,1 If c\value > 0 Color 255,255,255 Text (c\x*15)+307,(c\y*15)+307,c\value,1,1 End If Next Flip While Not(KeyHit(1)) Wend End |
| ||
| - Using the cells coordinates, I generate a unique RndSeed (no other cell can have the same). - Using the unique cell RndSeed, I decide if the cell has a value, and what is that value Remove these steps. The random number generator is only supposed to be seeded once, or to reset it to a particular state. Calling Rnd() will also set the seed value ready for the next time Rnd() is called. By manually forcing the seed values, you're actually breaking the random number engine (since it is entirely reliant on the above fact to work at all). Especially since the value is based on the cell coordinates to ensure the numbers have certain properties: there's nothing random about this system whatsoever. Last edited 2011 |
| ||
Not quite sure what you're trying to do with all the string stuff but the loops...While Len(Str(Abs(x))) > Len(Str(Abs(x))) sy = "0"+sy Wend ; making sure the x and y strings are the same length to avoid generating possible duplicates seeds While Len(Str(Abs(y))) > Len(Str(Abs(y))) sx = "0"+sx Wend ; ...will never iterate since the conditions can never be true. |
| ||
| big10p > oops, typo. Thanks for noticing it. Also, that code is indeed retarded as the string lengthened is not the string used for lenght comparison. I guess im not fully awaken. Anyways, it was supposed to be len(x) > len(y) and the other way arround. The point is to convert coordinates like -4,309 to 004,309. The +/- sign being placed back on the next 2 lines in form of "1" or "2", giving 2004,1309. Yasha > Then how can I attribute a stable rndseed to each cell ? In the full project, my goal is to generate a map based on a seed, however all cells are not loaded at once (sort of streaming) so other rnd() calls might have been made meanwhile. Also im not sure to understand your explanation. I tought that two different rndseeds would give different results for sure ... Last edited 2011 Last edited 2011 |
| ||
Here's some code that does what you want it to do:Graphics 600,600,16,2 ;seed the random number generator with the current time (different every time the program is run) Global global_seed = MilliSecs() Type cell Field x,y Field seed Field value End Type Function add_cell(x,y) c.cell = New cell c\x = x : c\y = y SeedRnd global_seed For i=1 To Abs(x*100+y) Rnd(3) Next ;1 chance out of 4 assign a value to the cell k = Int(Rnd(3)) If k = 1 k = Int(Rnd(100)) ; still using the unique cell seed c\value = k End If End Function ; create the cells For x = -20 To 20 For y = -20 To 20 add_cell(x,y) Next Next ; draw the cells SetBuffer BackBuffer() For c.cell = Each cell Color 0,150,0 Rect (c\x*15)+300,(c\y*15)+300,14,14,1 If c\value > 0 Color 255,255,255 Text (c\x*15)+307,(c\y*15)+307,c\value,1,1 End If Next Flip WaitKey End Now, to explain the pattern, it's time for some fun maths! The way the random number generator works is that it stores a seed number, and every time you call Rand(0,x), it does the following: - the "random" number is (x-(seed Mod x)), that is, calculate the remainder when you divide the seed by x, then subtract that from x. - Now do something complicated to the seed, such as multiplying it by a big number, taking that modulo another number, and so on. Store that as the new seed number. The "do something complicated" bit is what makes the numbers produced seem random - the pattern connecting seed numbers is so complicated it looks like there's no pattern. - return the "random" number. To see that this is true, run this code: For c=1 To 12 SeedRnd c n=Rand(4) Print Str(c)+": "+Str(n) Next Note how, although each time I ask for a random number with a different seed, there's a pattern. Because you're setting the seed each time you want a random number, the "do something complicated bit" never happens, so the randomness depends on how you make your seeds. Let's look at how you make your seeds First of all, let's look at the row where y=1. x = "1"+Str(x), so if x=1, sx="11". If x=12, then sx="112". So if x has one digit then sx=10+x, and if it has two digits sx=100+x. Because y=1, sy="11". As sy has two digits, the string sx+sy is the same as the number 100*Int(sx)+Int(sy). This is the seed you then use to make a random number. Now modular arithmetic comes in to play. To decide whether a cell gets a value or not, you say k=Int(Rnd(3)). So k is (3-(my_seed Mod 3)). But my_seed = sx*100+sy = (10+x)*100+11, when x<10. Because of the way modular arithmetic works, I can take all the numbers Mod 3 and get the same result. 100 Mod 3 is 1, 10 Mod 3 is 1, and 11 Mod 3 is 2. my_seed Mod 3 = ((1+x)*1+2) Mod 3 = (x + 3) Mod 3 = x Mod 3. So the "random" number is just x Mod 3! So you should see that k=1 on every third cell. And that's what you do see:  So that's where the pattern comes from! If you wanted you could do a bit more complicated maths to see where the pattern in the y-direction comes from, but I think I've already made my point. Notice that the pattern breaks down when y>=10, that is, when it has more than one digit:  Last edited 2011 Last edited 2011 |
| ||
| *beaten to it by Warpy the Resident Genius* Last edited 2011 |
| ||
| Wow, thank you for the detailed explanation. I think i got most of it. If i got it right, my logic wasnt too bad but the mathematics of how the rndseed works does not allow this. The example you provided works, but is not exactly what i am looking for : - I want the map to be the same everytime i start the game, assuming the player uses the same "MapSeed" (not included in the exemple for simplification) - The map is virtually limit-less so I cannot generate all the cells at once. So when I need to load a specific cell, the rnd function might have been called alot hence making the cell content not the same every time the players run the game. - So I need to set the cell's random seed to the same value at the moment I load the cell so I can generate the "same random" content in it everytimes the players come nearby. Any idea how I could do that ? Again, thanks for taking so much time with the detailed explanation. |
| ||
| You can access the current seed with the RndSeed() function, to store in a variable and later set it back with SeedRnd. This lets you break off and use Rnd in between creating cells without changing the results, assuming you otherwise would have wanted them to be sequential. I don't think this is actually what you need, however. The best suggestion I can come up with is that you use a tiered-system similar to LOD for large terrains, because any other way of doing what you want would likely still not be making much use of random numbers. Essentially, divide your total world into say a hundred areas. Generate a random number for each area sequentially, and store this in a top-level "world" list (or don't, since what you really need is the seed and the index of the iteration for each area). Within each area are a hundred sub-areas. Set the seed to the area-value, and generate a random number for each sub-area. Within each sub-area are a hundred sub-sub-areas... etc, until we reach your desired level of detail. Each time your player changes cells (or however this game engine works), if the content hasn't been loaded, you can simply work down the world-tree until you get the array of random values for that sub-sub-sub-...-sub-sub-area. In theory you could do recalculate this each time from the world-seed just by using the area co-ordinates. This still keeps breaking the random-number-generator's seed chain, but because of the large areas, the effect will be mitigated and hopefully not noticeable. (You can make them bigger than a hundred to make it less noticeable, that's just an easy number to visualise.) It also doesn't insert seed values that have any obvious connection to their position in the sequence, which again should make it less noticeable. The other thing to note is that under this system, the world can be arbitrarily large, but not infinite - you need to know what the maximum extents will be in advance (making it "big enough" should be very easy though). Getting predictable values from an infinite world is certainly possible, but I don't think it can be done anywhere near as easily. Last edited 2011 |
| ||
| The code I gave will do that, if you change global_seed to a constant, instead of MilliSecs() |
| ||
| Warpy > oh sorry i misread it. However the line For i=1 To Abs(x*100+y)will do as many iterations for x = 0, y = 100 and x = 1, y = 0, hence giving the same result and an unwanted repetition in the map. Its a rather rare occurence, but since a cell can contain a very rare entity, you could end up with having a "very rare" entity every 100 cells. I was thinking about using that "bruteforce" method, with my original int mixing thing, however if the players reaches someplace like +999,+999 it gives me 19991999 / which is about 20 millions iterations to get to the wanted random number. Takes more than half a second on my compt, and since cells can be loaded about ten at once its just not an acceptable delay for "seamless streaming". I guess I have to think of a more elaborate structure as Yasha describes. Last edited 2011 |
| ||
ok, replace (x*100+y) with (If x>0 sx=2*x Else sx=-2*x+1 If y>0 sy=2*y Else sy=-2*y+1 pair = (sx+sy)*(sx+sy+1)/2+sy I can't see a way to give the proper randomness you want without loads of applications of Rnd. You could precache the seed after every 1000th iteration of Rnd when the program starts, up to a reasonable limit, and that way you'd only ever have to do at most 1000 iterations for a single cell. |
| ||
| Hey, that seed precache sounds good. I might try that. Right now what am i doing is that when theres too many iterations to do, I cut the number of iteration and shift the resulting random value to get a different integer ( 31.510855 becoming 15.10855 ) |
| ||
| I can't see a way to give the proper randomness you want without loads of applications of Rnd. That's why I use the following: Function SuperSeedRnd();Yes, "super seed" is a pun on "supersede." XD
If Rand(50) = 50;1 in 50 chance of reseeding, or 2%
SeedRnd (MilliSecs() + Rand(1000) * Rand(Rand(-50,50)) / (Rand(-1359,5438) + Rand(-7689,1235))
EndIf
End FunctionLudicrously obfuscated, I defy all but a genius mathematician with an MIT supercomputer to find patterns there. XD The best part is that this function goes at the beginning of your main loop, like: While Not KeyHit(1) SuperSeedRnd Cls ;All your code are belong to here Flip Wend End Then, at the beginning of each main loop, there's a 1 in 50 chance that the random generator will be re-seeded. Tadaaa! :D |
| ||
| Adam - just MilliSecs() would do there and give the same effect. The first time you call SuperSeedRnd, because the seed is still the default one until you have actually called SeedRnd, those Rand calls are effectively constant numbers. Calling SeedRnd just once with a properly random number (like MilliSecs) is enough to get properly random numbers. Doing it again won't make your numbers any more random. What we're discussing here is a way of *not* getting random numbers - Sacha wants to make it so the same tiles get the same values every time you run the program, but with no discernible pattern to their distribution. |
| ||
| Oh, herp derp; sorry 'bout that. I didn't realize we were talking static seeds here, guess I didn't read the thread closely enough. Erm, just ignore me. ^^; Last edited 2011 |
   |