1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
/**
* @file
* @brief Functions for picking random entries from weighted, gradiated lists
**/
#ifndef RANDOMPICK_H
#define RANDOMPICK_H
#include "random.h"
enum distrib_type
{
FLAT, // full chance throughout the range
SEMI, // 50% chance at range ends, 100% in the middle
PEAK, // 0% chance just outside range ends, 100% in the middle, range
// ends typically get ~20% or more
UP, // linearly from near-zero to 100%, increasing with depth
DOWN, // linearly from 100% at the start to near-zero
};
template <typename T>
struct random_pick_entry
{
int minr;
int maxr;
int rarity; // 0..1000
distrib_type distrib;
T value;
};
template <typename T, int max>
class random_picker
{
public:
virtual ~random_picker();
T pick(const random_pick_entry<T> *weights, int level, T none);
int rarity_at(const random_pick_entry<T> *pop,
int depth);
virtual bool veto(T val) { return false; }
};
template <typename T, int max>
random_picker<T, max>::~random_picker()
{
}
template <typename T, int max>
T random_picker<T, max>::pick(const random_pick_entry<T> *weights, int level,
T none)
{
struct { T value; int rarity; } valid[max];
int nvalid = 0;
int totalrar = 0;
for (const random_pick_entry<T> *pop = weights; pop->rarity; pop++)
{
if (level < pop->minr || level > pop->maxr)
continue;
if (veto(pop->value))
continue;
int rar = rarity_at(pop, level);
ASSERTM(rar > 0, "Rarity %d: %d at level %d", rar, pop->value, level);
valid[nvalid].value = pop->value;
valid[nvalid].rarity = rar;
totalrar += rar;
nvalid++;
}
if (!nvalid)
return none;
totalrar = random2(totalrar); // the roll!
for (int i = 0; i < nvalid; i++)
if ((totalrar -= valid[i].rarity) < 0)
return valid[i].value;
die("random_pick roll out of range");
}
template <typename T, int max>
int random_picker<T, max>::rarity_at(const random_pick_entry<T> *pop, int depth)
{
// 2520 is divisible by any number 1..10, and provides enough scale
// to make round-off errors even for degenerate distributions ok.
int rar = pop->rarity * 2520;
int len = pop->maxr - pop->minr;
switch (pop->distrib)
{
case FLAT: // 100% everywhere
return rar;
case SEMI: // 100% in the middle, 50% at the edges
if (len)
len *= 2;
else
len += 2; // a single-level range
return rar * (len - abs(pop->minr + pop->maxr - 2 * depth))
/ len;
case PEAK: // 100% in the middle, small at the edges, 0% outside
len += 2; // we want it to zero outside the range, not at the edge
return rar * (len - abs(pop->minr + pop->maxr - 2 * depth))
/ len;
case UP:
return rar * (depth - pop->minr + 1) / (len + 1);
case DOWN:
return rar * (pop->maxr - depth + 1) / (len + 1);
}
die("bad distrib");
}
#endif
|