Need for predictable random generator
I'm a web-game developer and I got a problem with random numbers. Let's say that a player has 20% chance to get a critical hit with his sword. That means, 1 out of 5 hits should be critical. The problem is I got very bad real life results — sometimes players get 3 crits in 5 hits, sometimes none in 15 hits. Battles are rather short (3-10 hits) so it's important to get good random distribution.
Currently I use PHP mt_rand(), but we are just moving our code to C++, so I want to solve this problem in our game's new engine.
I don't know if the solution is some uniform random generator, or maybe to remember previous random states to force proper distribution.
Answer
That means, 1 out of 5 hits should be critical. The problem is I got very bad real life results - sometimes players get 3 crits in 5 hits, sometimes none in 15 hits.
What you need is a shuffle bag. It solves the problem of true random being too random for games.
The algorithm is about like this: You put 1 critical and 4 non-critical hits in a bag. Then you randomize their order in the bag and pick them out one at a time. When the bag is empty, you fill it again with the same values and randomize it. That way you will get in average 1 critical hit per 5 hits, and at most 2 critical and 8 non-critical hits in a row. Increase the number of items in the bag for more randomness.
Here is an example of an implementation (in Java) and its test cases that I wrote some time ago.