Random Number Generation in Treasure Hunt

Hello gaming friends, in this article I will explain why we replaced our old random number generation (RNG) with a more sophisticated concept. I will start with a motivation and a requirement analysis for RNG in games like Treasure Hunt – A Pirate’s Tale and come to more technical terms later on.

Motivation for a new Random Number Generation

First things first: During the last Playtests, we received the feedback that #piratetale feels unfair. After a discussion with our test-crew we identified the problem. The crew observed that special damage events like fire outbreaks and the waterbreaches sometimes never happen. Whereby, sometimes the enemy seems to cause a fire outbreak with every second cannon salve. The player can control the probability of those events by ordering special cannon salve maneuvers. But such maneuver is only a one-time effect and nevertheless the probability stays relatively small.

Random Number Generation in Treasure Hunt
Random Number Generation in Treasure Hunt

The main problem was our simple implementation for random throws. We drew a uniformly distributed number between zero and 100 (percent). Then, we checked if the target probability is smaller and if that was the case the throw had been marked as success. Simply said, the distribution was inadequate. Nevertheless, my first thought was that we cannot achieve a good RNG when we share the random engine between different random properties. For clarification in our case a random property is one place that needs random throws. A cannon has an accuracy, but also a probability for causing a fire outbreak or a water breach. That means three random properties. But let’s concentrate on the main problem.

Some days later, a discussion with a coder friend of mine enlightened me. My friend argued that gamers, and also himself, tend to interpret a percent value like 50% as “I will hit the enemy every second time”. But although two throws are the expectation value there is a deviation. It starts to feels really unfair when you miss your enemy the fifth time in a row, doesn’t it? But that is how a uniform random distribution (URD) works and that’s why in our opinion something else suits games better.

Requirement Analysis

I did some research and came across two concepts. We were not the first ones thinking about what kind of randomness suits games best. Games like League of Legends or Dota 2 uses another kind of distribution. The devs of Dota 2 named this distribution pseudo random distribution (PRD) [1] and it is similar to the well-known normal distribution.

The second concept I found was the Permuted Congruential Generator (PCG) family of random number generators [2]. Those generators provide a nice feature called random streams. They allow the use of a high number of different random number sequences. Our idea is to use one stream for each random property to get rid of the bias effect. For understanding the bias effect, imagine there is an initial seed s, such that the random engine produces the sequence:

(a_1,b_1, …. , a_n, b_n), a_i \in \{0,...,49\}, ~ b_i \in \{50,...,100\}.

If two random properties access this random engine the first receives an expectation value of 24.5 and second of 74.5. Sure, this example is constructed but during the overhaul of our implementation we can simply get rid of the bias effect.

generated by Project Cartoon

Thanks to Melissa E. O’Neill, I also learnt that another challenge exists to achieve German thoroughness for our RNG. Most random engines do not pass empirical statistical tests, like the TestU01’s test suites [2]. The Mersenne Twister [3] does not pass those tests and is used in the modern C++ standard template library by default. Well, our old RNG implementation does not pass those tests either.

List of Requirements

We want to…

  • … give our players a fair experience and no frustration.
  • … use a bunch of random generators, one for each random property
  • … use a random number generator that passes empirical statistical tests
  • … get rid of the bias effect, where needed.
  • … collect information about random generation for the different properties.

Pseudo Random Distribution

“Don’t be unfair” is he most important requirement for our RNG. For us that means less randomness and more control for the players. The result is a less luck-dependent game. Therefore, we decided to use the pseudo random distribution (PRD) [1] over a uniform random distribution (URD). As far as we know, Dota introduced PRD, back in good old Warcraft III days. Relevant effects, like critical hits, stuns or bashes use PRD.

PRD has the same expectation value as a uniform random distribution but the deviation is less. In fact, PRD guarantees to throw a hit for a specific probability after a constant number of throws. The 12th throw is always a hit for a probability of 25% for example.

Theory

The probability of a success after i throws for PRD is simply calculated by using a Constant C_P for every target probability P, e.g. P=0.25, and the formula:

