Wie kann ich diese Zufallszahlengenerierung in meinem Kontext verbessern?

11

In meinem Spiel befindet sich oben auf dem Bildschirm ein Wort, Buchstaben regnen von oben nach unten und der Benutzer muss die Buchstaben berühren, um das Wort zu vervollständigen.

Momentan generiere ich Buchstaben nach dem Zufallsprinzip (tatsächlich sind Zufallszahlen und Zahlen der Index für das Buchstabenarray, z. B.: 0 = a, 1 = b), aber das Problem ist, dass es zu lange dauert, bis alle erforderlichen Buchstaben zum Ausfüllen der Buchstaben vorliegen Wort.

Ich möchte, dass die Zufallszahlen, die ich generiere, häufiger die erforderlichen Buchstaben generieren, damit der Spieler nicht den ganzen Tag damit verbringen muss, ein Wort zu vervollständigen.

Ich habe folgende Methoden ausprobiert:

  1. Erkennen Sie alle Buchstaben im Wort (das Wort ist immer 6 Buchstaben lang), generieren Sie das Array von Indizes der Länge 6, weisen Sie jedem Index des Arrays eine Zufallszahl von Buchstabe 2 bis Buchstabe + 2 zu und wählen Sie am Ende zufällig einen Index aus aus dem Array zu zeigen.

  2. Lassen Sie eine Selektorvariable, deren Wert im Bereich [0..2] liegt, zufällig generieren. Wenn Selektor == 0 ist, erkennen Sie Buchstaben, aus denen das Wort besteht, und wählen Sie zufällig einen Buchstaben aus. Andernfalls erhalten Sie zufällig ein Alphabet von az.

Beide Methoden haben mir keine Hilfe gegeben. Ich würde mich sehr freuen, wenn Sie mir helfen können.

Vielen Dank für das Lesen. Ich hoffe, Sie haben die Frage verstanden und ich warte auf die Antwort.

Daniyal Azram
quelle
2
"Beide Methoden haben mir keine Hilfe gegeben" Warum nicht? Was hat mit diesen Methoden nicht funktioniert?
Vaillancourt
Ich weiß nicht warum, aber es dauert immer noch zu viel Zeit wie 1 Minute, um alle erforderlichen Alphabete zu erhalten.
Daniyal Azram
@DaniyalAzram Sie sollten die Häufigkeit wahrscheinlich noch etwas erhöhen, wenn diese Buchstaben nicht oft genug erscheinen, da es so klingt, als ob dies Ihr Problem ist.
JFA

Antworten:

21

Sie wollen eigentlich keine zufällige Verteilung. Ich weise explizit darauf hin, denn was wir für das Design als "zufällig" betrachten, ist normalerweise keine echte Zufälligkeit.

Lassen Sie uns in diesem Sinne einige Optimierungswerte hinzufügen - dies sind Dinge, mit denen Sie herumspielen werden, bis sich das Design "richtig" anfühlt.

ChooseLetter() {
    const float WordLetterProbability = 0.5f;
    if (Random.NextFloat01() < WordLetterProbability) {
        // Pick a random letter in the word
    }
    else {
        // Pick a random letter *not* in the word
    }
}

Die Wahrscheinlichkeit steuert, wie wahrscheinlich es ist, dass Sie bei einem bestimmten Aufruf von ChooseLetter einen Wortbuchstaben erhalten. Bei 0,5 erhalten Sie ungefähr jedes zweite Mal einen Wortbuchstaben. Bei 0,25 ist jeder vierte ein Wortbuchstabe usw.

Dies ist immer noch ein bisschen simpel - da Zufälligkeit zufällig ist , haben Sie keine Garantie dafür, wie lange Sie zwischen Wortbuchstaben wechseln. (Theoretisch kann man für immer ohne einen Wortbuchstaben auskommen, es ist nur sehr, sehr unwahrscheinlich.) Stattdessen können wir einen Faktor hinzufügen, um die Wahrscheinlichkeit eines Wortbuchstabens jedes Mal zu erhöhen, wenn wir keinen erhalten:

