The Halton Sequence

The Halton sequence describes a deterministic sequence of numbers in (0,1) that is of low discrepancy, aka is quasi-random. As you can see from the example below, it has the desirable property of filling space more evenly than a typical pseudorandom number generator. Given this characteristic lack of clumping, the Halton sequence is very useful for initializing particle simulations, or populating crowds of entities in a world, as it cuts down on the number of initial intersections to resolve.

The sequence uses an arbitrary prime number for a base value, and repeatedly divides the interval by 1/(bi) to calculate the ith entry in a sequence using base b. When using the Halton sequence in a multidimensional space, such as ℝ2, we use a different base for each dimension.

See the wikipedia article for further details and some pseudocode.

Below is an interactive canvas for playing around with the sequence. Press the up and down arrows to move forward and backward in the sequence.

Powered by GameJS. Source code here.