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

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ć?

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.

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.

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ć.

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.