I want this to happen 1 in every 10 times. Generate a random number n, from 1 to 10. Return true on the nth time. Return false the other 9 times. After the 10th try, generate a new random number.
Thus, the special effect on a weapon or such activates 1 in 10 times, always, but he can't predict WHEN it'll happen (for the most part).
I built a simpler system (mostly math based) a few years back that is based on what Ian said above. The basic concept is that with a 1/5 drop rate, players really expect the first kill to be 1/5 and if they fail, the second to be 1/4 and if they fail again, the third to be 1/3. If you set up your drop rates in fraction form, remove the numerator from the denominator for each attempt, and add the initial denominator to the current denominator on each success you will have a (roughly) guaranteed 1 success for every 5 attempts. It is even easy to scale down, guaranteeing 2 successes for 10 attempts (50% power) or 20 successes for 100 attempts (5% power).
There are some more little fiddly things that need to be handled but the implementation is cheap both in storage and processing and is scalable.
permutation is a bit subtle to do well; if you just use Quantum's naive implementation, you can still get 2-in-a-row, although it only happens 1 in 1000 times (100 sets of 10), and you can get 18 in a row of misses (also 1 in 100 sets of 10).
If those happen to be acceptable rates for those events, then you can use the naive solution, but most likely you don't want that.
The non-binary cases are much more interesting and overt to talk about. If you have 10 voice tracks you can play in reaction to event E, and you always have to play them, and you think you want to play them at random...
Zeroeth solution: at each event, just play the next recording in order, and then repeat when you run out. "But that's not random!"
First solution: pick one at random, it has repeats and sounds dumb
Second solution: some complicated scheme where you deprioritize recent ones. Still repeats more than you want, or too hard to tune.
Third solution: randomly permute the 10 elements, do 10 events, randomly permute again. Problem: can still get repeats across premutation boundaries.
Fourth solution: Randomly choose one permutation once. Just play that permutation over and over forever, guaranteeing it's always 9 events until you hear the same one again.
Fifth solution: Randomize the order offline, so everyone always gets the exact same "random" order. This is identical to the 0th solution.
Problem with four and five: people may notice that the order repeats, that they'll always hear a given one after another given one. I've never heard that complaint, but that seems to be the only reason to move onto the next solution (although plenty of people have moved onto it):
Sixth solution: pick a random permutation. Play through it. Now, do small local swaps on the permutation to build the new permutation, guaranteeing that each event is, say, no less than 7 or 8 distant and no more than 12 or 13 distant from their previous usage.
Note that the last solution is very similar in behavior to one where you track "how long has it been since I last used this one" and then you only choose from the ones that have been at least 7 ago and with increasing priority as they get above 10.
I've definitely heard of people doing things along the line of these last two solutions.
"Problem with four and five: people may notice that the order repeats, that they'll always hear a given one after another given one. I've never heard that complaint,"
Yeah I certainly notice this and there are plenty of cases where it's definitely not okay. Like maybe it's okay for dialogue sequences (because that's sort of weird and gamey anyway, so it's okay if it's just a sequence), but if you used it for gun shot or footstep sounds, the pattern would be very obvious.
"Second solution: some complicated scheme where you deprioritize recent ones. Still repeats more than you want, or too hard to tune."
This is what I propose here; it's really not that complicated and has no disadvantages that I know of (other than yes, being slightly unintuitive to tweak; probably that could be fixed by exposing the tweak parameters in a more designer-friendly way and doing some math to convert).
I think basically all other options have disadvantages or are harder to tweak and implement. (eg. the complicated permutation that you suggest at the end could be made equivalent of course but seems much harder to get right)
Very interesting. I will implement it in my fighting engine. You can follow me at http://kokusaifightingengine.blogspot.com/
October 6, 2010 at 1:24 AM
I'm sure I've talked to people about this many times but I don't think I've ever written it up. Anyway,
here's one from the files of game developer arcana. I'm sure this is common knowledge, but one of those
things that's too trivial to write an article about.
When you use random numbers in games, you almost never actually want random numbers. Rather you want
something that *feels* sort of random to the player. In particular the biggest difference is that real
random numbers can be very bunchy, which almost always feels bad to the player.
Common cases are like random monster spawns or loot drops. It's really fucking annoying when you're
trying to cross some terrain in an Ultima type game and you get unlucky with the random number generator
and it wants to spawn a random encounter on every single fucking tile. Or if you're killing some mobs
who are supposed to drop a certain loot 1 in 10 times, and you kill 100 of them and they don't fucking
drop it because you keep getting unlucky in rand().
What we want is not actually rand. If you design a monster to drop loot roughly 1 in 10 times, you want
the player to get it after 5 - 20 kills. You don't really want them to get it on first kill, nor do you
want them to sit around forever not getting it.
In all cases, to do this what we need is a random generator which has *state* associated with the event.
You can't use a stateless random number generator. So for example with loot drop, the state remembers
that it has dropped nothing N times and that can start affecting the probability of next drop. Basically
what you want to do for something like that is start with a very low probability to drop loop (maybe even 0)
and then have it ratchet up after non-drop. Once the loot is dropped, you reset the probability back to 0.
So it's still random, but a more controllable experience for the designer.
Now, this state generally should decay in some way. That is, if you kill mobs and get no loot and then go away
and do a bunch of stuff, when you come back it should be back to baseline - it doesn't remember what happened
a long time ago. And then the next important issue is how does that state decay? Is it by time or by dicrete
events? Whether time or event driven makes the most sense depends on the usage.
The simplest version of a stateful semi-random generator is simply one that forbids repeats. Something like :
int Draw()
{
for(;;)
{
int i = RandMod(m_num);
if ( i != m_last )
{
m_last = i;
return i;
}
}
}
which is an okay solution in some cases. But more generally you want to not just forbid repeats, rather allow
them but make them less likely. And for N-ary events you don't just care about the last one, but all
the last ones.
A simple binary stateful semirandom generator is like this :
int Draw()
{
Tick();
float p = frandunit() * ( m_p0 + m_p1 );
if ( p < m_p0 )
{
m_p0 -= m_repeatPenalty;
m_p0 = MAX(m_p0,0.f);
return 0;
}
else
{
m_p1 -= m_repeatPenalty;
m_p1 = MAX(m_p1,0.f);
return 1;
}
}
You should be able to see that this is a simple weighted coin flip and we penalize repeats by some
repeat parameter. Here we have introduced the idea of a Tick() - the tick is some function that
push the probabilities back towards 50/50 , either by time evolution or by a fixed step.
More generally you want N-ary with various parameters. Here's some code :
//-----------------------------------------------------------
class WeightedDecayRand
{
public:
// redrawPenalty in [0,1] - 0 is a true rand, 1 forbids repeats
// restoreSpeed is how much chance of redraw is restored per second or per draw
explicit WeightedDecayRand(int num,float redrawPenalty,float restoreSpeed);
~WeightedDecayRand();
int Draw();
void Tick(float dt);
int DrawFixedDecay();
int DrawTimeDecay(double curTime);
private:
int m_num;
float * m_weights;
float m_redrawPenalty;
float m_restoreSpeed;
float m_weightSum;
double m_lastTime;
FORBID_CLASS_STANDARDS(WeightedDecayRand);
};
//-----------------------------------------------------------
WeightedDecayRand::WeightedDecayRand(int num,float redrawProbability,float restoreSpeed) :
m_num(num),
m_redrawPenalty(redrawProbability),
m_restoreSpeed(restoreSpeed)
{
m_weights = new float [num];
for(int i=0;i < num;i++)
{
m_weights[i] = 1.f;
}
m_weightSum = (float) num;
}
WeightedDecayRand::~WeightedDecayRand()
{
delete [] m_weights;
}
int WeightedDecayRand::Draw()
{
float p = frandunit() * m_weightSum;
for(int i=0;;i++)
{
if ( i == m_num-1 || p < m_weights[i] )
{
// accepted !
m_weightSum -= m_weights[i];
m_weights[i] -= m_redrawPenalty;
m_weights[i] = MAX(m_weights[i],0.f);
m_weightSum += m_weights[i];
return i;
}
else
{
p -= m_weights[i];
}
}
}
void WeightedDecayRand::Tick(float dt)
{
m_weightSum = 0;
for(int i=0;i < m_num;i++)
{
if ( m_weights[i] < 1.f )
{
m_weights[i] += dt * m_restoreSpeed;
m_weights[i] = MIN(m_weights[i],1.f);
}
m_weightSum += m_weights[i];
}
}
int WeightedDecayRand::DrawFixedDecay()
{
int ret = Draw();
Tick( 1.f );
return ret;
};
int WeightedDecayRand::DrawTimeDecay(double curTime)
{
if ( curTime != m_lastTime )
{
Tick( (float)(curTime - m_lastTime) );
m_lastTime = curTime;
}
int ret = Draw();
return ret;
};
//-----------------------------------------------------------
"09-06-10 - WeightedDecayRand"
12 Comments -
I found that when people ask for a random events, what they really want is a permutation of those events happening.
So a 1/10 loot drop becomes (literally) one loop drop for every 10 - not an independent 10% chance with each drop.
September 9, 2010 at 6:47 PM
"In particular the biggest difference is that real random numbers can be very bunchy, which almost always feels bad to the player. "
This is why I come here. To read intelligent thoughts. Feels like founding a clear water fountain in the Fallout3 wasteland !
September 9, 2010 at 7:44 PM
The formal, signal-processing way to think about it is:
http://en.wikipedia.org/wiki/Noise_shaping
September 9, 2010 at 9:23 PM
A similar approach is to say:
I want this to happen 1 in every 10 times. Generate a random number n, from 1 to 10. Return true on the nth time. Return false the other 9 times. After the 10th try, generate a new random number.
Thus, the special effect on a weapon or such activates 1 in 10 times, always, but he can't predict WHEN it'll happen (for the most part).
September 10, 2010 at 9:25 AM
I built a simpler system (mostly math based) a few years back that is based on what Ian said above. The basic concept is that with a 1/5 drop rate, players really expect the first kill to be 1/5 and if they fail, the second to be 1/4 and if they fail again, the third to be 1/3. If you set up your drop rates in fraction form, remove the numerator from the denominator for each attempt, and add the initial denominator to the current denominator on each success you will have a (roughly) guaranteed 1 success for every 5 attempts. It is even easy to scale down, guaranteeing 2 successes for 10 attempts (50% power) or 20 successes for 100 attempts (5% power).
There are some more little fiddly things that need to be handled but the implementation is cheap both in storage and processing and is scalable.
Relevant posts from my since abandoned blog:
http://designdeeply.blogspot.com/2006/09/swayed-random-number-generation.html
http://designdeeply.blogspot.com/2006/10/swayed-random-number-implementation.html
September 10, 2010 at 11:50 AM
Yeah, that's permutation as Ian mentioned. Permutation is a good tool to have in the toolbox.
September 10, 2010 at 11:53 AM
That was @Quantum
September 10, 2010 at 11:55 AM
permutation is a bit subtle to do well; if you just use Quantum's naive implementation, you can still get 2-in-a-row, although it only happens 1 in 1000 times (100 sets of 10), and you can get 18 in a row of misses (also 1 in 100 sets of 10).
If those happen to be acceptable rates for those events, then you can use the naive solution, but most likely you don't want that.
The non-binary cases are much more interesting and overt to talk about. If you have 10 voice tracks you can play in reaction to event E, and you always have to play them, and you think you want to play them at random...
Zeroeth solution: at each event, just play the next recording in order, and then repeat when you run out. "But that's not random!"
First solution: pick one at random, it has repeats and sounds dumb
Second solution: some complicated scheme where you deprioritize recent ones. Still repeats more than you want, or too hard to tune.
Third solution: randomly permute the 10 elements, do 10 events, randomly permute again. Problem: can still get repeats across premutation boundaries.
Fourth solution: Randomly choose one permutation once. Just play that permutation over and over forever, guaranteeing it's always 9 events until you hear the same one again.
Fifth solution: Randomize the order offline, so everyone always gets the exact same "random" order. This is identical to the 0th solution.
Problem with four and five: people may notice that the order repeats, that they'll always hear a given one after another given one. I've never heard that complaint, but that seems to be the only reason to move onto the next solution (although plenty of people have moved onto it):
Sixth solution: pick a random permutation. Play through it. Now, do small local swaps on the permutation to build the new permutation, guaranteeing that each event is, say, no less than 7 or 8 distant and no more than 12 or 13 distant from their previous usage.
Note that the last solution is very similar in behavior to one where you track "how long has it been since I last used this one" and then you only choose from the ones that have been at least 7 ago and with increasing priority as they get above 10.
I've definitely heard of people doing things along the line of these last two solutions.
As mentioned, I'm not sure why.
September 10, 2010 at 4:07 PM
"Problem with four and five: people may notice that the order repeats, that they'll always hear a given one after another given one. I've never heard that complaint,"
Yeah I certainly notice this and there are plenty of cases where it's definitely not okay. Like maybe it's okay for dialogue sequences (because that's sort of weird and gamey anyway, so it's okay if it's just a sequence), but if you used it for gun shot or footstep sounds, the pattern would be very obvious.
"Second solution: some complicated scheme where you deprioritize recent ones. Still repeats more than you want, or too hard to tune."
This is what I propose here; it's really not that complicated and has no disadvantages that I know of (other than yes, being slightly unintuitive to tweak; probably that could be fixed by exposing the tweak parameters in a more designer-friendly way and doing some math to convert).
I think basically all other options have disadvantages or are harder to tweak and implement. (eg. the complicated permutation that you suggest at the end could be made equivalent of course but seems much harder to get right)
September 10, 2010 at 4:42 PM
What you want is a Poisson Distribution.
September 15, 2010 at 9:14 AM
I hope that's a joke.
September 15, 2010 at 9:20 AM
Very interesting. I will implement it in my fighting engine. You can follow me at http://kokusaifightingengine.blogspot.com/
October 6, 2010 at 1:24 AM