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.

Haltonizer Screenshot

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.

Halton sequence along one axis

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.

Triforce from Halton

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!