Assume I’ve already placed these nodes (red dots) on a map. How would I go about making NPC move to the goal but by only following the closest node? I know how to have them get to the closest node (I just compare magnitude) but I just can’t make them move towards the goal without skipping all the rest of the nodes, or just stopping outright at a node that isn’t the goal.
Note:
-There won’t just be 1 defined path, there will be paths branching off the main path
Are the nodes fixed or dynamic?
If they are fixed, just precompute links between nodes within a certain distance threshold forming a mesh, and then you can use A* algorithm or so to find the path through the nodes that reaches the goal.
The nodes are fixed yea. Also do you mind going a little more into detail?
You make links between each set of nodes that is within a certain threshold, which I visualise below with black lines, and the NPC can move back and forth over these black lines:
Implement this in a data structure however it makes sense to you.
Then you use A* to find a path:
https://en.wikipedia.org/wiki/A*_search_algorithm
https://github.com/lattejed/a-star-lua
Then if you want them to traverse all nodes without skipping any, you modify the implementation of A* such that it rejects solutions that don’t traverse all of the nodes (i.e. if you have N nodes, reject paths that are shorter than N nodes).
what i do for my custom navigation is find the closets one towards the target. and then move to that node and repeat it
That’s what I’ve been tryna do
This has a lot of edge cases where your algorithm will break, for example that will never find a solution to the following situation:
Heres some code
this function searches the closets node to the position
walkpoint is the current node the character is at,
we run the function everytime the user is close to the next dot.
we stop when the nextdot is the desired dot
function FindNearest(Pos)
local Positions = {}
for i,v in pairs(PointToWalk:GetChildren()) do
table.insert(Positions,{v.Value,(v.Value.Position - Pos).magnitude})
end
table.sort(Positions,function(a,b)
if a and b then
return a[2] < b[2]
end
end)
return Positions[1][1]
end
The problem with always going to the closest point to the goal is that is a prioritized depth first search prone to finding local minimums, not the global minimum. The closest point to the goal may only be connected to points very far from the goal, or not be connected to the goal at all without backtracking. This is simply illustrated with the path found by that algorithm in this image:
A prioritized breadth first search would be to keep track of all the nodes you can walk to next and the distance the NPC would have to walk from the start position to get there. Then, continuously grab the next node with the minimum walking distance and add all nodes connected to it to the nodes we can walk to list, commonly called the ‘fringe’. This algorithm creates a minimum spanning tree from graphs with the root as the start position, and is called Dijkstra’s algorithm. It is used all over the place including in network routers. Instead of constructing the whole tree, you can just stop when the goal node is the next node to be expanded.
A* intelligently searches for the next node by using a heuristic (a function to determine cost and used to base decisions off of) which is based on both the walking distance to a node AND the node’s distance to the goal. A* knows that it is probably less productive to walk away from the goal, and only searches in that direction when it has reached a dead end or a path that seems to be getting nowhere.
Wikipedia (the best source to quote from) say that A*
Enter stage left hierarchical pathfinding. Also, some representations may be better than nodes. For example, navigation meshes composed of polygons result in better looking and shorter paths since there is more area the NPC can walk in. But those two algorithms are a bit more complex to implement and usually are not needed.
