Building a Better Random Drop

Random number generators are everywhere in video games. Their most transparent use is in RPGs (simulating dice rolls) where often explicit chances of success are presented to the player. They can also be critical in puzzle games (the choice of a piece in Tetris), in first and third-person shooters (the spray of bullets), and in strategy games (the generation of a world in Alpha Centauri), to name just a few applications.

One particular RPG mechanic that has spread pretty prolifically is the random item drop, which is a feature I think could be significantly improved. It’s certainly not the only chance oriented mechanic that could use an overhaul, but it’s likely the most frustrating.

Someone working on a game will generally specify an item as dropping, say, “one in fifty times”. The typical programmer will probably think “easy!” and pound out something like the following:

def should_drop(chance):
    return random.random() < chance

This is enough to ensure that a large enough player base will, on average, get the item on the fiftieth try. From the perspective of individual players, though, the result isn’t quite as pleasant.

The drop that never came

The general formula for the likelihood of getting n items, each with chance 1/k, after t tries is:

$(C$n,k,t$=\Big(1-\frac{1}{k}\Big)^{t-n}\frac{1}{k^n}\binom{k}{n}])$

From this equation we can pull a few illustrative probabilities.

Let’s first look at the case where a player has tried as many times as is “expected” (e.g. fifty for a one-in-fifty item) and has still received nothing. That means that k = t and n = 0. This equation simplifies beautifully and converges rapidly towards _e_^-1^, or about 36%. Over one third of players will not have received a drop after the expected number of attempts. In the case that they have tried twice the number of “expected” attempts, just under one seventh ( _e_^-2^) of players will still not have found the item.

An example of this in action: In the more recent Pokemon games, the player has a 1 in 8192 chance of encountering a shiny pokemon. About 1/7 of the player base will not see a shiny pokemon in their first 16384 random battles. That’s likely to outnumber the total number of battles a player will engage in before they finish and shelve the game for good. A player is never guaranteed to eventually succeed with random independent checks.

There is no benefit to anyone (developer or player) deriving from the fact that the distribution of drops is so smeared. We’ll consider this a flaw to be fixed when we construct our new “random” algorithm.

Bunches of luck

On the opposite end of the spectrum is the possibility that the player is actually too lucky and gets rare drops in close succession. Sometimes that is acceptable, but paired with a long string of bad drops, this could have a demoralizing effect as the player now considers some or all of that time wasted. Additionally, bunched up rare events don’t feel random to the player. We humans aren’t particularly good at gauging randomness, so we’ll want a fake random that the player perceives as being better.

Let’s try

To begin, let’s look again at the naive approach:

def naive(chance):
    while True:
        yield random.random() < chance

Calling the naive function gives us a sequence, where every item in it has an independent chance likelihood of being true. This is the approach that most games take with item drops, carrying with it the negatives mentioned earlier:

Players are never guaranteed to eventually succeed
Successes can be clustered

The most direct algorithm that is guaranteed to succeed is one that fails as many times as is necessary to ensure some average chance value, and then succeeds. For example, a “one in fifty” drop rate would be translated very literally into forty-nine failures and then one success, repeating forever.

In code, it might look a bit like this:

def exact_drop(chance):
    remainder = 0
    while True:
        remainder += chance
        if remainder > 1:
            remainder = remainder % 1
            yield True
        else:
            yield False

This approach was created explicitly to solve the “eventual success” problem, and it also happens to prevent clustering for chances less than 50% (where clustering isn’t expected).

It’s not without fault, though. I think that a rigid and perfectly predictable schedule doesn’t inspire the same level of interest or activity as one that is more variable. When every action has a possibility of additional significance, a player will more eagerly take one additional action. This suspicion is backed up by research in reward delivery and reinforcement.

A less predictable drop system keeps the player more engaged with the game, which is a good thing for all parties. It seems best to create a hybrid system between the two previously mentioned. The algorithm would require a certain number of actions before a success, but that number would be randomly determined and centered around the desired average number of attempts.

This description actually matches the algorithm used in Team Fortress 2 for determining item drop occurrences (but not contents). In Team Fortress 2, a player will typically get an item every 50 minutes, but might receive it as early as 30 minutes in, or as late as 70 minutes. We will use this as the foundation for our new item drop algorithm:

def tf2_drop(chance):
    expected_trials = 1/chance
    trial_spread = expected_trials * TF2_SPREAD

    min_trials = expected_trials - trial_spread
    if min_trials >= 1:
        max_trials = expected_trials  + trial_spread
    else:
        min_trials = 1
        max_trials = 2*expected_trials - 1

    while True:
        if min_trials % 1 > random.random():
            trial_min = math.ceil(min_trials)
        else:
            trial_min = math.floor(min_trials)

        if max_trials % 1 > random.random():
            trial_max = math.ceil(max_trials)
        else:
            trial_max = math.floor(max_trials)

        trials_til_success = random.randint(trial_min, trial_max)

        for _ in xrange(trials_til_success - 1):
            yield False
        yield True

The above contains some numeric gymnastics to make sure it’s general, but the core of the algorithm remains the same as what was described earlier. Some range is specified (here using the constant TF2_SPREAD) centered about the expected number of attempts, and a required number of attempts is randomly chosen in that new range.

This approach retains all the advantages of both the random and fixed algorithms. It will often avoid clustering where it isn’t appropriate (dependent upon the value of TF2_SPREAD), it’s guaranteed to eventually yield a success, and it isn’t so static as to be dull to the player (though random item drops can only be so interesting).

Implications

This is far from a new topic, so I had the advantage of reading counter-arguments citing (often incorrect) implications of changing random drop algorithms.

Impossibly rare items are not really feasible with this approach. The drop rates associated with those items have less to do with how many attempts a player must have before obtaining the item, and more to do with what percentage of the player base might be lucky enough to obtain it. This is probably a wholly multiplayer concern, but a naive drop algorithm would be required in this situation.

This approach will have little to no impact on the total number of a particular item in existence (for drop chances that are not unreasonable). The ratio between item drops and drop trigger events will always hover around the specified “drop rate”. What this change will do is distribute those items more evenly amongst all players (assuming use in a multiplayer setting), which will impact any trade economy that might exist.

Implementing stateful drop generators on a per-player-per-enemy-drop basis could be taxing on system resources. Care would have to be taken with ensuring that these generators are only retained for as long as they’re actually needed (i.e. tossing any existing generators when moving from one location to another).

Alternative approaches

There are other methods of improving the otherwise dreary experience of trying to secure a rare item drop. Both Final Fantasy XII and The World Ends With You introduce mechanics that let the player increase the odds of an item dropping by playing more strategically. In the case of Final Fantasy XII, repeatedly defeating the same enemy type increases a “chain combo” value, which increases the rate and value of that enemy type’s potential drops. In The World Ends With You, the player can manually increase the difficulty for various benefits, among them being a boosted item drop rate.

My favorite item drop system actually eschews randomness. The Etrian Odyssey series introduced me to the concept of “conditional drops”. In addition to typical random item drops, there were certain enemies that would drop special items if some conditions were met in battle. For example, defeating a Mandrake with a fire attack will result in “charcoal” being dropped, or defeating the Mantis in one turn would net you a “silver eye”. These items are otherwise unobtainable.

I prefer this approach because it’s elegant and potentially more logical than random items popping out of the corpses of your enemies. The biggest positive, though, is that it asks something very different of the player for success. In games with random item drops, the exchange is time for items. That sort of transaction is not a very fulfilling one. A conditional drop approach leverages the existing systems that have been implemented in the game. It asks that the player exhibit a mastery of these systems, and for doing so, they will be rewarded.