I'm trying to write a closest neighbor algorithm, but I'm not sure why it is not working, the cubes are being spawned by an object pool system, and it should take in consideration the other cubes around it that has the same script attached, this is my current script:
public class FindNearestNeighbour : Closest, IPooledObject
{
public static List<FindNearestNeighbour> findNearestNeighbours = new List<FindNearestNeighbour>();
private void Start()
{
findNearestNeighbours.Add(this);
}
void FindClosestObject(Vector3 from, List<FindNearestNeighbour> transforms)
{
if (transforms.Count > 1)
{
Vector3 location = Vector3.zero;
float Closest = Mathf.Infinity;
for (int i = 0; i < transforms.Count; i )
{
Vector3 loc = transforms[i].transform.position;
if (from != loc)
{
float distance = Mathf.Abs(loc.sqrMagnitude - from.sqrMagnitude);
if (distance < Closest)
{
Closest = distance;
location = loc;
Debug.DrawLine(from, location, Color.red);
}
}
}
}
}
public void OnObjectSpawn()
{
FindClosestObject(transform.position, findNearestNeighbours);
}
}
CodePudding user response:
I think the first of your main issues is that you keep calling
Debug.DrawLine(from, location, Color.red);
while you are still in the loop and still have possibly closer neighbors yet to find.
You want only one single call after the entire loop is finished!
And then the second you do
float distance = Mathf.Abs(loc.sqrMagnitude - from.sqrMagnitude);
this makes no sense! This calculates the difference both positions have in their individual distance from Vector3.zero
(world origin), not the difference between these two!
What you would want is rather
float distance = (loc - from).sqrMagnitude;
as already mentioned by rustyBucketBay
Using Linq
you can do this in one line:
using System.Linq;
...
// First filter out null items and yourself!
FindNearestNeighbour closest = findNearestNeighbours.Where(n => n && n != this)
// Then order by the distance where sqrMagnitude is significantly more
// efficient than using Vector3.Distance or magnitude
.OrderBy(n => (n.transform.position - transform.position).sqrMagnitude)
// finally return the first (closest) or null if there wasn't any
.FirstOrDefault();
Why is this so powerful?
Because you can easily adjust this and do e.g.
// First filter out null items and yourself!
FindNearestNeighbour[] closest = findNearestNeighbours.Where(n => n && n != this)
// Then order by the distance where sqrMagnitude is significantly more
// efficient than using Vector3.Distance or magnitude
.OrderBy(n => (n.transform.position - transform.position).sqrMagnitude)
// finally return up to the first ten (closest) items
.Take(10).ToArray();
to find the closest X items without having to go super complicated with your loop.
See
CodePudding user response:
You are substracting the squares of the positions in:
float distance = Mathf.Abs(loc.sqrMagnitude - from.sqrMagnitude);
I think you should better do:
float distance = (loc - from).sqrMagnitude;
Which is the square magnitude of the distance.