P^{i}_{p} = \min(1, i \cdot C_P), i\in\{1,...,N_{max}\}

The probability of a success for a uniform random distribution is always the target probability, e.g. p^{i}_{u}=0.25 independently what happened prior that events.

Diagramm

Besides those formulas, the following diagram shows the effect of PRD over URD.  The x-axis contains the count of the throws and the y axis states the probability for a hit. That means the height of a block represents the probability for a hit at that particular throw.

As you can see, PRD generates the outline of a Gaussian curve with most of the samples being a hit after 3 or 4 throws. URD mimics an exponential function that also has samples that need 10 or more tries.

A diagramm showing histograms
Number of tries needed for a 25% probability to be a Success

That means when using PRD the player experiences a progress although the outcome is random and that feels fairer. Besides that, PRD also enables deeper gameplay. We will give an example for that in the next section.

Implementation

The implementation shall provide a central access point to create new random properties based on PCG random streams. We want to use both distributions, PRD or URD, depending on the type of random property. On the client side we need a lightweight access to the random streams.

UML diagramm of the Random Number Generation in Treasure Hunt
UML of important Classes for RNG

The prior UML diagram gives a hint of the implementation used in #piratetale. The central hub is the URandomFacility that can be used to create new random streams. The client code uses a proxy object of the FPCGRandomStream called FRandomContext. The following code is used to initialize the random properties of a cannon.

RndAcc = RF->CreateRandomStream(Name + ” Acc”);
RndFire = RF->CreateRandomStream(Name + ” Fire”);
RndHole = RF->CreateRandomStream(Name + ” Waterbreach”);
RndCrewDmg = RF->CreateRandomStream(Name + ” CrewDmg”);
RndStationDmg = RF->CreateRandomStream(Name + ” StationDmg”);

The description is the only context a random stream owns and therefore can be used to identify the random property. Later, the following two lines generate a random PRD throw based on the cannons current probability for a fire outbreak.

RndFire.ChangePRDBaseProbability(GetProbabilityForFire());
auto success = RndFire.RandomPRD();

As you can see, the probability may change for every throw and there is an interesting interaction between changing probabilities, PRD and the amount of control a player has. Imagine a cannon salve maneuver that doubles the probability of a fire outbreak for every cannon. Although the probability is higher, you may have bad luck during the maneuver and neither cannon generates a fire.

For URD that means the next shots probability is as low as before. But, when we are using PRD the positive effect on the random property is stored until a fire outbreak occurs. That gives us devs a way to implement a deeper gameplay because we can even be more rewarding to players, who keep their cooldowns low.

Related Work and Outlook

Thanks to our early playtest we realized that our random number generation (RNG) introduces a feeling of unfairness for the players. Therefore, we replaced our basic RNG implementation with a more sophisticated concept based on the Permuted Congruential Generator (PCG) [2] family of random generators and the pseudo random distribution (PRD) [1].

We explained why PRD makes the game less unfair and introduced German thoroughness regarding the bias effect and the performance of our RNG regarding empirical statistical tests.

In the next month we have to decide which random properties shall be modeled by PRD and for which URD is better suited. We assume that the world-generation is best achieved by using URD. But we are not sure which distribution to use for dialog-based events and loot generation.

Hans-Christian Kühl of Rockfish Games shared an article about the random generation in Everspace [4]. Like Everspace in we plan to use a set of constraints to restrict the randomness of our world generation. Later playtests will show if these constraints are adequate.

We are looking forward to hear what you think about our solution and are curious about your approaches and solutions for RNG.

Best wishes
Tim

  1. Pseudo Random Distribution in Dota 2
  2. Melissa E. O’Neill (2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation. https://www.cs.hmc.edu/tr/hmc-cs-2014-0905.pdf
  3. Matsumoto, M., & Nishimura, T. (1998). Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation (TOMACS)8(1), 3-30
  4. Game Design Deep Dive: Managing randomization, frustration in Everspace

Leave a Reply

Your email address will not be published. Required fields are marked *