Getting back old/incorrect paths when using MultiTargetPath

General
1

I’m using MultiTargetPath, and sometimes one of the endpoints I specify is close to the start position. Often (though not always) in this case the path I actually get back is an old path from somewhere else with the same destination, so the starting node is very far away from the start point.

Here’s the console message A* prints:
Path Completed : Computation Time 0.13 ms Searched Nodes 0
Last Found Path Length 0
Path Number 4

But here’s what I get when I print the DebugString() for the path object:
Path Completed : Computation Time 0.13 ms Searched Nodes 0
Last Found Path Length 5
Path Number 4

I’m using A* 3.7, have a point graph, and have pathsForAll = false. I think I can work around this by checking myself to see if I’m close to the destination, but this complicates things. I’m also not 100% sure that it never occurs when the start points is not near the destination, that’s just the easiest case to see.

2

Hi

Possibly affected by: MultiTargetPath overwrites input array with strange results?

4

Hi

I see you deleted your post, did you find some new info?

5

I had a theory but on more testing it didn’t pan out. FWIW: My problem is different from the one you posted - I checked and when this occurs, the input endPoints array is unchanged, nor is A* logging errors about failing to find a path.

There are maybe two problems here. One is that, sometimes (not not always), MultiTargetPath.path and MultiTargetPath.nodePaths[chosenTarget] are not the same, but I would expect them to be the same.

The other, more serious, is that often the returned path is bogus, which I’m assuming is related to the start position and target being at the same node. I’m digging in the MultiTargetPath code right now to try to be more specific about what is going on.

6

I added some debugging to the top of MultiTargetPath.Initialize:

for (int j=0;j < targetNodes.Length;j++) {
    if (startNode == targetNodes[j]) {
        PathNode r = pathHandler.GetPathNode(startNode);

        int count = 0;
        PathNode c = r;
        while (c != null) {
            c = c.parent;
            count++;
        }
        Debug.Log("Found count " + count);

        FoundTarget (r, j);
    } else if (targetNodes[j] != null) {
        pathHandler.GetPathNode (targetNodes[j]).flag1 = true;
    }
}

Here I’d expect the count to never be above one (right?), since the start node is the same as the target node, but instead I’m seeing that the count is often high. Importantly, it always has the length of an earlier path, so I’m assuming that pathHandler.GetPathNode(startNode) returning a PathNode with some leftover data. I haven’t dug deeper than that.

7

Ah. You definitely found a bug there.
You can see that a few lines below I reset the start node

PathNode startRNode = pathHandler.GetPathNode(startNode);
startRNode.node = startNode;
startRNode.pathID = pathID;
startRNode.parent = null; // <----
startRNode.cost = 0;
startRNode.G = GetTraversalCost (startNode);
startRNode.H = CalculateHScore (startNode);

But since that call to FoundTarget was done before the start node had been initialized it would return an older path.

I think the solution will be to move the part which initializes the start node to the top of the Initialize method.

8

I am not sure why path.path != path.nodePaths[choosenPath] however since the code for that is just

if (anySucceded) {
	CompleteState = PathCompleteState.Complete;

	if (!pathsForAll) {

		path = nodePaths[chosenTarget];
		vectorPath = vectorPaths[chosenTarget];

		//....
	}
} else {
	CompleteState = PathCompleteState.Error;
}

if (callback != null) {
	callback (this);
}
9

I moved the startRNode initialization to the top of Initialize(), then used that instead of calling GetPathNode() inside the for loop. That seems to have solved the bad path problem. Thanks!

I think I see the issue w/ path being incorrect also. I’m using coroutines so my agents are busywaiting on IsDone(), and using the path once that returns true, rather than using a callback. But sometimes IsDone() is returning true BEFORE ReturnPath is actually called. I don’t know why. But I can work around it I guess by waiting for the callback instead.

10

Ok.

Yeah, IsDone is for when the path has been completed, but it might not have been returned yet. You can use this if you want to make sure it has also been returned.

var path = StartPath (...);
yield return StartCoroutine(path.WaitForPath());
// Done!
11

That’s much better. Thanks!

12

Cool.
I will add some more unit tests for the MultiTargetPath (and some other paths) to try to prevent similar bugs if there are any.

13

Now, when I have a lot of pathfinding going on, I’m eventually getting this error:

“This should have been cleared after it was called on ‘this’ path. Was it not called? Or did the delegate reset not work?”

The callstack is:
Pathfinding.MultiTargetPath:ResetFlags(Path) (at Assets/AstarPathfindingProject/Pathfinders/MultiTargetPath.cs:537)
AstarPath:CalculatePathsThreaded(Object) (at Assets/AstarPathfindingProject/Core/AstarPath.cs:2548)

14

Huh. Am I still using that. I thought I had changed it… Possibly I have done it in a branch which is not yet merged into the release branch yet.

Anyway. This is likely due to multithreading race conditions (I assume you are using multithreading with more than one thread).

The solution is to change the ResetFlags method like this (and add the Cleanup method):

public override void Cleanup() {
	ResetFlags();
}

/** Reset flag1 on all nodes after the pathfinding has completed (no matter if an error occurs or if the path is canceled) */
void ResetFlags () {
	// Reset all flags
	for ( int i = 0; i < targetNodes.Length; i++ ) {
		if (targetNodes[i] != null) pathHandler.GetPathNode (targetNodes[i]).flag1 = false;
	}
}

And remove the line which registers a callback to OnPathPostSearch in the Initialize method.

15

Thanks for finding all the bugs btw :smile:

16

That fix appears to work. I’m sure this is the very last bug.

17

Uploaded 3.7.1 which includes fixes for these bugs.