Как создать взвешенную коллекцию, а затем выбрать из нее случайный элемент?

34

У меня есть ящик для лута, который я хочу заполнить случайным предметом. Но я хочу, чтобы у каждого предмета был свой шанс быть выбранным. Например:

  • 5% шанс 10 золота
  • 20% шанс меча
  • 45% шанс щита
  • 20% шанс брони
  • 10% шанс зелья

Как я могу сделать так, чтобы я выбрал точно один из пунктов выше, где эти проценты являются соответствующими шансами на получение добычи?

Evorlor
источник
1
К сведению, теоретически O (1) время на выборку возможно для любого конечного распределения, даже для распределения, элементы которого меняются динамически. См. Например, cstheory.stackexchange.com/questions/37648/… .
Нил Янг

Ответы:

37

Мягкое решение вероятностей

Жестко запрограммированное вероятностное решение имеет тот недостаток, что вам необходимо установить вероятности в своем коде. Вы не можете определить их во время выполнения. Это также трудно поддерживать.

Вот динамическая версия того же алгоритма.

  1. Создайте массив пар фактических предметов и веса каждого предмета
  2. Когда вы добавляете элемент, вес элемента должен быть его собственным весом плюс сумма весов всех элементов, уже находящихся в массиве. Таким образом, вы должны отслеживать сумму отдельно. Тем более, что оно понадобится вам для следующего шага.
  3. Чтобы получить объект, сгенерируйте случайное число между 0 и суммой весов всех элементов.
  4. итерируйте массив от начала до конца, пока не найдете запись с весом, большим или равным случайному числу

Вот пример реализации в Java в форме класса шаблона, который вы можете создать для любого объекта, который использует ваша игра. Затем вы можете добавить объекты с помощью метода .addEntry(object, relativeWeight)и выбрать одну из записей, которые вы добавили ранее с.get()

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class WeightedRandomBag<T extends Object> {

    private class Entry {
        double accumulatedWeight;
        T object;
    }

    private List<Entry> entries = new ArrayList<>();
    private double accumulatedWeight;
    private Random rand = new Random();

    public void addEntry(T object, double weight) {
        accumulatedWeight += weight;
        Entry e = new Entry();
        e.object = object;
        e.accumulatedWeight = accumulatedWeight;
        entries.add(e);
    }

    public T getRandom() {
        double r = rand.nextDouble() * accumulatedWeight;

        for (Entry entry: entries) {
            if (entry.accumulatedWeight >= r) {
                return entry.object;
            }
        }
        return null; //should only happen when there are no entries
    }
}

Использование:

WeightedRandomBag<String> itemDrops = new WeightedRandomBag<>();

// Setup - a real game would read this information from a configuration file or database
itemDrops.addEntry("10 Gold",  5.0);
itemDrops.addEntry("Sword",   20.0);
itemDrops.addEntry("Shield",  45.0);
itemDrops.addEntry("Armor",   20.0);
itemDrops.addEntry("Potion",  10.0);

// drawing random entries from it
for (int i = 0; i < 20; i++) {
    System.out.println(itemDrops.getRandom());
}

Вот тот же класс, реализованный в C # для вашего проекта Unity, XNA или MonoGame:

using System;
using System.Collections.Generic;

class WeightedRandomBag<T>  {

    private struct Entry {
        public double accumulatedWeight;
        public T item;
    }

    private List<Entry> entries = new List<Entry>();
    private double accumulatedWeight;
    private Random rand = new Random();

    public void AddEntry(T item, double weight) {
        accumulatedWeight += weight;
        entries.Add(new Entry { item = item, accumulatedWeight = accumulatedWeight });
    }

    public T GetRandom() {
        double r = rand.NextDouble() * accumulatedWeight;

        foreach (Entry entry in entries) {
            if (entry.accumulatedWeight >= r) {
                return entry.item;
            }
        }
        return default(T); //should only happen when there are no entries
    }
}

И вот один в JavaScript :

