Weighted random selector for Unity.
Created by Hiroya Aramaki (Makihiro)
Weighted Random Selector is an algorithm for randomly selecting elements based on their weights.
For example.
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);
}
ToWeightedSelector
Overloads 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);
}
Dictionary<TItem,float>
pattern 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.
WeightedSelectMethod.Linear
) The simplest algorithm that walks linearly along the weights.
This method is an O(n)
operation, where n
is number of weights.
WeightedSelectMethod.Binary
) 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.
WeightedSelectMethod.Alias
) 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.
This library is under the MIT License.