Code Trip
  • Blog
  • Archive
  • Projects
  • Portfolio
  • CV

Generating random points in a ring

6/12/2016

0 Comments

 
Recently I was working on a game where enemies were spawned somewhere in a ring around the player. The inner radius was set so that they always spawned offscreen and the outer radius was set so that enemies were never too far away. After we zoomed the camera out we had to increase these radii and suddenly the game was noticably hitching whenever it tried to spawn enemies. The culprit was a bit of code that looked something like this:
do
{
    spawnPos = RandomPointInCircle(outerRadius);
}
while (PointIsInCircle(spawnPos, innerRadius));
I wrote this bit of code and I'm glad I was the one to fix it as it reminded me of two interesting lessons I learnt with a good friend of mine while at university, one of which I then evidently forgot. She wrote an excellent in-depth article about our little discoveries. Back then we weren't dealing with such exotic geometry as a ring, merely a circle. The obvious way to do this is to pick a random length between 0 and the radius then a random angle, like so:
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));
}
​The first interesting thing we found was that the obvious way to pick a random point in a circle does not give an even distribution. The problem with this approach is that points are just as likely to be near the centre as near the edge, but in a circle half of the area is in the outer third. See Rachel's article for more detail, including illustrations of the distribution this approach gives you.

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;
}
This approach is known as rejection sampling and the second interesting thing we found was that rejection sampling is a terrible idea if you want consistently performant code. The problem with this approach is that you have no idea how many attempts it will take to find a point in the circle - it might take 1 or 1,000,000. This is the lesson I forgot. (For the right way to generate points in a circle see Rachel's article.)

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));
}
0 Comments

    Author

    Connor Halford. Studied Computer Games Technology at Abertay, worked as a Games Programmer at MediaTonic, now working as a Programmer at Climax Studios.
    ​

    Useful Sites

    hilite.me converts source code into formatted, embeddable HTML without the need for CSS or Javascript.

    tablesgenerator.com performs a similar task as hilite.me but for tabular data.

    Archives
    All posts

    June 2017
    December 2016
    September 2016
    August 2016
    June 2016
    May 2016
    April 2016
    February 2016
    January 2016
    October 2015
    September 2015
    August 2015
    June 2015
    May 2015
    March 2015
    February 2015
    January 2015
    December 2014
    September 2014
    August 2014
    July 2014
    March 2014
    February 2014
    August 2013
    June 2013
    December 2012

    Categories

    All
    Advice
    AI
    Algorithms
    AMPS
    Audio
    Boost
    Box2D
    Coursework
    DirectX
    Flash
    Game Boy Advance
    Game Jam
    Graphics Programming
    Honours Project
    Maths
    Nonograms
    Oh God Why
    OpenGL
    PICO-8
    Pixel Art
    PlayStation 4
    PlayStation Vita
    Procedural Generation
    SFML
    Shaders
    Spirit Shift
    Twine
    Unity
    XAudio2
    Year 1
    Year 2
    Year 3
    Year 4

    RSS Feed

Powered by Create your own unique website with customizable templates.