Article

Randomness in Games - Shuffling, Weighted Random and Pseudo-Random Distribution

“25% crit chance, and I went 15 swings in a row without a crit!” What players feel as random and what is mathematically random are not the same thing. This chapter covers reproducible random number generators, correct shuffling, loot tables, and pseudo-random distributions that make randomness “feel fairer”.

The problem: random, but the right kind of random

Random numbers are everywhere in games: crits, drops, map generation, AI decisions, shuffling and dealing cards. But “just call rand()” brings a string of problems:

  • Not reproducible: a player reports “there's a bug on floor 3 of the map with seed 12345”, and you can't generate that same map

  • Quietly biased: a shuffle looks random, yet some permutations clearly come up more often than others

  • Doesn't feel fair: a mathematically perfect 25% crit chance, and players still feel they have terrible luck

This chapter tackles them one by one.


A reproducible random number generator

Almost all random numbers in a computer are pseudo-random: a deterministic algorithm derives a stream of random-looking numbers from a “seed”. The same seed always produces the same stream, which is exactly the property games need: procedural maps, replays, and lockstep multiplayer all depend on it.

Why not the standard library

rand() may only cover 0–32767, its quality varies, and it is global state, so multiple systems sharing it interfere with each other. std::mt19937 is deterministic on its own, but the implementations of distributions such as std::uniform_int_distribution are not standardized: the same seed can give different results on MSVC and GCC. When you need cross-platform reproducibility, you should control every step yourself, from the generator to the distribution.

This series uses PCG32: only 16 bytes of state, fast, good statistical quality, and under 20 lines of code:

// PCG32 (pcg-random.org): small, fast, good statistical quality, and exactly reproducible from a seed.
// When a game needs "the same seed generates the same map" or "replay a recording", you can't use rand() or std::random_device
class Pcg32 {
public:
    explicit Pcg32(uint64_t seed = 0x853c49e6748fea9bULL, uint64_t stream = 0xda3e39cb94b95bdbULL) {
        state_ = 0;
        inc_ = (stream << 1u) | 1u;
        next();
        state_ += seed;
        next();
    }

    uint32_t next() {
        uint64_t old = state_;
        state_ = old * 6364136223846793005ULL + inc_;
        auto xorshifted = static_cast<uint32_t>(((old >> 18u) ^ old) >> 27u);
        auto rot = static_cast<uint32_t>(old >> 59u);
        return (xorshifted >> rot) | (xorshifted << ((~rot + 1u) & 31u));
    }

    // Uniform integer in [0, bound). Plain next() % bound is biased, so we reject the part that "doesn't fill a whole round"
    uint32_t below(uint32_t bound) {
        uint32_t threshold = (~bound + 1u) % bound;  // = 2^32 mod bound
        for (;;) {
            uint32_t r = next();
            if (r >= threshold) return r % bound;
        }
    }

    int range(int lo, int hi) { return lo + static_cast<int>(below(static_cast<uint32_t>(hi - lo + 1))); }  // closed interval
    float nextFloat() { return static_cast<float>(next() >> 8) * (1.0f / 16777216.0f); }      // [0, 1)
    double nextDouble() { return static_cast<double>(next()) * (1.0 / 4294967296.0); }       // [0, 1)
    bool chance(double p) { return nextDouble() < p; }

private:
    uint64_t state_;
    uint64_t inc_;
};

Note how below is written. Plain next() % 6 is biased: 2³² isn't divisible by 6, so the leftover part makes the smaller faces come up slightly more often. The correct approach is to throw away the results that “don't fill a whole round” and draw again.


Shuffling: an algorithm that looks right but is wrong

To shuffle a deck, many people would write this: walk over every position and swap it with any position.

// Wrong: every position swaps with "any position". It looks random, but the n^n execution paths can't be split evenly across n! permutations
template <class T>
void naiveShuffle(std::vector<T>& items, Pcg32& rng) {
    for (size_t i = 0; i < items.size(); ++i) {
        size_t j = rng.below(static_cast<uint32_t>(items.size()));
        std::swap(items[i], items[j]);
    }
}

