Author Topic: I don't understand random seeds.  (Read 37293 times)

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: I don't understand random seeds.
« Reply #15 on: March 06, 2014, 03:34:13 PM »
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.

Eben

  • Rogueliker
  • ***
  • Posts: 339
  • Karma: +0/-0
  • Controversializer
    • View Profile
    • SquidPony!
Re: I don't understand random seeds.
« Reply #16 on: March 06, 2014, 03:35:18 PM »
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.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #17 on: March 06, 2014, 03:39:03 PM »
Very often the RNG needs to be deterministic.

How so? I don't need that feature in my roguelike games.

miki151

  • Rogueliker
  • ***
  • Posts: 264
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #18 on: March 06, 2014, 04:06:03 PM »
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.
KeeperRL, Dungeon Keeper in roguelike style:
http://keeperrl.com

chooseusername

  • Rogueliker
  • ***
  • Posts: 329
  • Karma: +0/-0
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #19 on: March 06, 2014, 07:34:25 PM »
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.

sokol815

  • Rogueliker
  • ***
  • Posts: 85
  • Karma: +0/-0
  • Web Developer by Day, still Web Developer by night
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #20 on: March 07, 2014, 02:45:56 PM »
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) or very simple:

JavaScript:
Code: [Select]
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.
« Last Edit: March 07, 2014, 06:30:31 PM by sokol815 »

Zireael

  • Rogueliker
  • ***
  • Posts: 604
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #21 on: March 07, 2014, 04:35:37 PM »
Random seeds are something I am considering for future versions of VotE, so I'm keeping an eye on this thread.

ekolis

  • 7DRL Reviewer
  • Rogueliker
  • *
  • Posts: 186
  • Karma: +0/-0
  • get ye dennis
    • View Profile
    • Ed's home page
    • Email
Re: I don't understand random seeds.
« Reply #22 on: March 07, 2014, 07:26:40 PM »
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.
The Ed draws near! What dost thou deaux?

>EAT SANDVICH

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #23 on: March 07, 2014, 09:44:36 PM »
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.

TheCreator

  • Rogueliker
  • ***
  • Posts: 370
  • Karma: +0/-0
    • View Profile
    • Fame
    • Email
Re: I don't understand random seeds.
« Reply #24 on: March 08, 2014, 09:10:55 AM »
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.
Fame (Untitled) - my game. Everything is a roguelike.

Frednotbob

  • Newcomer
  • Posts: 1
  • Karma: +0/-0
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #25 on: March 20, 2014, 07:29:21 AM »
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.

requerent

  • Rogueliker
  • ***
  • Posts: 355
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #26 on: March 20, 2014, 08:14:45 AM »
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.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #27 on: April 04, 2014, 06:35:24 PM »
Lol. Krice is such a troll.

I don't need a deterministic RNG. I need just a RNG.

sokol815

  • Rogueliker
  • ***
  • Posts: 85
  • Karma: +0/-0
  • Web Developer by Day, still Web Developer by night
    • View Profile
    • Email
Re: I don't understand random seeds.
« Reply #28 on: April 04, 2014, 07:43:19 PM »
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!

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: I don't understand random seeds.
« Reply #29 on: April 04, 2014, 10:05:31 PM »
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.