Ciągły ważony rozkład losowy, tendencyjny w kierunku jednego końca


28

Obecnie pracuję nad układem cząstek w naszej grze i opracowuję kształty emitera.

Mój jednolity losowy rozkład wzdłuż linii lub prostokąta działa dobrze - nie ma problemu.

Ale teraz chciałbym mieć coś w rodzaju 1 wymiarowego gradientu w tym rozkładzie. Oznaczałoby to na przykład, że niższe wartości są częstsze niż wyższe wartości.

Nie wiem, jakie byłyby odpowiednie matematyczne terminy dla tego problemu, więc moje umiejętności wyszukiwania są w tym przypadku raczej bezużyteczne. Potrzebuję czegoś, co jest obliczeniowo proste, ponieważ system cząstek musi być wydajny.



Czy nikt nie wspomina o rachunku różniczkowym i całkowym?
Alec Teal

Odpowiedzi:


42

Spójrz na to zdjęcie:

Mapowanie krzywych

Pokazuje proces mapowania (losowej) wartości na krzywą. Załóżmy, że generujesz równomiernie rozłożoną losową wartość X, od 0 do 1. Odwzorowując tę ​​wartość na krzywą - lub innymi słowy, używając f (X) zamiast X - możesz przekrzywić rozkład w dowolny sposób .

Na tym zdjęciu pierwsza krzywa zwiększa prawdopodobieństwo, że wyższe wartości; drugi zwiększa prawdopodobieństwo, że niższe wartości; a trzeci sprawia, że ​​wartości skupiają się w środku. Dokładna formuła krzywej nie jest tak naprawdę ważna i można ją wybrać według własnego uznania.

Na przykład pierwsza krzywa wygląda trochę jak pierwiastek kwadratowy, a druga - kwadrat. Trzeci jest trochę jak kostka, tylko przetłumaczony. Jeśli uważasz, że pierwiastek kwadratowy jest zbyt wolny, pierwsza krzywa również wygląda jak f (X) = 1- (1-X) ^ 2 - odwrócenie kwadratu. Lub hiperbola: f (X) = 2X / (1 + X).

Jak pokazuje czwarta krzywa, możesz po prostu użyć wstępnie obliczonej tabeli odnośników. Wygląda brzydko jak krzywa, ale prawdopodobnie będzie wystarczająco dobry dla układu cząstek.

Ta ogólna technika jest bardzo prosta i potężna. Niezależnie od potrzebnego rozkładu wyobraź sobie odwzorowanie krzywej, a szybko opracujesz formułę. Lub, jeśli twój silnik ma edytor, po prostu stwórz edytor wizualny dla krzywej!


dziękuję bardzo za bardzo dokładne i zrozumiałe wyjaśnienie. wszystkie inne posty też były bardzo pomocne, ale naprawdę mogłem zrozumieć twój post najłatwiej i najszybciej. wystawał bc, naprawdę trafił w sedno mojego sposobu rozumienia rzeczy. a aspekty, które wyjaśniasz, są dokładnie tym, czego szukałem (lub błąkałem się)! pozwoli mi to wykorzystać w wielu przypadkach w przyszłości. dzięki jeszcze raz !!! btw, bawiłem się niektórymi z twoich krzywych i działa to jak urok.
didito

5
FYI: Są to tak zwane funkcje kwantylowe: en.wikipedia.org/wiki/Quantile_function
Neil G

8

Dłuższe wyjaśnienie:

Jeśli masz pożądany rozkład prawdopodobieństwa, taki jak żądany gradient @didito, możesz opisać to jako funkcję. Powiedzmy, że chcesz rozkładu trójkątnego, w którym prawdopodobieństwo przy 0 wynosi 0,0, i chcesz wybrać liczbę losową od 0 do 1. Możemy zapisać ją jako y = x.

Następnym krokiem jest obliczenie całki tej funkcji. W tym przypadku jest to . Ocena od 0 do 1, to jest ½. Ma to sens - jest to trójkąt o podstawie 1 i wysokości 1, więc jego powierzchnia wynosi ½.x=1x2

