Naked Paul Toast’s Insights

In my previous entry, I discussed why floor(), when used with random() is often preferable than ceil().

Now, it’s time to discuss why round() is undesirable, when used with the random() function.

The round() function will round real values, towards the nearest whole number. 10.2 is rounded downward to 10, 8.7 is rounded upwards to 9.

Values with exactly .5 after the decimal point are a special case, as they are exactly halfway between the nearest decimal point. Game Maker uses a technique called Bankers’ Rounding when rounding .5 decimal points. Essentially, half the time it rounds downward, the other half upward. Always creating an even whole number.

0.5 will be rounded down to 0, 1.5 rounded up to 2, 2.5 rounded down to 2. This form of rounding is used to reduce cumulative errors that can be introduced by a lot of rounding.

The problem with using round is, it creates an uneven skewing on the outer most integers, returning them half the time the inner most integers are returned.

For example, if we are interested in a random integer with the range 0-2, one might consider:

rand_number=round(random(2));

Looking at the distribution, we will find that 0 will be returned 25% of the time, 1 50% of the time and 2 25% of the time. This is probably not what we want.

Think of it this way:
25% of the time 0 - 0.5 is returned and rounded down to 0.
25% of the time 0.500000001 - 1 is returned and rounded to 1.
25% of the time 1.000000001 - 1.49999999 is returned and rounded to 1.
25% of the time 1.5 - 1.9999999999 is returned and rounded to 2.

There is twice the chance for a 1 to be chosen over 0 or 2.

I wrote a quick simulation to practically demonstrate the problem, comparing a random movementment between a green object and a red object. The green object will choose a random direction (right, down, left and up) using the preferred:
rand_number=floor(random(4));

The red object will choose it’s random direction, using the flawed:
rand_number=round(random(3));

The object moves, in the background, a red and green graph displays in percentages, how often each direction is chosen. Whenever the object touches the the edge of the room, it adds one to a counter and centers the object again.

Running the program, immediately you see the red object’s “random” walk isn’t very random, it is heavily skewed towards the upper-left of the screen.

Running the simulation, after 10 iterations, we see uneven distributions for both the red and green objects. 10 iterations are not statistically significant, and any patterns seen in the distribution can be explained by variance.
.
.
.
.

After 100 iterations we see the red object has moved to the left and upwards. Both distributions are starting to regress towards what probabilities says they should be.
.
.
.
.
.
.
After 1000 iterations we see the patterns pretty solidly. The green object is still relatively close to the centre, the red object has hit the wall four times.
.
.
.
.
.
.

After 10,000 and 100,000 iterations, the percentage are within a few percentage points, of what probabilities suggest they should be. The Green object has hit the wall only 22 times, while the red object has hit it 352 times.

Now picture the effects of putting flawed AI in your own games. Your enemies movement patterns might also show the same flawed movement. This would allow the player to easily predict movements helping them to avoid danger.

You can download the executable, or the GM 7 source, to test or modify.
rand_test.exe, rand_test.gmk, rand_test.zip.

This entry was posted on Tuesday, June 17th, 2008 at 1:03 am and is filed under Game Maker, Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. Responses are currently closed, but you can trackback from your own site.