2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ So the target isn't one of the waypoints? \$\endgroup\$ – Sean Carey Jan 22 at 1:20
  • \$\begingroup\$ No. Target, as well as initial position, can move, and this leads to several reasons why I can't make them waypoints. \$\endgroup\$ – lentinant Jan 22 at 1:28
  • \$\begingroup\$ 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? \$\endgroup\$ – Sean Carey Jan 22 at 1:56
  • \$\begingroup\$ 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. \$\endgroup\$ – lentinant Jan 22 at 2:54
  • \$\begingroup\$ 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. \$\endgroup\$ – Patrick Hughes Jan 22 at 20:14
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – VaTTeRGeR Feb 21 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.