The problem is in the counting: with n cards, each step has n choices, giving nⁿ execution paths, while there are only n! permutations. For 6 cards that's 46656 paths mapping onto 720 permutations, and 46656 isn't divisible by 720, so it's impossible for every permutation to be equally likely.

The correct approach is Fisher–Yates: go from back to front, and swap each position only with “itself or anything before it”. That gives exactly n! paths, in one-to-one correspondence with the n! permutations:

// Fisher–Yates shuffle: from back to front, each position swaps only with "itself or anything before it". O(n), and every permutation is equally likely
template <class T>
void shuffle(std::vector<T>& items, Pcg32& rng) {
    for (size_t i = items.size(); i > 1; --i) {
        size_t j = rng.below(static_cast<uint32_t>(i));  // j ∈ [0, i-1]
        std::swap(items[i - 1], items[j]);
    }
}

Three tabs: shuffle compares the two shuffles, with a heatmap showing how often each card (row) lands in each position (column); crit compares independent random and pseudo-random crits; loot is a weighted loot table. Pressing “reset” gives you exactly the same random sequence. Open separately ↗

On the shuffle tab, let the demo run for a while (you can turn the speed up to 8×). The Fisher–Yates cells gradually converge to a uniform 16.7%, while the naive shuffle always keeps a clear diagonal stripe: card k is especially likely to end up near position k-1, with a maximum deviation of over 20%.


Loot tables: weighted random

For loot tables like “common 60%, rare 10%, legendary 1%”, the standard approach is to precompute the prefix sums of the weights, then on each draw generate a random number in [0, total weight) and binary-search for the interval it falls in:

// Weighted random (loot table): precompute prefix sums, then binary-search on each draw, O(log n)
class WeightedTable {
public:
    explicit WeightedTable(const std::vector<double>& weights) {
        double sum = 0;
        for (double w : weights) cumulative_.push_back(sum += w);
    }

    int pick(Pcg32& rng) const {
        double r = rng.nextDouble() * cumulative_.back();
        auto it = std::upper_bound(cumulative_.begin(), cumulative_.end(), r);
        return static_cast<int>(it - cumulative_.begin());
    }

    double probability(int i) const {
        double prev = i == 0 ? 0 : cumulative_[i - 1];
        return (cumulative_[i] - prev) / cumulative_.back();
    }

    int size() const { return static_cast<int>(cumulative_.size()); }

private:
    std::vector<double> cumulative_;
};

Preprocessing is O(n) and each draw is O(log n). When the weight table is large and draws are extremely frequent, you can switch to the alias method, which brings a draw down to O(1).

The demo's loot tab shows the expected probability (vertical line) and the actual frequency (bar) side by side. The more you draw, the closer the two get, which is the law of large numbers. But with few draws, the actual frequency of a legendary item can be far from 1%, and that's exactly where player complaints come from.


How to make randomness “feel fair”?

Shuffle bag

If you want results that are “random but even”, for example a falling-block game that wants each of the 7 shapes to appear exactly once in every 7 pieces, you can put all the outcomes into a bag, shuffle it, take them out one by one, and refill the bag when it's empty.

// Shuffle bag: put a set of outcomes in a bag, shuffle it, draw them one by one, and refill when empty. Guarantees each outcome appears exactly once per round
template <class T>
class ShuffleBag {
public:
    explicit ShuffleBag(std::vector<T> items) : items_(std::move(items)), next_(items_.size()) {}

    const T& next(Pcg32& rng) {
        if (next_ >= items_.size()) {
            shuffle(items_, rng);
            next_ = 0;
        }
        return items_[next_++];
    }

private:
    std::vector<T> items_;
    size_t next_;
};

Pseudo-random distribution (PRD)

With an independent 25% crit chance, the probability of 15 non-crits in a row is 0.75¹⁵ ≈ 1.3%. A fight can involve hundreds of swings, so almost every match will hit a stretch of “bad luck” at some point.