var WeightedRandomBag = function() {

    var entries = [];
    var accumulatedWeight = 0.0;

    this.addEntry = function(object, weight) {
        accumulatedWeight += weight;
        entries.push( { object: object, accumulatedWeight: accumulatedWeight });
    }

    this.getRandom = function() {
        var r = Math.random() * accumulatedWeight;
        return entries.find(function(entry) {
            return entry.accumulatedWeight >= r;
        }).object;
    }   
}

Pro:

  • Может обрабатывать любые весовые коэффициенты. Вы можете иметь предметы с астрономически малой вероятностью в наборе, если хотите. Весам также не нужно прибавлять до 100.
  • Вы можете прочитать предметы и веса во время выполнения
  • Использование памяти пропорционально количеству элементов в массиве

Contra:

  • Требуется больше программирования, чтобы получить право
  • В худшем случае вам может понадобиться выполнить итерацию всего массива ( O(n)сложность во время выполнения). Поэтому, когда у вас очень большой набор предметов и вы часто рисуете, это может стать медленным. Простая оптимизация заключается в том, чтобы сначала поставить наиболее вероятные элементы, чтобы в большинстве случаев алгоритм завершался рано. Более сложная оптимизация, которую вы можете сделать, состоит в том, чтобы использовать тот факт, что массив отсортирован, и выполнить поиск пополам. Это займет O(log n)время.
  • Вам нужно создать список в памяти, прежде чем вы сможете его использовать (хотя вы можете легко добавлять элементы во время выполнения. Удаление элементов также может быть добавлено, но для этого потребуется обновить накопленные веса всех элементов, которые появляются после удаленной записи, что снова имеет O(n)худшее время выполнения)
Philipp
источник
2
Код C # может быть написан с использованием LINQ: return records.FirstOrDefault (e => e.accumulatedWeight> = r). Что еще более важно, существует небольшая вероятность того, что из-за потери точности с плавающей запятой этот алгоритм вернет ноль, если случайное значение будет чуть-чуть больше, чем накопленное значение. В качестве меры предосторожности вы можете добавить небольшое значение (скажем, 1.0) к последнему элементу, но тогда вам придется явно указать в своем коде, что список является окончательным.
IMil
1
Один небольшой вариант, который я использовал лично, если вы хотите, чтобы значения веса во время выполнения не изменялись на значение «вес плюс все предыдущие», вы можете вычесть вес каждой переданной записи из вашего случайного значения, останавливаясь, когда случайное значение меньше текущего веса предметов (или когда вычитание веса делает значение <0)
Лунин
2
@ BlueRaja-DannyPflughoeft преждевременная оптимизация ... вопрос был о выборе объекта из открытого окна добычи Кто собирается открывать 1000 ящиков в секунду?
IMil
4
@IMil: Нет, этот вопрос является общим для выбора случайных взвешенных предметов . В частности, для лутбоксов этот ответ, вероятно, подходит, потому что есть небольшое количество элементов и вероятности не меняются (хотя, поскольку они обычно делаются на сервере, 1000 / сек не является нереальным для популярной игры) .
BlueRaja - Дэнни Пфлугхофт
4
@opa, затем отметьте, чтобы закрыть как обман. Действительно ли неправильно давать хороший ответ только потому, что вопрос уже задавался раньше?
Балдрикк
27

Примечание: я создал библиотеку C # для этой конкретной проблемы

Другие решения хороши, если у вас есть только небольшое количество предметов, и ваши вероятности никогда не меняются. Однако с большим количеством элементов или изменением вероятностей (например, удаление элементов после их выбора) вам понадобится что-то более мощное.

Вот два наиболее распространенных решения (оба из которых включены в вышеуказанную библиотеку)

Метод псевдонима Уокера

Умное решение, которое очень быстро ( O(1)!), Если ваши вероятности постоянны. По сути, алгоритм создает 2D-дартс («таблицу псевдонимов») из ваших вероятностей и бросает в нее дротик.

мишень для дротиков

Есть много статей в Интернете о том, как это работает, если вы хотите узнать больше.

