We have another technical post for you, this time about saving the game state and how we do it.
May 092017
May 262016
RNG stands for random number generator. In this article, I’ll show you what kind of RNG we use in various chance-based actions in Vaporum.
Why
One of the greatest RNG evils in games is long streaks of success or failure. Especially failure! How we hate to miss the attack 4 times in a row while the hit chance is 80%!
But why even care? We can just use this and be fine, right?
if (UnityEngine.Random.value < myChance) Hit();
Hell no! This most basic approach has exactly the one glaring issue: big streaks of luck or unluck (what a word). You will get them on regular basis. They are bad for your game.
Let’s see what we can do about them pesky streaks.
Where
First, let’s see where we use RNG. Major chance-based actions in Vaporum are:
- Weapon attacks (enemy attacks too)
- Critical hits
- Various on-hit passive skills and traits
To ensure consistent results of various actions, we have an instance of RNG on each of them. Every time an action is checked for success, based on the given chance, the RNG is polled for a result. It either returns true or false, success or failure.
Each weapon (enemy attacks count as weapons too) has two instances of RNG. One for hit chance, one for crit chance. Whenever you attack with a weapon, we check the hit RNG. If we got a hit, we then check the crit RNG.
Other effects, mostly passive traits, are only checked when appropriate. For example, if you have a passive trait that adds a chance to stun the enemy with hammers, and you attack with a hammer, the RNG of the trait is checked. If it succeeds, we apply the stun.
How
After trying out 3 various RNG systems (designed by us), we decided for the pseudo-random distribution (PRD) model. It gives us consistency of results, almost exclusively eliminates long unprobable streaks, but still leaves some room for occasional short streaks. You can read a fine article about it on this Dota 2 fan page.
The basic premise is that whenever your success check fails, the chance for the next check increases, and this goes on and on until it succeeds. And when it does, the chance is reset back to the base value. The base chance value is not the desired chance (as shown in tooltips for weapons and skills), but a pre-calculated constant. The first check is also run against this constant, not the displayed chance. Read that article to get a gist of it if you haven’t already.
Now the problem is, it’s hard to calculate that constant. As you can see, they have a pre-calculated constant for every 5% up to 80% in Dota 2. That’s fine for Dota, but not for us. We need constants for each percent, from 0% to 100%.
So how we get them? Approximation comes to help!
(It is a console application written in VS2015. Add a reference to System.Windows.Forms in your project (right-click project -> add reference -> ..., profit)).
using System;
using System.Diagnostics;
using System.Globalization;
using System.Windows.Forms;
namespace PRDTableGenerator
{
class Program
{
[STAThread]
static void Main(string[] args)
{
// Run the beast.
PRDPercentageTableGenerator.Generate();
// Wait for input so the console doesn't vanish into thin air.
Console.Read();
}
}
public static class PRDPercentageTableGenerator
{
// How many cycles to go thru when approximating. The greater the number, the more precise the result, but also greater generation duration.
private const int statisticCycles = 500000;
// The maximum allowed deviation of approximated probability from desired probability. Greater equals more precise and time-consuming.
private const double maxDeviation = 0.00001;
// Log messages about how we're faring?
private static bool logEnabled = true;
// Our basic RNG.
private static Random random = new Random();
// ------------------------------------------------------------
private static void Log(string message, params object[] args)
{
if (!logEnabled) return;
Console.WriteLine(message, args);
}
// ------------------------------------------------------------
// Check if we succeed with given chance.
private static bool Roll(double chance)
{
return random.NextDouble() < chance;
}
// ------------------------------------------------------------
// Test whether the given approximated C value results in a probability close enough to the desired probability.
private static int TestC(double baseVal, double desiredChance)
{
var hits = 0;
var c = baseVal;
for (var i = 0; i < statisticCycles; i++)
{
if (Roll(c))
{
hits++;
c = baseVal;
}
else
{
c += baseVal;
}
}
// Approximated probability.
var avg = (double)hits / (double)statisticCycles;
// Deviation from desired probability.
var diff = avg - desiredChance;
// Close enough.
if (Math.Abs(diff) < maxDeviation)
{
return 0;
}
// Nope! Too little.
else if (diff < 0)
{
return 1;
}
// Nope! Too much.
else
{
return -1;
}
}
// ------------------------------------------------------------
// Get an approximated C for the given probability.
private static double ApproximateCValue(double chance)
{
// Current C we're trying to get right.
var triedC = chance;
// Modifier by which to approximate on failed attempts.
var mod = triedC * 0.5f;
while (true)
{
// Check if we're close.
var result = TestC(triedC, chance);
// Ya bet we are, gringo!
if (result == 0)
{
Log("Approximated C value: {0}", triedC);
return triedC;
}
// Nah, we shot too low. Need to up the game.
else if (result == 1)
{
triedC += mod;
}
// Damn it, we overshot. Need to calm it down a lil.
else
{
triedC -= mod;
}
// Decrease the modifier so we're gonna get close enogh eventually.
mod *= 0.5f;
}
}
// ------------------------------------------------------------
private static string GenerateCSharpArray(float[] t)
{
var s = string.Empty;
s += "private static float[] chanceTable = new float[101]\n{\n";
for (var i = 0; i < t.Length; i++)
{
s += string.Format("\t/* {0}% */ {1}f,\n", i, t[i]);
}
s += "};";
return s;
}
// ------------------------------------------------------------
// Go go go, soldier!
public static void Generate()
{
// Make sure we use dots as decimal separator.
var customCulture = (CultureInfo)System.Threading.Thread.CurrentThread.CurrentCulture.Clone();
customCulture.NumberFormat.NumberDecimalSeparator = ".";
System.Threading.Thread.CurrentThread.CurrentCulture = customCulture;
// Let's measure how long it takes.
var sw = new Stopwatch();
sw.Start();
Log("Generating...");
// Create the array and fill the boundaries with the known values.
var t = new float[101];
t[0] = 0.0f;
t[100] = 1.0f;
// Toil away! Assign an approximated C value to each percentage probability in the array.
for (var i = 1; i < t.Length - 1; i++)
{
Log("\nGenerating C value for {0}% chance...", i);
t[i] = (float)ApproximateCValue(i * 0.01);
}
// Write the result, nice and dandy.
Console.WriteLine("\nResulting array of floats:\n");
var res = GenerateCSharpArray(t);
Console.WriteLine(res);
Clipboard.SetText(res);
Console.WriteLine("\n(Array copied to clipboard.)");
Console.WriteLine("\nTo understand how to use pseudo-random distribution in your game, check this cool article: http://dota2.gamepedia.com/Pseudo-random_distribution");
// Write the duration.
Console.WriteLine("\nGeneration took: {0:F1} seconds", sw.Elapsed.TotalSeconds);
sw.Stop();
}
}
}
Note: Running this takes about 30 seconds on my computer. May vary depending on your rig.
Whoa, so we get a static table now! Here’s how to use it:
using UnityEngine;
public class VapPRDRandom
{
private static float[] s_chanceTable = new float[101]
{
/* 0% */ 0f,
/* 1% */ 0.0001611328f,
/* 2% */ 0.0006103492f,
/* 3% */ 0.001390287f,
/* 4% */ 0.002450562f,
/* 5% */ 0.003812454f,
/* 6% */ 0.00544064f,
/* 7% */ 0.007358261f,
/* 8% */ 0.009589888f,
/* 9% */ 0.01202478f,
/* 10% */ 0.01469073f,
/* 11% */ 0.01783203f,
/* 12% */ 0.02094635f,
/* 13% */ 0.02451059f,
/* 14% */ 0.02819672f,
/* 15% */ 0.03222107f,
/* 16% */ 0.03644421f,
/* 17% */ 0.04079834f,
/* 18% */ 0.04570862f,
/* 19% */ 0.05053855f,
/* 20% */ 0.05546875f,
/* 21% */ 0.0610963f,
/* 22% */ 0.06668884f,
/* 23% */ 0.07258219f,
/* 24% */ 0.07850874f,
/* 25% */ 0.08446875f,
/* 26% */ 0.09119834f,
/* 27% */ 0.09778266f,
/* 28% */ 0.1045927f,
/* 29% */ 0.111832f,
/* 30% */ 0.1189695f,
/* 31% */ 0.1262213f,
/* 32% */ 0.1338988f,
/* 33% */ 0.1418493f,
/* 34% */ 0.1500781f,
/* 35% */ 0.1580311f,
/* 36% */ 0.1662726f,
/* 37% */ 0.1752441f,
/* 38% */ 0.1833201f,
/* 39% */ 0.1924883f,
/* 40% */ 0.2017426f,
/* 41% */ 0.2110553f,
/* 42% */ 0.220342f,
/* 43% */ 0.2302755f,
/* 44% */ 0.2397724f,
/* 45% */ 0.2494584f,
/* 46% */ 0.2596484f,
/* 47% */ 0.27014f,
/* 48% */ 0.280897f,
/* 49% */ 0.29093f,
/* 50% */ 0.3019776f,
/* 51% */ 0.3127797f,
/* 52% */ 0.322937f,
/* 53% */ 0.3341516f,
/* 54% */ 0.3480469f,
/* 55% */ 0.360863f,
/* 56% */ 0.3735327f,
/* 57% */ 0.3854644f,
/* 58% */ 0.3983658f,
/* 59% */ 0.4104217f,
/* 60% */ 0.4230034f,
/* 61% */ 0.4348656f,
/* 62% */ 0.4462058f,
/* 63% */ 0.4577338f,
/* 64% */ 0.4695821f,
/* 65% */ 0.4809301f,
/* 66% */ 0.4931479f,
/* 67% */ 0.5079261f,
/* 68% */ 0.5298079f,
/* 69% */ 0.5507703f,
/* 70% */ 0.5715531f,
/* 71% */ 0.5903955f,
/* 72% */ 0.611093f,
/* 73% */ 0.6303659f,
/* 74% */ 0.649352f,
/* 75% */ 0.6665279f,
/* 76% */ 0.6846761f,
/* 77% */ 0.7016721f,
/* 78% */ 0.7180756f,
/* 79% */ 0.7338443f,
/* 80% */ 0.7496008f,
/* 81% */ 0.7645162f,
/* 82% */ 0.7801579f,
/* 83% */ 0.7954523f,
/* 84% */ 0.8106738f,
/* 85% */ 0.8250977f,
/* 86% */ 0.8370593f,
/* 87% */ 0.8508409f,
/* 88% */ 0.8628125f,
/* 89% */ 0.8759527f,
/* 90% */ 0.8885157f,
/* 91% */ 0.9015872f,
/* 92% */ 0.9131664f,
/* 93% */ 0.9247211f,
/* 94% */ 0.9358692f,
/* 95% */ 0.9473711f,
/* 96% */ 0.9582562f,
/* 97% */ 0.9691508f,
/* 98% */ 0.9795209f,
/* 99% */ 0.9899905f,
/* 100% */ 1f,
};
[VapSave]
private readonly float[] m_accums = new float[101];
// ------------------------------------------------------------
public VapPRDRandom()
{
this.Init();
}
// ------------------------------------------------------------
private void Init()
{
for (var i = 0; i < this.m_accums.Length; i++)
{
this.m_accums[i] = this.GetC(i);
}
}
// ------------------------------------------------------------
private bool Check(float chance)
{
return UnityEngine.Random.value < chance;
}
// ------------------------------------------------------------
private float GetC(int chance)
{
return s_chanceTable[chance];
}
// ------------------------------------------------------------
private void ResetC(int chance)
{
this.m_accums[chance] = this.GetC(chance);
}
// ------------------------------------------------------------
public bool Success(float chance)
{
var c = Mathf.RoundToInt((chance * 100.0f));
if (Check(this.m_accums[c]))
{
this.ResetC(c);
return true;
}
this.m_accums[c] += this.GetC(c);
return false;
}
// ------------------------------------------------------------
public static void Test()
{
var s = new VapPRDRandom();
var realChance = 0.0f;
var realTries = 1;
var hitStreak = 0;
var missStreak = 0;
var subsequentHits = 0;
var subsequentMisses = 0;
for (var x = 0; x < realTries; x++)
{
var chance = 0.9f;
var tries = 100000;
var hits = 0;
for (var i = 0; i < tries; i++)
{
if (s.Success(chance))
{
hits++;
subsequentHits++;
hitStreak = (subsequentHits >= hitStreak) ? subsequentHits : hitStreak;
subsequentMisses = 0;
}
else
{
subsequentMisses++;
missStreak = (subsequentMisses >= missStreak) ? subsequentMisses : missStreak;
subsequentHits = 0;
}
}
Debug.Log("\n\n");
Debug.LogFormat("Chance: {0:P0}", chance);
Debug.LogFormat("Tries: {0}", tries);
Debug.LogFormat("Hits: {0}", hits);
Debug.LogFormat("Misses: {0}", tries - hits);
Debug.LogFormat("Hit Streak: {0}", hitStreak);
Debug.LogFormat("Miss Streak: {0}", missStreak);
realChance += (float)hits / tries;
}
Debug.LogFormat("Real Chance: {0:P1}", realChance / realTries);
}
}
Note: The [VapSave] attribute is our fancy save system. You basically just mark anything you want to save and you’re done! Lots of work behind the curtain though! (More on that in a later post, hopefully.)
So, we just pasted the generated constants into a static array, and the rest is fairly straightforward I hope.
You can use the static Test function to test if it gives expected results for various chance percentages. However, that is just a guide. Only playing your game will show if it survives the battle-test!
Now, we need to create instances of the VapPRDRandom in classes that use chance-based actions, and just poll the Success method.
Conclusion
There are several ways to achieve ‘good’, consistent randomness without the dreaded streaks. For us, the pseudo-random distribution model works like a charm, solving the random issues we struggled with. Hope this helps someone out there, struggling with the same thing.
Already using a system that works for you? Do tell!