Generating Random Integers With Arbitrary Probabilities

header

I finally laid my hands on Donald Knuth’s The Art of Computer Programming (what a wonderful set of books!), and found a neat algorithm for generating random integers 0, 1, 2, … , n – 1, with probabilities p_0, p_1, … , p_(n-1).

I have written about generating random numbers (floats) with arbitrary distributions for one dimension and higher dimensions, and indeed that method can be adapted for generating integers with specific probabilities. However, the method described below is much more concise, and efficient (I would guess) for this special case. Moreover, it is also easy to adapt it to generate floats for continuous distributions.

Continue reading “Generating Random Integers With Arbitrary Probabilities”

Estimating a Continuous Distribution from a Sample Set

header_rand_dist2 It is sometimes necessary to find the distribution given a sample set from that distribution. If we do not know anything about the distribution, we cannot recover it exactly, so here we look at ways of finding a (discrete) approximation.

Continue reading “Estimating a Continuous Distribution from a Sample Set”

Generating Random Points from Arbitrary Distributions for 2D and Up

header_rand_dist

I have already covered how to generate random numbers from arbitrary distributions in the one-dimensional case. Here we look at a generalisation of that method that works for higher dimensions.

The basic trick, while easy to understand, is hard to put in words (without reverting to mathematical equations). For two dimensions, we divide the plane into slices. Each slice is a 1D distribution. We also calculate a distribution from summing the frequencies in each slice. The latter distribution gives us one coordinate, and the appropriate slice to use. The distribution of that slice then gives the second coordinate. All distributions are put into inverse accumulative response curves as was done to generate one-dimensional random numbers. (You should review that before implementing the 2D case).

In more dimensions, we also slice the space up into 1D distributions. Sums of these give us more distributions, which we can sum again, and again, until we reach a single distribution. This is used for the first coordinate, and to determine which distribution to use for the next coordinate. This goes on, until a 1D slice gives us the final coordinate. Again, all distributions are converted to inverse accumulative response curves.

If the above is unclear, I hope the detailed description below clears things up.

Continue reading “Generating Random Points from Arbitrary Distributions for 2D and Up”

Random Steering – 7 Components for a Toolkit

Random steering is often a useful for simulating interesting steering motion. In this post we look at components that make up a random steering toolkit. These can be combined in various ways to get agents to move in interesting ways.

You might want to have a look at Craig Reynolds’ Steering Behaviour for Autonomous Characters — the wander behaviour is what is essentially covered in this tutorial. The main difference is that we control the angle of movement directly, while Reynolds produce a steering force. This post only look at steering — we assume the forward speed is constant. All references to velocity or acceleration refers to angular velocity and angular acceleration.

Whenever I say “a random number”, I mean a uniformly distributed random floating point value between 0 and 1.

Continue reading “Random Steering – 7 Components for a Toolkit”