Get node closest to given vector3.
I need to modify a GetNode method to return the closest node to the vector3 specified. At the moment, it returns the node at the given vector. For example, if I was to call GetNode(new Vector3(300,0,50)), and there is no node at that point, it will return the closest node, like (200,0,30). Can anyone tell me how to do this? The things I've tried haven't worked.
public Node GetNode(Vector3 pos)
{
//Searches for a node with a specific vector.
Vector3 roundedPos = new Vector3(Mathf.FloorToInt(pos.x), Mathf.FloorToInt(pos.y), Mathf.FloorToInt(pos.z));
for(int i = 0; i < gridLength; i++)
{
for(int j = 0; j < gridWidth; j++)
{
if(grid[i,j].pos == roundedPos)
return grid[i,j];
}
}
return new Node(pos, true, new Vector2(pos.x, pos.z));
}
Answer by Bunny83 · Apr 11, 2013 at 12:18 PM
Searching for the closest position / smallest value has been asked several times here. It'ss really not difficult:
public Node GetNode(Vector3 pos)
{
Vector3 roundedPos = new Vector3(Mathf.FloorToInt(pos.x), Mathf.FloorToInt(pos.y), Mathf.FloorToInt(pos.z));
float minDist = float.PositiveInfinity;
Node closestNode = null;
for(int i = 0; i < gridLength; i++)
{
for(int j = 0; j < gridWidth; j++)
{
float sqrDist = (grid[i,j].pos - roundedPos).sqrMagnitude;
if (sqrDist < minDist)
{
minDist = sqrDist;
closestNode = grid[i,j];
}
}
}
return closestNode;
}
So is there a way to do this without going through the entire grid of nodes? like a proximity range thing. Why i ask: this above code will be very bad for performance if it hasto do this together with a pathfinder for several characters. It would be better to know the Position of the character, and then check outwards in a circle from that position until the first one hits.. but is there a way to do this, without brute forcing it?
Well, the short answer is: it depends.
The longer answer is: it depends on several factors. The main factor is how are your nodes organised? In the case of this question the nodes seem to be placed on a grid. So you can check the nodes in growing rings around a given grid position. Once you found "nodes" in a ring you can stop since all nodes in outer rings will be further away than a node in a closer ring. $$anonymous$$eep in $$anonymous$$d that depending on the given grid position a "ring" might not be complete because you reach the end of your grid. So you need proper edge handling. A ring is essentially 4 lines along the edges of a rectangle that encloses the current ring. So each ring step you decrease the $$anonymous$$ coordinates by 1 and increase the max coordinate by 1. If a coordinate goes out of bounds you can ignore that line. So if $$anonymous$$X is smaller than 0 (assu$$anonymous$$g your grid starts at 0) you can ignore the left vertical edge. But also keep in $$anonymous$$d to clamp the start and ed positions according to your grid. So again if $$anonymous$$X is below 0 but $$anonymous$$Y is still in bounds you have to make sure you start your horizontal lines (top and bottom) at 0 and not at $$anonymous$$X. It's essentially a radial floodfill until it finds a node.
Another option is if your nodes are static (do not move) you can create a quadtree(2d) / octree(3d) to quickly query nodes within a certain area. Though it may also depend on what you consider "closest" and if a node is really just the abstraction (a single point without size) or some concrete thing (object, tile) with a certain dimension. In the second case you may want to consider the size of the object as well.
From the original question it's not clear what's the relation between the worldspace position of a node and the grid position. For the ring approach you of course need to be able to translate a worldspace position into a grid coordinate (which in this case most likely would be the integer part of "roundedPos").
If you have further questions, please ask a seperate question. We can't handle different question here. Q&A sites have one question on top and the answers will try to answer this question. Your case most likely looks a bit different. So when asking a seperate question, make sure you add all details necessary. You may include a link to this question for reference.
I actually found a solution that fit my project. In my case i have a character who needs to mark nodes as Occupied, while he stands on them, so the other characters go around him. So i simply check all nodes for each character and Ask if their Vector3.Distance <= characterSize. this can be put out into a Coroutine, (probably wont work with threads, cuss your playing with Transform.Position that requires main thread).... (unless you can store a regular Vector3 as the position on your nodes and avoid needing a $$anonymous$$onobehavior).