Recently I've been thinking way too much about this stuff, so here's a full blog post about it. The aim of this post is to provide a resource other programmers can refer to whenever they have to tackle this problem. There's lots of use-cases for algorithms which generate points or vectors within the limits of a circle - a particle emitter might distribute particles over a circular area; a weapon or special ability might create explosions throughout a target zone; a shotgun's shots spread out in a cone; and so on. So how do you write a speedy, simple, understandable vector-generating function?
Depending on circumstances, you might have different requirements and want to optimise for different things:
Depending on circumstances, you might have different requirements and want to optimise for different things:
- You probably want your points to be uniformly (evenly) distributed across the circle. To verify if an algorithm is outputting uniformly-distributed points, we check the average (mean) distance from the centre of the circle to each point. It should be about (2/3 * radius). This is because half the area of a circle is in its outer third, so when the average distance is (2/3 * radius) you know half the points are in the outer third.
- You may want to minimise calls to the random number generator. Why? Because RNGs can be a bit crap. Certainly the C++ standard library's rand() function is. It might be bad for lots of different reasons. It might have a short period, meaning that it begins to repeat itself after a few thousand calls, which might be a big deal to you. Or it might not be very fast, which is unlikely to be impactful, but this stuff can get pretty weird.
- You might want to avoid using the square-root function. There's a discussion on stackoverflow regarding the speed of sqrt, in which someone says that it is "about 4 times slower than addition using -O2, or about 13 times slower without using -O2." Not huge in the fully-optimised case, but still big enough to add up, and you might be working on hardware where the implementation of sqrt is bad.
- You might want to avoid using many calls to trigonometry functions, because these might be bottlenecks in your code. Sure, you can write sin and cos functions that use a lookup table to speed things along, but maybe you don't want to have to stoop to doing all that work in what should be the age of fast processors. Again, as with rand(), these standard-library should-just-god-damn-work utilities aren't perfect.
- You want to avoid branching in performance-critical code. You can factor comparisons out using smart maths, sometimes, but that involves adding in extra code.