How to improve this random number generation in my context?

Question

In my game there is a word at top of the screen, letters are raining down from top and the user has to touch the letters to complete the word.

Currently I am generating letters randomly (actually random numbers and numbers are the index for the array of letters. e.g: 0=a, 1=b) but the problem is that it takes too much time to get all the required letters to complete the word.

What I want is that the random numbers that I am generating should generate required letters more often so player don't have to spend all day to complete one word.

I have tried following methods:

1. Detect all the letters in the word (word is always 6 letters long), generate the array of indexes of length 6, assign each index of the array to random number from letter-2 to letter+2 and in the end pick randomly one index from the array to show.

2. Have a selector variable whose value is in the range [0..2], generated randomly, if selector == 0 then detect letters which make the word and randomly pick one letter, else randomly get any alphabet from a-z.

Both of these methods have not provide me with any help. I will be very happy if you can help me.

Thanks for reading this, I hope you understood the question and I am waiting for the response.

Answer 1

You don't actually want a random distribution. I point this out explictly, because what we consider "random" for design is usually not true randomness.

Now, with that in mind, let's add some tweaking values -- these are things you'll fiddle with until the design feels "right".

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
    }
}

The probability controls how likely a given call to ChooseLetter will give you a word letter -- at 0.5, you'll get a word letter roughly every other time. At 0.25, one out of four will be a word letter, etc.

This is still a bit simplistic -- because randomness is, well, random, you don't actually have a guarantee on how long you'll go between word letters. (In theory, you can go forever without a word letter, it's just very very unlikely.) Instead, we can add a factor to increase the probability of a word letter every time we don't get one:

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, so now we never go more than two letters without a word letter. (Because, after two misses, we have a 1.0 probability of getting a word letter.)

Finally, we need to take in to consideration how choosing the letter in a word works. In order to provide the player with the letters they actually need, we need to remove letters from the set as they get them.

For example, if the word is "test", and the player already has 's', we don't want to give them another 's', because they don't need it!

From here, the rest is tweaking to fit your design.

Answer 2

You could weight the probability of all your letters according to the frequency with which they occur in the language your words are in. A good guideline is the scrabble set. The English version, for example, has 12 E's but only one Z and one Q.

A simple way to implement this is by putting all the letters in a consecutive string with each letter appearing as often as desired and then have your RNG take a letter from a random position. Pseudocode example:

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

char randomLetter = letters[randomIntegerBetween(0, letters.length - 1)];

Answer 3

Here is one way to improve it using one single parameter k that you can tweak.

Instead of just picking a random letter:

1. pick a random letter A
2. pick a random number X
3. if X > k and A is not in [list of remaining needed letters], try again at 1.

The smaller k is, the more often the final letter A will be one that is actually needed.

To tweak the algorithm, play with any value for k, e.g k = 0.5. If you find the game is too hard, try 0.4 instead, etc. until you find a reasonable value. This also directly gives you a difficulty setting, which for instance you may want to increase as the player advances in the game.

Answer 4

A simple way to guarantee that the required letters show up within a given time is to use fill an array with the letters in the word and the rest of the alphabet (perhaps repeated), then randomly shuffle the array (c++ has std::random_shuffle in the standard library, if you're using a different language it is not difficult to implement).

If you want the letters in the word to show up more quickly, put more copies of the word-letters in the array.

Answer 5

If you are using C++ you can use an already existing distribution http://en.cppreference.com/w/cpp/numeric/random/piecewise_constant_distribution

It also has amortized constant time complexity which is better than naive methods. example:

#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';
    }
}