Hello
I’m try to update to the latest version from 4.3.83, In this changelog below you mentioned that the MultiTargetPath got modified, I’ve maintained a custom MultiTargetPath myself thus I’d like to know what part of code you changed to fix this problem.
4.3.85 (2023-12-07)
commit 9cded5c7a52138cb795f07b489eaf54ce745b2f3
Author: Aron Granberg <aron.granberg@gmail.com>
Date: Tue Dec 5 14:05:49 2023 +0100
Fixed MultiTargetPath could throw an exception if MultiTargetPath.calculatePartial was enabled.
diff --git a/Assets/AstarPathfindingProject/Pathfinders/ABPath.cs b/Assets/AstarPathfindingProject/Pathfinders/ABPath.cs
index d0da5438f..d66f27ae3 100644
--- a/Assets/AstarPathfindingProject/Pathfinders/ABPath.cs
+++ b/Assets/AstarPathfindingProject/Pathfinders/ABPath.cs
@@ -49,11 +49,7 @@ namespace Pathfinding {
* Set by different path types.
* \since Added in 3.0.8.3
*/
- protected virtual bool hasEndPoint {
- get {
- return true;
- }
- }
+ protected virtual bool hasEndPoint => true;
/** Calculate partial path if the target node cannot be reached.
* If the target node cannot be reached, the node which was closest (given by heuristic) will be chosen as target node
@@ -405,7 +401,8 @@ namespace Pathfinding {
void CompletePartial () {
CompleteState = PathCompleteState.Partial;
- endPoint = endNode.ClosestPointOnNode(originalEndPoint);
+ endPoint = pathHandler.GetNode(partialBestTargetPathNodeIndex).ClosestPointOnNode(originalEndPoint);
cost = partialBestTargetGScore;
Trace(partialBestTargetPathNodeIndex);
}
diff --git a/Assets/AstarPathfindingProject/changelog.cs b/Assets/AstarPathfindingProject/changelog.cs
index 24f3d9ab8..1ef46a4e5 100644
--- a/Assets/AstarPathfindingProject/changelog.cs
+++ b/Assets/AstarPathfindingProject/changelog.cs
@@ -7,6 +7,7 @@
- Added \reflink{GraphMask.FromGraphIndex}.
- Added support for rendering gizmos while the scene view is in wireframe mode. This is supported on Unity 2023.1 and up.
- Fixed a memory leak that could happen if the AstarPath component was put in a prefab.
+ - Fixed \reflink{MultiTargetPath} could throw an exception if \reflink{MultiTargetPath.calculatePartial} was enabled.
- Fixed an exception being thrown if the scene contained some \reflink{FollowerEntity} components that had gravity enabled, and some that had gravity disabled.
- Fixed a rare exception that could be thrown when the AIPath or RichAI components were drawing gizmos.
- Pathfinding would not work in WebGL builds (regression in 4.3.83).
This is the full diff. Note that the changes are made in the ABPath script, so you most likely don’t need to change anything in your MultiTargetPath variant.
Hello
let me know what code you have changed at this changelog in 5.0.6
commit 45537698481e2b959e4dee3e58477a154f3a1f25
Author: Aron Granberg
Date: Wed Mar 27 13:03:22 2024 +0100
Fixed MultiTargetPath could calculate incorrect paths on grid graphs in some situations.
diff --git a/Assets/AstarPathfindingProject/Developer/TestingScripts/UnitTests.cs b/Assets/AstarPathfindingProject/Developer/TestingScripts/UnitTests.cs
index 8c99f1a59..fdf4bdab8 100644
--- a/Assets/AstarPathfindingProject/Developer/TestingScripts/UnitTests.cs
+++ b/Assets/AstarPathfindingProject/Developer/TestingScripts/UnitTests.cs
@@ -3485,6 +3485,60 @@ public class UnitTests : MonoBehaviour {
DrawPath(p, Color.black);
yield return null;
}
+
+ var allReachable = PathUtilities.GetReachableNodes(AstarPath.active.GetNearest(new Vector3(0, 0, 0)).node);
+ // Note: This is the max number of temporary nodes - 1 (one is used for the start node)
+ var chunkSize = 255;
+ for (int i = 0; i < (allReachable.Count + chunkSize-1) / chunkSize; i++) {
+ var chunk = allReachable.Skip(i*chunkSize).Take(chunkSize).ToList();
+ p = MultiTargetPath.Construct(Vector3.zero, chunk.Select(node => (Vector3)node.position).ToArray(), null, null);
+ StartAndWaitForPath(p);
+ DrawPath(p, Color.black);
+ AssertPath(p, !p.error);
+ AssertEqi(p.nodePaths.Count(path => path != null), chunk.Count);
+ yield return null;
+ }
+
+ yield return null;
+ yield return StartCoroutine(CreateAlignedGridGraph());
+
+ // Test grid graph special cases (when targeting unwalkable nodes)
+ var start = new Vector3(3, 0, -1);
+ var targets = new (Vector3, int)[] {
+ // To edge of long thin obstacle (walkable)
+ (new Vector3(3, 0, -4), 4),
+ // To other edge of long thin obstacle (walkable)
+ (new Vector3(3, 0, -6), 9),
+ // To middle of long thin obstacle (unwalkable)
+ (new Vector3(3, 0, -5), 4),
+ // To center of unwalkable tile (unwalkable), path goes diagonally, connecting to a point diagonally from the target
+ (new Vector3(1, 0, 1), 2),
+ // To center of unwalkable tile (unwalkable), path goes straight, connecting to a point diagonally from the target
+ (new Vector3(4, 0, 1), 2),
+ // To point slightly outside graph
+ (new Vector3(11, 0, -1), 8),
+ (new Vector3(-5, 0, 4), 8),
+ (new Vector3(-6, 0, 4), 9),
+ (new Vector3(7, 0, 1), 4),
+ // Various points within an unwalkable node. Forcing the nearest node to be on different sides of the node.
+ (new Vector3(7, 0, 1), 4),
+ (new Vector3(7, 0, 1.4f), 4),
+ (new Vector3(7, 0, 0.6f), 4),
+ (new Vector3(7.4f, 0, 1), 4),
+ };
+ p = MultiTargetPath.Construct(start, targets.Select(t => t.Item1).ToArray(), null, null);
+ StartAndWaitForPath(p);
+ AssertPath(p, !p.error);
+ for (int i = 0; i < targets.Length; i++) {
+ if (p.nodePaths[i].Count != targets[i].Item2) {
+ using(Draw.WithLineWidth(2)) {
+ Draw.Polyline(p.vectorPaths[i], Color.red);
+ }
+ }
+ AssertEqi(p.nodePaths[i].Count, targets[i].Item2, "Path to target " + i + " should have " + targets[i].Item2 + " nodes, but has " + p.nodePaths[i].Count);
+ }
+ AssertEqi(p.chosenTarget, 4);
+ yield return null;
}
IEnumerator TestXPath () {
@@ -3584,9 +3638,9 @@ public class UnitTests : MonoBehaviour {
yield return null;
yield return null;
- for (int i = 0; i < 5; i++) {
+ for (int i = 0; i < 8; i++) {
yield return StartCoroutine(InitScene());
- yield return StartCoroutine(CreateAstar());
+ yield return StartCoroutine(CreateAstar((ThreadCount)i));
yield return StartCoroutine(CreateGridGraph());
AstarPath.active.Scan();
@@ -3595,7 +3649,16 @@ public class UnitTests : MonoBehaviour {
AstarPath.StartPath(ABPath.Construct(Vector3.zero, Vector3.one*10));
AstarPath.StartPath(ABPath.Construct(Vector3.zero, Vector3.one*10));
- AstarPath.active.UpdateGraphs(new Bounds(Vector3.zero, Vector3.one*10));
+ if (i > 3) {
+ // Create so many paths that it cannot possibly complete them all in one frame
+ for (int j = 0; j < 3000; j++) {
+ AstarPath.StartPath(ABPath.Construct(Vector3.zero, Vector3.one*10));
+ }
+ }
+
+ if ((i % 2) == 0) {
+ AstarPath.active.UpdateGraphs(new Bounds(Vector3.zero, Vector3.one*10));
+ }
yield return null;
}
}
diff --git a/Assets/AstarPathfindingProject/Pathfinders/ABPath.cs b/Assets/AstarPathfindingProject/Pathfinders/ABPath.cs
index b5deaa269..9de10e9c6 100644
--- a/Assets/AstarPathfindingProject/Pathfinders/ABPath.cs
+++ b/Assets/AstarPathfindingProject/Pathfinders/ABPath.cs
@@ -213,17 +213,17 @@ namespace Pathfinding {
* Image below shows paths when this special case has been disabled
* \shadowimage{abpath_grid_not_special.gif}
*/
- protected virtual bool EndPointGridGraphSpecialCase (GraphNode closestWalkableEndNode, int targetIndex) {
+ protected virtual bool EndPointGridGraphSpecialCase (GraphNode closestWalkableEndNode, Vector3 originalEndPoint, int targetIndex) {
var gridNode = closestWalkableEndNode as GridNode;
if (gridNode != null) {
var gridGraph = GridNode.GetGridGraph(gridNode.GraphIndex);
// Find the closest node, not neccessarily walkable
- var endNNInfo2 = AstarPath.active.GetNearest(originalEndPoint, NNConstraintNone);
+ var endNNInfo2 = gridGraph.GetNearest(originalEndPoint, NNConstraintNone);
var gridNode2 = endNNInfo2.node as GridNode;
- if (gridNode != gridNode2 && gridNode2 != null && gridNode.GraphIndex == gridNode2.GraphIndex) {
+ if (gridNode != gridNode2 && gridNode2 != null) {
// Calculate the coordinates of the nodes
var x1 = gridNode.NodeInGridIndex % gridGraph.width;
var z1 = gridNode.NodeInGridIndex / gridGraph.width;
@@ -290,7 +290,7 @@ namespace Pathfinding {
return false;
}
- /** Helper method to set PathNode.flag1 to a specific value for all nodes adjacent to a grid node */
+ /** Helper method to add endpoints around a specific unwalkable grid node */
void AddEndpointsForSurroundingGridNodes (GridNode gridNode, Vector3 desiredPoint, int targetIndex) {
// Loop through all adjacent grid nodes
var gridGraph = GridNode.GetGridGraph(gridNode.GraphIndex);
@@ -313,9 +313,9 @@ namespace Pathfinding {
nz = z + GridGraph.neighbourZOffsets[i];
}
+ var adjacentNode = gridGraph.GetNode(nx, nz);
// Check if the position is still inside the grid
- if (nx >= 0 && nz >= 0 && nx < gridGraph.width && nz < gridGraph.depth) {
- var adjacentNode = gridGraph.nodes[nz*gridGraph.width + nx];
+ if (adjacentNode != null) {
pathHandler.AddTemporaryNode(new TemporaryNode {
type = TemporaryNodeType.End,
position = (Int3)adjacentNode.ClosestPointOnNode(desiredPoint),
@@ -361,7 +361,7 @@ namespace Pathfinding {
// Some path types might want to use most of the ABPath code, but will not have an explicit end point at this stage
uint endNodeIndex = 0;
if (hasEndPoint) {
- var endNNInfo = AstarPath.active.GetNearest(endPoint, nnConstraint);
+ var endNNInfo = AstarPath.active.GetNearest(originalEndPoint, nnConstraint);
endPoint = endNNInfo.position;
if (endNNInfo.node == null) {
@@ -386,9 +386,7 @@ namespace Pathfinding {
#if !ASTAR_NO_GRID_GRAPH
// Potentially we want to special case grid graphs a bit
// to better support some kinds of games
- // If this returns true it will overwrite the
- // endNode, endPoint, heuristicObjective fields
- if (!EndPointGridGraphSpecialCase(endNNInfo.node, 0))
+ if (!EndPointGridGraphSpecialCase(endNNInfo.node, originalEndPoint, 0))
#endif
{
pathHandler.AddTemporaryNode(new TemporaryNode {
diff --git a/Assets/AstarPathfindingProject/Pathfinders/MultiTargetPath.cs b/Assets/AstarPathfindingProject/Pathfinders/MultiTargetPath.cs
index af39b5c46..ccd7e331f 100644
--- a/Assets/AstarPathfindingProject/Pathfinders/MultiTargetPath.cs
+++ b/Assets/AstarPathfindingProject/Pathfinders/MultiTargetPath.cs
@@ -289,7 +289,8 @@ namespace Pathfinding {
bool anyNotNull = false;
for (int i = 0; i < targetPoints.Length; i++) {
- var endNNInfo = AstarPath.active.GetNearest(targetPoints[i], nnConstraint);
+ var originalTarget = targetPoints[i];
+ var endNNInfo = AstarPath.active.GetNearest(originalTarget, nnConstraint);
targetNodes[i] = endNNInfo.node;
@@ -320,9 +321,7 @@ namespace Pathfinding {
#if !ASTAR_NO_GRID_GRAPH
// Potentially we want to special case grid graphs a bit
// to better support some kinds of games
- // If this returns true it will overwrite the
- // endNode, endPoint, heuristicObjective fields
- if (!EndPointGridGraphSpecialCase(endNNInfo.node, i))
+ if (!EndPointGridGraphSpecialCase(endNNInfo.node, originalTarget, i))
#endif
{
pathHandler.AddTemporaryNode(new TemporaryNode {
diff --git a/Assets/AstarPathfindingProject/changelog.cs b/Assets/AstarPathfindingProject/changelog.cs
index 3f6a3e038..35d287918 100644
--- a/Assets/AstarPathfindingProject/changelog.cs
+++ b/Assets/AstarPathfindingProject/changelog.cs
@@ -9,6 +9,7 @@
- Made \reflink{GraphUpdateScene.GetGraphUpdate} virtual.
- Fixed \reflink{FollowerEntity} could return incorrect values for a few properties (e.g. \reflink{FollowerEntity.hasPath}) after it had been disabled.
- Fixed \reflink{RandomPath} could in very rare situations cause an exception that crashed the pathfinding threads, due to a race condition.
+ - Fixed \reflink{MultiTargetPath} could calculate incorrect paths on grid graphs in some situations.
- Fixed various edge cases when the AstarPath component is put in a prefab.
- Fixed \reflink{RecastMeshObj} components could log an error message about being moved, even if they had not moved.
- If an \reflink{RVOSimulator} is enabled in a scene that already has an active RVOSimulator, the new one will be disabled and a warning will be logged.