rand () ponownie podaje te same liczby dla małego zakresu

9

Próbuję stworzyć rodzaj gry, w której mam siatkę 20 x 20 i wyświetlam gracza (P), cel (T) i trzech wrogów (X). Wszystkie mają współrzędne X i Y, które są przypisywane za pomocą rand(). Problem polega na tym, że jeśli spróbuję zdobyć więcej punktów w grze (uzupełnienia energii itp.), Nakładają się one na jeden lub więcej innych punktów, ponieważ zasięg jest niewielki (od 1 do 20 włącznie).

Oto moje zmienne i sposób, w jaki przypisuję im wartości: (to COORDjest structtylko z X i Y)

const int gridSize = 20;
COORD player;
COORD target;
COORD enemy1;
COORD enemy2;
COORD enemy3;

//generate player
srand ( time ( NULL ) );
spawn(&player);
//generate target
spawn(&target);
//generate enemies
spawn(&enemy1);
spawn(&enemy2);
spawn(&enemy3);

void spawn(COORD *point)
{
    //allot X and Y coordinate to a point
    point->X = randNum();
    point->Y = randNum();
}

int randNum()
{
    //generate a random number between 1 and gridSize
    return (rand() % gridSize) + 1;
}

Chcę dodać więcej elementów do gry, ale prawdopodobieństwo nakładania się rośnie, gdy to robię. Czy jest jakiś sposób to naprawić?

Rabeez Riaz
źródło
8
rand () to zły RNG
maniak ratchet,
3
rand()to żałosne RNG, a przy tak małym zasięgu nie musisz się tylko spodziewać kolizji, są prawie gwarantowane.
Deduplicator,
1
Chociaż prawdą jest, że rand()jest to kiepski RNG, prawdopodobnie jest odpowiedni dla gry dla jednego gracza, a jakość RNG nie jest tutaj problemem.
Gort the Robot
13
Mówienie o jakości rand()wydaje się tutaj nieistotne. Nie ma w tym żadnej kryptografii, a każdy RNG najprawdopodobniej spowoduje kolizje na tak małej mapie.
Tom Cornebize,
2
To, co widzisz, jest znane jako problem urodzinowy. Jeśli liczby losowe są konwertowane na zakres mniejszy niż naturalny zakres PRNG, prawdopodobieństwo uzyskania dwóch wystąpień o tej samej liczbie jest znacznie wyższe, niż mogłoby się wydawać. Jakiś czas temu napisałem na ten temat napis na Stackoverflow tutaj.
ConcernedOfTunbridgeWells

Odpowiedzi:

40

Podczas gdy użytkownicy, którzy narzekają rand()i zalecają lepsze RNG, mają rację co do jakości liczb losowych, brakuje im również większego obrazu. Duplikatów w strumieniach liczb losowych nie da się uniknąć, są faktem. Oto lekcja na temat urodzin .

Na siatce 20 * 20 = 400 możliwych pozycji odradzania należy się spodziewać duplikatu punktu odradzania (prawdopodobieństwo 50%), nawet przy odrodzeniu tylko 24 jednostek. Przy 50 podmiotach (wciąż tylko 12,5% całej siatki) prawdopodobieństwo duplikatu wynosi ponad 95%. Musisz poradzić sobie z kolizjami.

Czasami możesz narysować wszystkie próbki na raz, a następnie możesz użyć algorytmu losowego, aby narysować nprzedmioty z wyraźną różnicą. Wystarczy wygenerować listę wszystkich możliwości. Jeśli pełna lista możliwości jest zbyt duża, aby ją zapisać, możesz generować pozycje odradzania pojedynczo, tak jak teraz (tylko z lepszym RNG) i po prostu ponownie generować, gdy nastąpi kolizja. Chociaż prawdopodobne jest wystąpienie niektórych kolizji, wiele kolizji z rzędu jest wykładniczo mało prawdopodobne, nawet jeśli większość siatki jest zapełniona.


