# Mob level distribution

Distributing mobs in a dungeon based on player’s level (or some dungeon level difficulty factor) was somewhat straightforward, but I would still like to document the progress. I needed to place a mob that’s somewhat within the difficulty level I want, plus minus a few difficulty levels to spice it up.

Above you can see three rats, three cats, a dog (`r`

, `c`

, `d`

, all level 1), a
farmer (`f`

, level 2), and a lonely bandit (`b`

, level 3) in a level 1 dungeon.

Without going straight into measure theory, I generated intervals for each mob based on the diff of desired level and their level, and then randomly selected a point within the boundaries. Here’s the abstract code:

```
import bisect
import random
def get_random_element(data, target, chance):
"""Get random element from data set skewing towards target.
Args:
data -- A dictionary with keys as elements and values as weights.
Duplicates are allowed.
target -- Target weight, results will be skewed towards target
weight.
chance -- A float 0..1, a factor by which chance of picking adjacent
elements decreases (i.e, with chance 0 we will always
select target element, with chance 0.5 probability of
selecting elements adjacent to target are halved with each
step).
Returns:
A random key from data with distribution respective of the target
weight.
"""
intervals = [] # We insert in order, no overlaps.
next_i = 0
for element, v in data.iteritems():
d = max(target, v) - min(target, v)
size = 100
while d > 0: # Decrease chunk size for each step of `d`.
size *= chance
d -= 1
if size == 0:
continue
size = int(size)
intervals.append((next_i, next_i + size, element))
next_i += size + 1
fst, _, _ = zip(*intervals)
rnd = random.randint(0, next_i - 1)
idx = bisect.bisect(fst, rnd) # This part is O(log n).
return intervals[idx - 1][2]
```

Now, if I test the above for, say, a 1000000 iterations, with a chance of 0.5 (halving probability of selecting adjacent elements with each step), and 2 as a target, here’s the distribution I end up with:

```
target, chance, iterations = 2, 0.5, 1000000
data = collections.OrderedDict([ # Ordered to make histogram prettier.
('A', 0), ('B-0', 1), ('B-1', 1), ('C', 2), ('D', 3), ('E', 4),
('F', 5), ('G', 6), ('H', 7), ('I', 8), ('J', 9),
])
res = collections.OrderedDict([(k, 0) for k, _ in data.iteritems()])
# This is just a test, so there's no need to optimize this for now.
for _ in xrange(iterations):
res[get_random_element(data, target, chance)] += 1
pyplot.bar(
range(len(res)), res.values(), width=0.7, align='center', color='green')
pyplot.xticks(range(len(res)), res.keys())
pyplot.title(
'iterations={}, target={}, chance={}'.format(
iterations, target, chance))
pyplot.show()
```

You can see elements B-0 and B-1 having roughly the same distribution, since they have the same weight.

Now, if I decrease the `chance`

, likelihood of target being selected increases,
while likelihood of surrounding elements being selected decreases:

I works the opposite way as well, increasing the `chance`

decreases likelihood
of the target being selected and increases the probability for surrounding
elements.

For the sake of completeness, it works with 0 chance of surrounding elements being picked:

And an equal chance of picking surrounding elements:

After playing around with the configuration in Jupyter Notebook, I cleaned up the algorithm above and included it into mob placement routine.