0
\$\begingroup\$

I am working on a 2D game in Java. My goal is to place a ball as close as possible to the center without overlapping the balls that are already there. How can this be done?

\$\endgroup\$
2
  • 2
    \$\begingroup\$ What exactly do you need to accomplish, placing the ball or finding the position that is nearest to the center without overlapping the balls already in place? What have you tried? \$\endgroup\$
    – Alexander
    May 18, 2021 at 17:20
  • \$\begingroup\$ This can be done in many ways. Some ideas is to look up collision detection for balls/circles in 2D. One idea could maybe to store the positions of the other balls and then place then new ones on the edge of those. It all depends on what exact behaviour you want. \$\endgroup\$
    – Sandsten
    May 18, 2021 at 17:43

2 Answers 2

2
\$\begingroup\$

If you take each circle that's already been placed, and expand it by the radius of the one you want to place. Together, these circles form an "exclusion zone" - places where the center of your new circle cannot go without overlapping one of the circles already there. I've visualized the exclusion zone in pink created by the grey circles below. The big black dot is the center of the map we want to try to place our new circle close to.

enter image description here

If the target point we want to approach is inside this pink exclusion zone, then the closest our new circle's center can get is somewhere along the perimeter of the blob these exclusion circles form together. I've highlighted that perimeter in red. We'll check each arc on that perimeter to find our closest point.

To speed up out checks of what is or isn't in the exclusion zone, we can divide our map into a grid of buckets. Above, I've chosen the bucket size to be \$\sqrt 2 \cdot r_\text{min}\$ where \$r_\text{min}\$ is the smallest radius of any grey circle. This means that there can be at most one grey circle center in any bucket, and we only ever need to scan a fixed set of buckets around our test point to find all the exclusion circles that could exclude it - no matter how many circles there are in total.

If all your circles have the same radius, then that's a 5x5 box centered on the point to test. If you have 25 or fewer circles, then just brute forcing through the full list would be just as good.

Alright, with that out of the way, let's get into the meat of the algorithm:

  1. We check to see if the target point we want to approach is in our exclusion zone. If not, we're done - place your new circle at that point.

    If it is, then we'll add all circles overlapping it to what we'll call "the open set". These are the circles we've found, but haven't investigated in detail yet.

  2. While the open set is non-empty, take an exclusion circle out of it and add it to the "closed set". These are the circles we've checked thoroughly.

    We'll call this our "parent circle".

  3. Next we'll find the point along the parent circle's circumference that's closest to our target point, by projecting the line from the parent's center through the target out to the exclusion radius. (Note that this point might not be on the outer perimeter of the whole blob - we'll check that next)

Closest point on perimeter

toTarget = target - parentCircleCenter;
closest = parentCircleCenter + toTarget.Scale(parentExclusionRadius / toTarget.Magnitude());
  1. If this blue point is not the closest candidate we've found so far, we give up on this circle. No other point on its perimeter will be any closer. So we grab the next circle off the open set and repeat from 2. (Note that this can't happen for the first circle we check, since we have no better candidate so far)

  2. If the blue point is the closest we've found so far, we check whether it's inside any other circle on the exclusion zone.

    If not (like the example on the left), then we record it as our best candidate and continue to the next circle in the open set.

  3. If the blue point is inside another exclusion circle (like the example on the right), then we walk through each other exclusion circle it's a part of. We'll call these "child circles" to distinguish them from the parent we started with.

    We'll skip over any child circles that are already in the closed set, to ensure we don't end up going in a loop checking the same circles over and over.

  4. As we check each child circle overlapping this blue point, we add it to the open set if it wasn't in it already.

  5. We find the two points of intersection between the child circle and the parent circle - you can use the formulas here for that.

    Intersection points

  6. We check if either of these two intersection points is closer than our best candidate so far.

    If so, we check whether this intersection point is excluded by any circles other than the parent-child pair we just looked at. If so, we add that neighbouring circle as another child to check. If not, then we log the point as our best candidate.

    Once we've looked at both intersection points and either logged them as our best candidate or rejected them as worse / excluded, we continue to the next child circle in 6.

  7. Once we run out of child circles to check, we examine the next circle in the open set in 2 - giving us a new parent circle.

  8. Once we've emptied the open set, we're done. The best candidate point that we've found is the best possible.

Note that unlike a randomized approach, this route is guaranteed to find the closest point there is, and that it will do so in a bounded number of steps, linear in the number of circles we need to avoid (we do a bounded amount of work per circle added to the closed set, and we add each circle to the closed set only once).

Also, in the pathological case where there is no available place to put a new circle, this approach will determine that in its normal runtime instead of running forever. 😉

\$\endgroup\$
2
  • \$\begingroup\$ yep that seems guaranteed, not randomized.. just tad a bit more complicated :) \$\endgroup\$
    – ShoulO
    May 18, 2021 at 23:31
  • \$\begingroup\$ but I give my upvote :) \$\endgroup\$
    – ShoulO
    May 18, 2021 at 23:57
0
\$\begingroup\$

While making games I face similar problems quite often. What I found is that often best (quickest,easiest) way is.. not to look for that perfect answer, instead use computer to work it out for me.

This dead simple solution will work:

So there is infinite number of points. Lets find that one.

a) write function which checks if given point is valid. It should check distance to each balls center and if there is enough space for your ball, return true.

b) write a while loop where different points are checked until valid is found. In this loop first supply the center point, then Random point close to it, then another.. until fitting point is found.

That's it. Lazy dumb solution but it will work, and yes it might take few hundred cycles to find it, but in user time it will be just a moment. Also add some protection from forever-loop.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Let's say we're 500 loops in and we haven't yet found a suitable point. What protection would you recommend so we can avoid looping another 500 times while still returning a decent location if there is one? \$\endgroup\$
    – DMGregory
    May 18, 2021 at 19:01
  • \$\begingroup\$ if there is such point eventualy computer will find it. Why not let it run another 500 cycles? What would be necesarry though - is to make sure such point exists in the first place before running. (by for example adding much less balls than space, etc) \$\endgroup\$
    – ShoulO
    May 18, 2021 at 19:06
  • \$\begingroup\$ So then what is your recommended way to "add some protection from forever-loop"? \$\endgroup\$
    – DMGregory
    May 18, 2021 at 19:34
  • 1
    \$\begingroup\$ ok, In fact no protection is strictly necessary (just don't make silly mistake causing forever loop). I answered OP's question: how to find such point. If such point exists my algorithm will find it. OP didn't ask (at least not yet) how to make sure such point exist. Maybe it is a given, that such point exist, - question was how to find it. \$\endgroup\$
    – ShoulO
    May 18, 2021 at 20:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .