Ich versuche eine Art Spiel zu machen, in dem ich ein Raster von 20x20 habe und einen Spieler (P), ein Ziel (T) und drei Feinde (X) anzeige. Alle diese haben eine X- und eine Y-Koordinate, die mit zugewiesen werden rand(). Das Problem ist, dass wenn ich versuche, mehr Punkte im Spiel zu bekommen (Energie nachfüllen usw.), diese sich mit einem oder mehreren der anderen Punkte überschneiden, weil die Reichweite klein ist (1 bis einschließlich 20).
Dies sind meine Variablen und wie ich ihnen Werte zuweise: (das COORDist ein structmit nur einem X und einem 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;
}Ich möchte dem Spiel mehr Dinge hinzufügen, aber die Wahrscheinlichkeit einer Überlappung steigt, wenn ich das tue. Gibt es eine Möglichkeit, dies zu beheben?
rand()ist ein mitleidiges RNG, und bei einer so geringen Reichweite muss man nicht nur mit Kollisionen rechnen , sie sind fast garantiert.rand()es sich um ein mieses RNG handelt, aber es ist wahrscheinlich für ein Einzelspielerspiel geeignet, und die RNG-Qualität ist hier nicht das Problem.rand()zu sprechen, scheint hier irrelevant zu sein. Es ist keine Kryptographie beteiligt, und jedes RNG wird sehr wahrscheinlich Kollisionen in einer so kleinen Karte verursachen.Antworten:
Während die Benutzer, die sich über
rand()bessere RNGs beschweren und diese empfehlen, hinsichtlich der Qualität der Zufallszahlen Recht haben, fehlt ihnen auch das Gesamtbild. Duplikate in Zufallszahlenströmen können nicht vermieden werden, sie sind eine Tatsache des Lebens. Dies ist die Lehre aus dem Geburtstagsproblem .Bei einem Raster von 20 * 20 = 400 möglichen Spawnpositionen ist ein doppelter Spawnpunkt zu erwarten (50% Wahrscheinlichkeit), selbst wenn nur 24 Entitäten erzeugt werden. Bei 50 Entitäten (immer noch nur 12,5% des gesamten Rasters) liegt die Wahrscheinlichkeit eines Duplikats bei über 95%. Sie müssen mit Kollisionen umgehen.
Manchmal können Sie alle Samples gleichzeitig zeichnen, dann können Sie einen Shuffle-Algorithmus verwenden, um
ngarantiert unterschiedliche Elemente zu zeichnen . Sie müssen nur die Liste aller Möglichkeiten erstellen. Wenn die vollständige Liste der Möglichkeiten zu groß ist, um sie zu speichern, können Sie wie jetzt nacheinander Spawn-Positionen generieren (nur mit einem besseren RNG) und bei einer Kollision einfach neu generieren. Obwohl einige Kollisionen wahrscheinlich sind, sind viele Kollisionen in einer Reihe exponentiell unwahrscheinlich, selbst wenn der größte Teil des Gitters gefüllt ist.quelle
Wenn Sie immer vermeiden möchten, eine neue Entität an einem Ort abzuspielen, der bereits einem anderen zugeordnet wurde, können Sie Ihren Prozess geringfügig ändern. Dies würde eindeutige Standorte garantieren, erfordert jedoch etwas mehr Overhead. Hier sind die Schritte:
Solange Sie den Speicherort aus dem Satz entfernen, aus dem Sie auswählen, sollte es keine Chance geben, dass eine zweite Entität denselben Speicherort erhält (es sei denn, Sie wählen die Speicherorte aus mehr als einem Thread gleichzeitig aus).
Ein reales Analogon dazu wäre das Ziehen einer Karte aus einem Kartenspiel. Derzeit mischen Sie das Deck, ziehen eine Karte und markieren sie, legen die gezogene Karte wieder in das Deck, mischen neu und ziehen erneut. Der obige Ansatz überspringt das Zurücklegen der Karte in das Deck.
quelle
In Bezug darauf
rand() % n, weniger als ideal zu seinTun
rand() % nhat eine ungleichmäßige Verteilung. Sie erhalten eine unverhältnismäßige Anzahl bestimmter Werte, da die Anzahl der Werte kein Vielfaches von 20 istAls nächstes
rand()wird typischerweise ein linearer Kongruenzgenerator verwendet (es gibt viele andere , nur dies ist der wahrscheinlichste implementierte - und mit weniger als idealen Parametern (es gibt viele Möglichkeiten, die Parameter auszuwählen)). Das größte Problem dabei ist, dass die niedrigen Bits darin (die, die Sie mit einem% 20Typausdruck erhalten) oft nicht so zufällig sind. Ich erinnere mich an einerand()von Jahren , wo das niedrigste Bit von abgewechselt ,1um0mit jedem Anrufrand()- es ist nicht sehr zufällig war.Aus der Manpage von rand (3):
Dies mag jetzt in die Geschichte verbannt sein, aber es ist durchaus möglich, dass Sie immer noch eine schlechte rand () - Implementierung haben, die sich irgendwo im Stapel versteckt. In diesem Fall ist es immer noch durchaus anwendbar.
Die Sache zu tun ist, tatsächlich eine gute Zufallszahlenbibliothek zu verwenden (die gute Zufallszahlen liefert) und dann nach Zufallszahlen innerhalb des gewünschten Bereichs zu fragen.
Ein Beispiel für ein gutes Zufallszahlen-Codebit (ab 13:00 im verknüpften Video)
Vergleichen Sie dies mit:
Führen Sie beide Programme aus und vergleichen Sie, wie oft bestimmte Zahlen in dieser Ausgabe angezeigt werden (oder nicht).
In Verbindung stehendes Video: rand () als schädlich angesehen
Einige historische Aspekte von rand (), die Fehler in Nethack verursachen, die man bei seinen eigenen Implementierungen beobachten und berücksichtigen sollte:
Nethack RNG Problem
Obwohl das oben Genannte aus dem Jahr 2003 stammt, sollte es dennoch beachtet werden, da möglicherweise nicht alle Systeme, auf denen Ihr beabsichtigtes Spiel ausgeführt wird, ein aktuelles Linux-System mit einer guten rand () -Funktion sind.
Wenn Sie dies nur für sich selbst tun, können Sie testen, wie gut Ihr Zufallszahlengenerator ist, indem Sie Code schreiben und die Ausgabe mit ent testen .
Über die Eigenschaften von Zufallszahlen
Es gibt andere Interpretationen von "zufällig", die nicht genau zufällig sind. In einem zufälligen Datenstrom ist es durchaus möglich, dieselbe Zahl zweimal zu erhalten. Wenn Sie eine Münze werfen (zufällig), ist es durchaus möglich, zwei Köpfe hintereinander zu bekommen. Oder wirf zweimal einen Würfel und erhalte zweimal hintereinander dieselbe Zahl. Oder ein Roulette-Rad drehen und dort zweimal die gleiche Nummer bekommen.
Die Verteilung von Zahlen
Beim Abspielen einer Songliste erwarten die Leute, dass "zufällig" bedeutet, dass derselbe Song oder Künstler nicht ein zweites Mal hintereinander gespielt wird. Eine Wiedergabeliste mit den Beatles zweimal hintereinander spielen wird als ‚nicht zufällig‘ zu haben (obwohl es ist zufällig). Die Wahrnehmung, dass für eine Wiedergabeliste von vier Songs insgesamt acht Mal gespielt wurde:
ist eher 'zufällig' als:
Mehr dazu zum 'Mischen' von Songs: Wie mische ich Songs?
Bei wiederholten Werten
Wenn Sie Werte nicht wiederholen möchten, sollten Sie einen anderen Ansatz in Betracht ziehen. Generieren Sie alle möglichen Werte und mischen Sie sie.
Wenn Sie anrufen
rand()(oder einen anderen Zufallszahlengenerator), rufen Sie ihn mit Ersatz an. Sie können immer zweimal dieselbe Nummer erhalten. Eine Möglichkeit besteht darin, die Werte immer wieder herauszuwerfen, bis Sie einen auswählen, der Ihren Anforderungen entspricht. Ich werde darauf hinweisen, dass dies eine nicht deterministische Laufzeit hat und es möglich ist, dass Sie sich in einer Situation befinden, in der es eine Endlosschleife gibt, wenn Sie nicht mit einer komplexeren Rückverfolgung beginnen.Liste und Auswahl
Eine andere Möglichkeit besteht darin, eine Liste aller möglichen gültigen Zustände zu erstellen und dann ein zufälliges Element aus dieser Liste auszuwählen. Finde alle leeren Stellen (die einigen Regeln entsprechen) im Raum und wähle dann eine zufällige aus dieser Liste aus. Und dann mach es immer wieder, bis du fertig bist.
Mischen
Der andere Ansatz besteht darin, zu mischen, als wäre es ein Kartenspiel. Beginnen Sie mit allen leeren Stellen im Raum und weisen Sie sie dann zu, indem Sie die leeren Stellen nacheinander jeder Regel / jedem Prozess zuordnen und nach einer leeren Stelle fragen. Sie sind fertig, wenn Ihnen die Karten ausgehen oder die Dinge nicht mehr nach ihnen fragen.
quelle
Next, rand() is typically a linear congruential generatorDies gilt derzeit nicht auf vielen Plattformen. Aus der rand (3) Manpage von Linux: "Die Versionen von rand () und srand () in der Linux C Library verwenden denselben Zufallszahlengenerator wie random (3) und srandom (3), also die Bits niedrigerer Ordnung sollte so zufällig sein wie die höherwertigen Bits. " Wie @delnan betont, ist die Qualität des PRNG hier nicht das eigentliche Problem.RAND_MAX32767 beträgt der Unterschied 1638 Möglichkeiten, einige Zahlen zu erhalten, gegenüber 1639 für andere. Es scheint unwahrscheinlich, dass das OP einen großen praktischen Unterschied macht.Die einfachste Lösung für dieses Problem wurde in früheren Antworten zitiert: Es besteht darin, neben jeder Ihrer 400 Zellen eine Liste mit Zufallswerten zu erstellen und diese Zufallsliste dann zu sortieren. Ihre Liste der Zellen wird als Zufallsliste sortiert und auf diese Weise gemischt.
Dieses Verfahren hat den Vorteil, dass die Überlappung zufällig ausgewählter Zellen vollständig vermieden wird.
Der Nachteil ist, dass Sie für jede Ihrer Zellen einen zufälligen Wert in einer separaten Liste berechnen müssen . Also machst du es lieber nicht, während das Spiel gestartet ist.
Hier ist ein Beispiel, wie Sie es tun können:
Ergebnis:
Ändern Sie einfach NUMBER_OF_SPAWNS, um mehr oder weniger zufällige Zellen zu erhalten. Dadurch wird die für die Aufgabe erforderliche Rechenzeit nicht geändert.
quelle