# Closest node in A* pathfinding

For my 2D Unity game, I've implemented A* pathfinding based on waypoints. System already handles building graph from waypoints on scene (which are manually placed objects), as well as finding and caching closest routes.

So, general idea is to select closest waypoint to character, closest waypoint to target position, and use pathfinding algorithm to find closest route (which is pre-cached already).

Yet, I've stumbled into issue - I don't know how to actually get closest waypoint. Well, there are several ways I think of, in the worst case I can just brute-force closest non-blocked waypoint from the collection, but that would be bad performance-wise.

So, are there any proper ways to get start or end points?

• So the target isn't one of the waypoints? Jan 22, 2019 at 1:20
• No. Target, as well as initial position, can move, and this leads to several reasons why I can't make them waypoints. Jan 22, 2019 at 1:28
• So the A* never calculates a path from the character to the target? The best it can do is calculate a path from the character to the waypoint that is closest to the target? Jan 22, 2019 at 1:56
• So far, yes. As target and character may move, game would still need to constantly determine, which waypoints are connected to target and character, and which are not, not to mention calculating path on fly instead of using cached one. Jan 22, 2019 at 2:54
• This will be tricky if you have cul de sacs in your map, the physically closest waypoint may create a longer and odd looking path if that waypoint is in a bad spot relative to your true destination. Jan 22, 2019 at 20:14

If the movement is limited per frame you only need to look at the neighbours of the previous character and target waypoints to find the new ones. So you only need the expensive search when you have teleports or on spawn. And with fixed teleport targets and spawn points you can cache those as well.

The standard computer science answer for finding closest node is to build a voronoi diagram with the nodes and get closest nodes from that.

However any spatial partitioning will give you the speedup you need.

• I strongly agree with the last part, together with spatial partitioning it's very cheap to "brute force"-find the nearest waypoint. You're probably looking at less than ~20 distance-comparisons to find the closest waypoint if you hand-place waypoints anyway. Feb 21, 2019 at 13:45