źródło
Pomyślałem o odrodzeniu w przypadku kolizji, ale jeśli mam więcej przedmiotów, tak jak zamierzam, wtedy wyszukiwanie kolizji byłoby skomplikowane. Musiałbym również edytować czeki w przypadku dodania lub usunięcia punktu z gry. Jestem dość niedoświadczony, więc jeśli istnieje obejście tego problemu, nie mogę tego zobaczyć.
Rabeez Riaz
7
Jeśli masz szachownicę 20x20, w przeciwieństwie do ciągłej (rzeczywistej) płaszczyzny XY 20x20, to masz 400-komórkową tablicę przeglądową do sprawdzania kolizji. To jest TRIVIAL.
John R. Strohm,
@RabeezRiaz Jeśli masz większą mapę, będziesz mieć strukturę danych opartą na siatce (siatka składająca się z pewnego obszaru komórek, a każdy element wewnątrz tej komórki jest przechowywany na liście). Jeśli twoja mapa jest jeszcze większa, zaimplementujesz prostoliniowe drzewo.
rwong
2
@RabeezRiaz: jeśli wyszukiwanie jest zbyt skomplikowane, skorzystaj z jego pierwszej sugestii: wygeneruj listę wszystkich 400 możliwych lokalizacji początkowych, potasuj je, aby były w losowej kolejności (wyszukaj algorytm), a następnie zacznij używać lokalizacji z przodu, gdy potrzebujesz do generowania rzeczy (śledź ile już użyłeś). Brak kolizji.
RemcoGerlich,
2
@RabeezRiaz Nie musisz przetasować całej listy, jeśli potrzebujesz tylko niewielkiej liczby losowych wartości, po prostu przetasuj potrzebną część (jak w, weź losową wartość z listy 1..400, usuń ją i powtarzaj aż do masz wystarczająco dużo elementów). W rzeczywistości tak właśnie działa algorytm tasowania.
Dorus,
3

Jeśli zawsze chcesz uniknąć gry nowym bytem w lokalizacji, która została już przydzielona do czegoś innego, możesz nieco zmienić swój proces. Zapewniłoby to unikalne lokalizacje, ale wymaga nieco więcej kosztów ogólnych. Oto kroki:

  1. Skonfiguruj zbiór odniesień do wszystkich możliwych lokalizacji na mapie (dla mapy 20 x 20 byłoby to 400 lokalizacji)
  2. Wybierz losową lokalizację z tej kolekcji 400 (rand () działałoby w tym przypadku dobrze)
  3. Usuń tę możliwość z kolekcji możliwych lokalizacji (więc ma teraz 399 możliwości)
  4. Powtarzaj, aż wszystkie podmioty mają określoną lokalizację

Tak długo, jak usuwasz lokalizację z zestawu, z którego wybierasz, druga istota nie powinna otrzymywać tej samej lokalizacji (chyba że wybierasz lokalizacje z więcej niż jednego wątku na raz).

Prawdziwym analogiem tego świata byłoby wyciągnięcie karty z talii kart. Obecnie tasujesz talię, dobierasz kartę i zaznaczasz ją, odkładasz wyciągniętą kartę z powrotem do talii, ponownie tasujesz i ponownie ciągniesz. Powyższe podejście pomija odłożenie karty z powrotem do talii.

Lyise
źródło
1

Pewnie rand() % nbędąc mniej niż idealnym

Doing rand() % nma nierównomierny rozkład. Otrzymasz nieproporcjonalną liczbę niektórych wartości, ponieważ liczba wartości nie jest wielokrotnością 20

Następnie rand()jest zwykle liniowym generatorem kongruencjalnym (jest wiele innych , tylko ten jest najprawdopodobniej zaimplementowany - i z parametrami mniej niż idealnymi (istnieje wiele sposobów wyboru parametrów)). Największym problemem jest to, że często małe bity (te, które otrzymujesz z % 20wyrażeniem typu) nie są tak losowe. Pamiętam jeden rand()z lat temu, w którym najniższy bit zmieniał się od 1do 0przy każdym wywołaniu do rand()- nie był zbyt przypadkowy.

Na stronie podręcznika rand (3):

Wersje rand () i srand () w bibliotece Linux C używają tego samego
generator liczb losowych jako random () i srandom (), więc w niższej kolejności
bity powinny być tak losowe, jak bity wyższego rzędu. Jednak na starszych
implementacje rand () oraz bieżące implementacje na różnych
w systemach, bity niższego rzędu są znacznie mniej losowe niż bity wyższe
zamówić bity. Nie używaj tej funkcji w zamierzonych aplikacjach
przenośny, gdy potrzebna jest dobra losowość.

To może być teraz przeniesione do historii, ale jest całkiem możliwe, że wciąż masz słabą implementację rand () ukrytą gdzieś na stosie. W takim przypadku nadal ma to zastosowanie.

Należy użyć dobrej biblioteki liczb losowych (która daje dobre liczby losowe), a następnie poprosić o liczby losowe w żądanym zakresie.

Przykład dobrego bitu liczb losowych (od 13:00 w połączonym wideo)

#include <iostream>
#include <random>
int main() {
    std::mt19937 mt(1729); // yes, this is a fixed seed
    std::uniform_int_distribution<int> dist(0, 99);
    for (int i = 0; i < 10000; i++) {
        std::cout << dist(mt) << " ";
    }
    std::cout << std::endl;
}

Porównaj to z:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
    srand(time(NULL));
    for (int i = 0; i < 10000; i++) {
        printf("%d ", rand() % 100);
    }
    printf("\n");
}

Uruchom oba te programy i porównaj, jak często określone liczby pojawiają się (lub nie pojawiają) na tym wyjściu.

