Mam skrzynkę z łupami, którą chcę wypełnić losowym przedmiotem. Ale chcę, aby każdy przedmiot miał inną szansę na wybranie. Na przykład:

• 5% szansy na 10 sztuk złota
• 20% szansy na miecz
• 45% szansy na tarczę
• 20% szansy na zbroję
• 10% szansy na miksturę

Jak mogę to zrobić, aby wybrać dokładnie jeden z powyższych przedmiotów, gdzie te procenty są odpowiednimi szansami na zdobycie łupów?

Miękko zakodowane prawdopodobieństwo

Wadliwe rozwiązanie prawdopodobieństwa ma tę wadę, że trzeba ustawić prawdopodobieństwa w kodzie. Nie można ich ustalić w czasie wykonywania. Jest również trudny do utrzymania.

Oto dynamiczna wersja tego samego algorytmu.

1. Utwórz tablicę par rzeczywistych przedmiotów i ich wagi
2. Po dodaniu przedmiotu waga przedmiotu musi być jego własnym ciężarem powiększonym o sumę wag wszystkich przedmiotów znajdujących się już w tablicy. Więc powinieneś śledzić sumę osobno. Zwłaszcza, że ​​będziesz go potrzebować do następnego kroku.
3. Aby pobrać obiekt, wygeneruj losową liczbę od 0 do sumy wag wszystkich przedmiotów
4. iteruj tablicę od początku do końca, aż znajdziesz pozycję o wadze większej lub równej liczbie losowej

Oto przykładowa implementacja w Javie w postaci klasy szablonów, którą można utworzyć dla dowolnego obiektu używanego przez grę. Następnie możesz dodać obiekty za pomocą metody .addEntry(object, relativeWeight)i wybrać jeden z wpisów, które dodałeś wcześniej.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
    }
}

Stosowanie:

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());
}

Oto ta sama klasa zaimplementowana w C # dla twojego projektu Unity, XNA lub 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
    }
}

A oto jeden w 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;
    }   
}

Zawodowiec:

• Może obsługiwać dowolne proporcje masy. Jeśli chcesz, możesz mieć w zestawie przedmioty z astronomicznie małym prawdopodobieństwem. Odważniki również nie muszą sumować się do 100.
• Możesz odczytać elementy i ciężary w czasie wykonywania
• Zużycie pamięci proporcjonalne do liczby elementów w tablicy

Contra:

• Wymaga trochę więcej programowania, aby się dobrze
• W najgorszym przypadku może być konieczne powtórzenie całej tablicy ( O(n)złożoność środowiska wykonawczego). Więc kiedy masz bardzo duży zestaw przedmiotów i często rysujesz, może stać się powolny. Prosta optymalizacja polega na umieszczeniu najbardziej prawdopodobnych pozycji na pierwszym miejscu, aby algorytm zakończył się w większości przypadków wcześniej. Bardziej złożoną optymalizacją, jaką możesz zrobić, jest wykorzystanie faktu, że tablica jest posortowana i przeszukiwanie bisekcji. To zajmuje tylko O(log n)czas.
• Musisz zbudować listę w pamięci, zanim będziesz mógł z niej korzystać (chociaż możesz łatwo dodawać elementy w środowisku wykonawczym. Można również dodawać usuwanie elementów, ale wymagałoby to aktualizacji skumulowanych wag wszystkich elementów, które pojawiają się po usuniętym wpisie, które znowu ma O(n)najgorszy czas działania)

Uwaga: Stworzyłem bibliotekę C # dla tego konkretnego problemu

Inne rozwiązania są w porządku, jeśli masz tylko niewielką liczbę przedmiotów, a twoje prawdopodobieństwo nigdy się nie zmienia. Jednak przy wielu przedmiotach lub zmieniających się prawdopodobieństwach (np. Usuwaniu przedmiotów po ich wybraniu) będziesz potrzebować czegoś mocniejszego.

Oto dwa najczęstsze rozwiązania (oba są zawarte w powyższej bibliotece)

Alias ​​Walkera

Sprytne rozwiązanie, które jest niezwykle szybkie ( O(1)!), Jeśli prawdopodobieństwo jest stałe. Zasadniczo algorytm tworzy tarczę 2D („tabelę aliasów”) na podstawie twoich prawdopodobieństw i rzuca w nią strzałką.

