How to divde a group of objects into pairs by proximity?

Hey everyone, so I have a scene with a group of objects, with a maximum of around 20. What I would like to do is halve this group when a player gets a powerup, by having each object find its closest partner and then have each object in the pair lerp towards the center point between them and then just destroy one of the pair once they reach the center. I am at a loss of how to pair up the objects.

What I was thinking about doing was using Physics.OverlapSphere that covers the entire screen so each object could find its own closest partner, but this would only work for two objects. With four objects for instance, sphere 1 may be closest to sphere 2, but sphere 2 may be closest to sphere 3 and sphere 4 may be closest to sphere 3 as well (and so on and so forth for more objects).

I’m wondering if anyone has some thoughts on how to go about trying to pair up objects based on proximity and how to resolve the problem of when a single sphere is the closest partner of more than one other sphere? Or possibly an easier/different way about approaching the problem. My guess is some sort of array manipulation might be the answer, but like I said, I seem to be at a loss on how to go about filtering out multiple pairings of an object.

The answer to this question is actually quite complex for such a simple idea: To find if an object is properly paired, you should collect references to all the objects you’re doing this with in an array (or a list), first. The next step is crucial, as it will give us some idea of how things are shaped: You will need to find the pair within the entire list with the greatest distance between them. These will be your “endpoints.”

Let’s call these objStart and objEnd. The benefit to this setup is that we now know where we should be starting (either one is fine). Simply find the closest object to each end, pair those up, then remove them from the list, and repeat this process until all the objects have been paired up. For example:

public static void PairObjects(List<GameObject> objects, List<GameObject> buffer)
{
    int startIndex;// Index in objects for the starting point
    int endIndex;// Index in objects for the ending point
    Vector3 start = null;// Starting object position
    Vector3 end = null;// Ending object position
    float maxDist = 0.0f;// Maximum distance between pairs of objects 
                         // being compared, so far

    // Search through and find the two game objects with the 
    // highest distance between them.
    for(int i = 0; i < objects.Count-1; i++)
    {
        start = objects*.transform.position;// starting position of the current*

// pair being compared
end = objects[i+1].transform.position;// ending position of the current
// pair being compared
// Compare all the rest of the objects
for(int j = i+2; j < objects.Count-2; j++)
{
Vector3 pos = objects[j].transform.position;// next comparison
float dist = Vector3.Distance(start, pos);// distance between the two
if(Vector3.Distance(start, pos) > maxDist)
{
startIndex = i;
endIndex = j;
}
}
}
GameObject startObj = objects[startIndex];
if(startIndex != 0)
{
GameObject temp = objects[0];
objects[0] = startObj;
objects[startIndex] = temp;
}
GameObject endObj = objects[endIndex];
if(endIndex != objects.Count-1)
{
GameObject temp = objects[objects.Count-1];
objects[objects.Count-1] = endObj;
objects[endIndex] = temp;
}
float minDist = maxDist;
GameObject ldStart = endObj;
start = startObj.transform.position;
for(int i = 1; i < objects.Count; i++)
{
Vector3 pos = objects*.transform.position;*
float dist = Vector3.Distance(start, pos);
if(dist < minDist)
{
ldStart = objects*;*
minDist = dist;
}
}
minDist = maxDist;
GameObject ldEnd = startObj;
end = endObj.transform.position;
for(int i = 0; i < objects.Count-1; i++)
{
Vector3 pos = objects*.transform.position;*
float dist = Vector3.Distance(end, pos);
if(dist < minDist)
{
ldEnd = objects*;*
minDist = dist;
}
}
buffer.Add(startObj);
objects.Remove(startObj);
if(ldStart != endObj)
{
buffer.Add(ldStart);
objects.Remove(ldStart);
}
buffer.Add(endObj);
objects.Remove(endObj);
if(ldEnd != startObj)
{
buffer.Add(ldEnd);
objects.Remove(ldEnd);
}
}
There’s two ways you could potentially use this method. The first way (which, depending on the number of objects you’re planning on having in your list here, you may or may not want to use) would be to make this method tail-recursive (add an if statement to the beginning that tells it to simply return if objects is empty, and add a call to the method, itself, at the end of the method).
The other, and honestly more suggested method I have for you would be to call this method once every update call, in a monobehaviour. This way you can split up the calls to multiple frames, rather than doing it all on one frame (which might just give a cool little effect to your method, as well).
[EDIT] you’ll have to forgive any bugs I left in here, it’s quite a bit of code, and I wasn’t at my computer (nor do I have time now to actually test it) but if there are bugs, they should be fairly minor.