Następnie wybierasz losowo punkt równomiernie od 0 do obszaru (½ w naszym przykładzie). Nazwijmy to z. (Wybieramy równomiernie z rozkładu skumulowanego ).

Następnym krokiem jest cofnięcie się, aby dowiedzieć się, która wartość x (nazwiemy to x̂) odpowiada obszarowi z. Szukamy , ocenianego od 0 do x̂, równego z. Kiedy rozwiązujesz dla , otrzymujesz .x=1x21x̂2=zx̂=2z

W tym przykładzie wybierasz z od 0 do ½, a następnie pożądaną liczbą losową jest . Uproszczony, możesz napisać go jako - dokładnie to, co zalecił eBiznes.2zrand(0,1)


dzięki za wartościowe dane wejściowe. Zawsze lubię słyszeć, jak wykwalifikowani ludzie rozwiązują problemy. ale nadal muszę owinąć głowę, żeby być szczerym ...
didito

to jest niesamowite. Zawsze sqrt(random())tworzyłem całe życie, ale doszedłem do niego empirycznie. Próbowanie powiązania losowej liczby z krzywą i zadziałało. Teraz, gdy jestem trochę bardziej wykwalifikowany w matematyce, wiedza o tym, dlaczego to działa, jest bardzo cenna!
Gustavo Maciel

5

Prawdopodobnie uzyskasz dokładne przybliżenie tego, co chcesz, stosując system wykładniczy.

Ustaw x na podstawie czegoś takiego jak 1- (wartość rnd ^) (Zakładając, że rnd ma wartość od 0 do 1), a otrzymasz kilka różnych zachowań skośnych od lewej do prawej w zależności od tego, czego używasz. Wyższa wartość zapewni bardziej wypaczony rozkład

Możesz użyć internetowego narzędzia do tworzenia wykresów, aby uzyskać ogólne pomysły na zachowania, które dają różne równania przed ich umieszczeniem, lub możesz po prostu bawić się równaniami bezpośrednio w układzie cząsteczek, w zależności od tego, jaki styl bardziej odpowiada Twoim upodobaniom.

EDYTOWAĆ

W przypadku systemu cząstek, w którym czas pracy procesora na cząsteczkę jest bardzo ważny, użycie Math.Pow (lub odpowiednika językowego) może bezpośrednio doprowadzić do spadku wydajności. Jeśli wymagana jest większa wydajność, a wartość nie jest zmieniana w czasie wykonywania, rozważ przejście na równoważną funkcję, taką jak x * x zamiast x ^ 2.

(Wykładniki ułamkowe mogą być większym problemem, ale ktoś z silniejszym zapleczem matematycznym niż ja prawdopodobnie mógłby wymyślić dobry sposób na utworzenie funkcji aproksymacji)


1
Zamiast używać programu do tworzenia wykresów, możesz po prostu wykreślić rozkład wersji Beta, ponieważ jest to szczególny przypadek. Dla danego valuejest to Beta (wartość 1).
Neil G

dzięki. próbowałem wykreślić kilka wykresów i myślę, że może mnie to zabrać tam, gdzie chcę.
didito

@Neil G dziękuje za podpowiedź z „dystrybucją beta” - brzmi to interesująco i przydatnie ... Zrobię trochę badań na ten temat
didito

3

Termin, którego szukasz, to Weighted Random Numberswiększość algorytmów, które widziałem, używają funkcji trig, ale myślę, że wymyśliłem sposób, który będzie skuteczny:

Utwórz tabelę / tablicę / listę (cokolwiek), która zawiera wartość mnożnika dla funkcji losowej. Wypełnij go ręcznie lub programowo ...

randMulti= {.1,.1,.1,.1,.1,.1,.2,.2,.3,.3,.9,1,1,1,} 

... następnie Pomnóż randomprzez losowo wybrany randMultii na koniec przez maksymalną wartość rozkładu ...

weightedRandom = math.random()*randMulti[Math.random(randMulti.length)]*maxValue