Единственная проблема заключается в том, что если ваши вероятности изменяются, вам необходимо заново создать таблицу псевдонимов, что является медленным. Таким образом, если вам нужно удалить предметы после того, как они собраны, это не решение для вас.

Основанное на дереве решение

Другое распространенное решение - создать массив, в котором каждый элемент хранит сумму вероятности и всех элементов перед ним. Затем просто сгенерируйте случайное число из [0,1) и выполните двоичный поиск, где это число попадает в список.

Это решение очень легко кодировать / понимать, но выбор выполняется медленнее, чем метод псевдонима Уокера, и изменение вероятностей все еще происходит O(n). Мы можем улучшить его, превратив массив в дерево бинарного поиска, где каждый узел отслеживает сумму вероятностей во всех элементах своего поддерева. Затем, когда мы генерируем число из [0,1), мы можем просто пройтись по дереву, чтобы найти элемент, который оно представляет.

Это дает нам O(log n)возможность выбрать предмет и изменить вероятности! Это делает NextWithRemoval()очень быстро!

Результаты

Вот несколько быстрых тестов из приведенной выше библиотеки, сравнивающих эти два подхода

         Тесты WeightedRandomizer | Дерево | Стол
-------------------------------------------------- ---------------------------------
Добавить () x10000 + NextWithReplacement () x10: | 4 мс | 2 мс
Добавить () x10000 + NextWithReplacement () x10000: | 7 мс | 4 мс
Добавить () x10000 + NextWithReplacement () x100000: | 35 мс | 28 мс
(Add () + NextWithReplacement ()) x10000 (с чередованием) | 8 мс | 5403 мс
Добавить () x10000 + NextWithRemoval () x10000: | 10 мс | 5948 мс

Итак, как вы можете видеть, для особого случая статических (неизменяемых) вероятностей метод псевдонима Уокера работает примерно на 50-100% быстрее. Но в более динамичных случаях дерево на несколько порядков быстрее !

BlueRaja - Дэнни Пфлугхофт
источник
Древовидное решение также дает нам достойное время выполнения ( nlog(n)) при сортировке элементов по весу.
Натан Меррилл
2
Я скептически отношусь к вашим результатам, но это правильный ответ. Не уверен, почему это не лучший ответ, учитывая, что это на самом деле канонический способ решения этой проблемы.
WHN
Какой файл содержит решение на основе дерева? Во-вторых, ваша таблица тестов: алиас Уокера - это столбец «таблица»?
Якк
1
@Yakk: код для древовидного решения здесь . Она построена на реализацию с открытым исходным кодом в качестве AA-дерева . И «да» на ваш второй вопрос.
BlueRaja - Дэнни Пфлюгофт
1
Часть Walker довольно просто только для ссылок.
накопление
17

Решение Колесо Фортуны

Вы можете использовать этот метод, когда вероятности в вашем пуле предметов имеют довольно большой общий знаменатель, и вам нужно очень часто использовать его.

Создайте массив опций. Но вставляйте каждый элемент в него несколько раз, причем количество дубликатов каждого элемента пропорционально его вероятности появления. В приведенном выше примере все элементы имеют вероятности, которые являются множителями 5%, поэтому вы можете создать массив из 20 элементов, например:

10 gold
sword
sword
sword
sword
shield
shield
shield
shield
shield
shield
shield
armor
armor
armor
armor
potion
potion

Затем просто выберите случайный элемент этого списка, сгенерировав одно случайное целое число от 0 до длины массива - 1.

Недостатки:

  • Вам нужно создать массив при первом создании элемента.
  • Когда предполагается, что один из ваших элементов имеет очень низкую вероятность, вы получите действительно большой массив, который может потребовать много памяти.

Преимущества:

  • Если у вас уже есть массив и вы хотите рисовать его несколько раз, тогда он очень быстрый. Только одно случайное целое число и один доступ к массиву.
