How to find a biggest gap between objects?

Questions & Answers
1

Hey guys. So I have a player and objects around him with random x-z position. The goal is to find the best way in between those objects (yellow line). The best way means to go trough the middle point between two farthest towers (green line).

The question is - how do I script this? How can I find this gap between farthest objects (green line)?

I already tried two approaches:

  1. I found all possible pairs of objects and distance between them, I picked the biggest distance, but it is not giving me the gap I need.
  2. I tried to found closest object for each object in the scene, then picked the biggest distance, but it was not working for the player perspective.

Any ideas how can I crack it out please?

Again - I need to find a green line (biggest gap between two objects) from player perspective.

194470-capture.png
194470-capture.png665×666 13.2 KB

2

The path you are trying to find is neither the closest distance between towers beginning with the closest tower or the farthest distance. Maybe you want some point along the current path. Without counting for the current path/direction it is not possible to find the line you want, because it could just as well be straight down in your example.

Here is a method that might help you, but i’m not sure.

static public float PointDistanceToLineSeg(Vector2 p, Vector2 l0, Vector2 l1/*, out Vector2 o_vClosest*/)
{
    Vector2 l0_l1;
    float dist;
    l0_l1 = l1 - l0;
    float l2 = (l0_l1.x * l0_l1.x + l0_l1.y * l0_l1.y); // i.e. |l0-l1|^2 -  avoid a sqrt
    if (l2 < 0.01)
    {
        //just take l0, the line is too short
        dist = PointDistance(l0, p);
        //if (o_vClosest!=null) o_vClosest = l0;
    }
    else
    {
        //consider the line extending the segment, parameterized as l0 + t (l1 - l0).
        //we find projection of point p onto the line. 
        //it falls where t = [(p-l0) . (l1-l0)] / |l1-l0|^2
        float t = Vector2.Dot(p - l0, l0_l1) / l2;
        if (t < 0.0)
        {
            //beyond the 'l0' end of the segment
            dist = PointDistance(l0, p);
            //if (o_vClosest!=null) o_vClosest = l0;
        }
        else if (t > 1.0f)
        {
            //beyond the 'l1' end of the segment
            dist = PointDistance(l1, p);
            //if (o_vClosest!=null) o_vClosest = l1;
        }
        else
        {
            //projection falls on the segment
            Vector2 projection = l0 + (l0_l1 * t);
            dist = PointDistance(p, projection);
            //if (o_vClosest!=null) o_vClosest = projection;
        }
    }
    return dist;
}