Wierzę, że będzie to znacznie szybsze niż korzystanie z sqrtinnych bardziej złożonych obliczeniowo funkcji i pozwoli na bardziej niestandardowe wzorce grupowania.


2
Jeśli możesz poświęcić pamięć, tabela 100 wstępnie obliczonych wartości byłaby szybsza (i nieco dokładniejsza). Wątpię, czy użytkownik byłby w stanie rozróżnić wersje pełne i wstępnie obliczone.
Daniel Blezek

@Daniel byłoby szybciej, ale przy 100 losowych wartościach dość łatwo jest zobaczyć powtarzające się wzorce.
AttackingHobo

To, że wydaje się, że istnieje powtarzalny wzór, nie oznacza, że ​​nie jest on przypadkowy. Istotą przypadkowości jest jej nieprzewidywalność, co dosłownie oznacza, że ​​o ile nie można przewidzieć, że nie będzie wzorca, nie można też przewidzieć, że taki może być (przynajmniej przez krótki czas). Będziesz musiał wykonać kilka testów, ale jeśli znajdziesz wzorce z wieloma testami przy użyciu różnych nasion, algorytm generowania liczb pseudolosowych może wymagać przeglądu.
Randolf Richardson

@AttackingHobo dzięki za tę sztuczkę. lubię używać LUT. a formuła jest dość łatwa do zrozumienia. nie myślałem o tym wcześniej. nie widzę drewna dla drzew ... :) również uważam, że należy unikać powtarzania wzorów, ale prawdopodobnie i tak nie zostanie to rozpoznane. mimo to wstępne obliczenie wszystkich wartości zaszkodziłoby wrażeniom wizualnym. w każdym razie, dziękuję za przypomnienie mi, że jest to czynnik, który należy wziąć pod uwagę na temat przypadkowości ...
didito

dziękuję również za podniesienie terminu Ważone „Liczby losowe”!
didito

2

Myślę, że to, o co prosisz, to rozkład osiągnięty za pomocą funkcji pierwiastka kwadratowego.

[position] = sqrt(rand(0, 1))

Zapewni to rozkład w polu pojedynczego wymiaru, w [0, 1]którym prawdopodobieństwo położenia jest równoważne z tym położeniem, tj. „Rozkład trójkątny”.

Alternatywne generowanie bez kwadratów:

[position] = 1-abs(rand(0, 1)-rand(0, 1))