Philipp
источник
3
В качестве гибридного решения, позволяющего избежать второго недостатка, вы можете обозначить последний слот как «другой» и обрабатывать его другими способами, такими как подход с использованием массива Филиппа. Таким образом, вы можете заполнить этот последний слот массивом с вероятностью 99,9% зелья и шансом 0,1% Epic Scepter of the Apocalypse. Такой двухуровневый подход использует преимущества обоих подходов.
Cort Ammon - Восстановить Монику
1
Я использую несколько вариантов этого в моем собственном проекте. Что я делаю, так это вычисляю каждый элемент и вес и сохраняю их в массиве, [('gold', 1),('sword',4),...]суммирую все веса, а затем выбрасываю случайное число от 0 до суммы, затем повторяю массив и вычисляю, где приземляется случайное число (т.е. а reduce) Прекрасно работает с массивами, которые часто обновляются, и не требует значительных потерь памяти.
1
@Thebluefish Это решение описано в моем другом ответе «Решение с мягким кодом вероятностей»
Филипп,
7

Жестко-вероятностное решение

Самый простой способ найти случайный элемент из взвешенной коллекции - это пройти по цепочке операторов if-else, где каждое if-else увеличивается, вероятно, так как предыдущий не попадает.

int rand = random(100); //Random number between 1 and 100 (inclusive)
if(rand <= 5) //5% chance
{
    print("You found 10 gold!");
}
else if(rand <= 25) //20% chance
{
    print("You found a sword!");
}
else if(rand <= 70) //45% chance
{
    print("You found a shield!");
}
else if(rand <= 90) //20% chance
{
    print("You found armor!");
}
else //10% chance
{
    print("You found a potion!");
}

Причина, по которой условные выражения равны его вероятности плюс все предыдущие возможности условных вычислений, заключается в том, что предыдущие условные обозначения уже исключили возможность того, что они являются этими элементами. Таким образом, для условного щита else if(rand <= 70)70 равно 45% шанса щита, плюс 5% шанса золота и 20% шанса меча.

Преимущества:

  • Легко программировать, потому что не требует структур данных.

Недостатки:

  • Сложно поддерживать, потому что вам нужно поддерживать частоту выпадения в вашем коде. Вы не можете определить их во время выполнения. Поэтому, если вы хотите получить что-то большее в будущем, вы должны проверить другие ответы.
Evorlor
источник
3
Это было бы очень неприятно поддерживать. Например, если вы хотите удалить золото, и чтобы зелье заняло свое место, вам нужно отрегулировать вероятности всех предметов между ними.
Александр - Восстановить Монику
1
Чтобы избежать проблемы, о которой упоминает @Alexander, вместо этого вы можете вычитать текущую скорость на каждом шаге, а не добавлять ее к каждому условию.
AlexanderJ93
2

В C # вы можете использовать сканирование Linq для запуска вашего аккумулятора, чтобы проверить случайное число в диапазоне от 0 до 100.0f и .First (), чтобы получить. Так что, как одна строка кода.

Так что-то вроде:

var item = a.Select(x =>
{
    sum += x.prob;
    if (rand < sum)
        return x.item;
    else
        return null;
 }).FirstOrDefault());

sumявляется инициализированным нулем целым числом и aявляется списком вероятностей / элементов структуры / кортежей / экземпляров. randранее сгенерированное случайное число в диапазоне.

Это просто накапливает сумму по списку диапазонов до тех пор, пока она не превысит ранее выбранное случайное число, и возвращает либо элемент, либо ноль, где ноль будет возвращено, если диапазон случайных чисел (например, 100) меньше общего диапазона взвешивания по ошибке и выбранное случайное число находится за пределами общего диапазона взвешивания.

Однако вы заметите, что веса в OP близко соответствуют нормальному распределению (кривая Белла). Я думаю, что в общем случае вам не понадобятся конкретные диапазоны, вы будете стремиться к распределению, которое сужается либо вокруг кривой колокола, либо только на убывающей экспоненциальной кривой (например). В этом случае вы можете просто использовать математическую формулу для генерации индекса в массив элементов, отсортированных в порядке предпочтительной вероятности. Хорошим примером является CDF в нормальном распределении

Также пример здесь .

