Created by Hiroya Aramaki (Makihiro)
Weighted Random Selector is an algorithm for randomly selecting elements based on their weights.
For example.
- Drop items based on rarity.
- Events that occur with a certain probability
It can be used to determine things with probability.
Choice is a library that was created to make it easier to implement.
// This is the simplest usage.
var randomSelectedItem = items
.ToWeightedSelector(item => item.weight)
.SelectItemWithUnityRandom();
Great introduction article on Weighted Random Select: https://blog.bruce-hill.com/a-faster-weighted-random-choice
Download any version from releases.
Releases: https://github.com/mackysoft/Choice/releases
Or, you can add this package by opening PackageManager and entering
https://github.com/mackysoft/Choice.git?path=Assets/MackySoft/MackySoft.Choice
from the Add package from git URL
option.
Or, you can install this package from the Open UPM registry.
More details here.
openupm add com.mackysoft.choice
// To use Choice, add this namespace.
using MackySoft.Choice;
public class WeightedItem {
public string id;
public float weight;
}
public WeightedItem SelectItem () {
// Prepare weighted items.
var items = new WeightedItem[] {
new WeightedItem { id = "π", weight = 8f },
new WeightedItem { id = "π", weight = 4f },
new WeightedItem { id = "π", weight = 0f },
new WeightedItem { id = "π", weight = 6f },
new WeightedItem { id = "π", weight = -1f }
};
// Create the WeightedSelector.
var weightedSelector = items.ToWeightedSelector(item => item.weight);
// The probability of each item being selected,
// π is 44%, π is 22%, and π is 33%.
// π and π will never be selected because their weights are less or equal to 0.
return weightedSelector.SelectItemWithUnityRandom();
// Same as weightedSelector.SelectItem(UnityEngine.Random.value);
}
The ToWeightedSelector
method has many overloads and can be used for a variety of patterns.
public struct ItemEntry {
public Item item;
public float weight;
}
public IWeightedSelector<Item> WeightedEntryPattern () {
var entries = new ItemEntry[] {
new ItemEntry { item = new Item { id = "π" }, weight = 1f },
new ItemEntry { item = new Item { id = "π" }, weight = 5f },
new ItemEntry { item = new Item { id = "π" }, weight = 3f }
};
// Create a WeightedSelector by selecting item and weight from entry respectively.
return entries.ToWeightedSelector(
itemSelector: entry => entry.item,
weightSelector: entry => entry.weight
);
}
public class WeightedItem {
public string id;
public float weight;
}
public IWeightedSelector<WeightedItem> WeightedItemPattern () {
var items = new WeightedItem[] {
new WeightedItem { id = "π", weight = 1f },
new WeightedItem { id = "π", weight = 5f },
new WeightedItem { id = "π", weight = 3f }
};
// Create a WeightedSelector using the weight of the WeightedItem.
return fromWeightedItem = items.ToWeightedSelector(weightSelector: item => item.weight);
}
public class Item {
public string id;
}
public IWeightedSelector<Item> DictionaryPattern () {
// This need a Dictionary<TItem,float>. (Strictly speaking, IEnumerable<KeyValuePair<TItem,float>>)
var dictionary = new Dictionary<Item,float>(
{ new Item { id = "π" }, 1f },
{ new Item { id = "π" }, 5f },
{ new Item { id = "π" }, 3f }
);
// Create a WeightedSelector with the dictionary key as item and value as weight.
return dictionary.ToWeightedSelector();
}
Since the ToWeightedSelector
method is defined as an extension of IEnumerable<T>
, it can be connected from the LINQ query operators.
var randomSelectedItem = items
.Where(item => item != null) // null check
.ToWeightedSelector(item => item.weight)
.SelectItemWithUnityRandom();
When creating a WeightedSelector, you can specify the IWeightedSelectMethod
.
var weightedSelector = items.ToWeightedSelector(
item => item.weight,
WeightedSelectMethod.Binary // Use the binary search algorithm.
);
All ToWeightedSelector
methods can specify IWeightedSelectMethod
.
If this is not specified, the linear scan algorithm will be used automatically.
The simplest algorithm that walks linearly along the weights.
This method is an O(n)
operation, where n
is number of weights.
The binary search algorithm that is faster than linear scan by preprocessing to store the current sum of weights.
It has an additional storage cost of O(n)
, but is accelerated by up to O(log(n))
for each selection, where n
is number of weights.
The fastest algorithm.
It takes O(n)
run time to set up, but the selection is performed in O(1)
run time,
where n
is number of weights.
Therefore, this is a very effective algorithm for selecting multiple items.
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.0104ms | 0.0055ms | 0.0081ms | 0.0393ms | 0.3408ms |
Binary Search | 0.0091ms | 0.0083ms | 0.0126ms | 0.0659ms | 0.5944ms |
Alias Method | 0.0069ms | 0.0065ms | 0.01ms | 0.0459ms | 0.4094ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.0155ms | 0.0064ms | 0.0077ms | 0.0381ms | 0.353ms |
Binary Search | 0.0077ms | 0.008ms | 0.0123ms | 0.0659ms | 0.5919ms |
Alias Method | 0.0062ms | 0.0065ms | 0.01ms | 0.0462ms | 0.41ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.009ms | 0.0053ms | 0.0081ms | 0.0378ms | 0.3388ms |
Binary Search | 0.0073ms | 0.0079ms | 0.0129ms | 0.0653ms | 0.5927ms |
Alias Method | 0.0054ms | 0.0062ms | 0.0104ms | 0.0461ms | 0.4194ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.0113ms | 0.0077ms | 0.0182ms | 0.1219ms | 1.19ms |
Binary Search | 0.0109ms | 0.0114ms | 0.0237ms | 0.158ms | 1.4975ms |
Alias Method | 0.0136 | 0.022ms | 0.0151ms | 0.0601ms | 0.5041ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.012ms | 0.0072ms | 0.0174ms | 0.1272ms | 1.1738ms |
Binary Search | 0.0095ms | 0.0099ms | 0.023ms | 0.16ms | 1.5503ms |
Alias Method | 0.0141ms | 0.0104ms | 0.0148ms | 0.0618ms | 0.5235ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.0095ms | 0.009ms | 0.0179ms | 0.1216ms | 1.1503ms |
Binary Search | 0.0096ms | 0.0103ms | 0.0225ms | 0.1572ms | 1.4991ms |
Alias Method | 0.0129ms | 0.0105ms | 0.015ms | 0.0607ms | 0.5176ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.0201ms | 0.024ms | 0.0822ms | 0.741ms | 7.2211ms |
Binary Search | 0.0212ms | 0.0211ms | 0.0433ms | 0.3118ms | 2.6434ms |
Alias Method | 0.0717ms | 0.0364ms | 0.0395ms | 0.086ms | 0.5462ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.0231ms | 0.0247ms | 0.0855ms | 0.7027ms | 7.0025ms |
Binary Search | 0.0224ms | 0.0231ms | 0.0441ms | 0.2776ms | 2.6521ms |
Alias Method | *0.039ms | 0.0358ms | 0.0405ms | 0.0861ms | 0.5561ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.0194ms | 0.0232ms | 0.0892ms | 0.7582ms | 7.1886ms |
Binary Search | 0.0206ms | 0.0218ms | 0.0447ms | 0.2804ms | 2.6375ms |
Alias Method | 0.0376ms | 0.0381ms | 0.0413ms | 0.0871ms | 0.5728ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.1147ms | 0.1672ms | 0.7792ms | 6.7539ms | 66.8329ms |
Binary Search | 0.1205ms | 0.1183ms | 0.1504ms | 0.4758ms | 3.7755ms |
Alias Method | 0.2783ms | 0.2722ms | 0.2925ms | 0.3238ms | 0.7824ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.1068ms | 0.1717ms | 0.8331ms | 6.8282ms | 68.455ms |
Binary Search | 0.1217ms | 0.1173ms | 0.1499ms | 0.5026ms | 3.7627ms |
Alias Method | 0.2785ms | 0.2889ms | 0.2876ms | 0.3318ms | 0.908ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.102ms | 0.1636ms | 0.7271ms | 6.743ms | 66.4393ms |
Binary Search | 0.1241ms | 0.1208ms | 0.1501ms | 0.5216ms | 4.0165ms |
Alias Method | 0.2782ms | 0.2755ms | 0.2777ms | 0.3454ms | 0.8068ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 1.1885ms | 1.7971ms | 8.0482ms | 69.1749ms | 664.8696ms |
Binary Search | 1.3329ms | 1.3181ms | 1.3454ms | 1.7735ms | 6.1215ms |
Alias Method | 2.8859ms | 2.8719ms | 2.8832ms | 2.9779ms | 3.4764ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 1.1676ms | 1.6953ms | 8.0905ms | 70.1629ms | 668.3197ms |
Binary Search | 1.3118ms | 1.3361ms | 1.3407ms | 1.786ms | 6.1105ms |
Alias Method | 2.8833ms | 2.934ms | 2.951ms | 2.9845ms | 3.6259ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 1.3098ms | 1.9826ms | 8.063ms | 68.9301ms | 666.9364ms |
Binary Search | 1.4456ms | 1.3787ms | 4.6233ms | 1.7861ms | 6.0783ms |
Alias Method | 2.9751ms | 2.9144ms | 2.9236ms | 2.9851ms | 3.5149ms |
Iterations | 1 | 10 | 100 | 1000 | 10000 |
---|---|---|---|---|---|
Linear Scan | 0.0207ms | 0.7364ms | 6.5433ms | 67.3963ms | 671.3184ms |
Binary Search | 0.0015ms | 0.0055ms | 0.0492ms | 0.496ms | 4.828ms |
Alias Method | 0.0005ms | 0.0011ms | 0.0066ms | 0.0579ms | 0.5559ms |
Hiroya Aramaki is a indie game developer in Japan.
- Blog: https://mackysoft.net/blog
- Twitter: https://twitter.com/makihiro_dev
This library is under the MIT License.