Problem: they keep taking the long way

I’ve been having a problem with the pathfinding system, and I think I understand the cause of it, but I’m not quite sure how to solve it. Hoping this may have been dealt with before and my searches just missed it.

Anyways, as for the problem, here’s a screenshot that illustrates what’s going on:

The little space guy (highlighted in blue) has selected a piece of hull (orange stripes) to move to, and because line of sight to it is blocked, the pathfinding system is used. However, instead of taking a short trip around the outside of the hull, a fairly long route is chosen.

My best guess as to the problem is, when computing a path to a point not on the grid (which the hull piece is not), the pathfinding system chooses the closest grid node to that point and computes a path to that point. Even if the hull’s position was closer to the outside grid nodes, then, I would just have a reverse of the problem when the shortest path is to stay inside the ship.

Even if I’m correct in my understanding of what’s going on here, that still leaves me at a loss for the solution within the constraints of the A* Pathfinding Project system. If I were to code up a solution myself, I might go with something like selecting all nodes within a particular radius as goal nodes, or selecting the first N closest, though both of those would end up being heuristics that need to be tweaked for the particular environment.

Any thoughts?


Well, I can’t really use a heuristic like that, then people would start to complain about it not calculating the path to the node that was actually closest.

So as a first solution, is there something you can do to hint it towards one side of the other? That would be easiest.

Otherwise you can use a MultiTargetPath. Find a few of the closest walkable nodes (AstarPath.GetNearest (somePosition, NNConstraint.Default)), e.g by checking 6 points around your original point with small offsets. Then start a MultiTargetPath with the pathsForAll field set to false. Then you can use it in the same way as a normal path request.
If you are using one of the included movement scripts, find the part of the code where it requests the path and change it to request a MultiTargetPath instead.

Cool, it looks like I can work with MultiTargetPath to do what I want, I think I’ll try to re-write my game entities to have a list of one or more move targets, and then just set one on either side of the hull components.

Before I get to implementing, though, I have a couple questions:

  1. The documentation for pathsForAll states that “If true, a path to all targets will be returned, otherwise just the one to the closest one.”; by closest one, do you mean that it will only calculate a path to the targetPoint closest to the specified startPoint? If so, I think I’d want to set this true, then iterate over the returned paths to find the shortest one.

  2. If pathsForAll is set true, am I guaranteed that the vectorPaths indices match the targetPoints indices? eg: vectorPaths[0] contains a path to targetPoints[0], vectorPaths[1] a path to targetPoints[1], etc. I know this might seem obvious, but I just like to check my assumptions before my code relies on them.

Many thanks for your help! I’m quite impressed with your pathfinding system so far, it’s saved me a lot of time!

  1. Bad wording, it will return the shortest path which leads to any of the supplied targets (so you want it to be true).

  2. Yes, that is guaranteed (at least I think so… I haven’t worked with that code in some time but I can’t see a reason why I wouldn’t have implemented it that way)

Alright, many thanks for the answers to my questions, I think I can get this working now.

Just wanted to post a quick follow-up, in case any one else runs into a problem like this. I ended up storing a Vector3[] AltMovePoints in the game entities, and when pathfinding if this is non-empty call Seeker.StartMultiTargetPath() with pathsForAll = false and the same OnPathDelegate as I normally use with Seeker.StartPath(), otherwise if AltMovePoints is empty I just do normal pathfinding with Seeker.StartPath().

Under (pretty much) the same situation as my first image showed, the space guy now takes the shortest path. Huzzah!

The green squares in this image represent the AltMovePoints, and the yellow circle is the normal move target.

Thanks again for your help Aron!