# How to improve this random number generation in my context?

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.

• "both of these methods haven't provide me with any help" Why not? What did not work with these methods? – Vaillancourt Jun 13 '16 at 16:20
• I don't know why but It still is taking too much time like 1 minute to get all alphabets required. – Daniyal Azram Jun 13 '16 at 16:22
• @DaniyalAzram you should probably increase the frequency some more if these letters aren't appearing often enough, as it sounds like that is what your problem is. – JFA Jun 14 '16 at 20:05

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.

• Wow! how did you even came up with that?:p I will test your method tomorrow morning and I think it will work, I will provide more feedback once I test this mehod. Thank you very much for such answer. – Daniyal Azram Jun 13 '16 at 17:32
• Statistics! As either a game designer or programmer, statistics are very worth learning. At the very least, an understanding of probability (and how to combine them) is extremely useful. – ACEfanatic02 Jun 13 '16 at 17:35
• Come to suggest the same thing. Great answer. Also keep in mind, that a solution like this one could be a way to introduce difficulty levels. Easy=0.5, medium=0.25, hard=0.10. etc – Tasos Jun 13 '16 at 23:06
• I disagree that this isn't random. This IS random, it's just a piecewise distribution whereas we usually think of the uniform distribution. And to add to your idea I'd go further than just "Pick a random letter in the word" I'd distribute that by the letters that occur most. For example "mississippi" needs more s's and i's so choose more of them. – Blaine Jun 14 '16 at 3:10
• – Ilmari Karonen Jun 14 '16 at 9:34

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)];

• +1 This is a good concept, but I suspect there is a more elegant implementation. – Evorlor Jun 13 '16 at 20:50
• – Evorlor Jun 13 '16 at 20:53
• For a more fine-grained distribution, you can store a table of letter frequencies scaled so that they sum to 1, generate a random number from 0 to 1, and loop over the table subtracting the frequency of each letter from the random number until it becomes zero or negative. You can even optimize this by sorting the most common letters first in the table. Or use something like the alias method to avoid looping over the table entirely. – Ilmari Karonen Jun 14 '16 at 9:50
• This wouldn't solve the problem. The problem is the user needs specific letters to finish the game. Say they need a Z? What then? This would just make rare letters harder to get making the user even more frustrated. – AmazingDreams Jun 14 '16 at 15:04
• @AmazingDreams point out good thing but we can modify it a little so I will assign more weight to the required alphabets and less weight to others. I must say this is very good concept to follow. – Daniyal Azram Jun 15 '16 at 8:22

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.

• Thanks for the answer but this seem just like the ACEfanatic02's answer. – Daniyal Azram Jun 15 '16 at 8:19

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.

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