Handling random with unique chance in Python [duplicate]

Question

Okay, let's say you have a handful of enemies, each with their own 'rarity' to spawn. For example:

monsterlist = []

snake = 'snake', 60
wolf = 'wolf', 80
antlion = 'antlion', 30

monsterlist.append(snake, wolf, antlion)

Now I want to spawn one at random:

totalchance = 0

for monster in monsterlist:
    totalchance += monster[1] #add each monster's rarity to totalchance
chance = random.randint(0, totalchance)

if chance <= targetlist[0][1]: #chance is <= than first entry's rarity
    #spawn first monster
elif chance <= targetlist[0][1] + targetlist[1][1]: #chance <= second target's rarity
    #spawn second monster
#etc

Assuming you have a large amount of monsters in monsterlist, this is going to take stupid amounts of code just to calculate chance to spawn, I like to assume there's a less annoying way to do this, right?

Answer 1

You want to use a weighted choice algorithm. Here's some code. (I modified my own working code to fit your case, but it should work):

Ignoring the definition of WeightedChoice() for the moment, using WeightedChoice() is simple:

# The weighted list of monsters. Each item is a tuple: (VALUE, WEIGHT)
monsterlist = (
    ('snake', 60),
    ('wolf', 80),
    ('antlion', 30),
)

# do this (again) each time monsterlist changes:
weightedChoice = WeightedChoice(monsterlist);

# do this each time you want to grab a random monster:
print(weightedChoice.next())

Now the definition of WeightedChoice(). Based on Weighted random generation in Python. Refer to this blog post for a detailed explanation and comparison to other weight choice algoritms.

import random
import bisect

# Returns a random value, considering the weights of each item.
class WeightedChoice(object):
    def __init__(self, weights):
        self.totals = []
        self.weights = weights
        running_total = 0

        for w in weights:
            running_total += w[1]
            self.totals.append(running_total)

    def next(self):
        rnd = random.random() * self.totals[-1]
        i = bisect.bisect_right(self.totals, rnd)
        return self.weights[i][0]

Answer 2

Assuming the list of monsters and their rarities doesn't change during gameplay too often, you can precompute the totalchance variable and also a list of the partial sums, that is, the sums of the rarities of the first n monsters. Something like this:

# During initialization
totalchance = 0
partialsums = []
for monster in monsterlist:
    totalchance += monster[1]
    partialsums.append(totalchance)

# When spawning a monster
import bisect
chance = random.randint(0, totalchance)
monsterindex = bisect.bisect_left(partialsums, chance)
monstertospawn = monsterlist[monsterindex]
# Spawn an instance of monstertospawn...

Answer 3

If I'm understanding your question correctly, you are concerned about the complexity of your spawning code. You could probably benefit from some sorting. Start by sorting your spawn table by "rarity." Whenever your code wants to determine whether "by chance" something spawns or not, you could "roll the dice" and iterate through your sorted list to quickly find the "rarest" object that could spawn given your "roll."

Also, this is a good example of an algorithm that could be later optimized. I would suggest you just write it and later on when your game has taken shape, profile the game and see if this function is even consuming a considerable amount of time. If it's not, optimizing it will realize you virtually no gains.

Answer 4

I don't really know python at all.

If your monster list changes often classical weighted chance probably won't work for you, at least if you are pedantic about performance. The problem lies in calculating the maximum chance; you need to iterate over the list at least twice to get the value.

Option 1: Custom List

By creating a custom list class you can skip one loop over the values.

Let's say for instance we have some MonsterList class that you can use as follows:

monsterlist = MonsterList()
monsterlist.add('snake', 60);
monsterlist.add('troll', 80); # problem?
monsterlist.add('antlion', 30);

The internal representation would actually be:

[
  { 'snake', 0 } # 0
  { 'troll', 60 } # 0 + 60
  { 'antlion', 140 } # 0 + 60 + 80
  # 0 + 60 + 80 + 30 = 170
]

In other words the list would be keeping track of an internal total as you create it. To get a value you have a further two sub-options, in both cases you will need to choose a value between 0 and 170 (the current internal total).

Linear Search (O(n))

Simply loop over the list until the current item has a value less than the random value.

Binary Search (O(log2N))

Extend the internal representation to the following:

[
  { 'snake', 0, 60 } # 0
  { 'troll', 60, 140 } # 0 + 60
  { 'antlion', 140, 270 } # 0 + 60 + 80
  # 0 + 60 + 80 + 30 = 170
]

Now perform your basic binary search over the list, stopping when the random value is within the range in the internal representation.

This works because of the way we add values to the list; the running total is guaranteed to be sorted.

Option 2: Multiple Additions

Another option is to add each monster to the list multiple times, however, depending on how granular the weights could be you could land up with a rather large list - so this would be a memory-performance trade-off.

monsterlist = []

snake = 'snake'
troll = 'troll'
antlion = 'antlion'

# snake is twice as likely to appear in comparison to antlion.
# troll is three times as likely to appear in comparison to antlion.
# troll is 1.5 times as likely to appear in comparison to snake.
monsterlist.append(snake, snake, troll, troll, troll, antlion)

Getting a value from that list would merely involve choose a random index (given the count) and indexing the list directly (O(1)).

Answer 5

If the list of monster frequencies changes very frequently, you can't do much better than this. (Although keeping the list sorted in decreasing order of frequency, and keeping track of the total frequency so you don't need to recompute it, lets you avoid traversing the whole list most of the time.)

If the list doesn't change very often, there's a trick that lets you do fast lookups at the cost of some precalculation. I'll write up a better description of it here later when I have more time, but in the mean time take a look at this old Usenet thread ("Seeking reference for O(1) random variable lookup algorithm" in sci.crypt.random-numbers).

Finally, I second stephelton's advice: don't spend too much time optimizing this before you've profiled your code and found out how much time it's actually taking.