Pierwiastek kwadratowy w optymalnej implementacji to tylko kilka poleceń mnożenia i sumowania bez rozgałęzień. (Patrz: http://en.wikipedia.org/wiki/Fast_inverse_square_root ). Która z tych dwóch funkcji jest szybsza, może się różnić w zależności od platformy i generatora losowego. Na przykład na platformie x86 zajęłoby tylko kilka nieprzewidywalnych gałęzi w generatorze losowym, aby spowolnić drugą metodę.


Prawdopodobieństwo pozycji nie będzie równe pozycji (co jest matematycznie niemożliwe - trywialnie, dziedzina i zakres funkcji obejmuje zarówno 0,50, jak i 0,51), ani też nie jest rozkładem trójkątnym. ( en.wikipedia.org/wiki/Triangular_distribution )

1
Podczas gdy sqrt podaje kilka interesujących wzorów, systemy cząstek na ogół muszą bardzo bardzo obciążać procesor na cząsteczkę, więc zalecałbym unikanie pierwiastków kwadratowych (które są obliczeniowo wolne) tam, gdzie to możliwe. Czasami możesz uciec od samego ich wstępnego obliczenia, ale może sprawić, że twoje cząsteczki będą miały zauważalne wzory z czasem.
Lunin

1
@Joe Wreschnig, czy sam przeczytałeś ten artykuł z Wikipedii, umieściłeś a = 0, b = 1, c = 1 w formule generowania i dostałeś ją w moim poście.
aaaaaaaaaaaa

3
@Lunin, dlaczego narzekasz na pierwiastek kwadratowy, gdy masz wykładnik w swojej odpowiedzi?
aaaaaaaaaaaa

1
@Linin: Teoria wydajności to dość zaniedbana dziedzina, wiele z tego, co ludzie myślą, że wiedzą, gdzie mniej więcej 30 lat temu, gdy ALU były duże drogie i wolne. Nawet funkcja wykładnicza, którą właśnie odkryłeś, jest dość powolną funkcją arytmetyczną, rzadko jest bardzo znaczącym grzesznikiem wydajności. Rozgałęzienia (przy użyciu instrukcji if) i pominięcia pamięci podręcznej (odczytanie danych, które obecnie nie znajdują się w pamięci podręcznej) zazwyczaj kosztują najwięcej wydajności.
aaaaaaaaaaaa

1

Wystarczy użyć dystrybucji Beta:

  • Beta (1,1) jest płaska
  • Beta (1,2) jest gradientem liniowym
  • Beta (1,3) jest kwadratowa

itp.

Te dwa parametry kształtu nie muszą być liczbami całkowitymi.


dziękuję za pomoc. jak wspomniano powyżej, dystrybucja beta brzmi interesująco. ale nie mogę jeszcze zrozumieć treści strony Wikipedii. lub formuła / kod. no cóż, nie mam teraz czasu na dalsze badania: widzę, że boost ma kod dystrybucji beta, ale byłoby to przesadą. myślę, że najpierw muszę to przejrzeć, a potem napisać własną uproszczoną wersję.
didito

1
@didito: To nie jest takie trudne. Po prostu zamienisz swoje uniform_generator()połączenie na gsl_ran_beta(rng, a, b). Zobacz tutaj: gnu.org/software/gsl/manual/html_node/...
Neil G

dzięki za podpowiedź. Nie używam GSL (właściwie nie słyszałem o tym wcześniej), ale dobre połączenie. sprawdzę źródło!
didito

@didito: W takim przypadku wybrałbym rozwiązanie Lunina. Powodzenia.
Neil G

0

Jeszcze prościej, w zależności od prędkości generatora losowego, możesz po prostu wygenerować dwie wartości i uśrednić je.

Albo, jeszcze bardziej proste, gdzie X jest wynikiem RNG, pierwszy double y = double(1/x);, x = y*[maximum return value of rng];. To zrównoważy liczby wykładniczo do niższych liczb.

Generuj i uśredniaj więcej wartości, aby zwiększyć prawdopodobieństwo zbliżenia wartości do centrum.

Oczywiście działa to tylko w przypadku standardowych rozkładów krzywych dzwonkowych lub ich „złożonych” wersji *, ale w przypadku szybkiego generatora może być szybsze i prostsze niż używanie różnych funkcji matematycznych, takich jak sqrt.

Możesz znaleźć wszelkiego rodzaju badania tego dla krzywych dzwonka do kości. W rzeczywistości Anydice.com to dobra strona, która generuje wykresy dla różnych metod rzucania kostką. Chociaż używasz RNG, założenie jest takie samo, jak wyniki. Jest to więc dobre miejsce, aby zobaczyć rozkład, zanim jeszcze go zakodujesz.

* Ponadto można „złożyć” rozkład wyników wzdłuż osi, biorąc oś i odejmując uśredniony wynik, a następnie dodając oś. Na przykład chcesz, aby niższe wartości były bardziej powszechne, i powiedzmy, że chcesz, aby 15 było wartością minimalną, a 35 wartością maksymalną, w zakresie 20. Tak więc generujesz i uśredniasz razem dwie wartości o zakresie 20 ( dwukrotność żądanego zakresu), co da krzywą dzwonkową wyśrodkowaną na 20 (odejmujemy pięć na końcu, aby zmienić zakres z 20 na 40, na 15 na 35). Weź wygenerowane liczby X i Y.

Ostateczna liczba,

z =(x+y)/2;// average them
If (z<20){z = (20-z)+20;}// fold if below axis
return z-5;// return value adjusted to desired range

Jeśli zero jest twoim minimum, a nawet lepiej, zrób to zamiast tego,

z= (x+y)/2;
If (z<20){z = 20-z;}
else {z = z - 20;}
return z;
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.