Powiązane wideo: rand () uważane za szkodliwe

Niektóre historyczne aspekty rand () powodujące błędy w Nethacku, które należy obserwować i brać pod uwagę we własnych implementacjach:

  • Problem z Nethack RNG

    Rand () jest bardzo podstawową funkcją generowania liczb losowych przez Nethacka. Sposób, w jaki Nethack go używa, jest błędny lub można argumentować, że lrand48 () produkuje kiepskie pseudolosowe liczby. (Jednak lrand48 () jest funkcją biblioteki używającą zdefiniowanej metody PRNG, a każdy program, który jej używa, powinien uwzględniać słabości tej metody.)

    Błąd polega na tym, że Nethack polega (czasem wyłącznie tak, jak w przypadku rn (2)) na niższych bitach wyników z lrand48 (). Z tego powodu RNG w całej grze działa źle. Jest to szczególnie zauważalne, zanim działania użytkownika wprowadzą dalszą losowość, tj. W generowaniu postaci i tworzeniu pierwszego poziomu.

Chociaż powyższe pochodzi z 2003 roku, należy pamiętać, ponieważ może nie być tak, że wszystkie systemy z zamierzoną grą będą nowoczesnym systemem Linux z dobrą funkcją rand ().

Jeśli robisz to tylko dla siebie, możesz sprawdzić, jak dobry jest Twój generator liczb losowych, pisząc kod i testując dane wyjściowe za pomocą ent .


Na właściwości liczb losowych

Istnieją inne interpretacje „losowego”, które nie są dokładnie przypadkowe. W losowym strumieniu danych całkiem możliwe jest dwukrotne uzyskanie tej samej liczby. Jeśli rzucisz monetą (losowo), całkiem możliwe jest zdobycie dwóch głów z rzędu. Lub rzuć kostką dwa razy i uzyskaj ten sam numer dwa razy z rzędu. Lub zakręć kołem ruletki i uzyskaj dwa razy ten sam numer.

Rozkład liczb

Podczas odtwarzania listy utworów ludzie oczekują, że „losowy” będzie oznaczać, że ten sam utwór lub wykonawca nie zostanie odtworzony drugi raz z rzędu. Odtwarzanie listy odtwarzania The Beatles dwa razy z rzędu jest uważane za „nieprzypadkowe” (choć jest losowe). Postrzeganie, że dla listy odtwarzania czterech utworów odtwarzano w sumie osiem razy:

1 3 2 4 1 2 4 3

jest bardziej „losowy” niż:

1 3 3 2 1 4 4 2

Więcej informacji na temat „tasowania” utworów: jak przetasować utwory?

Na powtarzanych wartościach

Jeśli nie chcesz powtarzać wartości, należy rozważyć inne podejście. Wygeneruj wszystkie możliwe wartości i potasuj je.

Jeśli dzwonisz rand()(lub jakikolwiek inny generator liczb losowych), dzwonisz do niego z zastępstwem. Zawsze możesz uzyskać ten sam numer dwa razy. Jedną z opcji jest ciągłe wyrzucanie wartości, dopóki nie wybierzesz tej, która spełnia twoje wymagania. Zwrócę uwagę, że ma to nieokreślony czas działania i możliwe jest, że znajdziesz się w sytuacji, w której istnieje nieskończona pętla, chyba że zaczniesz wykonywać bardziej złożone śledzenie wstecz.

Lista i wybór

Inną opcją jest wygenerowanie listy wszystkich możliwych poprawnych stanów, a następnie wybranie losowego elementu z tej listy. Znajdź wszystkie puste miejsca (spełniające pewne zasady) w pokoju, a następnie wybierz losowe z tej listy. A potem rób to wielokrotnie, aż skończysz.

Człapać

Drugim podejściem jest tasowanie, jakby była to talia kart. Zacznij od wszystkich pustych miejsc w pokoju, a następnie zacznij przypisywać je, przydzielając puste miejsca, po jednym na raz, każdej regule / procesowi prosząc o puste miejsce. Skończysz, gdy zabraknie Ci kart lub przestaniesz o nie pytać.