Pseudo-random distribution (PRD) uses a different rule: the trigger probability on the Nth attempt is N × C, and once it triggers, N resets to zero. The swing right after a crit has a very low chance, the longer you go without a crit the higher it gets, and once N × C ≥ 1 it is guaranteed to trigger. With a suitable constant C, the long-run average probability is still 25%.

There's no simple closed-form solution for C, but the “average probability” increases monotonically with C, so we can binary-search for it:

// Pseudo-random distribution (PRD): the trigger probability on the Nth attempt is N·C, and N resets to zero after a trigger.
// The average probability is still p, but both "long streaks without a trigger" and "long streaks of triggers" become rarer
inline double prdAverageProbability(double c) {
    double expectedAttempts = 0;  // expected number of attempts between two triggers
    double notYet = 1;            // probability that none of the first n-1 attempts triggered
    for (int n = 1; notYet > 0; ++n) {
        double pn = std::min(1.0, n * c);
        expectedAttempts += n * notYet * pn;
        notYet *= 1 - pn;
    }
    return 1 / expectedAttempts;
}

// Solve for the constant C from the nominal probability p: the average probability increases monotonically with C, so use binary search
inline double prdConstant(double p) {
    double lo = 0, hi = p;
    for (int i = 0; i < 64; ++i) {
        double mid = (lo + hi) / 2;
        (prdAverageProbability(mid) < p ? lo : hi) = mid;
    }
    return (lo + hi) / 2;
}

class PrdRoll {
public:
    explicit PrdRoll(double p) : c_(prdConstant(p)) {}

    bool roll(Pcg32& rng) {
        ++attempts_;
        if (rng.chance(attempts_ * c_)) {
            attempts_ = 0;
            return true;
        }
        return false;
    }

    double constant() const { return c_; }

private:
    double c_;
    int attempts_ = 0;
};

C values for common probabilities, and the longest possible streak without a trigger:

Nominal probability P

Constant C

Longest streak without a trigger

5%

0.00380

263

10%

0.01475

67

15%

0.03222

31

20%

0.05570

17

25%

0.08474

11

30%

0.11895

8

40%

0.20155

4

50%

0.30210

3

Switch to the demo's crit tab: both timelines have a crit rate close to 25%, but the independent-random timeline has obvious gaps and clusters, while PRD's crits are spread much more evenly. In the histogram below, the gaps for independent random have a long tail, whereas PRD's gaps concentrate between 3 and 6 and never exceed 12.

PRD has a cost too

PRD makes “streaks of crits” rarer and the rhythm of crits more predictable. Skilled players can exploit this, for example by hitting minions first to “build up probability” before going after a hero. Whether to use it, and on which mechanics, is a design decision and not just a technical one.


Common pitfalls

Problem

Cause

Fix

Results are identical on every run, or different on every run

The seed is hard-coded, or always taken from the current time

Pass the seed in as an explicit parameter; take the time or system entropy only when you want randomness

Dice show 1–2 slightly more often

The modulo bias of next() % n

Use below(n) with rejection sampling

Shuffle results are biased

Swapping with any position

Use Fisher–Yates

Replays don't match the original game

Several systems share one generator and the call order changed

Give each system its own generator (different streams)

nextFloat() occasionally returns 1.0

Using next() / 4294967295.0 gives a closed interval

Take only the top 24 bits and multiply by 2⁻²⁴ to get [0, 1)


In real games

  • Procedural generation: a roguelike's seeded map is essentially just handing the seed to a generator like PCG (more in later updates).

  • Lockstep multiplayer: all clients must use the same seed and the same call order to get the same random results.

  • Crits, dodges, and proc-based passives: PRD is a common technique in MOBAs and ARPGs.

  • Gacha pity systems: on top of weighted random, add a counter that guarantees a drop after N misses. The principle is close to PRD.


Further reading

Copyright

Copyright of this article belongs to its author or rights holder. When reposting or quoting, please follow the applicable license terms and keep the link to this article.

XuYi, “Randomness in Games - Shuffling, Weighted Random and Pseudo-Random Distribution”, https://xuyi.dev/en/2026-11-09-warx1z

Comments

Comments

Loading comments…