Temple of The Roguelike Forums
Development => Programming => Topic started by: jasonpickering on March 05, 2014, 05:36:03 PM
-
Can anyone explain seeds to me? I don't understand how people use it to generate random stuff. I use flash and I am not sure if it depends on language or not. I figure the best example might be something similar. Let's say I have two monsters. How does the seed effect the monster selection.
-
Seeds are used to give a specific starting point to the number generator, which given the same seed will always generate the same set of numbers. This is useful for both testing randomized code by effectively freezing the randomness and making it deterministic and useful for doing things like sharing Dwarf Fortress worlds by only sharing the seed needed to make them.
The word "random" is misleading, there is no such thing as random in computing and even getting close is typically a waste of effort and a lot of effort.
-
I still don't understand why people bother writing "more perfect" RNG algorithms when they could just take some sort of sensor and attach it to the computer and use environmental noise. Heck, most computers these days have built-in fan speed and CPU temperature sensors - surely taking the least significant bit of that data and aggregating it over time could produce something useful?
-
Say, you are programming a space exploration game, and there must be 10K stars with planets or so. Instead of storing each star system, you store a single integer, the seed, for each of them, and when your ship visits the star system, you generate the system from the seed:
initialize_pseudo_random_number_generator(seed);
star_system = generate(); the seed uniquely determines the state of the PRNG, so every time you visit this star system, the PRNG will generate the same sequence of random numbers, and therefore the generated star system will allways look the same.
Optionally, if you PRNG permits that, you can do the following:
state = save_state_of_PRNG();
initialize_PRNG(seed);
star_system = generate();
restore_state_of_PRNG(state);
So, the usage of the random seed is limited to the 'generate' function call, and does not affect the subsequent commands.
On the downside, it's better to use seeds for things that cannot be easily changed by player's actions. This is why I gave an example with star systems. But they also can store landscapes, proceduraly generated textures, or things like this.
-
Pseudorandom number generators generate exactly the same output sequence when they get the same seed on input. This has both good sides (provide the same seed and input, and the system will behave exactly in the same way) and bad sides (if you are trying to randomly generate a key for your cryptography system, the adversary could break your cipher by trying all the possible seeds). In roguelikes, the first is usually a good thing (many games have an option of providing a "seed" to the generator, which allows two player to play in exactly the same dungeon; another use is that a game could be recorded by just recording the seed and the input), but there are potential cases where this is a problem (in an online tournament, the player could submit the layout of the first dungeon level to a program, which would try all the possible seeds and find one which matches this layout, and give the player an option to "predict" or even influence all the future dice rolls, or cheat in some other way).
I agree that the word "random" is misleading here (use "pseudorandom"), but there are better ways of generating randomness than using pseudo-RNGs (use the environmental noise collected from device drivers), and good sources of randomness are very useful in cryptography.
-
I still don't understand why people bother writing "more perfect" RNG algorithms when they could just take some sort of sensor and attach it to the computer and use environmental noise. Heck, most computers these days have built-in fan speed and CPU temperature sensors - surely taking the least significant bit of that data and aggregating it over time could produce something useful?
Often the "more perfect" part is actually "more cryptographically secure" which has more to do with what happens after the seed is obtained, in addition to the parameters of the seed itself.
Traditionally the sensor used to "randomly" seed prngs is the system clock.
For games with no competitive stakes, the default non-cryptographic prngs are fine, even if they give slightly clustered results in some cases.
+1 to koiwai's example as an in-game great use for the seed value
-
Writing a custom rng could be interesting. Although I'm not that good in those kind of algorithms..
Btw, can someone explain why rand() is giving the same number when I use a command (in Teemu) that doesn't use a turn, but if another message is output and I try the same command it returns a different value. I don't understand what is going on. Shouldn't rand() return a (pseudo)random number each time it's called?
-
Often the "more perfect" part is actually "more cryptographically secure" which has more to do with what happens after the seed is obtained, in addition to the parameters of the seed itself.
Traditionally the sensor used to "randomly" seed prngs is the system clock.
Well, yeah, but I'm not talking about taking a single seed and feeding it into an algorithm and never getting a new seed - I'm talking about using some unpredictable environmental input as input for a function which determines your random number. In essence, re-seeding the RNG with a new (but truly nondeterministic) input constantly.
-
ekolis:
At least in scinetific applications (and probably in crypto-), good PRNG gives you some guarantees about the distribution of the generated sequence of numbers. They also runs quickly. Many simulation techniques (like Gillespie algorithm) use a lot of random numbers, so speed is important. Hardware sensors, in general, don't give you such guarantees about their data. They can be slow too.
Krice:
rand() returns the same number several times in a row?
-
rand() returns the same number several times in a row?
When I think it harder it must be a bug in the message routine, because it's checking duplicate messages and exits when . is found, but in this case the message has two parts.
-
Okay so using my previous example of two monsters how would I write it in logic steps to make it choose one or the other.
Is it have it choose a random number, then assign each monster to one of those numbers?
-
Rand() takes the next number from the RNG sequence, which will typically be integers from 0 to MAX, or floats from 0 to 1. If you have a dice table with options 1 to 6, then you can compress the result of rand() into the set of results you want. For instance with (rand()%6) + 1 or floor(rand()*6)+1. Then you feed it into the dice table:
- 1-2: tomato monster
- 3-5: marmite monster
- 6: cookie monster
- Seed the random number generator
- Use RNG functions to generate the first monster
- Use RNG functions to generate the second monster
Steps 2 and 3 are very flexible and you've seen a lot of options for them in your other thread. Most of the options for generating a monster will call rand() once, so the Nth monster generated will be based on the Nth number from the RNG sequence (assuming that nothing else calls rand()).
As it says above, the same RNG seed means the same sequence of results from rand(), and that means the same monsters chosen.
-
I still don't understand why people bother writing "more perfect" RNG algorithms when they could just take some sort of sensor and attach it to the computer and use environmental noise. Heck, most computers these days have built-in fan speed and CPU temperature sensors - surely taking the least significant bit of that data and aggregating it over time could produce something useful?
What about portability? Most of smartphones don't have fans. I'm not sure about sensors, but it doesn't sound like a portable solution, either. Telling people that the game doesn't run on a computer without some piece of hardware just because the programmer doesn't know how to implement a good RNG is kind of lame, don't you think? :)
-
Very often the RNG needs to be deterministic.
-
Okay, so I basically need to figure out how to set the Seed for the RNG then any rand functions that come from it will always be the same. (I may need to test this out on some small tests). I would love if I could save a 6 digit number and always have the same world.
-
I think most of your games have deterministic mechanics so it might not affect you, but it's worth remembering that if you change the sequence of calls, you get a different result.
For instance, imagine if a drunk pirate has a call to rand() in its AI routine to decide where it moves.
The first time you play, you set seed 710 77345, generate level 1, kill a drunk pirate after 10 moves, and then generate level two.
The second time you play, you set seed 710 77345, generate level 1, kill a drunk pirate after 8 moves, and then generate level two.
Level 1 will be the same both times, but while playing level 1, you called rand() either 10 or 8 times. That means when you generate level 2, you'll be at different steps in the RNG sequence and level 2 will be different. There are ways around this - you can use separate RNGs for level generation and gameplay, you can save the RNG state after generating a level and reload it later, and you can use the initial seed to choose one seed per level at the start of the game. Or you can make everything apart from level generation (even visual effects) deterministic.
-
Okay, so I basically need to figure out how to set the Seed for the RNG then any rand functions that come from it will always be the same. (I may need to test this out on some small tests). I would love if I could save a 6 digit number and always have the same world.
You'll always get the same sequence if you do the same type of calls in the same order. Be careful about taking user input and doing a random call with it that could change.
-
Very often the RNG needs to be deterministic.
How so? I don't need that feature in my roguelike games.
-
One reason is for debugging, it's easier to recreate a bug if you can regenerate the same world. Especially if you couple that with saving user input. You can basically take a game that crashed and rerun it on your computer in a debugger. Extremely helpful, though it can be difficult to keep the game deterministic.
I read a thread somewhere where players were exchanging the seeds of their favorite games in Brogue. That could be another reason.
-
One reason is for debugging, it's easier to recreate a bug if you can regenerate the same world. Especially if you couple that with saving user input. You can basically take a game that crashed and rerun it on your computer in a debugger. Extremely helpful, though it can be difficult to keep the game deterministic.
I read a thread somewhere where players were exchanging the seeds of their favorite games in Brogue. That could be another reason.
WRT Brogue. There are challenges where people give a seed, and then others go away and play it and come back with their score. Also, there are tools where people want to play a game which meets certain conditions, like having a pet gorilla from the first level, and a wand of something or other. So the tool is run which finds a seed which meets that condition, then people can play it. Yes, you can contrive that with a non-deterministic RNG, but you lose the reproducibility and the benefits it provides.
In a client-server game, the seed can be sent to the client and the client can model what happens rather than the server having to tell it every time.
-
multiplayer games (at least the well-made ones) generally use a shared random seed to keep the game in-sync across all clients. This makes it so multiplayer games can pass an initial game state, random seed, and user input instead of passing the original game state and all deltas that occurred (a huge mess and very data heavy). The old Starcraft uses this method (Not sure about the new one, I suspect it is quite similar).
Doing this also gives you built-in cheat detection. While passing input, you also pass a hash of the current game-state. A deterministic game will always generate the same hash for the same timestep on all clients, thus... clients compare timestep hashes, if one doesn't match up, they are cheating and are booted.
Random number generation can be very complex (Mersenne twister (http://en.wikipedia.org/wiki/Mersenne_twister#Pseudocode)) or very simple:
JavaScript:
window.seed = 99480;
//this algorithm takes a seed, squares it, then takes the middle 6 digits as the next random integer & the next seed.
function testRand(max){
var output = window.seed * window.seed; //square the seed
output = output.toString(); //turn the int into a string
output = output.substr(( output.length / 2 ) >> 0 - 3); //cut string in half - 3 characters.
output = output.substr(0,6); //terminate string at 6 characters
window.seed = parseInt(output); //turn string back into an int.
return window.seed % max; //max is the maximum random variable we want, mod keeps the value inside of it.
}
var arr = [];
var maxRand = 10;
for(var x = 0; x < maxRand;x++){
arr.push(0);
}
for(var x = 0; x < 10000;x++){
var res = testRand(maxRand);
arr[res]++;
}
console.log(arr);
//console.log outputs:
//[827, 1089, 1115, 1013, 909, 882, 1144, 1010, 974, 1037]
//this shows it is somewhat uniformly distributed across 0 - 9.
If you are in Chrome right now, you can actually just hit F12, then select the console tab, copy and paste the above code into the console and hit enter. you will see identical results.
-
Random seeds are something I am considering for future versions of VotE, so I'm keeping an eye on this thread.
-
I still don't understand why people bother writing "more perfect" RNG algorithms when they could just take some sort of sensor and attach it to the computer and use environmental noise. Heck, most computers these days have built-in fan speed and CPU temperature sensors - surely taking the least significant bit of that data and aggregating it over time could produce something useful?
What about portability? Most of smartphones don't have fans. I'm not sure about sensors, but it doesn't sound like a portable solution, either. Telling people that the game doesn't run on a computer without some piece of hardware just because the programmer doesn't know how to implement a good RNG is kind of lame, don't you think? :)
Sure, if you're going for portability, then you need something more generic. But it seems like far too much effort is wasted on replicating something that is mathematically impossible to replicate, when in many cases it is available basically for free, without any special mathematical wizardry.
-
Reading noise from devices is obviously much slower than a reasonably efficient rng algorithm.
Besides the reproducibility/determinism benefits of using pseudorandom number generators, high quality random number generation is not really essential to games. Speed may be important, but usually the impressive statistical properties of a typical rng are far beyond what's needed.
-
Sure, if you're going for portability, then you need something more generic. But it seems like far too much effort is wasted on replicating something that is mathematically impossible to replicate, when in many cases it is available basically for free, without any special mathematical wizardry.
Software RNG is good enough for games and not necessarily requires more effort than implementing a hardware-based solution would. Yes, it's a wizardry sometimes, but it can also be a lot of fun.
-
Okay, so I basically need to figure out how to set the Seed for the RNG then any rand functions that come from it will always be the same. (I may need to test this out on some small tests). I would love if I could save a 6 digit number and always have the same world.
This might help. It's a slice from the tutorial code I'm using to build my own game (it uses the libtcod library):
Map::Map(int width, int height)
: width(width),height(height) {
seed=TCODRandom::getInstance()->getInt(0,0x7FFFFFFF); //The 'seed' is simply a pseudo-random number, selected by an ordinary generator. It can be any value (just remove the call to TCODRandom and enter your own number).
}
void Map::init(bool withActors) {
rng = new TCODRandom(seed, TCOD_RNG_CMWC); // 'rng' uses the number generated by 'seed'.
tiles=new Tile[width*height];
map=new TCODMap(width,height);
TCODBsp bsp(0,0,width,height);
bsp.splitRecursive(rng,8,ROOM_MAX_SIZE,ROOM_MAX_SIZE,1.5f,1.5f);
BspListener listener(*this);
bsp.traverseInvertedLevelOrder(&listener,(void *)withActors);
}
//Below is just an overview of how 'rng' is used to generate a room using BSP nodes.
// 'map.rng->getInt' uses the seeded value, along with a couple of other variables, to create rooms of a size somewhere between ROOM_MIN_SIZE and the maximum size of that room's BSP node, and to set the room's x/y coordinates.
w=map.rng->getInt(ROOM_MIN_SIZE, node->w-2);
h=map.rng->getInt(ROOM_MIN_SIZE, node->h-2);
x=map.rng->getInt(node->x+1, node->x+node->w-w-1);
y=map.rng->getInt(node->y+1, node->y+node->h-h-1);
As long as the seed is set to the same number, 'rng' will always create the same BSP tree and generate the same map layout. The call to TCODRandom() in Map::map ensures that the seed will always be different.
-
Very often the RNG needs to be deterministic.
How so? I don't need that feature in my roguelike games.
Lol. Krice is such a troll.
-
Lol. Krice is such a troll.
I don't need a deterministic RNG. I need just a RNG.
-
I don't need a deterministic RNG. I need just a RNG.
Deterministic RNG's make it so much easier to reproduce errors/develop features (because then it is the same game every time you run with the same seed)
It also gives you a nice way to store dungeon levels.
The first thing I did when I started working on my javascript roguelike was to go out and find a deterministic rng algorithm and get it working.
Plus, you can ask the player if they want to play on a specific seed, so they can play the same game their friend is playing, and brag to them about how they are better at it!
It's never too late to take advantage of dRNG's, Krice!
-
Woah, wait a minute. If you can play the same game twice, this means the game does not have permadeath. You can start over with exactly the same game world and if you make the same moves, the same sequence of events will occur. If you die, you can just repeat your game up to a safe number of turns earlier and continue as if nothing happened.
Obviously, this could be automated, but that wouldn't even be necessary in principle.
-
Woah, wait a minute. If you can play the same game twice, this means the game does not have permadeath. You can start over with exactly the same game world and if you make the same moves, the same sequence of events will occur. If you die, you can just repeat your game up to a safe number of turns earlier and continue as if nothing happened.
Obviously, this could be automated, but that wouldn't even be necessary in principle.
that would be if you used the same seeded dRNG for everything....
the way I do this is I create the world off of a seed (whether given or taken from the unix timestamp), then I go back and switch out the RNG with a random seed (unix timestamp)... this then leads to the ability to play the same world with a different in-game-playing seed.
I first use the above seeded dRNG to choose which races and creatures inhabit the world. I then go and reset the dRNG again to the same seed to actually generate the mainworld, and generate arrays of Seeds for each individual dungeon that should be generated.
Say I have 5 dungeons of depth 5, 20, 50, 100 and 40. now I have the main world generated, and I have 5 arrays of corresponding lengths with nothing but an integer seed in them.
When the PC goes to dive into one of those dungeons, the game will swap out the current RNG with the generate world RNG, reseed it with the appropriate generated seed for that level, and generate the dungeon level. It can then swap back to the RNG we were using before and populate the level.
That way you can play the same maps, but the items, danger rooms, enemies and all are different, which will allow your friend to say: "Lucky! I didn't get the dagger of dragon slaying on D3!"
-
Alternatively--
dRNG for items/level/monsters etc, but a weighted RNG for combat, spells, gas propagation, etc.
-
I've got a question about this, actually. What's to stop some mad programmer from seeding a random number generator with a referenced, but uninitialized integer pointer?
For example, what if the programmer wrote something like this:
int *uninitialized_ptr;
seed(*uninitialized_ptr);
Since, technically speaking, the seed function only cares about receiving an integer value, and doesn't generaly use that vlue to reference any other memory locations, I don't think it would break the code. Further, even though technically the RNG would still be deterministic, that determinism would be unreproducible because not even the programmer knew the seed, yes?
Or will this cause something to blow up somewhere in the backlands of Ohio?
-
Dereferencing uninitialized pointers results in "undefined behavior," but it's not random. In principle, you can figure out what values your uninitialized pointers point to before you run the program (though I don't recommend it).
-
Since the pointed memory location of an uninitialised pointer is not specified in the standard, it could point to any memory location - including a location that the operating system won't allow the program to read, or a location outside the range of the computer's memory. Some compilers may warn about the attempt to dereference an uninitialised pointer, and in some modes may convert that warning into an error that prevents compilation. So it's not very likely to run without crashing.
-
Uninitialized variables can be used, a crude example:
unsigned int i, junk[100];
for (i = 0; i < 100 && junk[i] == 0; i++)
;
printf("Seed: %u\n", junk[i]);
Still it is a bad practice, since it relies on undefined behavior. Compiler can optimize it out, which can lead to weird situations. More information: http://kqueue.org/blog/2012/06/25/more-randomness-or-less/
If you want a seed that varies a lot why not ask kernel for entropy instead or at least use clock_gettime(2) function, which provides nanosecond precision?
Some of those issues are addressed by arc4random(3) family of functions. They don't require seeding, they take care of it on its own (reseeding also). One problem here is portability, those functions are native only on *BSD systems and Mac OS X. On Linux they can be found in libbsd library. There are also portable versions of it (working also under Windows I think), one example: https://www.mirbsd.org/a4rcontrb.htm
Function arc4random_uniform(3) is also nice, since it can be used to obtain numbers in a specified range without modulo bias. Possible issue that can occur is performance. Those are cryptography grade PRNGs, so speed is a secondary objective.
-
Oh, cool Melville! So basically, there *isn't* anything preventing us from seeding the rand() function with an uninitialized pointer, but it's likely to make something go boom, am I right? I think I'll look into that clock_gettime() function, actually. It sounds promising.
-
Oh, cool Melville! So basically, there *isn't* anything preventing us from seeding the rand() function with an uninitialized pointer, but it's likely to make something go boom, am I right? I think I'll look into that clock_gettime() function, actually. It sounds promising.
If you are using rand(3), seeding is probably least of your problems. Bad PRNG is still a bad PRNG, no matter how good the seed is. Even when you are using a better PRNG like Mersenne twister, time(3) is good enough in most cases - what matters is uniqueness of the seed across games. I would be more worried about a modulo bias than seed itself.
ASLR (Address space layout randomization) is used by mmap(3) on most systems, I wonder if it could be abused as a part of a seed? Still this is over complicating things in my opinion.
Example showing differences between time(3) and clock_gettime(2).
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long int give_seed(void);
int
main(void)
{
int i;
for (i = 0; i < 20; i++)
printf("Seed: %ld\t%lld\n", give_seed(),
(long long) time(NULL));
return EXIT_SUCCESS;
}
long int
give_seed(void)
{
struct timespec ts;
(void) clock_gettime(CLOCK_REALTIME, &ts);
return (ts.tv_sec ^ ts.tv_nsec);
}
I forgot to mention that arc4random(3) is non-deterministic, entropy is injected multiple times, since it is geared toward cryptographic applications. That could be a wrong usage case for roguelike, depending on your needs.