Game Development Reference
In-Depth Information
include nuclear reactions, stellar evolution, and low-density airflow over spacecraft reentering
the earth's atmosphere.
■
Tidbit
The term “Monte Carlo” was introduced by one of the pioneers of probabilistic methods,
Stanislaw Marcin Ulam, in honor of his uncle, who was a gambler at the Monte Carlo casino.
Monte Carlo simulations are fairly recent; formal Monte Carlo simulations were first
performed in the 1940s, but the theoretical background for the Monte Carlo technique evolved
from earlier research. Nineteenth century scientists tried to estimate the value of functions by
throwing darts at a picture of the function curve. In the early twentieth century, statisticians in
British universities were working with experimental sampling methods that had some similar-
ities to Monte Carlo.
The real driving force in the development of Monte Carlo methods occurred during World
War II when research was being performed to develop the atomic bomb. Scientists realized
that probabilistic techniques could be used to simulate neutron diffusion. Before long, Monte
Carlo methods were being applied to solve complex equations in nuclear physics, and scien-
tists soon discovered many other subjects to which Monte Carlo methods could be applied.
Monte Carlo methods can be used in game programming situations as a way of applying
“orderly” randomness to a system of objects. The behavior of an individual object is random in
that there will be more than one state the object can be in, and there is no way of knowing what
that state will be at any given time. While the behavior of any given object is random, it is also
orderly in that some states are more likely than others according to the nature of the probability
function.
For example, let's say you were modeling the flight of arrows released from a company
of bowmen. It would be pretty boring if the arrows all flew in exactly the same trajectory and
landed on exactly the same spot. Using a probability function and a random number gener-
ator, the arrows can be given a distribution of initial velocities and flight angles. This process
would give a much more realistic look to the flight of arrows.
The basic elements of a Monte Carlo simulation are system subcomponents, probability
functions, and random numbers. A probability function is used to assign behaviors to the
system subcomponents. The subcomponents might be air molecules, ants, or anything else for
that matter. The probability values to apply to the probability function are normally obtained
from a random number generator. The overall behavior of the system can be found by summing
up, or integrating, the behavior of the subcomponents.
The concept of a Monte Carlo simulation may seem rather confusing to you, so let's go
over a couple of simple applications for the Monte Carlo technique.
Using Monte Carlo Methods to Simulate Crowd Behavior
One good use of Monte Carlo methods in game programming situations is to simulate the
behavior of a group of independent objects. The individual objects (people, cows, cars, etc.)
can have characteristics (speed, weight, height, etc.) whose values are assigned based on a
probability function. When the simulation begins, random numbers are generated, and these
random numbers are used to model the behavior of the individual objects. The objects act
