diff options
Diffstat (limited to 'Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders')
16 files changed, 2028 insertions, 0 deletions
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ABPath.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ABPath.cs new file mode 100644 index 0000000..1f067d6 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ABPath.cs @@ -0,0 +1,550 @@ +using UnityEngine; +using System.Collections.Generic; +using Unity.Mathematics; + +namespace Pathfinding { + /// <summary> + /// Basic path, finds the shortest path from A to B. + /// + /// This is the most basic path object it will try to find the shortest path between two points. + /// Many other path types inherit from this type. + /// See: Seeker.StartPath + /// See: calling-pathfinding (view in online documentation for working links) + /// See: getstarted (view in online documentation for working links) + /// </summary> + public class ABPath : Path { + /// <summary>Start node of the path</summary> + public GraphNode startNode => path.Count > 0 ? path[0] : null; + + /// <summary>End node of the path</summary> + public GraphNode endNode => path.Count > 0 ? path[path.Count-1] : null; + + /// <summary>Start Point exactly as in the path request</summary> + public Vector3 originalStartPoint; + + /// <summary>End Point exactly as in the path request</summary> + public Vector3 originalEndPoint; + + /// <summary> + /// Start point of the path. + /// This is the closest point on the <see cref="startNode"/> to <see cref="originalStartPoint"/> + /// </summary> + public Vector3 startPoint; + + /// <summary> + /// End point of the path. + /// This is the closest point on the <see cref="endNode"/> to <see cref="originalEndPoint"/> + /// </summary> + public Vector3 endPoint; + + /// <summary> + /// Total cost of this path as used by the pathfinding algorithm. + /// + /// The cost is influenced by both the length of the path, as well as any tags or penalties on the nodes. + /// By default, the cost to move 1 world unit is <see cref="Int3.Precision"/>. + /// + /// If the path failed, the cost will be set to zero. + /// + /// See: tags (view in online documentation for working links) + /// </summary> + public uint cost; + + /// <summary> + /// Determines if a search for an end node should be done. + /// Set by different path types. + /// Since: Added in 3.0.8.3 + /// </summary> + protected virtual bool hasEndPoint => true; + + /// <summary> + /// True if this path type has a well defined end point, even before calculation starts. + /// + /// This is for example true for the <see cref="ABPath"/> type, but false for the <see cref="RandomPath"/> type. + /// </summary> + public virtual bool endPointKnownBeforeCalculation => true; + + /// <summary> + /// 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 + /// and a partial path will be returned. + /// This only works if a heuristic is used (which is the default). + /// If a partial path is found, CompleteState is set to Partial. + /// Note: It is not required by other path types to respect this setting + /// + /// The <see cref="endNode"/> and <see cref="endPoint"/> will be modified and be set to the node which ends up being closest to the target. + /// + /// Warning: Using this may make path calculations significantly slower if you have a big graph. The reason is that + /// when the target node cannot be reached, the path must search through every single other node that it can reach in order + /// to determine which one is closest. This may be expensive, and is why this option is disabled by default. + /// </summary> + public bool calculatePartial; + + /// <summary> + /// Current best target for the partial path. + /// This is the node with the lowest H score. + /// </summary> + protected uint partialBestTargetPathNodeIndex = GraphNode.InvalidNodeIndex; + protected uint partialBestTargetHScore = uint.MaxValue; + protected uint partialBestTargetGScore = uint.MaxValue; + + /// <summary> + /// Optional ending condition for the path. + /// + /// The ending condition determines when the path has been completed. + /// Can be used to for example mark a path as complete when it is within a specific distance from the target. + /// + /// If ending conditions are used that are not centered around the endpoint of the path, + /// then you should also set the <see cref="heuristic"/> to None to ensure the path is still optimal. + /// The performance impact of setting the <see cref="heuristic"/> to None is quite large, so you might want to try to run it with the default + /// heuristic to see if the path is good enough for your use case anyway. + /// + /// If null, no custom ending condition will be used. This means that the path will end when the target node has been reached. + /// + /// Note: If the ending condition returns false for all nodes, the path will just keep searching until it has searched the whole graph. This can be slow. + /// + /// See: <see cref="PathEndingCondition"/> + /// </summary> + public PathEndingCondition endingCondition; + + /// <summary>@{ @name Constructors</summary> + + /// <summary> + /// Default constructor. + /// Do not use this. Instead use the static Construct method which can handle path pooling. + /// </summary> + public ABPath () {} + + /// <summary> + /// Construct a path with a start and end point. + /// The delegate will be called when the path has been calculated. + /// Do not confuse it with the Seeker callback as they are sent at different times. + /// If you are using a Seeker to start the path you can set callback to null. + /// + /// Returns: The constructed path object + /// </summary> + public static ABPath Construct (Vector3 start, Vector3 end, OnPathDelegate callback = null) { + var p = PathPool.GetPath<ABPath>(); + + p.Setup(start, end, callback); + return p; + } + + protected void Setup (Vector3 start, Vector3 end, OnPathDelegate callbackDelegate) { + callback = callbackDelegate; + UpdateStartEnd(start, end); + } + + /// <summary> + /// Creates a fake path. + /// Creates a path that looks almost exactly like it would if the pathfinding system had calculated it. + /// + /// This is useful if you want your agents to follow some known path that cannot be calculated using the pathfinding system for some reason. + /// + /// <code> + /// var path = ABPath.FakePath(new List<Vector3> { new Vector3(1, 2, 3), new Vector3(4, 5, 6) }); + /// + /// ai.SetPath(path); + /// </code> + /// + /// You can use it to combine existing paths like this: + /// + /// <code> + /// var a = Vector3.zero; + /// var b = new Vector3(1, 2, 3); + /// var c = new Vector3(2, 3, 4); + /// var path1 = ABPath.Construct(a, b); + /// var path2 = ABPath.Construct(b, c); + /// + /// AstarPath.StartPath(path1); + /// AstarPath.StartPath(path2); + /// path1.BlockUntilCalculated(); + /// path2.BlockUntilCalculated(); + /// + /// // Combine the paths + /// // Note: Skip the first element in the second path as that will likely be the last element in the first path + /// var newVectorPath = path1.vectorPath.Concat(path2.vectorPath.Skip(1)).ToList(); + /// var newNodePath = path1.path.Concat(path2.path.Skip(1)).ToList(); + /// var combinedPath = ABPath.FakePath(newVectorPath, newNodePath); + /// </code> + /// </summary> + public static ABPath FakePath (List<Vector3> vectorPath, List<GraphNode> nodePath = null) { + var path = PathPool.GetPath<ABPath>(); + + for (int i = 0; i < vectorPath.Count; i++) path.vectorPath.Add(vectorPath[i]); + + path.completeState = PathCompleteState.Complete; + ((IPathInternals)path).AdvanceState(PathState.Returned); + + if (vectorPath.Count > 0) { + path.UpdateStartEnd(vectorPath[0], vectorPath[vectorPath.Count - 1]); + } + + if (nodePath != null) { + for (int i = 0; i < nodePath.Count; i++) path.path.Add(nodePath[i]); + } + + return path; + } + + /// <summary>@}</summary> + + /// <summary> + /// Sets the start and end points. + /// Sets <see cref="originalStartPoint"/>, <see cref="originalEndPoint"/>, <see cref="startPoint"/>, <see cref="endPoint"/> + /// </summary> + protected void UpdateStartEnd (Vector3 start, Vector3 end) { + originalStartPoint = start; + originalEndPoint = end; + + startPoint = start; + endPoint = end; + } + + /// <summary> + /// Reset all values to their default values. + /// All inheriting path types must implement this function, resetting ALL their variables to enable recycling of paths. + /// Call this base function in inheriting types with base.Reset (); + /// </summary> + protected override void Reset () { + base.Reset(); + + originalStartPoint = Vector3.zero; + originalEndPoint = Vector3.zero; + startPoint = Vector3.zero; + endPoint = Vector3.zero; + calculatePartial = false; + partialBestTargetPathNodeIndex = GraphNode.InvalidNodeIndex; + partialBestTargetHScore = uint.MaxValue; + partialBestTargetGScore = uint.MaxValue; + cost = 0; + endingCondition = null; + } + +#if !ASTAR_NO_GRID_GRAPH + /// <summary>Cached <see cref="Pathfinding.NNConstraint.None"/> to reduce allocations</summary> + static readonly NNConstraint NNConstraintNone = NNConstraint.None; + + /// <summary> + /// Applies a special case for grid nodes. + /// + /// Assume the closest walkable node is a grid node. + /// We will now apply a special case only for grid graphs. + /// In tile based games, an obstacle often occupies a whole + /// node. When a path is requested to the position of an obstacle + /// (single unwalkable node) the closest walkable node will be + /// one of the 8 nodes surrounding that unwalkable node + /// but that node is not neccessarily the one that is most + /// optimal to walk to so in this special case + /// we mark all nodes around the unwalkable node as targets + /// and when we search and find any one of them we simply exit + /// and set that first node we found to be the 'real' end node + /// because that will be the optimal node (this does not apply + /// in general unless the heuristic is set to None, but + /// for a single unwalkable node it does). + /// This also applies if the nearest node cannot be traversed for + /// some other reason like restricted tags. + /// + /// Returns: True if the workaround was applied. If this happens, new temporary endpoints will have been added + /// + /// Image below shows paths when this special case is applied. The path goes from the white sphere to the orange box. + /// [Open online documentation to see images] + /// + /// Image below shows paths when this special case has been disabled + /// [Open online documentation to see images] + /// </summary> + 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 = gridGraph.GetNearest(originalEndPoint, NNConstraintNone); + var gridNode2 = endNNInfo2.node as GridNode; + + if (gridNode != gridNode2 && gridNode2 != null) { + // Calculate the coordinates of the nodes + var x1 = gridNode.NodeInGridIndex % gridGraph.width; + var z1 = gridNode.NodeInGridIndex / gridGraph.width; + + var x2 = gridNode2.NodeInGridIndex % gridGraph.width; + var z2 = gridNode2.NodeInGridIndex / gridGraph.width; + + bool wasClose = false; + switch (gridGraph.neighbours) { + case NumNeighbours.Four: + if ((x1 == x2 && System.Math.Abs(z1-z2) == 1) || (z1 == z2 && System.Math.Abs(x1-x2) == 1)) { + // If 'O' is gridNode2, then gridNode is one of the nodes marked with an 'x' + // x + // x O x + // x + wasClose = true; + } + break; + case NumNeighbours.Eight: + if (System.Math.Abs(x1-x2) <= 1 && System.Math.Abs(z1-z2) <= 1) { + // If 'O' is gridNode2, then gridNode is one of the nodes marked with an 'x' + // x x x + // x O x + // x x x + wasClose = true; + } + break; + case NumNeighbours.Six: + // Hexagon graph + for (int i = 0; i < 6; i++) { + var nx = x2 + GridGraph.neighbourXOffsets[GridGraph.hexagonNeighbourIndices[i]]; + var nz = z2 + GridGraph.neighbourZOffsets[GridGraph.hexagonNeighbourIndices[i]]; + if (x1 == nx && z1 == nz) { + // If 'O' is gridNode2, then gridNode is one of the nodes marked with an 'x' + // x x + // x O x + // x x + wasClose = true; + break; + } + } + break; + default: + // Should not happen unless NumNeighbours is modified in the future + throw new System.Exception("Unhandled NumNeighbours"); + } + + if (wasClose) { + // We now need to find all nodes marked with an x to be able to mark them as targets + AddEndpointsForSurroundingGridNodes(gridNode2, originalEndPoint, targetIndex); + + // hTargetNode is used for heuristic optimizations + // (also known as euclidean embedding). + // Even though the endNode is not walkable + // we can use it for better heuristics since + // there is a workaround added (EuclideanEmbedding.ApplyGridGraphEndpointSpecialCase) + // which is there to support this case. + // TODO + return true; + } + } + } + + return false; + } + + /// <summary>Helper method to add endpoints around a specific unwalkable grid node</summary> + void AddEndpointsForSurroundingGridNodes (GridNode gridNode, Vector3 desiredPoint, int targetIndex) { + // Loop through all adjacent grid nodes + var gridGraph = GridNode.GetGridGraph(gridNode.GraphIndex); + + // Number of neighbours as an int + int mxnum = gridGraph.neighbours == NumNeighbours.Four ? 4 : (gridGraph.neighbours == NumNeighbours.Eight ? 8 : 6); + + // Calculate the coordinates of the node + var x = gridNode.NodeInGridIndex % gridGraph.width; + var z = gridNode.NodeInGridIndex / gridGraph.width; + + for (int i = 0; i < mxnum; i++) { + int nx, nz; + if (gridGraph.neighbours == NumNeighbours.Six) { + // Hexagon graph + nx = x + GridGraph.neighbourXOffsets[GridGraph.hexagonNeighbourIndices[i]]; + nz = z + GridGraph.neighbourZOffsets[GridGraph.hexagonNeighbourIndices[i]]; + } else { + nx = x + GridGraph.neighbourXOffsets[i]; + nz = z + GridGraph.neighbourZOffsets[i]; + } + + var adjacentNode = gridGraph.GetNode(nx, nz); + // Check if the position is still inside the grid + if (adjacentNode != null) { + pathHandler.AddTemporaryNode(new TemporaryNode { + type = TemporaryNodeType.End, + position = (Int3)adjacentNode.ClosestPointOnNode(desiredPoint), + associatedNode = adjacentNode.NodeIndex, + targetIndex = targetIndex, + }); + } + } + } +#endif + + /// <summary>Prepares the path. Searches for start and end nodes and does some simple checking if a path is at all possible</summary> + protected override void Prepare () { + //Initialize the NNConstraint + nnConstraint.tags = enabledTags; + var startNNInfo = AstarPath.active.GetNearest(startPoint, nnConstraint); + + //Tell the NNConstraint which node was found as the start node if it is a PathNNConstraint and not a normal NNConstraint + var pathNNConstraint = nnConstraint as PathNNConstraint; + if (pathNNConstraint != null) { + pathNNConstraint.SetStart(startNNInfo.node); + } + + startPoint = startNNInfo.position; + + if (startNNInfo.node == null) { + FailWithError("Couldn't find a node close to the start point"); + return; + } + + if (!CanTraverse(startNNInfo.node)) { + FailWithError("The node closest to the start point could not be traversed"); + return; + } + + pathHandler.AddTemporaryNode(new TemporaryNode { + associatedNode = startNNInfo.node.NodeIndex, + position = (Int3)startNNInfo.position, + type = TemporaryNodeType.Start, + }); + + // If it is declared that this path type has an end point + // 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(originalEndPoint, nnConstraint); + endPoint = endNNInfo.position; + + if (endNNInfo.node == null) { + FailWithError("Couldn't find a node close to the end point"); + return; + } + + // This should not trigger unless the user has modified the NNConstraint + if (!CanTraverse(endNNInfo.node)) { + FailWithError("The node closest to the end point could not be traversed"); + return; + } + + // This should not trigger unless the user has modified the NNConstraint + if (startNNInfo.node.Area != endNNInfo.node.Area) { + FailWithError("There is no valid path to the target"); + return; + } + + endNodeIndex = endNNInfo.node.NodeIndex; + +#if !ASTAR_NO_GRID_GRAPH + // Potentially we want to special case grid graphs a bit + // to better support some kinds of games + if (!EndPointGridGraphSpecialCase(endNNInfo.node, originalEndPoint, 0)) +#endif + { + pathHandler.AddTemporaryNode(new TemporaryNode { + associatedNode = endNNInfo.node.NodeIndex, + position = (Int3)endNNInfo.position, + type = TemporaryNodeType.End, + }); + } + } + + TemporaryEndNodesBoundingBox(out var mnTarget, out var mxTarget); + heuristicObjective = new HeuristicObjective(mnTarget, mxTarget, heuristic, heuristicScale, endNodeIndex, AstarPath.active.euclideanEmbedding); + MarkNodesAdjacentToTemporaryEndNodes(); + AddStartNodesToHeap(); + } + + void CompletePartial () { + CompleteState = PathCompleteState.Partial; + // TODO: Add unit test for this + endPoint = pathHandler.GetNode(partialBestTargetPathNodeIndex).ClosestPointOnNode(originalEndPoint); + cost = partialBestTargetGScore; + Trace(partialBestTargetPathNodeIndex); + } + + protected override void OnHeapExhausted () { + if (calculatePartial && partialBestTargetPathNodeIndex != GraphNode.InvalidNodeIndex) { + CompletePartial(); + } else { + FailWithError("Searched all reachable nodes, but could not find target. This can happen if you have nodes with a different tag blocking the way to the goal. You can enable path.calculatePartial to handle that case as a workaround (though this comes with a performance cost)."); + } + } + + protected override void OnFoundEndNode (uint pathNode, uint hScore, uint gScore) { + if (pathHandler.IsTemporaryNode(pathNode)) { + // Common case, a temporary node is used to represent the target. + // However, it may not be clamped to the closest point on the node. + // In particular the grid graph special case will not clamp it. + // So we clamp it here instead. + var tempNode = pathHandler.GetTemporaryNode(pathNode); + var associatedNode = pathHandler.GetNode(tempNode.associatedNode); + if (endingCondition != null && !endingCondition.TargetFound(associatedNode, partialBestTargetHScore, gScore)) { + // The ending condition is not fulfilled, so we should not stop here. + // This is a weird situation where the ending condition doesn't consider the closest node to the destination + // as a valid end node. It can be useful in rare cases, though. + return; + } + endPoint = (Vector3)tempNode.position; + endPoint = associatedNode.ClosestPointOnNode(endPoint); + } else { + // The target node is a normal node. We use the center of the node as the end point. + // This can happen when using a custom ending condition. + var node = pathHandler.GetNode(pathNode); + endPoint = (Vector3)node.position; + } + cost = gScore; + CompleteState = PathCompleteState.Complete; + Trace(pathNode); + } + + public override void OnVisitNode (uint pathNode, uint hScore, uint gScore) { + // This method may be called multiple times without checking if the path is complete yet. + if (CompleteState != PathCompleteState.NotCalculated) return; + + if (endingCondition != null) { + var node = pathHandler.GetNode(pathNode); + if (endingCondition.TargetFound(node, hScore, gScore)) { + OnFoundEndNode(pathNode, hScore, gScore); + if (CompleteState == PathCompleteState.Complete) { + return; + } + } + } + + if (hScore < partialBestTargetHScore) { + partialBestTargetPathNodeIndex = pathNode; + partialBestTargetHScore = hScore; + partialBestTargetGScore = gScore; + } + } + + /// <summary>Returns a debug string for this path.</summary> + protected override string DebugString (PathLog logMode) { + if (logMode == PathLog.None || (!error && logMode == PathLog.OnlyErrors)) { + return ""; + } + + var text = new System.Text.StringBuilder(); + + DebugStringPrefix(logMode, text); + if (!error) { + text.Append(" Path Cost: "); + text.Append(cost); + } + + if (!error && logMode == PathLog.Heavy) { + if (hasEndPoint && endNode != null) { + // text.Append("\nEnd Node\n G: "); + // text.Append(nodeR.G); + // text.Append("\n H: "); + // text.Append(nodeR.H); + // text.Append("\n F: "); + // text.Append(nodeR.F); + text.Append("\n Point: "); + text.Append(((Vector3)endPoint).ToString()); + text.Append("\n Graph: "); + text.Append(endNode.GraphIndex); + } + + text.Append("\nStart Node"); + text.Append("\n Point: "); + text.Append(((Vector3)startPoint).ToString()); + text.Append("\n Graph: "); + if (startNode != null) text.Append(startNode.GraphIndex); + else text.Append("< null startNode >"); + } + + DebugStringSuffix(logMode, text); + + return text.ToString(); + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ABPath.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ABPath.cs.meta new file mode 100644 index 0000000..c840f0e --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ABPath.cs.meta @@ -0,0 +1,7 @@ +fileFormatVersion: 2 +guid: 7833eca4f9a3c4a119943a3ef09cdfc9 +MonoImporter: + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ConstantPath.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ConstantPath.cs new file mode 100644 index 0000000..60d0630 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ConstantPath.cs @@ -0,0 +1,155 @@ + +using UnityEngine; +using Unity.Mathematics; +using System.Collections.Generic; + +namespace Pathfinding { + /// <summary> + /// Finds all nodes within a specified distance from the start. + /// This class will search outwards from the start point and find all nodes which it costs less than <see cref="EndingConditionDistance.maxGScore"/> to reach, this is usually the same as the distance to them multiplied with 1000. + /// + /// The path can be called like: + /// <code> + /// // Here you create a new path and set how far it should search. + /// ConstantPath cpath = ConstantPath.Construct(transform.position, 20000, null); + /// AstarPath.StartPath(cpath); + /// + /// // Block until the path has been calculated. You can also calculate it asynchronously + /// // by providing a callback in the constructor above. + /// cpath.BlockUntilCalculated(); + /// + /// // Draw a line upwards from all nodes within range + /// for (int i = 0; i < cpath.allNodes.Count; i++) { + /// Debug.DrawRay((Vector3)cpath.allNodes[i].position, Vector3.up, Color.red, 2f); + /// } + /// </code> + /// + /// When the path has been calculated, all nodes it searched will be stored in the variable <see cref="ConstantPath.allNodes"/> (remember that you need to cast it from Path to ConstantPath first to get the variable). + /// + /// This list will be sorted by the cost to reach that node (more specifically the G score if you are familiar with the terminology for search algorithms). + /// [Open online documentation to see images] + /// </summary> + public class ConstantPath : Path { + public GraphNode startNode; + public Vector3 startPoint; + public Vector3 originalStartPoint; + + /// <summary> + /// Contains all nodes the path found. + /// This list will be sorted by G score (cost/distance to reach the node). + /// </summary> + public List<GraphNode> allNodes; + + /// <summary> + /// Determines when the path calculation should stop. + /// This is set up automatically in the constructor to an instance of the Pathfinding.EndingConditionDistance class with a maxGScore is specified in the constructor. + /// + /// See: Pathfinding.PathEndingCondition for examples + /// </summary> + public PathEndingCondition endingCondition; + + /// <summary> + /// Constructs a ConstantPath starting from the specified point. + /// + /// Searching will be stopped when a node has a G score (cost to reach it) greater or equal to maxGScore + /// in order words it will search all nodes with a cost to get there less than maxGScore. + /// </summary> + /// <param name="start">From where the path will be started from (the closest node to that point will be used).</param> + /// <param name="maxGScore">Searching will be stopped when a node has a G score (cost to reach the node) greater than this.</param> + /// <param name="callback">Will be called when the path has been calculated, leave as null if you use a Seeker component.</param> + public static ConstantPath Construct (Vector3 start, int maxGScore, OnPathDelegate callback = null) { + var p = PathPool.GetPath<ConstantPath>(); + + p.Setup(start, maxGScore, callback); + return p; + } + + /// <summary>Sets up a ConstantPath starting from the specified point</summary> + protected void Setup (Vector3 start, int maxGScore, OnPathDelegate callback) { + this.callback = callback; + startPoint = start; + originalStartPoint = startPoint; + + endingCondition = new EndingConditionDistance(this, maxGScore); + } + + protected override void OnEnterPool () { + base.OnEnterPool(); + if (allNodes != null) Util.ListPool<GraphNode>.Release(ref allNodes); + } + + /// <summary> + /// Reset the path to default values. + /// Clears the <see cref="allNodes"/> list. + /// Note: This does not reset the <see cref="endingCondition"/>. + /// + /// Also sets <see cref="heuristic"/> to Heuristic.None as it is the default value for this path type + /// </summary> + protected override void Reset () { + base.Reset(); + allNodes = Util.ListPool<GraphNode>.Claim(); + endingCondition = null; + originalStartPoint = Vector3.zero; + startPoint = Vector3.zero; + startNode = null; + heuristic = Heuristic.None; + } + + protected override void Prepare () { + nnConstraint.tags = enabledTags; + var startNNInfo = AstarPath.active.GetNearest(startPoint, nnConstraint); + + startNode = startNNInfo.node; + if (startNode == null) { + FailWithError("Could not find close node to the start point"); + return; + } + + pathHandler.AddTemporaryNode(new TemporaryNode { + type = TemporaryNodeType.Start, + position = (Int3)startNNInfo.position, + associatedNode = startNode.NodeIndex, + }); + heuristicObjective = new HeuristicObjective(int3.zero, Heuristic.None, 0.0f); + AddStartNodesToHeap(); + } + + protected override void OnHeapExhausted () { + CompleteState = PathCompleteState.Complete; + } + + protected override void OnFoundEndNode (uint pathNode, uint hScore, uint gScore) { + throw new System.InvalidOperationException("ConstantPaths do not have any end nodes"); + } + + public override void OnVisitNode (uint pathNode, uint hScore, uint gScore) { + var node = pathHandler.GetNode(pathNode); + if (endingCondition.TargetFound(node, hScore, gScore)) { + CompleteState = PathCompleteState.Complete; + } else { + allNodes.Add(node); + } + } + } + + /// <summary> + /// Target is found when the path is longer than a specified value. + /// Actually this is defined as when the current node's G score is >= a specified amount (EndingConditionDistance.maxGScore). + /// The G score is the cost from the start node to the current node, so an area with a higher penalty (weight) will add more to the G score. + /// However the G score is usually just the shortest distance from the start to the current node. + /// + /// See: Pathfinding.ConstantPath which uses this ending condition + /// </summary> + public class EndingConditionDistance : PathEndingCondition { + /// <summary>Max G score a node may have</summary> + public int maxGScore = 100; + + public EndingConditionDistance (Path p, int maxGScore) : base(p) { + this.maxGScore = maxGScore; + } + + public override bool TargetFound (GraphNode node, uint H, uint G) { + return (int)G >= maxGScore; + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ConstantPath.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ConstantPath.cs.meta new file mode 100644 index 0000000..17683d1 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/ConstantPath.cs.meta @@ -0,0 +1,7 @@ +fileFormatVersion: 2 +guid: 9c10cdc7060e34b84aae81aeb516a4f1 +MonoImporter: + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FleePath.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FleePath.cs new file mode 100644 index 0000000..7c3d62c --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FleePath.cs @@ -0,0 +1,59 @@ +using UnityEngine; + +namespace Pathfinding { + /// <summary> + /// Returns a path heading away from a specified point to avoid. + /// The search will terminate when G \> length (passed to the constructor) + FleePath.spread. + /// + /// Can be used to make an AI to flee from an enemy (cannot guarantee that it will not be forced into corners though :D ) + /// <code> + /// + /// // Call a FleePath call like this, assumes that a Seeker is attached to the GameObject + /// Vector3 thePointToFleeFrom = Vector3.zero; + /// + /// // The path will be returned when the path is over a specified length (or more accurately when the traversal cost is greater than a specified value). + /// // A score of 1000 is approximately equal to the cost of moving one world unit. + /// int theGScoreToStopAt = 10000; + /// + /// // Create a path object + /// FleePath path = FleePath.Construct (transform.position, thePointToFleeFrom, theGScoreToStopAt); + /// // This is how strongly it will try to flee, if you set it to 0 it will behave like a RandomPath + /// path.aimStrength = 1; + /// // Determines the variation in path length that is allowed + /// path.spread = 4000; + /// + /// // Get the Seeker component which must be attached to this GameObject + /// Seeker seeker = GetComponent<Seeker>(); + /// + /// // Start the path and return the result to MyCompleteFunction (which is a function you have to define, the name can of course be changed) + /// seeker.StartPath(path, MyCompleteFunction); + /// + /// </code> + /// </summary> + public class FleePath : RandomPath { + /// <summary> + /// Default constructor. + /// Do not use this. Instead use the static Construct method which can handle path pooling. + /// </summary> + public FleePath () {} + + /// <summary> + /// Constructs a new FleePath. + /// The FleePath will be taken from a pool. + /// </summary> + public static FleePath Construct (Vector3 start, Vector3 avoid, int searchLength, OnPathDelegate callback = null) { + var p = PathPool.GetPath<FleePath>(); + + p.Setup(start, avoid, searchLength, callback); + return p; + } + + protected void Setup (Vector3 start, Vector3 avoid, int searchLength, OnPathDelegate callback) { + Setup(start, searchLength, callback); + // Set the aim to a point in the opposite direction from the point we to avoid + // TODO: Why is this multiplication by 10 here? + // Might want to remove it + aim = start - (avoid-start)*10; + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FleePath.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FleePath.cs.meta new file mode 100644 index 0000000..d10c8cb --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FleePath.cs.meta @@ -0,0 +1,7 @@ +fileFormatVersion: 2 +guid: 7dbd923c08b724d578abb732392cebdf +MonoImporter: + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPath.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPath.cs new file mode 100644 index 0000000..3bf6c68 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPath.cs @@ -0,0 +1,198 @@ +using System; +using UnityEngine; +using Unity.Mathematics; +using System.Collections.Generic; + +namespace Pathfinding { + /// <summary> + /// Calculates paths from everywhere to a single point. + /// This path is a bit special, because it does not do anything useful by itself. What it does is that it calculates paths to all nodes it can reach, it floods the graph. + /// This data will remain stored in the path. Then you can calculate a <see cref="FloodPathTracer"/> path. That path will trace the path from its starting point all the way to where this path started. + /// A FloodPathTracer search is extremely fast to calculate compared to a normal path request. + /// + /// It is very useful in for example tower defence games, where all your AIs will walk to the same point but from different places, and you do not update the graph or change the target point very often. + /// + /// Usage: + /// - At start, you calculate ONE FloodPath and save the reference (it will be needed later). + /// - Then when a unit is spawned or needs its path recalculated, start a FloodPathTracer path from the unit's position. + /// It will then find the shortest path to the point specified when you calculated the FloodPath extremely quickly. + /// - If you update the graph (for example place a tower in a TD game) or need to change the target point, you calculate a new FloodPath and make all AIs calculate new FloodPathTracer paths. + /// + /// Note: Since a FloodPathTracer path only uses precalculated information, it will always use the same penalties/tags as the FloodPath it references. + /// If you want to use different penalties/tags, you will have to calculate a new FloodPath. + /// + /// Here follows some example code of the above list of steps: + /// <code> + /// public static FloodPath fpath; + /// + /// public void Start () { + /// fpath = FloodPath.Construct (someTargetPosition, null); + /// AstarPath.StartPath (fpath); + /// } + /// </code> + /// + /// When searching for a new path to someTargetPosition from let's say transform.position, you do + /// <code> + /// FloodPathTracer fpathTrace = FloodPathTracer.Construct (transform.position,fpath,null); + /// seeker.StartPath (fpathTrace,OnPathComplete); + /// </code> + /// Where OnPathComplete is your callback function. + /// + /// Another thing to note is that if you are using an NNConstraint on the FloodPathTracer, they must always inherit from <see cref="FloodPathConstraint"/>. + /// The easiest is to just modify the instance of FloodPathConstraint which is created as the default one. + /// + /// \section flood-path-builtin-movement Integration with the built-in movement scripts + /// The built-in movement scripts cannot calculate a FloodPathTracer path themselves, but you can use the SetPath method to assign such a path to them: + /// <code> + /// var ai = GetComponent<IAstarAI>(); + /// // Disable the agent's own path recalculation code + /// ai.canSearch = false; + /// ai.SetPath(FloodPathTracer.Construct(ai.position, floodPath)); + /// </code> + /// + /// [Open online documentation to see images] + /// </summary> + public class FloodPath : Path { + public Vector3 originalStartPoint; + public Vector3 startPoint; + public GraphNode startNode; + + /// <summary> + /// If false, will not save any information. + /// Used by some internal parts of the system which doesn't need it. + /// </summary> + public bool saveParents = true; + + protected Dictionary<uint, uint> parents; + uint validationHash; + + public bool HasPathTo (GraphNode node) { + if (parents != null) { + for (uint k = 0; k < node.PathNodeVariants; k++) { + if (parents.ContainsKey(node.NodeIndex + k)) return true; + } + } + return false; + } + + /// <summary> + /// Checks if the flood path data is still valid. + /// + /// This check is quite strict, not allowing any nodes to have been destroyed since the path was calculated. + /// The reason for this strictness is that if a node has been destroyed, and then a node has been created, they + /// may end up sharing the same node index. This could cause the path generated by a FloodPathTracer to be + /// completely messed up if it would have passed through the destroyed node. + /// </summary> + internal bool IsValid (GlobalNodeStorage nodeStorage) { + return nodeStorage.destroyedNodesVersion == validationHash; + } + + public uint GetParent (uint node) { + return parents.TryGetValue(node, out var v) ? v : 0; + } + + /// <summary> + /// Default constructor. + /// Do not use this. Instead use the static Construct method which can handle path pooling. + /// </summary> + public FloodPath () {} + + public static FloodPath Construct (Vector3 start, OnPathDelegate callback = null) { + var p = PathPool.GetPath<FloodPath>(); + + p.Setup(start, callback); + return p; + } + + public static FloodPath Construct (GraphNode start, OnPathDelegate callback = null) { + if (start == null) throw new ArgumentNullException("start"); + + var p = PathPool.GetPath<FloodPath>(); + p.Setup(start, callback); + return p; + } + + protected void Setup (Vector3 start, OnPathDelegate callback) { + this.callback = callback; + originalStartPoint = start; + startPoint = start; + heuristic = Heuristic.None; + } + + protected void Setup (GraphNode start, OnPathDelegate callback) { + this.callback = callback; + originalStartPoint = (Vector3)start.position; + startNode = start; + startPoint = (Vector3)start.position; + heuristic = Heuristic.None; + } + + protected override void Reset () { + base.Reset(); + originalStartPoint = Vector3.zero; + startPoint = Vector3.zero; + startNode = null; + /// <summary>TODO: Avoid this allocation</summary> + parents = new Dictionary<uint, uint>(); + saveParents = true; + validationHash = 0; + } + + protected override void Prepare () { + if (startNode == null) { + //Initialize the NNConstraint + nnConstraint.tags = enabledTags; + var startNNInfo = AstarPath.active.GetNearest(originalStartPoint, nnConstraint); + + startPoint = startNNInfo.position; + startNode = startNNInfo.node; + } else if (startNode.Destroyed) { + FailWithError("Start node has been destroyed"); + return; + } else { + startPoint = (Vector3)startNode.position; + } + +#if ASTARDEBUG + Debug.DrawLine((Vector3)startNode.position, startPoint, Color.blue); +#endif + + if (startNode == null) { + FailWithError("Couldn't find a close node to the start point"); + return; + } + + if (!CanTraverse(startNode)) { + FailWithError("The node closest to the start point could not be traversed"); + return; + } + + pathHandler.AddTemporaryNode(new TemporaryNode { + type = TemporaryNodeType.Start, + position = (Int3)startPoint, + associatedNode = startNode.NodeIndex, + }); + heuristicObjective = new HeuristicObjective(int3.zero, Heuristic.None, 0.0f); + AddStartNodesToHeap(); + validationHash = pathHandler.nodeStorage.destroyedNodesVersion; + } + + protected override void OnHeapExhausted () { + CompleteState = PathCompleteState.Complete; + } + + protected override void OnFoundEndNode (uint pathNode, uint hScore, uint gScore) { + throw new System.InvalidOperationException("FloodPaths do not have any end nodes"); + } + + public const uint TemporaryNodeBit = 1u << 31; + + public override void OnVisitNode (uint pathNode, uint hScore, uint gScore) { + // Insert into internal search tree + if (saveParents) { + var parentIndex = pathHandler.pathNodes[pathNode].parentIndex; + parents[pathNode] = parentIndex | (pathHandler.IsTemporaryNode(parentIndex) ? TemporaryNodeBit : 0); // != 0 ? (pathHandler.IsTemporaryNode(parentIndex) ? pathHandler.GetTemporaryNode(parentIndex).associatedNode : parentIndex) : 0; + } + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPath.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPath.cs.meta new file mode 100644 index 0000000..c65c82e --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPath.cs.meta @@ -0,0 +1,7 @@ +fileFormatVersion: 2 +guid: 13037e083edb4439e8039fcc998ef099 +MonoImporter: + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPathTracer.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPathTracer.cs new file mode 100644 index 0000000..b743983 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPathTracer.cs @@ -0,0 +1,150 @@ +using UnityEngine; + +namespace Pathfinding { + /// <summary> + /// Restrict suitable nodes by if they have been searched by a FloodPath. + /// + /// Suitable nodes are in addition to the basic contraints, only the nodes which return true on a FloodPath.HasPathTo (node) call. + /// See: Pathfinding.FloodPath + /// See: Pathfinding.FloodPathTracer + /// </summary> + public class FloodPathConstraint : NNConstraint { + readonly FloodPath path; + + public FloodPathConstraint (FloodPath path) { + if (path == null) { Debug.LogWarning("FloodPathConstraint should not be used with a NULL path"); } + this.path = path; + } + + public override bool Suitable (GraphNode node) { + return base.Suitable(node) && path.HasPathTo(node); + } + } + + /// <summary> + /// Traces a path created with the Pathfinding.FloodPath. + /// + /// See Pathfinding.FloodPath for examples on how to use this path type + /// + /// [Open online documentation to see images] + /// </summary> + public class FloodPathTracer : ABPath { + /// <summary>Reference to the FloodPath which searched the path originally</summary> + protected FloodPath flood; + + protected override bool hasEndPoint => false; + + /// <summary> + /// Default constructor. + /// Do not use this. Instead use the static Construct method which can handle path pooling. + /// </summary> + public FloodPathTracer () {} + + public static FloodPathTracer Construct (Vector3 start, FloodPath flood, OnPathDelegate callback = null) { + var p = PathPool.GetPath<FloodPathTracer>(); + + p.Setup(start, flood, callback); + return p; + } + + protected void Setup (Vector3 start, FloodPath flood, OnPathDelegate callback) { + this.flood = flood; + + if (flood == null || flood.PipelineState < PathState.Returning) { + throw new System.ArgumentException("You must supply a calculated FloodPath to the 'flood' argument"); + } + + base.Setup(start, flood.originalStartPoint, callback); + nnConstraint = new FloodPathConstraint(flood); + } + + protected override void Reset () { + base.Reset(); + flood = null; + } + + /// <summary> + /// Initializes the path. + /// Traces the path from the start node. + /// </summary> + protected override void Prepare () { + if (!this.flood.IsValid(pathHandler.nodeStorage)) { + FailWithError("The flood path is invalid because nodes have been destroyed since it was calculated. Please recalculate the flood path."); + return; + } + + base.Prepare(); + + if (CompleteState == PathCompleteState.NotCalculated) { + for (uint i = 0; i < pathHandler.numTemporaryNodes; i++) { + var nodeIndex = pathHandler.temporaryNodeStartIndex + i; + ref var tempNode = ref pathHandler.GetTemporaryNode(nodeIndex); + if (tempNode.type == TemporaryNodeType.Start) { + var node = pathHandler.GetNode(tempNode.associatedNode); + + // This is guaranteed by the FloodPathConstraint + bool found = false; + for (uint k = 0; k < node.PathNodeVariants; k++) { + if (flood.GetParent(node.NodeIndex + k) != 0) { + found = true; + CompleteState = PathCompleteState.Complete; + Trace(node.NodeIndex + k); + break; + } + } + if (!found) { + FailWithError("The flood path did not contain any information about the end node. Have you modified the path's nnConstraint to an instance which does not subclass FloodPathConstraint?"); + } + return; + } + } + + FailWithError("Could not find a valid start node"); + } + } + + protected override void CalculateStep (long targetTick) { + if (CompleteState != PathCompleteState.Complete) throw new System.Exception("Something went wrong. At this point the path should be completed"); + } + + /// <summary> + /// Traces the calculated path from the start node to the end. + /// This will build an array (<see cref="path)"/> of the nodes this path will pass through and also set the <see cref="vectorPath"/> array to the <see cref="path"/> arrays positions. + /// This implementation will use the <see cref="flood"/> (FloodPath) to trace the path from precalculated data. + /// </summary> + protected override void Trace (uint fromPathNodeIndex) { + uint pathNodeIndex = fromPathNodeIndex; + int count = 0; + + while (pathNodeIndex != 0) { + if ((pathNodeIndex & FloodPath.TemporaryNodeBit) != 0) { + // Skip over temporary nodes + pathNodeIndex = flood.GetParent(pathNodeIndex & ~FloodPath.TemporaryNodeBit); + } else { + var node = pathHandler.GetNode(pathNodeIndex); + if (node == null) { + FailWithError("A node in the path has been destroyed. The FloodPath needs to be recalculated before you can use a FloodPathTracer."); + return; + } + if (!CanTraverse(node)) { + FailWithError("A node in the path is no longer walkable. The FloodPath needs to be recalculated before you can use a FloodPathTracer."); + return; + } + path.Add(node); + vectorPath.Add((Vector3)node.position); + var next = flood.GetParent(pathNodeIndex); + if (next == pathNodeIndex) { + break; + } + pathNodeIndex = next; + } + + count++; + if (count > 10000) { + Debug.LogWarning("Infinite loop? >10000 node path. Remove this message if you really have that long paths"); + break; + } + } + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPathTracer.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPathTracer.cs.meta new file mode 100644 index 0000000..19f3ceb --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/FloodPathTracer.cs.meta @@ -0,0 +1,7 @@ +fileFormatVersion: 2 +guid: e5753a5fb7a0047bca02db8138a07343 +MonoImporter: + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/MultiTargetPath.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/MultiTargetPath.cs new file mode 100644 index 0000000..a8f4b95 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/MultiTargetPath.cs @@ -0,0 +1,500 @@ +using UnityEngine; +using System.Collections.Generic; +using Pathfinding.Util; +using Unity.Mathematics; + +namespace Pathfinding { + /// <summary> + /// A path which searches from one point to a number of different targets in one search or from a number of different start points to a single target. + /// + /// This is faster than searching with an ABPath for each target if pathsForAll is true. + /// This path type can be used for example when you want an agent to find the closest target of a few different options. + /// + /// When pathsForAll is true, it will calculate a path to each target point, but it can share a lot of calculations for the different paths so + /// it is faster than requesting them separately. + /// + /// When pathsForAll is false, it will perform a search using the heuristic set to None and stop as soon as it finds the first target. + /// This may be faster or slower than requesting each path separately. + /// It will run a Dijkstra search where it searches all nodes around the start point until the closest target is found. + /// Note that this is usually faster if some target points are very close to the start point and some are very far away, but + /// it can be slower if all target points are relatively far away because then it will have to search a much larger + /// region since it will not use any heuristics. + /// + /// See: Seeker.StartMultiTargetPath + /// See: MultiTargetPathExample.cs (view in online documentation for working links) "Example of how to use multi-target-paths" + /// + /// Version: Since 3.7.1 the vectorPath and path fields are always set to the shortest path even when pathsForAll is true. + /// </summary> + public class MultiTargetPath : ABPath { + /// <summary>Callbacks to call for each individual path</summary> + public OnPathDelegate[] callbacks; + + /// <summary>Nearest nodes to the <see cref="targetPoints"/></summary> + public GraphNode[] targetNodes; + + /// <summary>Number of target nodes left to find</summary> + protected int targetNodeCount; + + /// <summary>Indicates if the target has been found. Also true if the target cannot be reached (is in another area)</summary> + public bool[] targetsFound; + + /// <summary>The cost of the calculated path for each target. Will be 0 if a path was not found.</summary> + public uint[] targetPathCosts; + + /// <summary>Target points specified when creating the path. These are snapped to the nearest nodes</summary> + public Vector3[] targetPoints; + + /// <summary>Target points specified when creating the path. These are not snapped to the nearest nodes</summary> + public Vector3[] originalTargetPoints; + + /// <summary>Stores all vector paths to the targets. Elements are null if no path was found</summary> + public List<Vector3>[] vectorPaths; + + /// <summary>Stores all paths to the targets. Elements are null if no path was found</summary> + public List<GraphNode>[] nodePaths; + + /// <summary>If true, a path to all targets will be returned, otherwise just the one to the closest one.</summary> + public bool pathsForAll = true; + + /// <summary>The closest target index (if any target was found)</summary> + public int chosenTarget = -1; + + /// <summary>False if the path goes from one point to multiple targets. True if it goes from multiple start points to one target point</summary> + public bool inverted { get; protected set; } + + public override bool endPointKnownBeforeCalculation => false; + + /// <summary> + /// Default constructor. + /// Do not use this. Instead use the static Construct method which can handle path pooling. + /// </summary> + public MultiTargetPath () {} + + public static MultiTargetPath Construct (Vector3[] startPoints, Vector3 target, OnPathDelegate[] callbackDelegates, OnPathDelegate callback = null) { + MultiTargetPath p = Construct(target, startPoints, callbackDelegates, callback); + + p.inverted = true; + return p; + } + + public static MultiTargetPath Construct (Vector3 start, Vector3[] targets, OnPathDelegate[] callbackDelegates, OnPathDelegate callback = null) { + var p = PathPool.GetPath<MultiTargetPath>(); + + p.Setup(start, targets, callbackDelegates, callback); + return p; + } + + protected void Setup (Vector3 start, Vector3[] targets, OnPathDelegate[] callbackDelegates, OnPathDelegate callback) { + inverted = false; + this.callback = callback; + callbacks = callbackDelegates; + if (callbacks != null && callbacks.Length != targets.Length) throw new System.ArgumentException("The targets array must have the same length as the callbackDelegates array"); + targetPoints = targets; + + originalStartPoint = start; + + startPoint = start; + + if (targets.Length == 0) { + FailWithError("No targets were assigned to the MultiTargetPath"); + return; + } + + endPoint = targets[0]; + + originalTargetPoints = new Vector3[targetPoints.Length]; + for (int i = 0; i < targetPoints.Length; i++) { + originalTargetPoints[i] = targetPoints[i]; + } + } + + protected override void Reset () { + base.Reset(); + pathsForAll = true; + chosenTarget = -1; + inverted = true; + } + + protected override void OnEnterPool () { + if (vectorPaths != null) + for (int i = 0; i < vectorPaths.Length; i++) + if (vectorPaths[i] != null) Util.ListPool<Vector3>.Release(vectorPaths[i]); + + vectorPaths = null; + vectorPath = null; + + if (nodePaths != null) + for (int i = 0; i < nodePaths.Length; i++) + if (nodePaths[i] != null) Util.ListPool<GraphNode>.Release(nodePaths[i]); + + nodePaths = null; + path = null; + callbacks = null; + targetNodes = null; + targetsFound = null; + targetPathCosts = null; + targetPoints = null; + originalTargetPoints = null; + + base.OnEnterPool(); + } + + /// <summary>Set chosenTarget to the index of the shortest path</summary> + void ChooseShortestPath () { + // When pathsForAll is false there will be at most one non-null path + chosenTarget = -1; + if (nodePaths != null) { + uint bestG = uint.MaxValue; + for (int i = 0; i < nodePaths.Length; i++) { + if (nodePaths[i] != null) { + var g = targetPathCosts[i]; + if (g < bestG) { + chosenTarget = i; + bestG = g; + } + } + } + } + } + + void SetPathParametersForReturn (int target) { + path = nodePaths[target]; + vectorPath = vectorPaths[target]; + + if (inverted) { + startPoint = targetPoints[target]; + originalStartPoint = originalTargetPoints[target]; + } else { + endPoint = targetPoints[target]; + originalEndPoint = originalTargetPoints[target]; + } + cost = path != null ? targetPathCosts[target] : 0; + } + + protected override void ReturnPath () { + if (error) { + // Call all callbacks + if (callbacks != null) { + for (int i = 0; i < callbacks.Length; i++) + if (callbacks[i] != null) callbacks[i] (this); + } + + if (callback != null) callback(this); + + return; + } + + bool anySucceded = false; + + // Set the end point to the start point + // since the path is reversed + // (the start point will be set individually for each path) + if (inverted) { + endPoint = startPoint; + originalEndPoint = originalStartPoint; + } + + for (int i = 0; i < nodePaths.Length; i++) { + if (nodePaths[i] != null) { + // Note that we use the lowercase 'completeState' here. + // The property (CompleteState) will ensure that the complete state is never + // changed away from the error state but in this case we don't want that behaviour. + completeState = PathCompleteState.Complete; + anySucceded = true; + } else { + completeState = PathCompleteState.Error; + } + + if (callbacks != null && callbacks[i] != null) { + SetPathParametersForReturn(i); + callbacks[i] (this); + + // In case a modifier changed the vectorPath, update the array of all vectorPaths + vectorPaths[i] = vectorPath; + } + } + + if (anySucceded) { + completeState = PathCompleteState.Complete; + SetPathParametersForReturn(chosenTarget); + } else { + completeState = PathCompleteState.Error; + } + + if (callback != null) { + callback(this); + } + } + + protected void RebuildOpenList () { + BinaryHeap heap = pathHandler.heap; + + for (int i = 0; i < heap.numberOfItems; i++) { + var pathNodeIndex = heap.GetPathNodeIndex(i); + Int3 pos; + if (pathHandler.IsTemporaryNode(pathNodeIndex)) { + pos = pathHandler.GetTemporaryNode(pathNodeIndex).position; + } else { + pos = pathHandler.GetNode(pathNodeIndex).DecodeVariantPosition(pathNodeIndex, pathHandler.pathNodes[pathNodeIndex].fractionAlongEdge); + } + // Note: node index can be 0 here because the multi target path never uses the euclidean embedding + var hScore = (uint)heuristicObjective.Calculate((int3)pos, 0); + heap.SetH(i, hScore); + } + + pathHandler.heap.Rebuild(pathHandler.pathNodes); + } + + protected override void Prepare () { + nnConstraint.tags = enabledTags; + var startNNInfo = AstarPath.active.GetNearest(startPoint, nnConstraint); + var startNode = startNNInfo.node; + + if (endingCondition != null) { + FailWithError("Multi target paths cannot use custom ending conditions"); + return; + } + + if (startNode == null) { + FailWithError("Could not find start node for multi target path"); + return; + } + + if (!CanTraverse(startNode)) { + FailWithError("The node closest to the start point could not be traversed"); + return; + } + + // Tell the NNConstraint which node was found as the start node if it is a PathNNConstraint and not a normal NNConstraint + if (nnConstraint is PathNNConstraint pathNNConstraint) { + pathNNConstraint.SetStart(startNNInfo.node); + } + + pathHandler.AddTemporaryNode(new TemporaryNode { + associatedNode = startNNInfo.node.NodeIndex, + position = (Int3)startNNInfo.position, + type = TemporaryNodeType.Start, + }); + + vectorPaths = new List<Vector3>[targetPoints.Length]; + nodePaths = new List<GraphNode>[targetPoints.Length]; + targetNodes = new GraphNode[targetPoints.Length]; + targetsFound = new bool[targetPoints.Length]; + targetPathCosts = new uint[targetPoints.Length]; + targetNodeCount = 0; + + bool anyWalkable = false; + bool anySameArea = false; + bool anyNotNull = false; + + for (int i = 0; i < targetPoints.Length; i++) { + var originalTarget = targetPoints[i]; + var endNNInfo = AstarPath.active.GetNearest(originalTarget, nnConstraint); + + targetNodes[i] = endNNInfo.node; + + targetPoints[i] = endNNInfo.position; + if (targetNodes[i] != null) { + anyNotNull = true; + } + + bool notReachable = false; + + if (endNNInfo.node != null && CanTraverse(endNNInfo.node)) { + anyWalkable = true; + } else { + notReachable = true; + } + + if (endNNInfo.node != null && endNNInfo.node.Area == startNode.Area) { + anySameArea = true; + } else { + notReachable = true; + } + + if (notReachable) { + // Signal that the pathfinder should not look for this node because we have already found it + targetsFound[i] = true; + } else { + targetNodeCount++; +#if !ASTAR_NO_GRID_GRAPH + // Potentially we want to special case grid graphs a bit + // to better support some kinds of games + if (!EndPointGridGraphSpecialCase(endNNInfo.node, originalTarget, i)) +#endif + { + pathHandler.AddTemporaryNode(new TemporaryNode { + associatedNode = endNNInfo.node.NodeIndex, + position = (Int3)endNNInfo.position, + targetIndex = i, + type = TemporaryNodeType.End, + }); + } + } + } + + startPoint = startNNInfo.position; + + if (!anyNotNull) { + FailWithError("Couldn't find a valid node close to the any of the end points"); + return; + } + + if (!anyWalkable) { + FailWithError("No target nodes could be traversed"); + return; + } + + if (!anySameArea) { + FailWithError("There's no valid path to any of the given targets"); + return; + } + + MarkNodesAdjacentToTemporaryEndNodes(); + AddStartNodesToHeap(); + RecalculateHTarget(); + } + + void RecalculateHTarget () { + if (pathsForAll) { + // Sequentially go through all targets. + // First we will find the path to the first target (or at least aim for it, we might find another one along the way), + // then we will change the heuristic objective to the second target and so on. + // This does not guarantee that we find the targets in order of closest to furthest, + // but that is not required since we want to find all paths anyway. + var target = FirstTemporaryEndNode(); + heuristicObjective = new HeuristicObjective(target, target, heuristic, heuristicScale, 0, null); + } else { + // Create a bounding box that contains all the end points, + // and use that to calculate the heuristic. + // This will ensure we find the closest target first. + TemporaryEndNodesBoundingBox(out var mnTarget, out var mxTarget); + heuristicObjective = new HeuristicObjective(mnTarget, mxTarget, heuristic, heuristicScale, 0, null); + } + + // Rebuild the open list since all the H scores have changed + RebuildOpenList(); + } + + protected override void Cleanup () { + // Make sure that the shortest path is set + // after the path has been calculated + ChooseShortestPath(); + base.Cleanup(); + } + + protected override void OnHeapExhausted () { + CompleteState = PathCompleteState.Complete; + } + + protected override void OnFoundEndNode (uint pathNode, uint hScore, uint gScore) { + if (!pathHandler.IsTemporaryNode(pathNode)) { + FailWithError("Expected the end node to be a temporary node. Cannot determine which path it belongs to. This could happen if you are using a custom ending condition for the path."); + return; + } + + var targetIndex = pathHandler.GetTemporaryNode(pathNode).targetIndex; + if (targetsFound[targetIndex]) throw new System.ArgumentException("This target has already been found"); + + Trace(pathNode); + vectorPaths[targetIndex] = vectorPath; + nodePaths[targetIndex] = path; + vectorPath = Util.ListPool<Vector3>.Claim(); + path = Util.ListPool<GraphNode>.Claim(); + + targetsFound[targetIndex] = true; + targetPathCosts[targetIndex] = gScore; + + targetNodeCount--; + + // Mark all end nodes for this target as ignored to avoid including them + // in the H-score calculation and to avoid calling OnFoundEndNode for this + // target index again. + for (uint i = 0; i < pathHandler.numTemporaryNodes; i++) { + var nodeIndex = pathHandler.temporaryNodeStartIndex + i; + ref var node = ref pathHandler.GetTemporaryNode(nodeIndex); + if (node.type == TemporaryNodeType.End && node.targetIndex == targetIndex) { + node.type = TemporaryNodeType.Ignore; + } + } + + // When we find the first target, we can stop because it will be the closest one. + if (!pathsForAll) { + CompleteState = PathCompleteState.Complete; + targetNodeCount = 0; + return; + } + + + // If there are no more targets to find, return here and avoid calculating a new hTarget + if (targetNodeCount <= 0) { + CompleteState = PathCompleteState.Complete; + return; + } + + RecalculateHTarget(); + } + + protected override void Trace (uint pathNodeIndex) { + base.Trace(pathNodeIndex); + + if (inverted) { + // Reverse the paths + int half = path.Count/2; + + for (int i = 0; i < half; i++) { + GraphNode tmp = path[i]; + path[i] = path[path.Count-i-1]; + path[path.Count-i-1] = tmp; + } + + for (int i = 0; i < half; i++) { + Vector3 tmp = vectorPath[i]; + vectorPath[i] = vectorPath[vectorPath.Count-i-1]; + vectorPath[vectorPath.Count-i-1] = tmp; + } + } + } + + protected override string DebugString (PathLog logMode) { + if (logMode == PathLog.None || (!error && logMode == PathLog.OnlyErrors)) { + return ""; + } + + System.Text.StringBuilder text = pathHandler.DebugStringBuilder; + text.Length = 0; + + DebugStringPrefix(logMode, text); + + if (!error) { + text.Append("\nShortest path was "); + text.Append(chosenTarget == -1 ? "undefined" : nodePaths[chosenTarget].Count.ToString()); + text.Append(" nodes long"); + + if (logMode == PathLog.Heavy) { + text.Append("\nPaths (").Append(targetsFound.Length).Append("):"); + for (int i = 0; i < targetsFound.Length; i++) { + text.Append("\n\n Path ").Append(i).Append(" Found: ").Append(targetsFound[i]); + + if (nodePaths[i] != null) { + text.Append("\n Length: "); + text.Append(nodePaths[i].Count); + } + } + + text.Append("\nStart Node"); + text.Append("\n Point: "); + text.Append(((Vector3)endPoint).ToString()); + text.Append("\n Graph: "); + text.Append(startNode.GraphIndex); + text.Append("\nBinary Heap size at completion: "); + text.AppendLine((pathHandler.heap.numberOfItems-2).ToString()); // -2 because numberOfItems includes the next item to be added and item zero is not used + } + } + + DebugStringSuffix(logMode, text); + + return text.ToString(); + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/MultiTargetPath.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/MultiTargetPath.cs.meta new file mode 100644 index 0000000..3f7415c --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/MultiTargetPath.cs.meta @@ -0,0 +1,7 @@ +fileFormatVersion: 2 +guid: 610d59b3e8ca0400192a16c204ad20fb +MonoImporter: + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/RandomPath.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/RandomPath.cs new file mode 100644 index 0000000..0c8db40 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/RandomPath.cs @@ -0,0 +1,229 @@ +using UnityEngine; +using Unity.Mathematics; + +namespace Pathfinding { + /// <summary> + /// Finds a path in a random direction from the start node. + /// + /// Terminates and returns when G \>= length (passed to the constructor) + RandomPath.spread or when there are no more nodes left to search. + /// + /// <code> + /// + /// // Call a RandomPath call like this, assumes that a Seeker is attached to the GameObject + /// + /// // The path will be returned when the path is over a specified length (or more accurately when the traversal cost is greater than a specified value). + /// // A score of 1000 is approximately equal to the cost of moving one world unit. + /// int theGScoreToStopAt = 50000; + /// + /// // Create a path object + /// RandomPath path = RandomPath.Construct(transform.position, theGScoreToStopAt); + /// // Determines the variation in path length that is allowed + /// path.spread = 5000; + /// + /// // Get the Seeker component which must be attached to this GameObject + /// Seeker seeker = GetComponent<Seeker>(); + /// + /// // Start the path and return the result to MyCompleteFunction (which is a function you have to define, the name can of course be changed) + /// seeker.StartPath(path, MyCompleteFunction); + /// + /// </code> + /// + /// [Open online documentation to see videos] + /// + /// See: wander (view in online documentation for working links) + /// </summary> + public class RandomPath : ABPath { + /// <summary> + /// G score to stop searching at. + /// The G score is rougly the distance to get from the start node to a node multiplied by 1000 (per default, see Pathfinding.Int3.Precision), plus any penalties. + /// + /// [Open online documentation to see videos] + /// </summary> + public int searchLength; + + /// <summary> + /// All G scores between <see cref="searchLength"/> and <see cref="searchLength"/>+<see cref="spread"/> are valid end points, a random one of them is chosen as the final point. + /// On grid graphs a low spread usually works (but keep it higher than nodeSize*1000 since that it the default cost of moving between two nodes), on NavMesh graphs + /// I would recommend a higher spread so it can evaluate more nodes. + /// + /// [Open online documentation to see videos] + /// </summary> + public int spread = 5000; + + /// <summary> + /// If an <see cref="aim"/> is set, the higher this value is, the more it will try to reach <see cref="aim"/>. + /// + /// Recommended values are between 0 and 10. + /// </summary> + public float aimStrength; + + /// <summary>Currently chosen end node</summary> + uint chosenPathNodeIndex; + uint chosenPathNodeGScore; + + /// <summary> + /// The node with the highest G score which is still lower than <see cref="searchLength"/>. + /// Used as a backup if a node with a G score higher than <see cref="searchLength"/> could not be found + /// </summary> + uint maxGScorePathNodeIndex; + + /// <summary>The G score of <see cref="maxGScorePathNodeIndex"/></summary> + uint maxGScore; + + /// <summary> + /// An aim can be used to guide the pathfinder to not take totally random paths. + /// For example you might want your AI to continue in generally the same direction as before, then you can specify + /// aim to be transform.postion + transform.forward*10 which will make it more often take paths nearer that point + /// See: <see cref="aimStrength"/> + /// </summary> + public Vector3 aim; + + int nodesEvaluatedRep; + + /// <summary>Random number generator</summary> + readonly System.Random rnd = new System.Random(); + + protected override bool hasEndPoint => false; + + public override bool endPointKnownBeforeCalculation => false; + + protected override void Reset () { + base.Reset(); + + searchLength = 5000; + spread = 5000; + + aimStrength = 0.0f; + chosenPathNodeIndex = uint.MaxValue; + maxGScorePathNodeIndex = uint.MaxValue; + chosenPathNodeGScore = 0; + maxGScore = 0; + aim = Vector3.zero; + + nodesEvaluatedRep = 0; + } + + public RandomPath () {} + + public static RandomPath Construct (Vector3 start, int length, OnPathDelegate callback = null) { + var p = PathPool.GetPath<RandomPath>(); + + p.Setup(start, length, callback); + return p; + } + + protected RandomPath Setup (Vector3 start, int length, OnPathDelegate callback) { + this.callback = callback; + + searchLength = length; + + originalStartPoint = start; + originalEndPoint = Vector3.zero; + + startPoint = start; + endPoint = Vector3.zero; + + return this; + } + + /// <summary> + /// Calls callback to return the calculated path. + /// See: <see cref="callback"/> + /// </summary> + protected override void ReturnPath () { + if (path != null && path.Count > 0) { + originalEndPoint = endPoint; + } + if (callback != null) { + callback(this); + } + } + + protected override void Prepare () { + nnConstraint.tags = enabledTags; + var startNNInfo = AstarPath.active.GetNearest(startPoint, nnConstraint); + + startPoint = startNNInfo.position; + endPoint = startPoint; + +#if ASTARDEBUG + Debug.DrawLine((Vector3)startNNInfo.node.position, startPoint, Color.blue); +#endif + + if (startNNInfo.node == null) { + FailWithError("Couldn't find close nodes to the start point"); + return; + } + + if (!CanTraverse(startNNInfo.node)) { + FailWithError("The node closest to the start point could not be traversed"); + return; + } + + heuristicScale = aimStrength; + + pathHandler.AddTemporaryNode(new TemporaryNode { + type = TemporaryNodeType.Start, + position = (Int3)startNNInfo.position, + associatedNode = startNNInfo.node.NodeIndex, + }); + heuristicObjective = new HeuristicObjective((int3)(Int3)aim, heuristic, heuristicScale); + AddStartNodesToHeap(); + } + + protected override void OnHeapExhausted () { + if (chosenPathNodeIndex == uint.MaxValue && maxGScorePathNodeIndex != uint.MaxValue) { + chosenPathNodeIndex = maxGScorePathNodeIndex; + chosenPathNodeGScore = maxGScore; + } + + if (chosenPathNodeIndex != uint.MaxValue) { + OnFoundEndNode(chosenPathNodeIndex, 0, chosenPathNodeGScore); + } else { + FailWithError("Not a single node found to search"); + } + } + + protected override void OnFoundEndNode (uint pathNode, uint hScore, uint gScore) { + if (pathHandler.IsTemporaryNode(pathNode)) { + base.OnFoundEndNode(pathNode, hScore, gScore); + } else { + // The target node is a normal node. + var node = pathHandler.GetNode(pathNode); + endPoint = node.RandomPointOnSurface(); + + cost = gScore; + CompleteState = PathCompleteState.Complete; + Trace(pathNode); + } + } + + public override void OnVisitNode (uint pathNode, uint hScore, uint gScore) { + // This method may be called multiple times without checking if the path is complete yet. + if (CompleteState != PathCompleteState.NotCalculated) return; + + if (gScore >= searchLength) { + if (gScore <= searchLength+spread) { + nodesEvaluatedRep++; + + // Use reservoir sampling to pick a node from the ones with the highest G score + if (rnd.NextDouble() <= 1.0f/nodesEvaluatedRep) { + chosenPathNodeIndex = pathNode; + chosenPathNodeGScore = gScore; + } + } else { + // If no node was in the valid range of G scores, then fall back to picking one right outside valid range + if (chosenPathNodeIndex == uint.MaxValue) { + chosenPathNodeIndex = pathNode; + chosenPathNodeGScore = gScore; + } + + OnFoundEndNode(chosenPathNodeIndex, 0, chosenPathNodeGScore); + } + } else if (gScore > maxGScore) { + maxGScore = gScore; + maxGScorePathNodeIndex = pathNode; + } + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/RandomPath.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/RandomPath.cs.meta new file mode 100644 index 0000000..aaaebe7 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/RandomPath.cs.meta @@ -0,0 +1,7 @@ +fileFormatVersion: 2 +guid: 2006bb8ffadf54c04ac4550f47be20b2 +MonoImporter: + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/XPath.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/XPath.cs new file mode 100644 index 0000000..3e79d3b --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/XPath.cs @@ -0,0 +1,131 @@ +using UnityEngine; + +namespace Pathfinding { + /// <summary> + /// Extended Path. + /// + /// This is the same as a standard path but it is possible to customize when the target should be considered reached. + /// Can be used to for example signal a path as complete when it is within a specific distance from the target. + /// + /// Note: More customizations does make it slower to calculate than an ABPath but not by very much. + /// + /// See: Pathfinding.PathEndingCondition + /// + /// Deprecated: Use an <see cref="ABPath"/> with the <see cref="ABPath.endingCondition"/> field instead. + /// </summary> + [System.Obsolete("Use an ABPath with the ABPath.endingCondition field instead")] + public class XPath : ABPath { + [System.Obsolete("Use ABPath.Construct instead")] + public new static ABPath Construct (Vector3 start, Vector3 end, OnPathDelegate callback = null) { + return ABPath.Construct(start, end, callback); + } + } + + /// <summary> + /// Customized ending condition for a path. + /// + /// If you want to create a path which needs a more complex ending condition than just reaching the end node, you can use this class. + /// Inherit from this class and override the <see cref="TargetFound"/> function to implement you own ending condition logic. + /// + /// For example, you might want to create an Ending Condition which stop searching when a node is close enough to a given point. + /// Then what you do is that you create your own class, let's call it MyEndingCondition and override the function TargetFound to specify our own logic. + /// We want to inherit from ABPathEndingCondition because only ABPaths have end points defined. + /// + /// <code> + /// public class MyEndingCondition : ABPathEndingCondition { + /// // Maximum world distance to the target node before terminating the path + /// public float maxDistance = 10; + /// + /// // Reuse the constructor in the superclass + /// public MyEndingCondition (ABPath p) : base(p) {} + /// + /// public override bool TargetFound (GraphNode node, uint H, uint G) { + /// return ((Vector3)node.position - abPath.originalEndPoint).sqrMagnitude <= maxDistance*maxDistance; + /// } + /// } + /// </code> + /// + /// The TargetReached method in the code above checks if the node that the path is currently searching is close enough to the target point for us to consider it a valid target node. + /// If true is returned, the path will immediately terminate and return the path to that point. + /// + /// To use a custom endition condition, you have to instantiate your class and then assign it to <see cref="ABPath.endingCondition"/> field. + /// + /// <code> + /// ABPath myPath = ABPath.Construct(startPoint, endPoint); + /// var ec = new MyEndingCondition(myPath); + /// ec.maxDistance = 100; // Or some other value + /// myPath.endingCondition = ec; + /// + /// // Calculate the path! + /// seeker.StartPath(myPath); + /// </code> + /// + /// Where seeker is a <see cref="Seeker"/> component. + /// + /// If ending conditions are used that are not centered around the endpoint of the path, + /// then the heuristic (<see cref="AstarPath.heuristic"/>) must be set to None to guarantee that the path is still optimal. + /// However, the performance impact of setting the heuristic to None is quite large, so you might want to try to run it with the default + /// heuristic to see if the path is good enough for your use case anyway. + /// + /// See: <see cref="ABPath"/> + /// See: <see cref="ConstantPath"/> + /// </summary> + public abstract class PathEndingCondition { + /// <summary>Path which this ending condition is used on</summary> + protected Path path; + + protected PathEndingCondition () {} + + public PathEndingCondition (Path p) { + if (p == null) throw new System.ArgumentNullException("p"); + this.path = p; + } + + /// <summary>Has the ending condition been fulfilled.</summary> + /// <param name="node">The current node.</param> + /// <param name="H">Heuristic score. See Pathfinding.PathNode.H</param> + /// <param name="G">Cost to reach this node. See Pathfinding.PathNode.G</param> + public abstract bool TargetFound(GraphNode node, uint H, uint G); + } + + /// <summary>Ending condition which emulates the default one for the ABPath</summary> + public class ABPathEndingCondition : PathEndingCondition { + /// <summary> + /// Path which this ending condition is used on. + /// Same as <see cref="path"/> but downcasted to ABPath + /// </summary> + protected ABPath abPath; + + public ABPathEndingCondition (ABPath p) { + if (p == null) throw new System.ArgumentNullException("p"); + abPath = p; + path = p; + } + + /// <summary> + /// Has the ending condition been fulfilled. + /// + /// This is per default the same as asking if node == p.endNode + /// </summary> + /// <param name="node">The current node.</param> + /// <param name="H">Heuristic score. See Pathfinding.PathNode.H</param> + /// <param name="G">Cost to reach this node. See Pathfinding.PathNode.G</param> + public override bool TargetFound (GraphNode node, uint H, uint G) { + return node == abPath.endNode; + } + } + + /// <summary>Ending condition which stops a fixed distance from the target point</summary> + public class EndingConditionProximity : ABPathEndingCondition { + /// <summary>Maximum world distance to the target node before terminating the path</summary> + public float maxDistance = 10; + + public EndingConditionProximity (ABPath p, float maxDistance) : base(p) { + this.maxDistance = maxDistance; + } + + public override bool TargetFound (GraphNode node, uint H, uint G) { + return ((Vector3)node.position - abPath.originalEndPoint).sqrMagnitude <= maxDistance*maxDistance; + } + } +} diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/XPath.cs.meta b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/XPath.cs.meta new file mode 100644 index 0000000..2f6b534 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Pathfinders/XPath.cs.meta @@ -0,0 +1,7 @@ +fileFormatVersion: 2 +guid: 0055d294de64544e0a18edeca86f45fd +MonoImporter: + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} |