Losowanie tabelkowe

2007-08-26 14:35

W niemal każdym programie chociaż raz zdarza się potrzeba, by “rzucić kośćmi” i pozwolić, by wydarzyło się coś losowego. Oznacza to skorzystanie z generatora liczb pseudolosowych, aby uzyskać ‘przypadkową’ wartość. Nie będzie ona faktycznie losowa, lecz dzięki zastosowaniu matematycznych formuł o dużej nieregularności rezultat może być bardzo zbliżony do ideału. Istnieje oczywiście wiele algorytmów wyznaczania liczb pseudolosowych, różniących się faktyczną przypadkowością uzyskiwanego wyniku.
W różnych językach programowania mamy natomiast odmienne sposoby na uzyskanie liczby ‘losowej’. Zwykle najwygodniejszym jest wartość z zakresu [0..1], bo odpowiada to matematycznemu pojęciu prawdopodobieństwa. Aby w C++ uzyskać taki rezultat, wystarczy napisać proste opakowanie na biblioteczną funkcję rand:

  1. float Random() { return rand() / (float)RAND_MAX; }

Mając taki generator, możemy już łatwo sprawdzić, czy “zdarzyło się” coś, czego prawdopodobieństwo znamy:
// doświadczenie losowe z określonym prawdopodobieństwem
bool RandomOccured(float fProbability) { return Random() <= fProbability; }[/cpp] W ten sposób możemy na przykład rzucać wirtualną monetą. Przykładowa tabelka ataku w World of WarcraftSprawa się jednak komplikuje, jeżeli możliwych wyników doświadczenia jest więcej, a przy okazji mają one różne prawdopodobieństwa zajścia. Tak się dzieje na przykład w grach RPG, w których konieczne jest obliczanie rezultatów zadanych ciosów (trafienie, pudło, unik, blok, itp.). Skuteczność postaci w walce zależy zwykle od jej statystyk, więc szanse poszczególnych wyników nie są stałe i zmieniają się w trakcie gry.
Dobre generatory liczb pseudolosowych są zaś nierzadko względnie kosztowne obliczeniowo. Dlatego zamiast wykonywać po jednym losowaniu dla każdego możliwego rezultatu (zaszedł – nie zaszedł), znacznie lepiej jest załatwić wszystko jednym losowaniem. Nie jest to trudne:
// doświadczenie losowe z prawdopodobieństwem określonym tabelką
int RandomResult(const float* aProbs, int n)
{
float fRand = Random();

float fAccum = 0.0f;
for (int = 0; i < n; ++i) { // sprawdzamy, czy wylosowana liczba mieści się w zakresie p-stwa if (fAccum <= fRand && fRand < fAccum + aProbs[i]) return i; fAccum += aProbs[i]; } // błąd return -1; }[/cpp] Tak naprawdę liczymy tutaj dla każdego możliwego rezultatu wartość tzw. dystrybuanty. Ale chyba nie warto wnikać w takie teoretyczne szczegóły – grunt, że powyższa metoda działa w praktyce :) Trzeba tutaj jednak pamiętać, aby prawdopodobieństwa sumowały się do 1. Jeśli tak nie jest, można przeskalować wylosowaną liczbę.

Tags: ,
Author: Xion, posted under Math, Programming »



Adding comments is disabled.

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.