const float BaseWordLetterProbability = 0.5f;
const float WordLetterProbabilityIncrease = 0.25f;
float WordLetterProbability = BaseWordLetterProbability;
ChooseLetter() {
    if (Random.NextFloat01() < WordLetterProbability) {
        // Pick a random letter in the word
        WordLetterProbability = BaseWordLetterProbability;
    }
    else {
        // Pick a random letter *not* in the word
        WordLetterProbability += WordLetterProbabilityIncrease;
    }
}

Okay, jetzt gehen wir nie mehr als zwei Buchstaben ohne einen Wortbuchstaben. (Weil wir nach zwei Fehlern eine Wahrscheinlichkeit von 1,0 haben, einen Wortbuchstaben zu bekommen.)

Schließlich müssen wir berücksichtigen, wie die Auswahl des Buchstabens in einem Wort funktioniert. Um dem Spieler die Buchstaben zu liefern, die er tatsächlich benötigt, müssen wir die Buchstaben aus dem Satz entfernen, sobald sie sie erhalten.

Wenn das Wort beispielsweise "Test" lautet und der Spieler bereits "s" hat, möchten wir ihm keine weiteren "s" geben, da er sie nicht benötigt!

Von hier aus wird der Rest an Ihr Design angepasst.

ACEfanatic02
quelle
Beeindruckend! Wie bist du überhaupt darauf gekommen ?: p Ich werde deine Methode morgen früh testen und ich denke, es wird funktionieren. Ich werde mehr Feedback geben, sobald ich diese Methode getestet habe. Vielen Dank für diese Antwort.
Daniyal Azram
4
Statistiken! Als Spieledesigner oder Programmierer sind Statistiken sehr lernenswert. Zumindest ist ein Verständnis der Wahrscheinlichkeit (und wie man sie kombiniert) äußerst nützlich.
ACEfanatic02
1
Kommen Sie, um dasselbe vorzuschlagen. Gute Antwort. Denken Sie auch daran, dass eine Lösung wie diese eine Möglichkeit sein könnte, Schwierigkeitsgrade einzuführen. Leicht = 0,5, mittel = 0,25, hart = 0,10. etc
Tasos
Ich bin nicht der Meinung, dass dies nicht zufällig ist. Dies ist zufällig, es ist nur eine stückweise Verteilung, während wir normalerweise an die gleichmäßige Verteilung denken. Und um Ihrer Idee etwas hinzuzufügen, würde ich weiter gehen als nur "Wählen Sie einen zufälligen Buchstaben im Wort". Ich würde das durch die Buchstaben verteilen, die am häufigsten vorkommen. Zum Beispiel braucht "Mississippi" mehr s und ich wähle mehr davon.
Blaine
21

Sie können die Wahrscheinlichkeit aller Ihrer Buchstaben anhand der Häufigkeit gewichten, mit der sie in der Sprache vorkommen, in der sich Ihre Wörter befinden. Eine gute Richtlinie ist das Scrabble-Set . Die englische Version hat zum Beispiel 12 E, aber nur ein Z und ein Q.

Eine einfache Möglichkeit, dies zu implementieren, besteht darin, alle Buchstaben in eine fortlaufende Zeichenfolge zu setzen, wobei jeder Buchstabe so oft wie gewünscht erscheint, und dann Ihr RNG einen Buchstaben von einer zufälligen Position nehmen zu lassen. Pseudocode-Beispiel:

const String letters = "AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJ/*...and so on...*/"

