do { spawnPos = RandomPointInCircle(outerRadius); } while (PointIsInCircle(spawnPos, innerRadius));
Vector2 RandomPointInCircle(float radius) { float r = RandomRange(0.0f, radius); float theta = RandomRange(0.0f, 2.0f * PI); return new Vector2(r * cos(theta), r * sin(theta)); }
Having encountered this problem the next simplest approach is to keep generating points in the square encompassing the circle until you find one that is also in the circle:
Vector2 RandomPointInCircle(float radius) { Vector2 point = new Vector2(0.0f, 0.0f); do { point.x = RandomRange(-radius, radius); point.y = RandomRange(-radius, radius); } while (!PointIsInCircle(point, radius)); return point; }
My initial idea for generating points in a ring was the obvious one: keep generating points in the outer circle until you find one that isn't in the inner circle. This is a rejection sampling approach and in fact it's quite an egregious one. Consider the ratio between the area of the inner circle and the area of the outer circle. If the inner circle is comparatively small then it becomes fairly likely that you will find a point outside of it in good time. But if the inner circle takes up a large proportion of the outer circle, i.e. if the ring is thin, it becomes more and more likely that a random point will be rejected.
This explains why increasing the size of our enemy spawn ring caused noticable performance hitches; both radii were increased by the same amount, meaning that as a ratio the inner circle now occupied a much larger proportion of the outer circle. That little do-while loop was regularly taking upwards of 600,000 attempts to find a point that was inside the outer circle but outside the inner one. Worse than that is that it was variable: sometimes it would only take a few thousand attempts (only), one particularly unlucky time it took over 11,000,000 attempts.
The solution for even distribution of points in a circle was to pick a random angle then a random weighted radius which takes into account the mathematics of circles. The solution for generating points in a ring follows a similar approach, as detailed here.
Vector2 RandomPointInRing(float minRadius, float maxRadius) { // Avoids rejection sampling! http://stackoverflow.com/a/9048443 float theta = RandomRange(0.0f, 2.0f * PI); float w = RandomRange(0.0f, 1.0f); float r = sqrt( (1.0f - w) * minRadius * minRadius + w * maxRadius * maxRadius ); return new Vector2(r * cos(theta), r * sin(theta)); }