# The Halton sequence: distributing points and exploring the universe

Happy Dart 2.0 Launch! 🎆 I’ve been keeping busy lately with code for my Dart-based game engine, but I’ve had the idea for a fun little mathematical toy bouncing around in my head for a while now. I’m pleased to say that this weekend I finally had an opportunity to sit down and build it out. Although this simple app doesn’t do a whole lot to showcase any of the fancier features of the Dart language, it’s still pretty cool. Especially if you like nerdy things.

To try the app out for yourself, click here! Start out by turning the *Points Count* up to `500`

or so. Click *Plot Random Points*. Then clear the canvas and quickly click *Plot Halton Points*. You can clear the canvas and repeat this a few times. Try to pay attention to how the points are distributed. With the red, *random* points, your eye will probably be drawn to areas where the points have bunched together. With the blue, *Halton* points, the points will generally seem more evenly spaced out. Big deal, right?

## Yes, it is a big deal

Actually, the *even-but-still-randomish* distribution of those points turns out to be incredibly useful. Yet strangely enough, not that many people know about it. I haven’t run into it much, at least.

Let’s say that you’re trying to write a game, as my brother and I were when we stumbled upon the Wikipedia page for the Halton sequence. In the game, you want to generate a random world map. The map contains resources to help players succeed. At first you might try distributing the resources completely randomly (well, technically *pseudorandomly*) using a built-in function such as C’s `rand`

. That’s effectively what the red dots are in this example.

The trouble with the totally random approach is that sometimes it randomly yields uneven results. Often the resources will be bunched together. Occasionally they might all fall entirely on one side of the map. Such unevenness is pretty undesirable, as it can provide an unfair advantage to one player or another. Nobody likes that.

## Halton to the rescue

Fortunately, the Halton sequence allows us to position resources (or anything, really) in a way that *feels* random enough, yet still avoids unevenness. So how does it work? Well–this example actually uses *two* Halton sequences simultaneously–one to produce *x*-coordinates, and one to produce *y*-coordinates. The coordinates are in the range of `0.0`

to `1.0`

.

To see how the pattern works along a single axis, try setting the *index increment* for the *y*-axis to `0`

. Then plot a single Halton point at a time. You’ll notice a pattern starting to form.

Eventually you’ll end up with a line of points that is roughly evenly spaced. When you use this effect along both axes simultaneously, each new point’s location *appears* to be random-ish. Nifty.

## Let’s see the code

The code at the heart of this demonstration is surprisingly simple. Here’s the `output`

function from `halton.dart`

:

```
static double output(int sequenceBase, num index) {
var result = 0.0;
var fraction = 1.0;
while (index > 0.0) {
fraction /= sequenceBase;
result += fraction * (index % sequenceBase);
index /= sequenceBase;
}
return result;
}
```

If you look closely, you’ll notice that it closely matches the psuedocode implementation from that Wikipedia article. Each Halton generator has a *base* number. I’ve found that `2`

and `3`

work best as bases if the appearance of randomness is what you’re seeking. Every time you generate a new point, each generator’s `indexIncrement`

is added to its `index`

. By mixing and matching increments and bases, you can produce distributions that feel more random or less random. Less random may be less useful, but it’s still pretty interesting.

## It gets weird

If you play around with different combinations enough, you can uncover some downright startling results. Take this one for instance.

Is that a *Triforce*?! Or maybe they’re just chromosomes. Whatever they are, they’re the output of a simple mathematical sequence. They’re built into the universe. 😮

## Majestic

I hope you’ve had fun nerding out with me today. Definitely take some time and see what cool distributions you can come up with on your own. Please play around with the code and feel free to use it for your own purposes, be they good or evil. It’s all available on Github. Enjoy!

## Comments