Społeczność
źródło
3
Next, rand() is typically a linear congruential generatorObecnie nie jest to prawdą na wielu platformach. Ze strony podręcznika rand (3) linuxa: „Wersje rand () i srand () w bibliotece Linux C używają tego samego generatora liczb losowych co random (3) i srandom (3), więc bity niższego rzędu powinny być tak losowe jak bity wyższego rzędu. ” Ponadto, jak wskazuje @delnan, jakość PRNG nie jest tutaj prawdziwym problemem.
Charles E. Grant,
4
Głosuję za tym, ponieważ to nie rozwiązuje rzeczywistego problemu.
user253751,
@immibis Wtedy druga odpowiedź również nie „rozwiązuje” rzeczywistego problemu i powinna zostać poddana ocenie. Myślę, że pytanie nie brzmi „napraw mój kod”, ale „dlaczego otrzymuję duplikaty liczb losowych?” Na drugie pytanie uważam, że odpowiedź jest udzielona.
Neil,
4
Nawet przy najmniejszej wartości RAND_MAX32767 różnica wynosi 1638 możliwych sposobów uzyskania niektórych liczb w porównaniu z 1639 dla innych. Wydaje się mało prawdopodobne, aby miało to praktyczne znaczenie dla PO.
Martin Smith,
@Neil „Napraw mój kod” nie jest pytaniem.
Wyścigi lekkości na orbicie
0

Najprostsze rozwiązanie tego problemu zostało przytoczone w poprzednich odpowiedziach: utworzenie listy losowych wartości obok każdej z 400 komórek, a następnie posortowanie tej losowej listy. Twoja lista komórek zostanie posortowana jako lista losowa i w ten sposób zostanie przetasowana.

Zaletą tej metody jest całkowite uniknięcie nakładania się losowo wybranych komórek.

Wadą jest to, że musisz obliczyć losową wartość na osobnej liście dla każdej z komórek. Więc wolisz tego nie robić, gdy gra się rozpoczęła.

Oto przykład, jak to zrobić:

#include <algorithm>
#include <iostream>
#include <vector>

#define NUMBER_OF_SPAWNS 20
#define WIDTH 20
#define HEIGHT 20

typedef struct _COORD
{
  int x;
  int y;
  _COORD() : x(0), y(0) {}
  _COORD(int xp, int yp) : x(xp), y(yp) {}
} COORD;

typedef struct _spawnCOORD
{
  float rndValue;
  COORD*coord;
  _spawnCOORD() : rndValue(0.) {}
} spawnCOORD;

struct byRndValue {
  bool operator()(spawnCOORD const &a, spawnCOORD const &b) {
    return a.rndValue < b.rndValue;
  }
};

int main(int argc, char** argv)
{
  COORD map[WIDTH][HEIGHT];
  std::vector<spawnCOORD>       rndSpawns(WIDTH * HEIGHT);

  for (int x = 0; x < WIDTH; ++x)
    for (int y = 0; y < HEIGHT; ++y)
      {
        map[x][y].x = x;
        map[x][y].y = y;
        rndSpawns[x + y * WIDTH].coord = &(map[x][y]);
        rndSpawns[x + y * WIDTH].rndValue = rand();
      }

  std::sort(rndSpawns.begin(), rndSpawns.end(), byRndValue());

  for (int i = 0; i < NUMBER_OF_SPAWNS; ++i)
    std::cout << "Case selected for spawn : " << rndSpawns[i].coord->x << "x"
              << rndSpawns[i].coord->y << " (rnd=" << rndSpawns[i].rndValue << ")\n";
  return 0;
}

Wynik:

root@debian6:/home/eh/testa# ./exe 
Case selected for spawn : 11x15 (rnd=6.93951e+06)
Case selected for spawn : 14x1 (rnd=7.68493e+06)
Case selected for spawn : 8x12 (rnd=8.93699e+06)
Case selected for spawn : 18x13 (rnd=1.16148e+07)
Case selected for spawn : 1x0 (rnd=3.50052e+07)
Case selected for spawn : 2x17 (rnd=4.29992e+07)
Case selected for spawn : 9x14 (rnd=7.60658e+07)
Case selected for spawn : 3x11 (rnd=8.43539e+07)
Case selected for spawn : 12x7 (rnd=8.77554e+07)
Case selected for spawn : 19x0 (rnd=1.05576e+08)
Case selected for spawn : 19x14 (rnd=1.10613e+08)
Case selected for spawn : 8x2 (rnd=1.11538e+08)
Case selected for spawn : 7x2 (rnd=1.12806e+08)
Case selected for spawn : 19x15 (rnd=1.14724e+08)
Case selected for spawn : 8x9 (rnd=1.16088e+08)
Case selected for spawn : 2x19 (rnd=1.35497e+08)
Case selected for spawn : 2x16 (rnd=1.37807e+08)
Case selected for spawn : 2x8 (rnd=1.49798e+08)
Case selected for spawn : 7x16 (rnd=1.50123e+08)
Case selected for spawn : 8x11 (rnd=1.55325e+08)

Wystarczy zmienić NUMBER_OF_SPAWNS, aby uzyskać więcej lub mniej losowych komórek, nie zmieni to czasu obliczeń wymaganego dla zadania.

KwentRell
źródło
„a następnie posortować je wszystkie” - uważam, że masz na myśli „tasowanie”
Trochę uzupełniłem wyjaśnienie. Teraz powinno być jaśniej.
KwentRell