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 COORD
jest struct
tylko 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ć?
rand()
to żałosne RNG, a przy tak małym zasięgu nie musisz się tylko spodziewać kolizji, są prawie gwarantowane.rand()
jest to kiepski RNG, prawdopodobnie jest odpowiedni dla gry dla jednego gracza, a jakość RNG nie jest tutaj problemem.rand()
wydaje się tutaj nieistotne. Nie ma w tym żadnej kryptografii, a każdy RNG najprawdopodobniej spowoduje kolizje na tak małej mapie.Odpowiedzi:
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ć
n
przedmioty 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
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:
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.
źródło
Pewnie
rand() % n
będąc mniej niż idealnymDoing
rand() % n
ma nierównomierny rozkład. Otrzymasz nieproporcjonalną liczbę niektórych wartości, ponieważ liczba wartości nie jest wielokrotnością 20Nastę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% 20
wyrażeniem typu) nie są tak losowe. Pamiętam jedenrand()
z lat temu, w którym najniższy bit zmieniał się od1
do0
przy każdym wywołaniu dorand()
- nie był zbyt przypadkowy.Na stronie podręcznika rand (3):
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)
Porównaj to z:
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
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:
jest bardziej „losowy” niż:
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ć.
źródło
Next, rand() is typically a linear congruential generator
Obecnie 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.RAND_MAX
32767 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.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ć:
Wynik:
Wystarczy zmienić NUMBER_OF_SPAWNS, aby uzyskać więcej lub mniej losowych komórek, nie zmieni to czasu obliczeń wymaganego dla zadania.
źródło