/****************************************************************************** * * box_muller_transformation * * A Box-Muller transformation picks two numbers using a uniformly-random * random number generator, and then uses those two numbers to come up with a * normally-distributed number. In essence, it is a normally-distributed * random number generator (using the standard normal [IE - avg = 0, std = 1]) * * Returns - A normally distributed number * ******************************************************************************/ float box_muller_transformation() { /* Two uniformly random numbers, and a temporary for the magnitude. */ float ur1, ur2, magnitude; /* See below for the link to the full explanation of how and why this works. */ do { ur1 = 2.0 * (rand() % 10000) / 10000.0 - 1.0; ur2 = 2.0 * (rand() % 10000) / 10000.0 - 1.0; magnitude = ur1 * ur1 + ur2 * ur2; } while ( magnitude >= 1.0 ); magnitude = sqrt( (-2.0 * log( magnitude ) ) / magnitude ); /* It's MAGIC! Actually, check out: * http://www.wikipedia.org/wiki/Box-Muller_transformation * * This is basically algorithm 2. */ return ur1 * magnitude; } /****************************************************************************** * * random_normal_value * * Generates a random value based on the normal distribution centered at Avg * with standard deviation std. NOTE: Technically, a normal distribution * extends to infinity in both directions. However, to make this plausible in * game terms we cap the distribution at 3 standard-deviations in either * direction. IE - if a magic missile is supposed to do an average of 12 * damage, with standard-deviation of 2, it will never do less than 12 - 2*3 = 6, * and never do more than 12 + 2*3 = 18. * * avg - The average value we should give out. * std - The standard deviation of the distribution. * * Returns - a random value. * ******************************************************************************/ float random_normal_value(float avg, float std) { /* Get a normally distributed random number. This is based on the standard * normal, so it will be between -3 and 3 99% of the time, the average will * be 0, and the standard deviation is 1. */ float val = box_muller_transformation(); /* We cap this value at +-3.0. If we don't, an occaisonal call to this could * feasibly be 10+, which makes it really hard to deal with the formula. * (IE - imagine a magic missile that once every 1000 casts or so does 1000 * damage... */ while (val > 3.0 || val < -3.0) val = box_muller_transformation(); /* Now, we have a standard-normal number. But we want to translate this into * a normal with a given average and standard deviation. The logic of the * following is ass follows - the avg term merely shifts the whole to be * centered around our arbitrary average. The std * val is tricky - this * may not actually be statisticaly valid, but it works well. The idea is * to scale the deviation from the average based on the supplied standard * deviation. * * Example: We want avg = 50, std = 10. We grab a normally distributed * value of say, .5. This translates into 50 + 10 * .5 == 55. This is * one-half standard deviation right of the average of 50. The original * is also one-half standard-deviation to the right of the average (of 0) * See? It's happy, and shiny, and good. */ return avg + std * val; }