char randomLetter = letters[randomIntegerBetween(0, letters.length - 1)];
Philipp
quelle
2
+1 Dies ist ein gutes Konzept, aber ich vermute, dass es eine elegantere Implementierung gibt.
Evorlor
Für eine feinkörnigere Verteilung können Sie eine Tabelle mit Buchstabenhäufigkeiten speichern, die so skaliert sind, dass sie sich zu 1 summieren, eine Zufallszahl von 0 bis 1 generieren und die Tabelle durchlaufen und die Häufigkeit jedes Buchstabens von der Zufallszahl bis dahin subtrahieren wird Null oder negativ. Sie können dies sogar optimieren, indem Sie die häufigsten Buchstaben zuerst in der Tabelle sortieren. Oder verwenden Sie so etwas wie die Alias-Methode , um zu vermeiden, dass die Tabelle vollständig durchlaufen wird.
Ilmari Karonen
4
Dies würde das Problem nicht lösen. Das Problem ist , der Benutzer muss bestimmte Buchstaben das Spiel zu beenden. Sagen sie, sie brauchen ein Z? Was dann? Dies würde es nur seltener machen, seltene Buchstaben zu bekommen, was den Benutzer noch frustrierter macht.
AmazingDreams
@AmazingDreams weisen auf eine gute Sache hin, aber wir können sie ein wenig ändern, damit ich den erforderlichen Alphabeten mehr Gewicht und anderen weniger Gewicht zuweisen werde. Ich muss sagen, dass dies ein sehr gutes Konzept ist.
Daniyal Azram
4

Hier ist eine Möglichkeit, es mit einem einzigen Parameter zu verbessern k, den Sie anpassen können.

Anstatt nur einen zufälligen Buchstaben auszuwählen:

  1. Wähle einen zufälligen Buchstaben A
  2. Wähle eine Zufallszahl X
  3. wenn X > k und A ist nicht in [list of remaining needed letters], versuchen Sie es erneut auf 1.

Je kleiner kist, desto öfter wird der letzte Buchstabe Atatsächlich benötigt.

Um den Algorithmus zu optimieren, spielt mit einem beliebigen Wert für k, zB k = 0.5 . Wenn Sie feststellen, dass das Spiel zu schwierig ist, versuchen Sie es 0.4stattdessen usw., bis Sie einen angemessenen Wert gefunden haben. Dies gibt Ihnen auch direkt eine Schwierigkeitseinstellung , die Sie beispielsweise erhöhen möchten, wenn der Spieler im Spiel Fortschritte macht.

Sam Hocevar
quelle
Vielen Dank für die Antwort, aber dies scheint genau die Antwort des ACEfanatic02 zu sein.
Daniyal Azram
3

Eine einfache Möglichkeit, um sicherzustellen, dass die erforderlichen Buchstaben innerhalb einer bestimmten Zeit angezeigt werden, besteht darin, ein Array mit den Buchstaben im Wort und dem Rest des Alphabets zu füllen (möglicherweise wiederholt) und das Array dann zufällig zu mischen (c ++ hat std :: random_shuffle) Wenn Sie in der Standardbibliothek eine andere Sprache verwenden, ist die Implementierung nicht schwierig.

Wenn Sie möchten, dass die Buchstaben im Wort schneller angezeigt werden, fügen Sie mehr Kopien der Wortbuchstaben in das Array ein.

GuyRT
quelle
0

Wenn Sie C ++ verwenden, können Sie eine bereits vorhandene Distribution http://en.cppreference.com/w/cpp/numeric/random/piecewise_constant_distribution verwenden

Es hat auch eine konstante zeitliche Komplexität amortisiert, die besser ist als naive Methoden. Beispiel:

#include <iostream>
#include <string>
#include <map>
#include <random>
#include <numeric>

int main()
{
    constexpr double containedLetterWeight = 3.0;
    constexpr int iterations = 10000;
    std::string word = "DISTRIBUTION";

    std::mt19937 rng(123);

    std::vector<double> values('Z' - 'A' + 2);
    std::iota(values.begin(), values.end(), 0.0);

    std::vector<double> weights('Z' - 'A' + 1, 1.0);
    for(const auto& c : word) weights[c - 'A'] = containedLetterWeight;

    std::piecewise_constant_distribution<> dist(values.begin(), values.end(), weights.begin());

    std::map<char, int> results;
    for(int n = 0; n < iterations; ++n)
    {
        ++results[static_cast<char>(dist(rng)) + 'A'];
    }
    for(const auto& p : results)
    {
        std::cout << p.first << ' ' << static_cast<float>(p.second) / iterations << '\n';
    }
}
Sopel
quelle