Wat is een goede generator voor willekeurige getallen voor een spel?

Wat is een goede generator voor willekeurige getallen om te gebruiken voor een spel in C++?

Mijn overwegingen zijn:

1. Er zijn veel willekeurige getallen nodig, dus snelheid is goed.
2. Spelers zullen altijd klagen over willekeurige getallen, maar ik zou ze graag willen verwijzen naar een referentie die uitlegt dat ik echt mijn werk heb gedaan.
3. Aangezien dit een commercieel project is waar ik niet veel tijd voor heb, zou het fijn zijn als het algoritme ofwel a) relatief eenvoudig te implementeren was of b) een goede niet-GPL-implementatie beschikbaar had.
4. Ik gebruik rand()al op heel veel plaatsen, dus elke andere generator kan maar beter goed zijn om alle benodigde wijzigingen te rechtvaardigen.

Ik weet niet veel over dit onderwerp, dus het enige alternatief dat ik kan bedenken is de Mersenne Twister; voldoet het aan al deze eisen? Is er iets anders dat beter is?

Bewerken:Mersenne Twister lijkt de consensuskeuze te zijn. Maar hoe zit het met punt #4? Is het echt zoveel beter dan rand()?

Bewerken 2:Laat me wat duidelijker zijn over punt 2: Spelers kunnen op geen enkele manier vals spelen door de willekeurige getallen te kennen. Periode. Ik wil dat het willekeurig genoeg is dat mensen (althans degenen die willekeur begrijpen) er niet over kunnen klagen, maar ik maak me geen zorgen over voorspellingen.
Daarom heb ik snelheid als belangrijkste overweging gesteld.

Bewerken 3:Ik neig nu naar de Marsaglia RNG’s, maar ik wil toch graag meer input. Daarom stel ik een premie in.

Bewerk 4:Even een opmerking: ik ben van plan vandaag een antwoord te accepteren net voor middernacht UTC (om te voorkomen dat je met iemands rep-cap knoeit). Dus als je overweegt te antwoorden, wacht dan niet tot het laatste moment!
Ik hou ook van het uiterlijk van Marsaglia’s XORshift-generatoren. Heeft iemand enige input over hen?

Antwoord 1, autoriteit 100%

Somswillen game-ontwikkelaars geen echte willekeur en een shuffle bagis meer geschikt.

Als je wel willekeur wilt, voldoet de Mersenne-twister aan je eisen. Het is snel, statistisch willekeurig, heeft een lange periode en er zijn tal van implementaties.

Bewerken: rand()wordt doorgaans geïmplementeerd als een lineaire congruentiële generator. Het is waarschijnlijk het beste als u een weloverwogen keuze maakt of het wel of niet goed genoeg is voor uw doeleinden.

Antwoord 2, autoriteit 88%

Er zijn tegenwoordig veel betere keuzes dan Mersenne Twister. Hier is een RNG genaamd WELL512, ontworpen door de ontwerpers van Mersenne, 10 jaar later ontwikkeld en een betere keuze voor games. De code is in het publieke domein geplaatst door Dr. Chris Lomont. Hij beweert dat deze implementatie 40% sneller is dan Mersenne, geen last heeft van slechte diffusie en trapping wanneer de toestand veel 0 bits bevat, en duidelijk een veel eenvoudigere code is. Het heeft een periode van 2^512; een pc doet er meer dan 10^100 jaar over om door de staten te fietsen, dus hij is groot genoeg.

Hier is een paper met een overzicht van PRNG’s waar ik de WELL512-implementatie vond.
http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

Dus – sneller, eenvoudiger, gemaakt door dezelfde ontwerpers 10 jaar later, en produceert betere cijfers dan Mersenne. Hoe kun je fout gaan? 🙂

UPDATE (11-18-14): fout opgelost (veranderd 0xDA442D20UL in 0xDA442D24UL, zoals beschreven in het artikel waarnaar hierboven is gelinkt).

