While working on the Make It Random library for Unity, I took up an engineering challenge: generation of random floating point numbers between zero and one quickly and with perfect uniform distribution. The most common method, dividing a random integer by the full range of possible integers, has a few substantial flaws that I hoped to avoid:

• First, it involves a division operation, which could naturally slow things down a bit.
• Secondly, although the distribution on a high level is uniform, it’s more clumpy for higher numbers closer to one, and more diffusely spread for lower numbers closer to zero, so the uniformity is imperfect.
• Third, the quantity of possible integers generated rarely maps cleanly to the possible number of floating point values available, and so different floating point values are likely to have at least slightly different probabilities of occurring, further weakening the uniformity.
• And fourth, even when the mapping from integers to floating point values is carefully managed, if the range of values needed is not a power of two, this adds further problems to any attempt to get perfect uniformity without sacrificing performance, due to how typical random engines generate data as chunks of bits.

With the help of various sources around the internet plus some clever use of probability mathematics, I was able to conquer all of these difficulties, providing perfectly uniform and fast generation of floating point numbers in the unit range. This includes all four variants of whether the lower and upper bounds are inclusive or exclusive. The techniques involved are explained below.

The first two are not at all new, but are included because I have not seen them discussed as often as I think they deserve, and because they help build the context for the third technique. This last technique is something I devised on my own, and although I have no doubt other smart people have already discovered it or something similar, I never ran across it while researching, so I’m eager to share it with others in this post. Plus, I suspect that the general technique can be usefully applied to other random value generation beyond just floating point numbers, so the more people are aware of it, the better. (more…)

While working on Worldbuilder v0.2, I spent a fair amount of time implementing an algorithm for generating distance fields on the surface of a sphere. It was admittedly a struggle, with many false starts, but I finally stumbled upon a solution that works well, producing a distance field with a high degree of accuracy, and executing very quickly with the help of the GPU.

Most of the literature I could find on the topic was focused either on generating distance fields for flat 2D images, or for full 3D space. In both cases, space was always Euclidean, whereas distance on the surface of a sphere behaves quite differently. Additionally, most algorithms I ran across were focused on calculating distances from a collection of points, but for reasons I’ll discuss below, I needed to calculate accurate distances from polygon outlines. Some of the 3D algorithms were tantalizingly close to what I wanted, since they often started with a triangle mesh as their input, but the 3D aspect greatly increased the complexity of the algorithms relative to my needs, while still not addressing my non-Euclidean needs.

In the end, the algorithm that I finally implemented is honestly nothing very impressive, and I kind of figured it out by accident. But it works, and it works well, despite being something of an ugly hack. As it might help others needing to do something similar, allow me to share the details of this algorithm, along with the journey getting there. Though admittedly, the journey does get a bit verbose at times, so feel free to jump straight to the final algorithm. I tried to keep that section relatively self-contained. Just know that you’re skipping over loads of pretty pictures. (more…)

Okay, after a few nights of good sleep and days not thinking about coding, it’s time for a reflection on my efforts during this past weekend’s Ludum Dare. (For reference, my entry can be viewed here and played here).

As was evident in my earlier posts, I didn’t really have a clear idea of where I was going, design-wise. Even on the last day, I wasn’t quite sure where I would end up, though it was of course much clearer how little time I had left to add any additional mechanics. But I didn’t let that lack of direction prevent me from continuing onward anyway, so that was a success of sorts. All too often, if I don’t know where I’m going, I fail to go anywhere at all. (more…)