Другой пример - вы можете взять случайное значение от 90 градусов до 180 градусов, чтобы получить нижний правый квадрант круга, взять компонент x с помощью cos (r) и использовать его для индексации в списке приоритетов.

С различными формулами вы можете иметь общий подход, при котором вы просто вводите список приоритетов любой длины (например, N) и отображаете результат формулы (например, cos (x) от 0 до 1) путем умножения (например, Ncos (x) ) = От 0 до N), чтобы получить индекс.

часовой
источник
3
Не могли бы вы дать нам эту строку кода, если это всего лишь одна строка? Я не так хорошо знаком с C #, поэтому я не знаю, что вы имеете в виду.
HEGX64
@HEGX64 added but using mobile and editor not working. Can you edit?
Sentinel
4
Can you change this answer to explain the concept behind it, rather than a specific imlementation in a specific language?
Raimund Krämer
@RaimundKrämer Erm, done?
Sentinel
Downvote without explanation = useless and antisocial.
WGroleau
1

Probabilities don’t need to be hard-coded. The items and the thresholds can be together in an array.

for X in itemsrange loop
  If items (X).threshold < random() then
     Announce (items(X).name)
     Exit loop
  End if
End loop

You do have to accumulate the thresholds still, but you can do it when creating a parameter file instead of coding it.

WGroleau
источник
3
Could you elaborate on how to calculate the correct threshold? For example, if you have three items with 33% chance each, how would you build this table? Since a new random() is generated each time, the first would need 0.3333, the second would need 0.5 and the last would need 1.0. Or did I read the algorithm wrong?
pipe
You compute it the way others did in their answers. For equal probabilities of X items, the first threshold is 1/X, the second, 2/X, etc.
WGroleau
Doing that for 3 items in this algorithm would make the thresholds 1/3, 2/3 and 3/3 but the outcome probabilities 1/3, 4/9 and 2/9 for the first, second and third item. Do you really mean to have the call to random() in the loop?
pipe
No, that's definitely a bug. Each check needs the same random number.
WGroleau
0

I done this function: https://github.com/thewheelmaker/GDscript_Weighted_Random Now! in your case you can use it like this:

on_normal_case([5,20,45,20,10],0)

It gives just a number between 0 to 4 but you can put it in array where you got the items.

item_array[on_normal_case([5,20,45,20,10],0)]

Or in function:

item_function(on_normal_case([5,20,45,20,10],0))

Here is the code. I made it on GDscript, you can, but it can alter other language, also check for logic errors:

func on_normal_case(arrayy,transformm):
    var random_num=0
    var sum=0
    var summatut=0
    #func sumarrays_inarray(array):
    for i in range(arrayy.size()):
        sum=sum+arrayy[i]
#func no_fixu_random_num(here_range,start_from):
    random_num=randi()%sum+1
#Randomies be pressed down
#first start from zero
    if 0<=random_num and random_num<=arrayy[0]:
        #print(random_num)
        #print(array[0])
        return 0+ transformm
    summatut=summatut+arrayy[0]
    for i in range(arrayy.size()-1):
        #they must pluss together
        #if array[i]<=random_num and random_num<array[i+1]:
        if summatut<random_num and random_num<=summatut+arrayy[i+1]:
            #return i+1+transform
            #print(random_num)
            #print(summatut)
            return i+1+ transformm

        summatut=summatut+arrayy[i+1]
    pass

It works like this: on_normal_case([50,50],0) This gives 0 or 1, it has same probability both.

on_normal_case([50,50],1) This gives 1 or 2, it has same probability both.

on_normal_case([20,80],1) This gives 1 or 2, it has bigger change to get two.

on_normal_case([20,80,20,20,30],1) This give random numbers range 1-5 and bigger numbers are more likely than smaller numbers.

on_normal_case([20,80,0,0,20,20,30,0,0,0,0,33],45) This throw dices between numbers 45,46,49,50,51,56 you see when there is zero it never occure.

So it function returns just one random number that depends lenght of that arrayy array and transformm number, and ints in the array are probability weights that a number might occure, where that number is location on the array, pluss transformm number.

Narutofan
источник