Istnieje wiele artykułów online o tym, jak to działa, jeśli chcesz dowiedzieć się więcej.

Jedynym problemem jest to, że jeśli zmienią się twoje prawdopodobieństwa, musisz ponownie wygenerować tabelę aliasów, co jest powolne. Dlatego jeśli musisz usunąć przedmioty po ich wybraniu, nie jest to dla ciebie rozwiązanie.

Rozwiązanie oparte na drzewach

Innym powszechnym rozwiązaniem jest utworzenie tablicy, w której każdy element przechowuje sumę swojego prawdopodobieństwa i wszystkie elementy przed nim. Następnie po prostu wygeneruj liczbę losową z [0,1) i przeprowadź binarne wyszukiwanie, gdzie ta liczba wyląduje na liście.

To rozwiązanie jest bardzo łatwe do kodowania / zrozumienia, ale dokonanie wyboru jest wolniejsze niż metoda aliasowa Walkera, a zmiana prawdopodobieństwa jest nadal O(n). Możemy to poprawić, zmieniając tablicę w drzewo wyszukiwania binarnego, w którym każdy węzeł śledzi sumę prawdopodobieństwa wszystkich elementów w swoim poddrzewie. Następnie, gdy generujemy liczbę z [0,1), możemy po prostu zejść po drzewie, aby znaleźć element, który reprezentuje.

To pozwala nam O(log n)wybrać przedmiot i zmienić prawdopodobieństwo! To sprawia, że NextWithRemoval()bardzo szybko!

Wyniki

Oto kilka szybkich testów porównawczych z powyższej biblioteki, porównujących te dwa podejścia

         WeightedRandomizer Benchmarks | Drzewo | Stół
-------------------------------------------------- ---------------------------------
Add () x10000 + NextWithReplacement () x10: | 4 ms | 2 ms
Add () x10000 + NextWithReplacement () x10000: | 7 ms | 4 ms
Add () x10000 + NextWithReplacement () x100000: | 35 ms | 28 ms
(Add () + NextWithReplacement ()) x10000 (z przeplotem) | 8 ms | 5403 ms
Add () x10000 + NextWithRemoval () x10000: | 10 ms | 5948 ms

Jak widać, w specjalnym przypadku prawdopodobieństw statycznych (niezmiennych) metoda Alias ​​Walkera jest o około 50-100% szybsza. Ale w bardziej dynamicznych przypadkach drzewo jest o kilka rzędów wielkości szybsze !

Rozwiązanie Wheel of Fortune

Możesz użyć tej metody, gdy prawdopodobieństwo w twojej puli przedmiotów ma dość duży wspólny mianownik i musisz z niego czerpać bardzo często.

Utwórz tablicę opcji. Ale wkładaj do niego każdy element wiele razy, z liczbą duplikatów każdego elementu proporcjonalną do jego szansy pojawienia się. W powyższym przykładzie wszystkie elementy mają prawdopodobieństwa, które są mnożnikami 5%, więc możesz utworzyć tablicę 20 elementów takich jak to:

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

Następnie po prostu wybierz losowy element z tej listy, generując jedną losową liczbę całkowitą między 0 a długością tablicy - 1.

Niedogodności:

• Musisz zbudować tablicę za pierwszym razem, gdy chcesz wygenerować element.
• Kiedy jeden z twoich elementów ma mieć bardzo małe prawdopodobieństwo, otrzymujesz naprawdę dużą tablicę, która może wymagać dużej ilości pamięci.

Zalety:

• Jeśli masz już tablicę i chcesz z niej rysować wiele razy, jest ona bardzo szybka. Tylko jedna losowa liczba całkowita i jeden dostęp do tablicy.

Rozwiązanie prawdopodobieństw zakodowanych na stałe

Najprostszym sposobem znalezienia losowego elementu z ważonej kolekcji jest przejście w dół łańcucha instrukcji if-else, w którym każde if-else zwiększa się prawdopodobnie, ponieważ poprzednia nie trafiła.

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!");
}

Powodem, dla którego warunki warunkowe są równe jego szansie plus wszystkie poprzednie szanse warunkowe, jest to, że poprzednie warunki warunkowe już wyeliminowały możliwość bycia tymi przedmiotami. Zatem dla warunku tarczy else if(rand <= 70)70 jest równe 45% szansie na tarczę, plus 5% szansie na złoto i 20% szansie na miecz.

