Find a position within one radius, but outside other radii

Question

I have an Object A which will attempt to stay within a certain distance of another Object B. I would like Object A to also try to stay outside a certain distance of one or more other Objects R.

The idea behind this question is the desire for a companion AI to follow the player around and provide support, but also try to stay out of the attack range of enemies.

Using the image above as an example, we'll say the distance/radius within which we want to stay to Object B is represented by the blue circle. The distances/radii we want to stay outside of for Objects R are represented by the red circles.

How can I find any point (perhaps the closest point? or the point least crowded by red circles?) in the blue circle that is not overlapped by a red circle?

Furthermore, approximately how expensive would it be to calculate these kinds of details?

And how would the answer(s) to the questions above be affected if we used spheres instead of circles (3D instead of 2D)?

I use Unity and C#, so please keep that in mind if you provide specific code examples. Thank you.

Answer 1

This is an interesting problem. I can think of two mechanical (brute-force-ish) approximate approaches. My math-fu is not strong enough to opine if an analytic solution is practical here. I hope there is such an approach! But here’s my “just get it done” suggestions.

By Gridded Area, approximate

We only care about the blue area. Represent that to the desired resolution, as a 2 dimensional array of “blue” or “not blue”, and start it with your circle. Then knock out red circles one by one. Any blue left is not in red (within the grid resolution).

Improvement 1. skip red circles that don’t intersect, dist(center1,center2) > (radius1 + radius2).

Improvement 2. instead of just Blue or Not-Blue, store a “distance from red center”, and when knocking red areas out, also fill in the whole blue area with the minimum distance to any of the red centers. Now the highest remaining blue cell is the “least crowded”.

Improvement 3. Keep the blue cells in a linked list, and knock out ones that are in red. For each new red circle, just walk the still-living blue cells.

Could work in 3d, but the resolution is even more expensive. The spheres would be sets of cubes, minecraft-style.

By Polygon, approximate

Represent your circles by N-gons, with whatever number of sides is “good enough”. Use boolean operations to carve away the blue area. Remaining blue polygon is blue, but it might have no sides left, meaning no safe blue area left. http://en.wikipedia.org/wiki/Boolean_operations_on_polygons has some notes on this, and links to boolean-operation libraries.

Could work in 3d, but, those boolean ops are even more expensive.

By Spring Forces

If the red circles/spheres are not necessarily absolutely solid, or if they represent zones of danger, another approach would be to apply forces of various kinds. If your companion object A tries always to move towards B, but is forced away by R, it will tend to find a way to get to B. This will work best if everything is moving, since "unsolvable" positions may get another chance. Something nonlinear pushing away from the the R circles, from gentle nudges far away, to "impenetrable" when A is at their actual physical boundary, would be appropriate.

To conclude…

If this is for game collisions, the grid or polygons may be good enough, especially for a low resolution or low polygon sides. (If this were an abstract math question… my answers would be unsatisfying.)

For a game AI, though, perhaps some variation on the "spring forces" might serve better, giving the object some lively and persistent motions. The simplest force would have your "companion" object A just follow a greedy path, and aim straight for B until it hits any of R, and then stop or slide around the Rs.

Answer 2

Try to get the sphere equations with respect to world space for each sphere like a sphere with radius r and centre (a,b,c) in WorldSpace Coordinates will be represented by the equation (x - a)^2 + (y - b)^2 + (z - c)^2 = r^2 then find the common portions and subtract the equations to get the blue part and any solution of the remaining equation will be a point. But you better write it down on paper and work out the math first instead of trying to write the program itself. Regarding the performance part, it really depends on how well you are able to solve the equations. Good Luck.