/* initialize state to random bits */
static unsigned long state[16];
/* init should also reset this to 0 */
static unsigned int index = 0;
/* return 32 bit random number */
unsigned long WELLRNG512(void)
   {
   unsigned long a, b, c, d;
   a = state[index];
   c = state[(index+13)&15];
   b = a^c^(a<<16)^(c<<15);
   c = state[(index+9)&15];
   c ^= (c>>11);
   a = state[index] = b^c;
   d = a^((a<<5)&0xDA442D24UL);
   index = (index + 15)&15;
   a = state[index];
   state[index] = a^b^d^(a<<2)^(b<<18)^(c<<28);
   return state[index];
   }

Antwoord 3, autoriteit 65%

George Marsagliaheeft enkele van de beste en snelste RNG’s ontwikkeld die momenteel beschikbaar zijn
Vermenigvuldigen-met-carryis opmerkelijk voor een uniforme distributie.

=== Update 12-09-2018 ===

Voor mijn eigen werk gebruik ik nu Xoshiro256* *, wat een soort evolutie/update is van Marsaglia’s XorShift.

=== Update 2021-02-23 ===

In .NET 6 (momenteel in preview) is de implementatie van System.Random gewijzigd om xoshiro256** te gebruiken, maar alleen voor de parameterloze constructor. De constructor die een seed neemt, gebruikt de oude PRNG om achterwaartse compatibiliteit te behouden. Voor meer info zie Random verbeteren (prestaties, API’s, …)

Antwoord 4, autoriteit 23%

Mersenne Twister is typisch in de branche, vooral omdat het zich goed leent voor SIMD en supersnel gemaakt kan worden. Knuthis ook populair (bedankt, David).

In de meeste game-applicaties is snelheid echt de kritische factor, aangezien spelers veel meer zullen klagen over een lage framerate dan dat ze zullen klagen over het feit dat er een lichte neiging is om een ​​3 te genereren wanneer deze wordt voorafgegaan door een 7 , 2 en 9 in die volgorde.

Uitzondering is natuurlijk gokken om geld, maar daar zal uw relevante vergunningverlenende instantie specifiek aangeven welke algoritmen u kunt gebruiken.

Antwoord 5, autoriteit 23%

Koop een goedkope webcam, een ioniserende rookmelder. Demonteer beide, rookmelders bevatten weinig radioactief materiaal – een bron van gammagolven – waardoor er fotonen op je webcam worden afgevuurd. Dat is jouw bron van echte willekeur 🙂

Antwoord 6, autoriteit 14%

Mersenne Twister is erg goed en ook nog eens snel. Ik heb het in een game gebruikt en het is helemaal niet moeilijk om te implementeren of te gebruiken.

Het WELL willekeurige algoritmeis ontworpen als een verbetering ten opzichte van de Mersenne Twister. Game Gems7 heeft meer informatie. erop, als je dat kunt lenen of hebben.

Op die WELL-pagina waarnaar ik je heb gelinkt, is het nummer de periode van het algoritme. Dat wil zeggen, u kunt 2^N – 1 getallen krijgen voordat het opnieuw moet worden ingezaaid, waarbij N is: 512, 1024, 19937 of 44497. Mersenne Twister heeft een periode van N = 19937, of 2^19937 – 1. U zult zie dit is een zeer groot aantal🙂

Het enige andere waar ik op kan wijzen is dat boosteen willekeurige bibliotheek, die u nuttig zou moeten vinden.

Als reactie op je bewerking, ja, de Twister of WELL is zoveel beter dan rand(). Ook schaadt de oude modulus-truc de verdeling van de getallen. Nog meer reden om boost te gebruiken 🙂

Antwoord 7, autoriteit 9%

In een realtime game kan een speler op geen enkele manier het verschil bepalen tussen een ‘goede’ generator en een ‘slechte’ generator. In een turn-based game heb je gelijk – een minderheid van fanatici zal klagen. Ze zullen je zelfs verhalen vertellen, in ondragelijke details, over hoe je hun leven hebt verpest met een slechte generator voor willekeurige getallen.

Als u een stel echte willekeurige nummers nodig hebt (en u bent een online game), kunt u wat op Willekeurige.org . Gebruik ze voor turn-based games of als zaden voor real-time games.

8, Autoriteit 7%

Gebaseerd op de willekeurige nummergenerator door Ian C. Bullard:

// utils.hpp
namespace utils {
    void srand(unsigned int seed);
    void srand();
    unsigned int rand();
}
// utils.cpp
#include "utils.hpp"
#include <time.h>
namespace {
    static unsigned int s_rand_high = 1;
    static unsigned int s_rand_low = 1 ^ 0x49616E42;
}
void utils::srand(unsigned int seed)
{
    s_rand_high = seed;
    s_rand_low = seed ^ 0x49616E42;
}
void utils::srand()
{
    utils::srand(static_cast<unsigned int>(time(0)));
}
unsigned int utils::rand()
{
    static const int shift = sizeof(int) / 2;
    s_rand_high = (s_rand_high >> shift) + (s_rand_high << shift);
    s_rand_high += s_rand_low;
    s_rand_low += s_rand_high;
    return s_rand_high;
}

Waarom?

• zeer, erg snel
• Hogere entropie dan de meeste standaard rand()implementaties
• gemakkelijk te begrijpen

9, Autoriteit 5%

Een aanvullende criteria die u moet overwegen is draadveiligheid. (En u moet draden in de hedendaagse multi-core-omgevingen gebruiken.) Gewoon Rand uit meer dan één thread kan rommelen met zijn deterministische gedrag (als uw spel daarvan afhangt). Ik zou je op zijn minst aanraden om over te schakelen naar Rand_r.

10, Autoriteit 2%

Ik zou ook stemmen voor de Mersenne Twister. Implementaties zijn op grote schaal beschikbaar, het heeft een zeer grote periode van 2 ^ 19937 -1, is redelijk snel en geeft de meeste willekeurige tests, waaronder de Diehard-tests die door Marsaglia zijn ontwikkeld. Rand () en Co., zijnde LCGS, produceren lagere kwaliteit afwijkingen en hun opeenvolgende waarden kunnen eenvoudig worden afgeleid.

Eén punt van opmerking is echter om MT goed te zaaien in een staat die willekeurige tests passeert. Meestal wordt een LCG zoals DAND48 () voor dat doel gebruikt.

Ik zou zeggen dat de MT voldoet aan alle vereisten die u hebt ingesteld (Project), en het zou een overkill zijn om te gaan voor iets als MWCG IMO.

11, Autoriteit 2%

Gamerand Implementeer het algoritme hier geplaatst
http://www.fiPcode.com/Archives/07-15-2002.shtml

Dit is iets dat ik oorspronkelijk heb ontwikkeld in de late jaren 80.
Het versmalt Rand () op looptijd van numerieke kwaliteit, en als zij voordeel om het snelste willekeurige algoritme mogelijk te zijn.

12

Ik wil het willekeurig genoeg dat mensen (tenminste degenen die willekeurigheid begrijpen)
kan er niet over klagen, maar ik maak me geen zorgen over voorspellingen.

A-HA!

Er is uw echte vereiste!

Niemand kan u fout vinden voor het gebruik van Mersenne Twister in deze toepassing.

13

Afhankelijk van het doel-besturingssysteem, kunt u mogelijk /dev/random gebruiken. Het vereist niet echt enige implementatie, en op Linux (en misschien sommige andere besturingssystemen) is het echt willekeurig. De leesblokken totdat er voldoende entropie beschikbaar is, dus misschien wil je het bestand lezen en opslaan in een buffer of iets anders met een andere thread. Als u een blokkerende leesaanroep niet kunt gebruiken, kunt u /dev/urandom gebruiken. Het genereert willekeurige gegevens bijna net zo goed als /dev/random, maar het hergebruikt enkele willekeurige gegevens om onmiddellijk uitvoer te geven. Het is niet zo veilig, maar het zou prima kunnen werken, afhankelijk van wat je ermee wilt doen.

Antwoord 14

Weet je wat? Vergeef me als je denkt dat dit antwoord compleet waardeloos is… Maar ik heb (om god weet waarom…) DateTime.Now.Millisecondsgebruikt als een manier om een willekeurig getal te krijgen. Ik weet dat het niet helemaal willekeurig is, maar het lijkt…

Ik kon gewoon niet de moeite nemen om zoveel te typen ENKEL om een willekeurig getal te krijgen! 😛