Zalety:

• Łatwy do zaprogramowania, ponieważ nie wymaga struktur danych.

Niedogodności:

• Trudne w utrzymaniu, ponieważ musisz utrzymać współczynniki drop w kodzie. Nie można ich ustalić w czasie wykonywania. Więc jeśli chcesz czegoś bardziej przyszłościowego, powinieneś sprawdzić inne odpowiedzi.

W języku C # można użyć skanu Linq, aby uruchomić akumulator, aby sprawdzić liczbę losową z zakresu od 0 do 100,0 f oraz First (), aby uzyskać. Tak jak jeden wiersz kodu.

Więc coś takiego:

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

sumjest liczbą całkowitą zainicjowaną przez zero i ajest listą struktur prob / item / krotek / instancji. randto wcześniej wygenerowana liczba losowa w zakresie.

To po prostu gromadzi sumę na liście zakresów, dopóki nie przekroczy poprzednio wybranej liczby losowej, i zwraca albo element, albo null, przy czym wartość null byłaby zwracana, jeśli zakres liczb losowych (np. 100) jest przez pomyłkę całkowity zakres ważenia , a wybrana liczba losowa jest poza całkowitym zakresem ważenia.

Zauważysz jednak, że ciężary w OP ściśle pasują do rozkładu normalnego (Krzywa Bell). Myślę, że generalnie nie będziesz chciał określonych zakresów, będziesz raczej chciał rozkładu, który zwęża się albo wokół krzywej dzwonowej, albo tylko na malejącej krzywej wykładniczej (na przykład). W takim przypadku możesz po prostu użyć wzoru matematycznego do wygenerowania indeksu w tablicy elementów, posortowanych według preferowanego prawdopodobieństwa. Dobrym przykładem jest CDF w normalnej dystrybucji

Również przykład tutaj .

Innym przykładem jest to, że możesz wziąć losową wartość od 90 stopni do 180 stopni, aby uzyskać prawą dolną ćwiartkę koła, weź składnik x za pomocą cos (r) i użyj go, aby zindeksować listę priorytetową.

Przy różnych formułach można zastosować ogólne podejście, w którym wystarczy wprowadzić listę o dowolnej długości (np. N) i odwzorować wynik formuły (np. Cos (x) wynosi od 0 do 1) przez pomnożenie (np .: Ncos (x ) = Od 0 do N), aby uzyskać indeks.

Prawdopodobieństwa nie muszą być zakodowane na stałe. Elementy i progi mogą być razem w tablicy.

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

Trzeba nadal gromadzić progi, ale można to zrobić, tworząc plik parametrów zamiast go kodować.

Zrobiłem tę funkcję: https://github.com/thewheelmaker/GDscript_Weighted_Random Now! w twoim przypadku możesz użyć tego w następujący sposób:

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

Daje tylko liczbę od 0 do 4, ale możesz umieścić ją w tablicy, w której dostałeś przedmioty.

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

Lub w funkcji:

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

Oto kod. Zrobiłem to na GDscript, możesz, ale może zmienić inny język, sprawdź także błędy logiczne:

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

Działa to tak: on_normal_case ([50,50], 0) Daje to 0 lub 1, ma to samo prawdopodobieństwo obu.

on_normal_case ([50,50], 1) Daje to 1 lub 2, ma to samo prawdopodobieństwo obu.

on_normal_case ([20,80], 1) Daje to 1 lub 2, ma większą zmianę, aby uzyskać dwa.

on_normal_case ([20,80,20,20,30], 1) Daje to losowe liczby w zakresie 1-5, a większe liczby są bardziej prawdopodobne niż mniejsze liczby.

on_normal_case ([20,80,0,0,20,20,20,,0,0,0,0,0,33], 45) Ten rzut kostką między liczbami 45,46,49,50,51,56 widać, kiedy tam wynosi zero, nigdy się nie zdarza.

Tak więc funkcja zwraca tylko jedną liczbę losową, która zależy od długości tej tablicy tablicowej i liczby transformmu, a liczby całkowite w tablicy są wagami prawdopodobieństwa, które mogłaby wystąpić liczba, gdzie liczba ta jest położeniem na tablicy, pluss liczba transformmu.