using UnityEngine; using System.Collections; using System.Collections.Generic; using Pathfinding; using Pathfinding.Drawing; using UnityEngine.Profiling; using Pathfinding.Util; using Pathfinding.Graphs.Navmesh; using Pathfinding.Graphs.Util; using Pathfinding.Jobs; using Pathfinding.Collections; using Pathfinding.Sync; using Unity.Jobs; #if NETFX_CORE using Thread = Pathfinding.WindowsStore.Thread; #else using Thread = System.Threading.Thread; #endif [ExecuteInEditMode] [AddComponentMenu("Pathfinding/AstarPath")] [DisallowMultipleComponent] /// /// Core component for the A* Pathfinding System. /// This class handles all of the pathfinding system, calculates all paths and stores the info. /// This class is a singleton class, meaning there should only exist at most one active instance of it in the scene. /// It might be a bit hard to use directly, usually interfacing with the pathfinding system is done through the class. /// [HelpURL("https://arongranberg.com/astar/documentation/stable/astarpath.html")] public class AstarPath : VersionedMonoBehaviour { /// The version number for the A* Pathfinding Project public static readonly System.Version Version = new System.Version(5, 3, 7); /// Information about where the package was downloaded public enum AstarDistribution { WebsiteDownload, AssetStore, PackageManager }; /// Used by the editor to guide the user to the correct place to download updates public static readonly AstarDistribution Distribution = AstarDistribution.AssetStore; /// /// Which branch of the A* Pathfinding Project is this release. /// Used when checking for updates so that users of the development /// versions can get notifications of development updates. /// public static readonly string Branch = "master"; /// Holds all graph data [UnityEngine.Serialization.FormerlySerializedAs("astarData")] public AstarData data; /// /// Returns the active AstarPath object in the scene. /// Note: This is only set if the AstarPath object has been initialized (which happens in Awake). /// public static AstarPath active; /// Shortcut to public NavGraph[] graphs => data.graphs; bool hasScannedGraphAtStartup = false; #region InspectorDebug /// /// Visualize graphs in the scene view (editor only). /// [Open online documentation to see images] /// public bool showNavGraphs = true; /// /// Toggle to show unwalkable nodes. /// /// Note: Only relevant in the editor /// /// See: /// public bool showUnwalkableNodes = true; /// /// The mode to use for drawing nodes in the sceneview. /// /// Note: Only relevant in the editor /// /// See: /// public GraphDebugMode debugMode; /// /// Low value to use for certain modes. /// For example if is set to G, this value will determine when the node will be completely red. /// /// Note: Only relevant in the editor /// /// See: /// See: /// public float debugFloor = 0; /// /// High value to use for certain modes. /// For example if is set to G, this value will determine when the node will be completely green. /// /// For the penalty debug mode, the nodes will be colored green when they have a penalty less than and red /// when their penalty is greater or equal to this value and something between red and green otherwise. /// /// Note: Only relevant in the editor /// /// See: /// See: /// public float debugRoof = 20000; /// /// If set, the and values will not be automatically recalculated. /// /// Note: Only relevant in the editor /// public bool manualDebugFloorRoof = false; /// /// If enabled, nodes will draw a line to their 'parent'. /// This will show the search tree for the latest path. /// /// Note: Only relevant in the editor /// public bool showSearchTree = false; /// /// Size of the red cubes shown in place of unwalkable nodes. /// /// Note: Only relevant in the editor. Does not apply to grid graphs. /// See: /// public float unwalkableNodeDebugSize = 0.3F; /// /// The amount of debugging messages. /// Use less debugging to improve performance (a bit) or just to get rid of the Console spamming. /// Use more debugging (heavy) if you want more information about what the pathfinding scripts are doing. /// The InGame option will display the latest path log using in-game GUI. /// /// [Open online documentation to see images] /// public PathLog logPathResults = PathLog.Normal; #endregion #region InspectorSettings /// /// Maximum distance to search for nodes. /// When searching for the nearest node to a point, this is the limit (in world units) for how far away it is allowed to be. /// /// This is relevant if you try to request a path to a point that cannot be reached and it thus has to search for /// the closest node to that point which can be reached (which might be far away). If it cannot find a node within this distance /// then the path will fail. /// /// [Open online documentation to see images] /// /// See: /// public float maxNearestNodeDistance = 100; /// /// Max Nearest Node Distance Squared. /// See: /// public float maxNearestNodeDistanceSqr => maxNearestNodeDistance*maxNearestNodeDistance; /// /// If true, all graphs will be scanned when the game starts, during OnEnable. /// If you disable this, you will have to call yourself to enable pathfinding. /// Alternatively you could load a saved graph from a file. /// /// If a startup cache has been generated (see save-load-graphs) (view in online documentation for working links), it always takes priority, and the graphs will be loaded from the cache instead of scanned. /// /// This can be useful to disable if you want to scan your graphs asynchronously, or if you have a procedural world which has not been created yet /// at the start of the game. /// /// See: /// See: /// public bool scanOnStartup = true; /// /// Do a full GetNearest search for all graphs. /// Additional searches will normally only be done on the graph which in the first fast search seemed to have the closest node. /// With this setting on, additional searches will be done on all graphs since the first check is not always completely accurate. /// More technically: GetNearestForce on all graphs will be called if true, otherwise only on the one graph which's GetNearest search returned the best node. /// Usually faster when disabled, but higher quality searches when enabled. /// Note: For the PointGraph this setting doesn't matter much as it has only one search mode. /// [System.Obsolete("This setting has been removed. It is now always true", true)] public bool fullGetNearestSearch = false; /// /// Prioritize graphs. /// Graphs will be prioritized based on their order in the inspector. /// The first graph which has a node closer than will be chosen instead of searching all graphs. /// /// Deprecated: This setting has been removed. It was always a bit of a hack. Use NNConstraint.graphMask if you want to choose which graphs are searched. /// [System.Obsolete("This setting has been removed. It was always a bit of a hack. Use NNConstraint.graphMask if you want to choose which graphs are searched.", true)] public bool prioritizeGraphs = false; /// /// Distance limit for . /// See: /// /// Deprecated: This setting has been removed. It was always a bit of a hack. Use NNConstraint.graphMask if you want to choose which graphs are searched. /// [System.Obsolete("This setting has been removed. It was always a bit of a hack. Use NNConstraint.graphMask if you want to choose which graphs are searched.", true)] public float prioritizeGraphsLimit = 1F; /// /// Reference to the color settings for this AstarPath object. /// Color settings include for example which color the nodes should be in, in the sceneview. /// public AstarColor colorSettings; /// /// Stored tag names. /// See: AstarPath.FindTagNames /// See: AstarPath.GetTagNames /// [SerializeField] protected string[] tagNames = null; /// /// The distance function to use as a heuristic. /// The heuristic, often referred to as just 'H' is the estimated cost from a node to the target. /// Different heuristics affect how the path picks which one to follow from multiple possible with the same length /// See: for more details and descriptions of the different modes. /// See: Wikipedia: Admissible heuristic /// See: Wikipedia: A* search algorithm /// See: Wikipedia: Dijkstra's Algorithm /// /// Warning: Reducing the heuristic scale below 1, or disabling the heuristic, can significantly increase the cpu cost for pathfinding, especially for large graphs. /// public Heuristic heuristic = Heuristic.Euclidean; /// /// The scale of the heuristic. /// If a value lower than 1 is used, the pathfinder will search more nodes (slower). /// If 0 is used, the pathfinding algorithm will be reduced to dijkstra's algorithm. This is equivalent to setting to None. /// If a value larger than 1 is used the pathfinding will (usually) be faster because it expands fewer nodes, but the paths may no longer be the optimal (i.e the shortest possible paths). /// /// Usually you should leave this to the default value of 1. /// /// Warning: Reducing the heuristic scale below 1, or disabling the heuristic, can significantly increase the cpu cost for pathfinding, especially for large graphs. /// /// See: Wikipedia: Admissible heuristic /// See: Wikipedia: A* search algorithm /// See: Wikipedia: Dijkstra's Algorithm /// public float heuristicScale = 1F; /// /// Number of pathfinding threads to use. /// Multithreading puts pathfinding in another thread, this is great for performance on 2+ core computers since the framerate will barely be affected by the pathfinding at all. /// - None indicates that the pathfinding is run in the Unity thread as a coroutine /// - Automatic will try to adjust the number of threads to the number of cores and memory on the computer. /// Less than 512mb of memory or a single core computer will make it revert to using no multithreading. /// /// It is recommended that you use one of the "Auto" settings that are available. /// The reason is that even if your computer might be beefy and have 8 cores. /// Other computers might only be quad core or dual core in which case they will not benefit from more than /// 1 or 3 threads respectively (you usually want to leave one core for the unity thread). /// If you use more threads than the number of cores on the computer it is mostly just wasting memory, it will not run any faster. /// The extra memory usage is not trivially small. Each thread needs to keep a small amount of data for each node in all the graphs. /// It is not the full graph data but it is proportional to the number of nodes. /// The automatic settings will inspect the machine it is running on and use that to determine the number of threads so that no memory is wasted. /// /// The exception is if you only have one (or maybe two characters) active at time. Then you should probably just go with one thread always since it is very unlikely /// that you will need the extra throughput given by more threads. Keep in mind that more threads primarily increases throughput by calculating different paths on different /// threads, it will not calculate individual paths any faster. /// /// Warning: If you are modifying the pathfinding core scripts or if you are directly modifying graph data without using any of the /// safe wrappers (like , multithreading can cause strange errors and cause pathfinding to stop working if you are not careful. /// /// Note: WebGL does not support threads at all (since javascript is single-threaded) so no threads will be used on that platform. /// /// Note: This setting only applies to pathfinding. Graph updates use the Unity Job System, which uses a different thread pool. /// /// See: CalculateThreadCount /// public ThreadCount threadCount = ThreadCount.One; /// /// Max number of milliseconds to spend on pathfinding during each frame. /// At least 500 nodes will be searched each frame (if there are that many to search). /// When using multithreading this value is irrelevant. /// public float maxFrameTime = 1F; /// /// Throttle graph updates and batch them to improve performance. /// If toggled, graph updates will batched and executed less often (specified by . /// /// This can have a positive impact on pathfinding throughput since the pathfinding threads do not need /// to be stopped as often, and it reduces the overhead per graph update. /// All graph updates are still applied, they are just batched together so that more of them are /// applied at the same time. /// /// Do not use this if you want minimal latency between a graph update being requested /// and it being applied. /// /// This only applies to graph updates requested using the method. Not those requested /// using . /// /// If you want to apply graph updates immediately at some point, you can call . /// /// See: graph-updates (view in online documentation for working links) /// public bool batchGraphUpdates = false; /// /// Minimum number of seconds between each batch of graph updates. /// If is true, this defines the minimum number of seconds between each batch of graph updates. /// /// This can have a positive impact on pathfinding throughput since the pathfinding threads do not need /// to be stopped as often, and it reduces the overhead per graph update. /// All graph updates are still applied however, they are just batched together so that more of them are /// applied at the same time. /// /// Do not use this if you want minimal latency between a graph update being requested /// and it being applied. /// /// This only applies to graph updates requested using the method. Not those requested /// using . /// /// See: graph-updates (view in online documentation for working links) /// public float graphUpdateBatchingInterval = 0.2F; #endregion #region DebugVariables #if ProfileAstar /// /// How many paths has been computed this run. From application start. /// Debugging variable /// public static int PathsCompleted = 0; public static System.Int64 TotalSearchedNodes = 0; public static System.Int64 TotalSearchTime = 0; #endif /// The time it took for the last call to to complete public float lastScanTime { get; private set; } /// /// The path to debug using gizmos. /// This is the path handler used to calculate the last path. /// It is used in the editor to draw debug information using gizmos. /// [System.NonSerialized] internal PathHandler debugPathData; /// The path ID to debug using gizmos [System.NonSerialized] internal ushort debugPathID; /// /// Debug string from the last completed path. /// Will be updated if == PathLog.InGame /// string inGameDebugPath; #endregion #region StatusVariables /// /// True while any graphs are being scanned. /// /// This is primarily relevant when scanning graph asynchronously. /// /// Note: Not to be confused with graph updates. /// /// Note: This will be false during and during the .LatePostScan event. /// /// See: IsAnyGraphUpdateQueued /// See: IsAnyGraphUpdateInProgress /// [field: System.NonSerialized] public bool isScanning { get; private set; } /// /// Number of parallel pathfinders. /// Returns the number of concurrent processes which can calculate paths at once. /// When using multithreading, this will be the number of threads, if not using multithreading it is always 1 (since only 1 coroutine is used). /// See: IsUsingMultithreading /// public int NumParallelThreads => pathProcessor.NumThreads; /// /// Returns whether or not multithreading is used. /// \exception System.Exception Is thrown when it could not be decided if multithreading was used or not. /// This should not happen if pathfinding is set up correctly. /// Note: This uses info about if threads are running right now, it does not use info from the settings on the A* object. /// public bool IsUsingMultithreading => pathProcessor.IsUsingMultithreading; /// /// Returns if any graph updates are waiting to be applied. /// Note: This is false while the updates are being performed. /// Note: This does *not* includes other types of work items such as navmesh cutting or anything added by . /// public bool IsAnyGraphUpdateQueued => graphUpdates.IsAnyGraphUpdateQueued; /// /// Returns if any graph updates are being calculated right now. /// Note: This does *not* includes other types of work items such as navmesh cutting or anything added by . /// /// See: IsAnyWorkItemInProgress /// public bool IsAnyGraphUpdateInProgress => graphUpdates.IsAnyGraphUpdateInProgress; /// /// Returns if any work items are in progress right now. /// Note: This includes pretty much all types of graph updates. /// Such as normal graph updates, navmesh cutting and anything added by . /// public bool IsAnyWorkItemInProgress => workItems.workItemsInProgress; /// /// Returns if this code is currently being exectuted inside a work item. /// Note: This includes pretty much all types of graph updates. /// Such as normal graph updates, navmesh cutting and anything added by . /// /// In contrast to this is only true when work item code is being executed, it is not /// true in-between the updates to a work item that takes several frames to complete. /// internal bool IsInsideWorkItem => workItems.workItemsInProgressRightNow; #endregion #region Callbacks /// /// Called on Awake before anything else is done. /// This is called at the start of the Awake call, right after has been set, but this is the only thing that has been done. /// Use this when you want to set up default settings for an AstarPath component created during runtime since some settings can only be changed in Awake /// (such as multithreading related stuff) /// /// // Create a new AstarPath object on Start and apply some default settings /// public void Start () { /// AstarPath.OnAwakeSettings += ApplySettings; /// AstarPath astar = gameObject.AddComponent(); /// } /// /// public void ApplySettings () { /// // Unregister from the delegate /// AstarPath.OnAwakeSettings -= ApplySettings; /// // For example threadCount should not be changed after the Awake call /// // so here's the only place to set it if you create the component during runtime /// AstarPath.active.threadCount = ThreadCount.One; /// } /// /// public static System.Action OnAwakeSettings; /// Called for each graph before they are scanned. In most cases it is recommended to create a custom class which inherits from Pathfinding.GraphModifier instead. public static OnGraphDelegate OnGraphPreScan; /// Called for each graph after they have been scanned. All other graphs might not have been scanned yet. In most cases it is recommended to create a custom class which inherits from Pathfinding.GraphModifier instead. public static OnGraphDelegate OnGraphPostScan; /// Called for each path before searching. Be careful when using multithreading since this will be called from a different thread. public static OnPathDelegate OnPathPreSearch; /// Called for each path after searching. Be careful when using multithreading since this will be called from a different thread. public static OnPathDelegate OnPathPostSearch; /// Called before starting the scanning. In most cases it is recommended to create a custom class which inherits from Pathfinding.GraphModifier instead. public static OnScanDelegate OnPreScan; /// Called after scanning. This is called before applying links, flood-filling the graphs and other post processing. In most cases it is recommended to create a custom class which inherits from Pathfinding.GraphModifier instead. public static OnScanDelegate OnPostScan; /// Called after scanning has completed fully. This is called as the last thing in the Scan function. In most cases it is recommended to create a custom class which inherits from Pathfinding.GraphModifier instead. public static OnScanDelegate OnLatePostScan; /// Called when any graphs are updated. Register to for example recalculate the path whenever a graph changes. In most cases it is recommended to create a custom class which inherits from Pathfinding.GraphModifier instead. public static OnScanDelegate OnGraphsUpdated; /// /// Called when pathID overflows 65536 and resets back to zero. /// Note: This callback will be cleared every time it is called, so if you want to register to it repeatedly, register to it directly on receiving the callback as well. /// public static System.Action On65KOverflow; /// /// Called right after callbacks on paths have been called. /// /// A path's callback function runs on the main thread when the path has been calculated. /// This is done in batches for all paths that have finished their calculation since the last frame. /// This event will trigger right after a batch of callbacks have been called. /// /// If you do not want to use individual path callbacks, you can use this instead to poll all pending paths /// and see which ones have completed. This is better than doing it in e.g. the Update loop, because /// here you will have a guarantee that all calculated paths are still valid. /// Immediately after this callback has finished, other things may invalidate calculated paths, like for example /// graph updates. /// /// This is used by the ECS integration to update all entities' pending paths, without having to store /// a callback for each agent, and also to avoid the ECS synchronization overhead that having individual /// callbacks would entail. /// public static System.Action OnPathsCalculated; #endregion #region MemoryStructures /// Processes graph updates readonly GraphUpdateProcessor graphUpdates; /// Holds a hierarchical graph to speed up some queries like if there is a path between two nodes internal readonly HierarchicalGraph hierarchicalGraph; /// Holds all active off-mesh links public readonly OffMeshLinks offMeshLinks; /// /// Handles navmesh cuts. /// See: /// public NavmeshUpdates navmeshUpdates = new NavmeshUpdates(); /// Processes work items readonly WorkItemProcessor workItems; /// Holds all paths waiting to be calculated and calculates them readonly PathProcessor pathProcessor; /// Holds global node data that cannot be stored in individual graphs internal GlobalNodeStorage nodeStorage; /// /// Global read-write lock for graph data. /// /// Graph data is always consistent from the main-thread's perspective, but if you are using jobs to read from graph data, you may need this. /// /// A write lock is held automatically... /// - During graph updates. During async graph updates, the lock is only held once per frame while the graph update is actually running, not for the whole duration. /// - During work items. Async work items work similarly to graph updates, the lock is only held once per frame while the work item is actually running. /// - When events run. /// - When graph related callbacks, such as , run. /// - During the last step of a graph's scanning process. See . /// /// To use e.g. AstarPath.active.GetNearest from an ECS job, you'll need to acquire a read lock first, and make sure the lock is only released when the job is finished. /// /// /// var readLock = AstarPath.active.LockGraphDataForReading(); /// var handle = new MyJob { /// // ... /// }.Schedule(readLock.dependency); /// readLock.UnlockAfter(handle); /// /// /// See: /// RWLock graphDataLock = new RWLock(); bool graphUpdateRoutineRunning = false; /// Makes sure QueueGraphUpdates will not queue multiple graph update orders bool graphUpdatesWorkItemAdded = false; /// /// Time the last graph update was done. /// Used to group together frequent graph updates to batches /// float lastGraphUpdate = -9999F; /// Held if any work items are currently queued PathProcessor.GraphUpdateLock workItemLock; /// Holds all completed paths waiting to be returned to where they were requested internal readonly PathReturnQueue pathReturnQueue; /// /// Holds settings for heuristic optimization. /// See: heuristic-opt (view in online documentation for working links) /// public EuclideanEmbedding euclideanEmbedding = new EuclideanEmbedding(); /// /// If an async scan is running, this will be set to the coroutine. /// /// This primarily used to be able to force the async scan to complete immediately, /// if the AstarPath component should happen to be destroyed while an async scan is running. /// IEnumerator asyncScanTask; #endregion /// /// Shows or hides graph inspectors. /// Used internally by the editor /// public bool showGraphs = false; /// /// The next unused Path ID. /// Incremented for every call to GetNextPathID /// private ushort nextFreePathID = 1; private AstarPath () { pathReturnQueue = new PathReturnQueue(this, () => { if (OnPathsCalculated != null) OnPathsCalculated(); }); // Make sure that the pathProcessor and node storage is never null nodeStorage = new GlobalNodeStorage(this); hierarchicalGraph = new HierarchicalGraph(nodeStorage); pathProcessor = new PathProcessor(this, pathReturnQueue, 1, false); offMeshLinks = new OffMeshLinks(this); workItems = new WorkItemProcessor(this); graphUpdates = new GraphUpdateProcessor(this); navmeshUpdates.astar = this; data = new AstarData(this); // Forward graphUpdates.OnGraphsUpdated to AstarPath.OnGraphsUpdated workItems.OnGraphsUpdated += () => { if (OnGraphsUpdated != null) { try { OnGraphsUpdated(this); } catch (System.Exception e) { Debug.LogException(e); } } }; pathProcessor.OnPathPreSearch += path => { var tmp = OnPathPreSearch; if (tmp != null) tmp(path); }; pathProcessor.OnPathPostSearch += path => { LogPathResults(path); var tmp = OnPathPostSearch; if (tmp != null) tmp(path); }; // Sent every time the path queue is unblocked pathProcessor.OnQueueUnblocked += () => { if (euclideanEmbedding.dirty) { euclideanEmbedding.RecalculateCosts(); } }; } /// /// Returns tag names. /// Makes sure that the tag names array is not null and of length 32. /// If it is null or not of length 32, it creates a new array and fills it with 0,1,2,3,4 etc... /// See: AstarPath.FindTagNames /// public string[] GetTagNames () { if (tagNames == null || tagNames.Length != 32) { tagNames = new string[32]; for (int i = 0; i < tagNames.Length; i++) { tagNames[i] = ""+i; } tagNames[0] = "Basic Ground"; } return tagNames; } /// /// Used outside of play mode to initialize the AstarPath object even if it has not been selected in the inspector yet. /// This will set the property and deserialize all graphs. /// /// This is useful if you want to do changes to the graphs in the editor outside of play mode, but cannot be sure that the graphs have been deserialized yet. /// In play mode this method does nothing. /// public static void FindAstarPath () { if (Application.isPlaying) return; if (active == null) active = UnityCompatibility.FindAnyObjectByType(); if (active != null && (active.data.graphs == null || active.data.graphs.Length == 0)) active.data.DeserializeGraphs(); } /// /// Tries to find an AstarPath object and return tag names. /// If an AstarPath object cannot be found, it returns an array of length 1 with an error message. /// See: AstarPath.GetTagNames /// public static string[] FindTagNames () { FindAstarPath(); return active != null? active.GetTagNames () : new string[1] { "There is no AstarPath component in the scene" }; } /// Returns the next free path ID internal ushort GetNextPathID () { if (nextFreePathID == 0) { nextFreePathID++; if (On65KOverflow != null) { System.Action tmp = On65KOverflow; On65KOverflow = null; tmp(); } } return nextFreePathID++; } void RecalculateDebugLimits () { #if UNITY_EDITOR debugFloor = float.PositiveInfinity; debugRoof = float.NegativeInfinity; bool ignoreSearchTree = !showSearchTree || debugPathData == null; UnsafeSpan debugPathNodes; if (debugPathData != null && debugPathData.threadID < active.nodeStorage.pathfindingThreadData.Length) debugPathNodes = active.nodeStorage.pathfindingThreadData[debugPathData.threadID].debugPathNodes; else debugPathNodes = default; for (int i = 0; i < graphs.Length; i++) { if (graphs[i] != null && graphs[i].drawGizmos) { graphs[i].GetNodes(node => { if (node.Walkable && (ignoreSearchTree || Pathfinding.Util.GraphGizmoHelper.InSearchTree(node, debugPathNodes, debugPathID))) { float value; if (debugMode == GraphDebugMode.Penalty) { value = node.Penalty; } else if (debugPathNodes.Length > 0) { var rnode = debugPathNodes[node.NodeIndex]; switch (debugMode) { case GraphDebugMode.F: value = rnode.g + rnode.h; break; case GraphDebugMode.G: value = rnode.g; break; default: case GraphDebugMode.H: value = rnode.h; break; } } else { value = 0; } debugFloor = Mathf.Min(debugFloor, value); debugRoof = Mathf.Max(debugRoof, value); } }); } } if (float.IsInfinity(debugFloor)) { debugFloor = 0; debugRoof = 1; } // Make sure they are not identical, that will cause the color interpolation to fail if (debugRoof-debugFloor < 1) debugRoof += 1; #else debugFloor = 0; debugRoof = 1; #endif } RedrawScope redrawScope; /// Calls OnDrawGizmos on all graphs public override void DrawGizmos () { if (active != this || graphs == null) { return; } InitializeColors(); if (!redrawScope.isValid) redrawScope = DrawingManager.GetRedrawScope(gameObject); if (!workItems.workItemsInProgress && !isScanning) { // When updating graphs, graph info might not be valid, // and we cannot render anything during those frames. // Therefore we use a redraw scope which will continue drawing // until we dispose it. redrawScope.Rewind(); if (showNavGraphs && !manualDebugFloorRoof) { RecalculateDebugLimits(); } Profiler.BeginSample("Graph.OnDrawGizmos"); // Loop through all graphs and draw their gizmos for (int i = 0; i < graphs.Length; i++) { if (graphs[i] != null && graphs[i].drawGizmos) graphs[i].OnDrawGizmos(DrawingManager.instance.gizmos, showNavGraphs, redrawScope); } Profiler.EndSample(); if (showNavGraphs) { euclideanEmbedding.OnDrawGizmos(); if (debugMode == GraphDebugMode.HierarchicalNode) hierarchicalGraph.OnDrawGizmos(DrawingManager.instance.gizmos, redrawScope); if (debugMode == GraphDebugMode.NavmeshBorderObstacles) hierarchicalGraph.navmeshEdges.OnDrawGizmos(DrawingManager.instance.gizmos, redrawScope); } } } #if !ASTAR_NO_GUI /// /// Draws the InGame debugging (if enabled) /// See: PathLog /// private void OnGUI () { if (logPathResults == PathLog.InGame && inGameDebugPath != "") { GUI.Label(new Rect(5, 5, 400, 600), inGameDebugPath); } } #endif /// /// Prints path results to the log. What it prints can be controled using . /// See: /// See: PathLog /// See: Pathfinding.Path.DebugString /// private void LogPathResults (Path path) { if (logPathResults != PathLog.None && (path.error || logPathResults != PathLog.OnlyErrors)) { string debug = (path as IPathInternals).DebugString(logPathResults); if (logPathResults == PathLog.InGame) { inGameDebugPath = debug; } else if (path.error) { Debug.LogWarning(debug); } else { Debug.Log(debug); } } } /// /// Checks if any work items need to be executed /// then runs pathfinding for a while (if not using multithreading because /// then the calculation happens in other threads) /// and then returns any calculated paths to the /// scripts that requested them. /// /// See: PerformBlockingActions /// See: PathProcessor.TickNonMultithreaded /// See: PathReturnQueue.ReturnPaths /// private void Update () { navmeshUpdates.Update(); // This class uses the [ExecuteInEditMode] attribute // So Update is called even when not playing // Don't do anything when not in play mode if (!Application.isPlaying) return; // Execute blocking actions such as graph updates // when not scanning if (!isScanning) { PerformBlockingActions(); } // Calculates paths when not using multithreading if (!pathProcessor.IsUsingMultithreading) pathProcessor.TickNonMultithreaded(); // Return calculated paths pathReturnQueue.ReturnPaths(true); } private void PerformBlockingActions (bool force = false) { if (workItemLock.Held && pathProcessor.queue.allReceiversBlocked) { // Return all paths before starting blocking actions // since these might change the graph and make returned paths invalid (at least the nodes) pathReturnQueue.ReturnPaths(false); Profiler.BeginSample("Work Items"); if (workItems.ProcessWorkItemsForUpdate(force)) { // At this stage there are no more work items, resume pathfinding threads workItemLock.Release(); } Profiler.EndSample(); } } /// /// Add a work item to be processed when pathfinding is paused. /// /// The callback will be called once when it is safe to update graphs. /// /// This is a convenience method that is equivalent to /// /// AddWorkItem(new AstarWorkItem(callback)); /// /// /// See: /// public void AddWorkItem (System.Action callback) { AddWorkItem(new AstarWorkItem(callback)); } /// /// Add a work item to be processed when pathfinding is paused. /// /// THe callback will be called once when it is safe to update graphs. /// /// This is a convenience method that is equivalent to /// /// AddWorkItem(new AstarWorkItem(callback)); /// /// /// See: /// public void AddWorkItem (System.Action callback) { AddWorkItem(new AstarWorkItem(callback)); } /// /// Add a work item to be processed when pathfinding is paused. /// /// The work item will be executed when it is safe to update nodes. This is defined as between the path searches. /// When using more threads than one, calling this often might decrease pathfinding performance due to a lot of idling in the threads. /// Not performance as in it will use much CPU power, but performance as in the number of paths per second will probably go down /// (though your framerate might actually increase a tiny bit). /// /// You should only call this function from the main unity thread (i.e normal game code). /// /// /// AstarPath.active.AddWorkItem(new AstarWorkItem(() => { /// // Safe to update graphs here /// var node = AstarPath.active.GetNearest(transform.position).node; /// node.Walkable = false; /// })); /// /// /// /// AstarPath.active.AddWorkItem(() => { /// // Safe to update graphs here /// var node = AstarPath.active.GetNearest(transform.position).node; /// node.position = (Int3)transform.position; /// }); /// /// /// You can run work items over multiple frames: /// /// AstarPath.active.AddWorkItem(new AstarWorkItem(() => { /// // Called once, right before the /// // first call to the method below /// }, /// force => { /// // Called every frame until complete. /// // Signal that the work item is /// // complete by returning true. /// // The "force" parameter will /// // be true if the work item is /// // required to complete immediately. /// // In that case this method should /// // block and return true when done. /// return true; /// })); /// /// /// See: /// public void AddWorkItem (AstarWorkItem item) { workItems.AddWorkItem(item); // Make sure pathfinding is stopped and work items are processed if (!workItemLock.Held) { workItemLock = PausePathfindingSoon(); } #if UNITY_EDITOR // If not playing, execute instantly if (!Application.isPlaying) { FlushWorkItems(); } #endif } #region GraphUpdateMethods /// /// Will apply queued graph updates as soon as possible, regardless of . /// Calling this multiple times will not create multiple callbacks. /// This function is useful if you are limiting graph updates, but you want a specific graph update to be applied as soon as possible regardless of the time limit. /// Note that this does not block until the updates are done, it merely bypasses the time limit. /// /// See: /// public void QueueGraphUpdates () { if (!graphUpdatesWorkItemAdded) { graphUpdatesWorkItemAdded = true; var workItem = graphUpdates.GetWorkItem(); // Add a new work item which first // sets the graphUpdatesWorkItemAdded flag to false // and then processes the graph updates AddWorkItem(new AstarWorkItem(context => { graphUpdatesWorkItemAdded = false; lastGraphUpdate = Time.realtimeSinceStartup; workItem.initWithContext(context); }, workItem.updateWithContext)); } } /// /// Waits a moment with updating graphs. /// If batchGraphUpdates is set, we want to keep some space between them to let pathfinding threads running and then calculate all queued calls at once /// IEnumerator DelayedGraphUpdate () { graphUpdateRoutineRunning = true; yield return new WaitForSeconds(graphUpdateBatchingInterval-(Time.realtimeSinceStartup-lastGraphUpdate)); QueueGraphUpdates(); graphUpdateRoutineRunning = false; } /// /// Update all graphs within bounds after delay seconds. /// The graphs will be updated as soon as possible. /// /// See: FlushGraphUpdates /// See: batchGraphUpdates /// See: graph-updates (view in online documentation for working links) /// public void UpdateGraphs (Bounds bounds, float delay) { UpdateGraphs(new GraphUpdateObject(bounds), delay); } /// /// Update all graphs using the GraphUpdateObject after delay seconds. /// This can be used to, e.g make all nodes in a region unwalkable, or set them to a higher penalty. /// /// See: FlushGraphUpdates /// See: batchGraphUpdates /// See: graph-updates (view in online documentation for working links) /// public void UpdateGraphs (GraphUpdateObject ob, float delay) { StartCoroutine(UpdateGraphsInternal(ob, delay)); } /// Update all graphs using the GraphUpdateObject after delay seconds IEnumerator UpdateGraphsInternal (GraphUpdateObject ob, float delay) { yield return new WaitForSeconds(delay); UpdateGraphs(ob); } /// /// Update all graphs within bounds. /// The graphs will be updated as soon as possible. /// /// This is equivalent to /// /// UpdateGraphs(new GraphUpdateObject(bounds)); /// /// /// See: FlushGraphUpdates /// See: batchGraphUpdates /// See: graph-updates (view in online documentation for working links) /// public void UpdateGraphs (Bounds bounds) { UpdateGraphs(new GraphUpdateObject(bounds)); } /// /// Update all graphs using the GraphUpdateObject. /// This can be used to, e.g make all nodes in a region unwalkable, or set them to a higher penalty. /// The graphs will be updated as soon as possible (with respect to /// /// See: FlushGraphUpdates /// See: batchGraphUpdates /// See: graph-updates (view in online documentation for working links) /// public void UpdateGraphs (GraphUpdateObject ob) { if (ob.internalStage != GraphUpdateObject.STAGE_CREATED) { throw new System.Exception("You are trying to update graphs using the same graph update object twice. Please create a new GraphUpdateObject instead."); } ob.internalStage = GraphUpdateObject.STAGE_PENDING; graphUpdates.AddToQueue(ob); // If we should limit graph updates, start a coroutine which waits until we should update graphs if (batchGraphUpdates && Time.realtimeSinceStartup-lastGraphUpdate < graphUpdateBatchingInterval) { if (!graphUpdateRoutineRunning) { StartCoroutine(DelayedGraphUpdate()); } } else { // Otherwise, graph updates should be carried out as soon as possible QueueGraphUpdates(); } } /// /// Forces graph updates to complete in a single frame. /// This will force the pathfinding threads to finish calculating the path they are currently calculating (if any) and then pause. /// When all threads have paused, graph updates will be performed. /// Warning: Using this very often (many times per second) can reduce your fps due to a lot of threads waiting for one another. /// But you probably wont have to worry about that. /// /// Note: This is almost identical to , but added for more descriptive name. /// This function will also override any time limit delays for graph updates. /// This is because graph updates are implemented using work items. /// So calling this function will also execute any other work items (if any are queued). /// /// Will not do anything if there are no graph updates queued (not even execute other work items). /// public void FlushGraphUpdates () { if (IsAnyGraphUpdateQueued || IsAnyGraphUpdateInProgress) { QueueGraphUpdates(); FlushWorkItems(); } } #endregion /// /// Forces work items to complete in a single frame. /// This will force all work items to run immidiately. /// This will force the pathfinding threads to finish calculating the path they are currently calculating (if any) and then pause. /// When all threads have paused, work items will be executed (which can be e.g graph updates). /// /// Warning: Using this very often (many times per second) can reduce your fps due to a lot of threads waiting for one another. /// But you probably wont have to worry about that /// /// Note: This is almost (note almost) identical to , but added for more descriptive name. /// /// Will not do anything if there are no queued work items waiting to run. /// public void FlushWorkItems () { if (workItems.anyQueued || workItems.workItemsInProgress) { if (active != this) throw new System.Exception("This AstarPath component is not initialized in a scene. Are you trying to add work items to a prefab or a disabled AstarPath component?"); using (PausePathfinding()) { PerformBlockingActions(true); } } } /// /// Calculates number of threads to use. /// If count is not Automatic, simply returns count casted to an int. /// Returns: An int specifying how many threads to use, 0 means a coroutine should be used for pathfinding instead of a separate thread. /// /// If count is set to Automatic it will return a value based on the number of processors and memory for the current system. /// If memory is <= 512MB or logical cores are <= 1, it will return 0. If memory is <= 1024 it will clamp threads to max 2. /// Otherwise it will return the number of logical cores clamped to 6. /// /// When running on WebGL this method always returns 0 /// public static int CalculateThreadCount (ThreadCount count) { #if UNITY_WEBGL return 0; #else if (count == ThreadCount.AutomaticLowLoad || count == ThreadCount.AutomaticHighLoad) { #if ASTARDEBUG Debug.Log(SystemInfo.systemMemorySize + " " + SystemInfo.processorCount + " " + SystemInfo.processorType); #endif int logicalCores = Mathf.Max(1, SystemInfo.processorCount); int memory = SystemInfo.systemMemorySize; if (memory <= 0) { Debug.LogError("Machine reporting that is has <= 0 bytes of RAM. This is definitely not true, assuming 1 GiB"); memory = 1024; } if (logicalCores <= 1) return 0; if (memory <= 512) return 0; if (count == ThreadCount.AutomaticHighLoad) { if (memory <= 1024) logicalCores = System.Math.Min(logicalCores, 2); } else { //Always run at at most processorCount-1 threads (one core reserved for unity thread). // Many computers use hyperthreading, so dividing by two is used to remove the hyperthreading cores, pathfinding // doesn't scale well past the number of physical cores anyway logicalCores /= 2; logicalCores = Mathf.Max(1, logicalCores); if (memory <= 1024) logicalCores = System.Math.Min(logicalCores, 2); logicalCores = System.Math.Min(logicalCores, 6); } return logicalCores; } else { int val = (int)count; return val; } #endif } /// Initializes the field void InitializePathProcessor () { int numThreads = CalculateThreadCount(threadCount); // Outside of play mode everything is synchronous, so no threads are used. if (!Application.isPlaying) numThreads = 0; int numProcessors = Mathf.Max(numThreads, 1); bool multithreaded = numThreads > 0; pathProcessor.StopThreads(); pathProcessor.SetThreadCount(numProcessors, multithreaded); } void InitializeColors () { colorSettings = colorSettings ?? new AstarColor(); colorSettings.PushToStatic(); } void ShutdownPathfindingThreads () { // Block until the pathfinding threads have // completed their current path calculation var graphLock = PausePathfinding(); navmeshUpdates.OnDisable(); euclideanEmbedding.dirty = false; // Discard all queued graph updates. Graph updates that are already in progress will still be allowed to finish, // as they may be allocating unmanaged data which we don't know how to safely deallocate. graphUpdates.DiscardQueued(); // TODO: Add unit test that verifies that work items that are added will always complete // Ensure work items complete before disabling this component. // This is important because work items may allocate temporary unmanaged memory, so we cannot just forget about them. FlushWorkItems(); if (logPathResults == PathLog.Heavy) Debug.Log("Processing Possible Work Items"); // Try to join pathfinding threads pathProcessor.StopThreads(); if (logPathResults == PathLog.Heavy) Debug.Log("Returning Paths"); // Return all paths pathReturnQueue.ReturnPaths(false); graphLock.Release(); euclideanEmbedding.OnDisable(); } /// /// Called after this component is enabled. /// /// Unless the component has already been activated in Awake, this method should: /// - Ensure the singleton holds (setting to this). /// - Make sure all subsystems that were disabled in OnDisable are again enabled. /// - This includes starting pathfinding threads. /// void OnEnable () { // If the component gets re-enabled during runtime. // Note that the first time the component loads, then Awake will run first // and will already have set the #active field. // In the editor, OnDisable -> OnEnable will be called when an undo or redo event happens (both in and outside of play mode). if (active != null) { if (active != this && Application.isPlaying) { if (this.enabled) { Debug.LogWarning("Another A* component is already in the scene. More than one A* component cannot be active at the same time. Disabling this one.", this); } enabled = false; } return; } // Very important to set this. Ensures the singleton pattern holds active = this; // Disable GUILayout to gain some performance, it is not used in the OnGUI call useGUILayout = false; if (OnAwakeSettings != null) { OnAwakeSettings(); } hierarchicalGraph.OnEnable(); // To make sure all graph modifiers have been enabled before scan (to avoid script execution order issues) GraphModifier.FindAllModifiers(); RelevantGraphSurface.FindAllGraphSurfaces(); InitializeColors(); navmeshUpdates.OnEnable(); // This will load the graph settings, or whole initialized graphs from the cache, if one has been supplied. data.OnEnable(); // Flush work items, possibly added when loading the graph data FlushWorkItems(); euclideanEmbedding.dirty = true; InitializePathProcessor(); // This class uses the [ExecuteInEditMode] attribute // So OnEnable is called even when not playing // Don't scan the graphs unless we are in play mode if (Application.isPlaying) { // Scan the graphs if #scanOnStartup is enabled, and we have not loaded a graph cache already. // We only do this the first time the AstarPath component is enabled. if (scanOnStartup && !hasScannedGraphAtStartup && (!data.cacheStartup || data.file_cachedStartup == null)) { hasScannedGraphAtStartup = true; Scan(); } } } /// /// Cleans up graphs to avoid memory leaks. /// /// This is called by Unity when: /// - The component is explicitly disabled in play mode or editor mode. /// - When the component is about to be destroyed /// - Including when the game stops /// - When an undo/redo event takes place (Unity will first disable the component and then enable it again). /// /// During edit and play mode this method should: /// - Destroy all node data (but not the graphs themselves) /// - Dispose all unmanaged data /// - Shutdown pathfinding threads if they are running (any pending path requests are left in the queue) /// void OnDisable () { redrawScope.Dispose(); if (active == this) { if (asyncScanTask != null) { Debug.LogWarning("An async scan was running when the AstarPath component was disabled. Blocking until the async scan is complete.", this); BlockUntilAsyncScanComplete(); } // Ensure there are no jobs running that might read or write graph data graphDataLock.WriteSync().Unlock(); ShutdownPathfindingThreads(); // We need to call dispose data here because in the editor the OnDestroy // method is not called but OnDisable is. It is vital that graph data // is destroyed even in the editor (e.g. when going from edit mode to play mode) // because a lot of data is stored as NativeArrays which need to be disposed. // There is also another case where this is important. When the unity // editor is configured to stop play mode after recompiling scripts // it seems to not call OnDestroy (or at least not reliably across all versions of Unity). // So we need to ensure we dispose of all the data during OnDisable. data.DestroyAllNodes(); data.DisposeUnmanagedData(); hierarchicalGraph.OnDisable(); nodeStorage.OnDisable(); offMeshLinks.OnDisable(); active = null; } } /// /// Clears up variables and other stuff, destroys graphs. /// Note that when destroying an AstarPath object, all static variables such as callbacks will be cleared. /// void OnDestroy () { if (logPathResults == PathLog.Heavy) Debug.Log("AstarPath Component Destroyed - Cleaning Up Pathfinding Data"); // active has already been set to null during OnDisable. // We temporarily make this object the active one just during the destruction. var prevActive = active; active = this; ShutdownPathfindingThreads(); pathProcessor.Dispose(); if (logPathResults == PathLog.Heavy) Debug.Log("Destroying Graphs"); // Clean up graph data // Data may be null if this object was never enabled because another A* instance existed. if (data != null) data.OnDestroy(); active = prevActive; if (logPathResults == PathLog.Heavy) Debug.Log("Cleaning up variables"); // Clear all static variables, otherwise the next scene might get weird data if (active == this) { // Clear all callbacks OnAwakeSettings = null; OnGraphPreScan = null; OnGraphPostScan = null; OnPathPreSearch = null; OnPathPostSearch = null; OnPreScan = null; OnPostScan = null; OnLatePostScan = null; On65KOverflow = null; OnGraphsUpdated = null; active = null; } } #region ScanMethods /// /// Allocate a bunch of nodes at once. /// This is faster than allocating each individual node separately and it can be done in a separate thread by using jobs. /// /// /// var nodes = new PointNode[128]; /// var job = AstarPath.active.AllocateNodes(nodes, 128, () => new PointNode(), 1); /// /// job.Complete(); /// /// /// See: /// /// Node array to fill /// How many nodes to allocate /// Delegate which creates a node. () => new T(). Note that new T(AstarPath.active) should *not* be used as that will cause the node to be initialized twice. /// How many variants of the node to allocate. Should be the same as \reflink{GraphNode.PathNodeVariants} for this node type. public Unity.Jobs.JobHandle AllocateNodes(T[] result, int count, System.Func createNode, uint variantsPerNode) where T : GraphNode { if (!pathProcessor.queue.allReceiversBlocked) { throw new System.Exception("Trying to initialize a node when it is not safe to initialize any nodes. Must be done during a graph update. See http://arongranberg.com/astar/docs/graph-updates.html#direct"); } return nodeStorage.AllocateNodesJob(result, count, createNode, variantsPerNode); } /// /// Initializes temporary path data for a node. /// /// Use like: InitializeNode(new PointNode()) /// /// See: /// internal void InitializeNode (GraphNode node) { if (!pathProcessor.queue.allReceiversBlocked) { throw new System.Exception("Trying to initialize a node when it is not safe to initialize any nodes. Must be done during a graph update. See http://arongranberg.com/astar/docs/graph-updates.html#direct"); } nodeStorage.InitializeNode(node); } internal void InitializeNodes (GraphNode[] nodes) { if (!pathProcessor.queue.allReceiversBlocked) { throw new System.Exception("Trying to initialize a node when it is not safe to initialize any nodes. Must be done during a graph update. See http://arongranberg.com/astar/docs/graph-updates.html#direct"); } for (int i = 0; i < nodes.Length; i++) nodeStorage.InitializeNode(nodes[i]); } /// /// Internal method to destroy a given node. /// This is to be called after the node has been disconnected from the graph so that it cannot be reached from any other nodes. /// It should only be called during graph updates, that is when the pathfinding threads are either not running or paused. /// /// Warning: This method should not be called by user code. It is used internally by the system. /// internal void DestroyNode (GraphNode node) { nodeStorage.DestroyNode(node); } /// /// Blocks until all pathfinding threads are paused and blocked. /// /// /// var graphLock = AstarPath.active.PausePathfinding(); /// // Here we can modify the graphs safely. For example by increasing the penalty of a node /// AstarPath.active.data.gridGraph.GetNode(0, 0).Penalty += 1000; /// /// // Allow pathfinding to resume /// graphLock.Release(); /// /// /// Returns: A lock object. You need to call on that object to allow pathfinding to resume. /// Note: In most cases this should not be called from user code. Use the method instead. /// /// See: /// public PathProcessor.GraphUpdateLock PausePathfinding () { // Ensure there are no jobs running that might read or write graph data, // as this method is typically used right before one modifies graph data. graphDataLock.WriteSync().Unlock(); return pathProcessor.PausePathfinding(true); } /// /// Blocks the path queue so that e.g work items can be performed. /// /// Pathfinding threads will stop accepting new path requests and will finish the ones they are currently calculating asynchronously. /// When the lock is released, the pathfinding threads will resume as normal. /// /// Note: You are unlikely to need to use this method. It is primarily for internal use. /// public PathProcessor.GraphUpdateLock PausePathfindingSoon () { return pathProcessor.PausePathfinding(false); } /// Blocks until the currently running async scan (if any) has completed void BlockUntilAsyncScanComplete () { // We can't block and wait for the async scan, so we have to spin. // Not great, but this is not something that should happen during normal gameplay. // It's more a fallback if the user doesn't wait for the async scan to complete before starting a new one. // Note: The ProgressScanningIteratorsConcurrently method used internally by the scan will ensure // that the thread yields its time slice in case it's just waiting for other threads. while (asyncScanTask != null && asyncScanTask.MoveNext()) {} asyncScanTask = null; } /// /// Scans a particular graph. /// Calling this method will recalculate the specified graph from scratch. /// This method is pretty slow (depending on graph type and graph complexity of course), so it is advisable to use /// smaller graph updates whenever possible. /// /// /// // Recalculate all graphs /// AstarPath.active.Scan(); /// /// // Recalculate only the first grid graph /// var graphToScan = AstarPath.active.data.gridGraph; /// AstarPath.active.Scan(graphToScan); /// /// // Recalculate only the first and third graphs /// var graphsToScan = new [] { AstarPath.active.data.graphs[0], AstarPath.active.data.graphs[2] }; /// AstarPath.active.Scan(graphsToScan); /// /// /// See: graph-updates (view in online documentation for working links) /// See: ScanAsync /// public void Scan (NavGraph graphToScan) { if (graphToScan == null) throw new System.ArgumentNullException(); Scan(new NavGraph[] { graphToScan }); } /// /// Scans all specified graphs. /// /// Calling this method will recalculate all specified graphs (or all graphs if the graphsToScan parameter is null) from scratch. /// This method is pretty slow (depending on graph type and graph complexity of course), so it is advisable to use /// smaller graph updates whenever possible. /// /// /// // Recalculate all graphs /// AstarPath.active.Scan(); /// /// // Recalculate only the first grid graph /// var graphToScan = AstarPath.active.data.gridGraph; /// AstarPath.active.Scan(graphToScan); /// /// // Recalculate only the first and third graphs /// var graphsToScan = new [] { AstarPath.active.data.graphs[0], AstarPath.active.data.graphs[2] }; /// AstarPath.active.Scan(graphsToScan); /// /// /// See: graph-updates (view in online documentation for working links) /// See: ScanAsync /// /// The graphs to scan. If this parameter is null then all graphs will be scanned public void Scan (NavGraph[] graphsToScan = null) { var prevStage = (ScanningStage)(-1); if (asyncScanTask != null) { Debug.LogWarning("An async scan was already running when a new scan was requested. Blocking until it is complete. You can check if a scan is currently in progress using the AstarPath.active.isScanning property.", this); BlockUntilAsyncScanComplete(); } Profiler.BeginSample("Scan"); Profiler.BeginSample("Init"); foreach (var p in ScanInternal(graphsToScan, false)) { if (prevStage != p.stage) { Profiler.EndSample(); Profiler.BeginSample(p.stage.ToString()); #if !NETFX_CORE && UNITY_EDITOR // Log progress to the console System.Console.WriteLine(p.stage); #endif prevStage = p.stage; } } Profiler.EndSample(); Profiler.EndSample(); } /// /// Scans a particular graph asynchronously. This is a IEnumerable, you can loop through it to get the progress /// /// You can scan graphs asyncronously by yielding when you iterate through the returned IEnumerable. /// Note that this does not guarantee a good framerate, but it will allow you /// to at least show a progress bar while scanning. /// /// /// IEnumerator Start () { /// foreach (Progress progress in AstarPath.active.ScanAsync()) { /// Debug.Log("Scanning... " + progress.ToString()); /// yield return null; /// } /// } /// /// /// See: Scan /// public IEnumerable ScanAsync (NavGraph graphToScan) { if (graphToScan == null) throw new System.ArgumentNullException(); return ScanAsync(new NavGraph[] { graphToScan }); } /// /// Scans all specified graphs asynchronously. This is a IEnumerable, you can loop through it to get the progress /// /// You can scan graphs asyncronously by yielding when you loop through the progress. /// Note that this does not guarantee a good framerate, but it will allow you /// to at least show a progress bar during scanning. /// /// /// IEnumerator Start () { /// foreach (Progress progress in AstarPath.active.ScanAsync()) { /// Debug.Log("Scanning... " + progress.ToString()); /// yield return null; /// } /// } /// /// /// Note: If the graphs are already scanned, doing an async scan will temporarily cause increased memory usage, since two copies of the graphs will be kept in memory during the async scan. /// This may not be desirable on some platforms. A non-async scan will not cause this temporary increased memory usage. /// /// See: Scan /// /// The graphs to scan. If this parameter is null then all graphs will be scanned public IEnumerable ScanAsync (NavGraph[] graphsToScan = null) { if (asyncScanTask != null) { Debug.LogWarning("An async scan was already running when a new async scan was requested. Blocking until the previous one is complete. You can check if a scan is currently in progress using the AstarPath.active.isScanning property.", this); BlockUntilAsyncScanComplete(); } asyncScanTask = ScanInternal(graphsToScan, true).GetEnumerator(); // We cannot inline the TickAsyncScanUntilCompletion function, because we want *this* function to // not be a coroutine, so that the setup runs immediately when calling ScanAsync, // instead of defering until the coroutine is ticked for the first time. // We tick the coroutine once here to do some inital setup. // This includes setting isScanning to true. try { asyncScanTask.MoveNext(); } catch { asyncScanTask = null; throw; } return TickAsyncScanUntilCompletion(asyncScanTask); } IEnumerable TickAsyncScanUntilCompletion (IEnumerator task) { while (true) { try { if (!task.MoveNext()) break; } catch { if (asyncScanTask == task) asyncScanTask = null; throw; } yield return task.Current; } if (asyncScanTask == task) asyncScanTask = null; } class DummyGraphUpdateContext : IGraphUpdateContext { public void DirtyBounds (Bounds bounds) {} } class DestroyGraphPromise : IGraphUpdatePromise { public IGraphInternals graph; public IEnumerator Prepare () { return null; } public void Apply (IGraphUpdateContext context) { graph.DestroyAllNodes(); } } IEnumerable ScanInternal (NavGraph[] graphsToScan, bool async) { if (graphsToScan == null) graphsToScan = graphs; if (graphsToScan == null || graphsToScan.Length == 0) { yield break; } // Guard to ensure the A* object is always enabled if the graphs have any valid data. // This is because otherwise the OnDisable method will not be called and some unmanaged data // in NativeArrays may end up leaking. if (!enabled) throw new System.InvalidOperationException("The AstarPath object must be enabled to scan graphs"); if (active != this) throw new System.InvalidOperationException("The AstarPath object is not enabled in a scene"); isScanning = true; var graphUpdateLock = PausePathfinding(); // Make sure all paths that are in the queue to be returned // are returned immediately // Some modifiers (e.g the funnel modifier) rely on // the nodes being valid when the path is returned pathReturnQueue.ReturnPaths(false); // Ensure all graph updates that are in progress get completed immediately. // Graph updates that are in progress may use graph data, and we don't want to re-scan the graphs under their feet. workItems.ProcessWorkItemsForScan(true); if (!Application.isPlaying) { data.FindGraphTypes(); GraphModifier.FindAllModifiers(); } yield return new Progress(0.05F, ScanningStage.PreProcessingGraphs); using (var writeLock2 = graphDataLock.WriteSync()) { try { if (OnPreScan != null) { OnPreScan(this); } GraphModifier.TriggerEvent(GraphModifier.EventType.PreScan); GraphModifier.TriggerEvent(GraphModifier.EventType.PreUpdate); } catch { isScanning = false; graphUpdateLock.Release(); throw; } } data.LockGraphStructure(); // Make sure the physics engine data is up to date. // Scanning graphs may use physics methods and it is very confusing if they // do not always pick up the latest changes made to the scene. Physics.SyncTransforms(); Physics2D.SyncTransforms(); var watch = System.Diagnostics.Stopwatch.StartNew(); // Destroy previous nodes, unless we are doing an async scan. // We do not want the graphs to be in an invalid state during the async scan, // so we cannot eagerly destroy them here. // This means that during an async scan we may have two copies of the graphs in memory. // Most of the data will be destroyed at the end of the async scan, but some memory will // still be reserved. So a non-async scan is more memory efficient. if (!async) { using (var writeLock2 = graphDataLock.WriteSync()) { Profiler.BeginSample("Destroy previous nodes"); for (int i = 0; i < graphsToScan.Length; i++) { if (graphsToScan[i] != null) { ((IGraphInternals)graphsToScan[i]).DestroyAllNodes(); } } Profiler.EndSample(); } } if (OnGraphPreScan != null) { using (var writeLock2 = graphDataLock.WriteSync()) { try { for (int i = 0; i < graphsToScan.Length; i++) { if (graphsToScan[i] != null) OnGraphPreScan(graphsToScan[i]); } } catch { isScanning = false; data.UnlockGraphStructure(); graphUpdateLock.Release(); throw; } } } // Loop through all graphs and start scanning them var promises = new List<(IGraphUpdatePromise, IEnumerator)>(graphsToScan.Length); for (int i = 0; i < graphsToScan.Length; i++) { if (graphsToScan[i] != null) { var promise = ((IGraphInternals)graphsToScan[i]).ScanInternal(async) ?? new DestroyGraphPromise { graph = (IGraphInternals)graphsToScan[i] }; var iterator = promise.Prepare(); promises.Add((promise, iterator)); } } // Scan all graphs concurrently by progressing all scanning iterators. // If the graphs use the job system internally (like the grid, recast and navmesh graphs), // then multiple graphs will even be scanned in parallel. while (true) { int firstNonFinished; try { firstNonFinished = GraphUpdateProcessor.PrepareGraphUpdatePromises(promises, async ? TimeSlice.MillisFromNow(2) : TimeSlice.Infinite); } catch { isScanning = false; data.UnlockGraphStructure(); graphUpdateLock.Release(); throw; } if (firstNonFinished == -1) { break; } else { // Just used for progress information // This graph will advance the progress bar from minp to maxp float meanProgress = 0; for (int i = 0; i < promises.Count; i++) meanProgress += promises[i].Item1.Progress; meanProgress /= promises.Count; yield return new Progress(Mathf.Lerp(0.1f, 0.8f, meanProgress), ScanningStage.ScanningGraph, firstNonFinished, promises.Count); } } yield return new Progress(0.95f, ScanningStage.FinishingScans); // Now we proceed with the last step of each graph's scanning process // This part will make the results of the scan visible to the rest of the game. // As a consequence, we must make sure to *not* yield anymore after this point, // since that would make the rest of the game run while the graphs may be in an invalid state. var writeLock = graphDataLock.WriteSync(); var ctx = new DummyGraphUpdateContext(); try { GraphUpdateProcessor.ApplyGraphUpdatePromises(promises, ctx); } catch { isScanning = false; data.UnlockGraphStructure(); graphUpdateLock.Release(); writeLock.Unlock(); throw; } for (int i = 0; i < graphsToScan.Length; i++) { if (graphsToScan[i] != null) { if (OnGraphPostScan != null) { try { OnGraphPostScan(graphsToScan[i]); } catch { isScanning = false; data.UnlockGraphStructure(); graphUpdateLock.Release(); writeLock.Unlock(); throw; } } // Notify the off mesh links subsystem that graphs have been recalculated, and we may need to recalculate off mesh links. // But skip this for the link graph, since that's the graph that holds the off mesh link nodes themselves. if (!(graphsToScan[i] is LinkGraph)) offMeshLinks.DirtyBounds(graphsToScan[i].bounds); } } // Unlock the graph structure here so that e.g. off-mesh-links can add the point graph required for them to work data.UnlockGraphStructure(); try { // Graph Modifiers and the OnGraphsUpdated callback may modify graphs arbitrarily, so this also needs to be inside the write lock if (OnPostScan != null) OnPostScan(this); GraphModifier.TriggerEvent(GraphModifier.EventType.PostScan); } catch { isScanning = false; graphUpdateLock.Release(); writeLock.Unlock(); throw; } // This lock may not be held if there are no work items pending if (workItemLock.Held) { Profiler.BeginSample("Work Items"); // Note that this never sends PostUpdate (or similar) events. Those are sent below instead. workItems.ProcessWorkItemsForScan(true); Profiler.EndSample(); workItemLock.Release(); } offMeshLinks.Refresh(); GraphModifier.TriggerEvent(GraphModifier.EventType.PostUpdateBeforeAreaRecalculation); // Recalculate connected components synchronously hierarchicalGraph.RecalculateIfNecessary(); // Scanning a graph *is* a type of update GraphModifier.TriggerEvent(GraphModifier.EventType.PostUpdate); if (OnGraphsUpdated != null) { try { OnGraphsUpdated(this); } catch { isScanning = false; graphUpdateLock.Release(); writeLock.Unlock(); throw; } } // Signal that we have stopped scanning here isScanning = false; try { if (OnLatePostScan != null) OnLatePostScan(this); GraphModifier.TriggerEvent(GraphModifier.EventType.LatePostScan); } catch { graphUpdateLock.Release(); writeLock.Unlock(); throw; } writeLock.Unlock(); euclideanEmbedding.dirty = true; euclideanEmbedding.RecalculatePivots(); // Perform any blocking actions FlushWorkItems(); // Resume pathfinding threads graphUpdateLock.Release(); watch.Stop(); lastScanTime = (float)watch.Elapsed.TotalSeconds; if (logPathResults != PathLog.None && logPathResults != PathLog.OnlyErrors) { Debug.Log("Scanned graphs in " + (lastScanTime*1000).ToString("0") + " ms"); } } #endregion internal void DirtyBounds (Bounds bounds) { offMeshLinks.DirtyBounds(bounds); workItems.DirtyGraphs(); } private static int waitForPathDepth = 0; /// /// Blocks until the path has been calculated. /// /// Normally it takes a few frames for a path to be calculated and returned. /// This function will ensure that the path will be calculated when this function returns /// and that the callback for that path has been called. /// /// If requesting a lot of paths in one go and waiting for the last one to complete, /// it will calculate most of the paths in the queue (only most if using multithreading, all if not using multithreading). /// /// Use this function only if you really need to. /// There is a point to spreading path calculations out over several frames. /// It smoothes out the framerate and makes sure requesting a large /// number of paths at the same time does not cause lag. /// /// Note: Graph updates and other callbacks might get called during the execution of this function. /// /// When the pathfinder is shutting down. I.e in OnDestroy, this function will not do anything. /// /// Throws: Exception if pathfinding is not initialized properly for this scene (most likely no AstarPath object exists) /// or if the path has not been started yet. /// Also throws an exception if critical errors occur such as when the pathfinding threads have crashed (which should not happen in normal cases). /// This prevents an infinite loop while waiting for the path. /// /// See: Pathfinding.Path.WaitForPath /// See: Pathfinding.Path.BlockUntilCalculated /// /// The path to wait for. The path must be started, otherwise an exception will be thrown. public static void BlockUntilCalculated (Path path) { if (active == null) throw new System.Exception("Pathfinding is not correctly initialized in this scene (yet?). " + "AstarPath.active is null.\nDo not call this function in Awake"); if (path == null) throw new System.ArgumentNullException(nameof(path)); if (active.pathProcessor.queue.isClosed) return; if (path.PipelineState == PathState.Created) { throw new System.Exception("The specified path has not been started yet."); } waitForPathDepth++; if (waitForPathDepth == 5) { Debug.LogError("You are calling the BlockUntilCalculated function recursively (maybe from a path callback). Please don't do this."); } if (path.PipelineState < PathState.ReturnQueue) { if (active.IsUsingMultithreading) { while (path.PipelineState < PathState.ReturnQueue) { if (active.pathProcessor.queue.isClosed) { waitForPathDepth--; throw new System.Exception("Pathfinding Threads seem to have crashed."); } // Wait for threads to calculate paths Thread.Sleep(1); active.PerformBlockingActions(true); } } else { while (path.PipelineState < PathState.ReturnQueue) { if (active.pathProcessor.queue.isEmpty && path.PipelineState != PathState.Processing) { waitForPathDepth--; throw new System.Exception("Critical error. Path Queue is empty but the path state is '" + path.PipelineState + "'"); } // Calculate some paths active.pathProcessor.TickNonMultithreaded(); active.PerformBlockingActions(true); } } } active.pathReturnQueue.ReturnPaths(false); waitForPathDepth--; } /// /// Adds the path to a queue so that it will be calculated as soon as possible. /// The callback specified when constructing the path will be called when the path has been calculated. /// Usually you should use the Seeker component instead of calling this function directly. /// /// /// // There must be an AstarPath instance in the scene /// if (AstarPath.active == null) return; /// /// // We can calculate multiple paths asynchronously /// for (int i = 0; i < 10; i++) { /// var path = ABPath.Construct(transform.position, transform.position+transform.forward*i*10, OnPathComplete); /// /// // Calculate the path by using the AstarPath component directly /// AstarPath.StartPath(path); /// } /// /// /// The path that should be enqueued. /// If true, the path will be pushed to the front of the queue, bypassing all waiting paths and making it the next path to be calculated. /// This can be useful if you have a path which you want to prioritize over all others. Be careful to not overuse it though. /// If too many paths are put in the front of the queue often, this can lead to normal paths having to wait a very long time before being calculated. /// Typically path.BlockUntilCalculated will be called when not in play mode. However, the play mode check will not work if /// you call this from a separate thread, or a job. In that case you can set this to true to skip the check. public static void StartPath (Path path, bool pushToFront = false, bool assumeInPlayMode = false) { // Copy to local variable to avoid multithreading issues var astar = active; if (System.Object.ReferenceEquals(astar, null)) { Debug.LogError("There is no AstarPath object in the scene or it has not been initialized yet"); return; } if (path.PipelineState != PathState.Created) { throw new System.Exception("The path has an invalid state. Expected " + PathState.Created + " found " + path.PipelineState + "\n" + "Make sure you are not requesting the same path twice"); } if (astar.pathProcessor.queue.isClosed) { path.FailWithError("No new paths are accepted"); return; } if (astar.graphs == null || astar.graphs.Length == 0) { Debug.LogError("There are no graphs in the scene"); path.FailWithError("There are no graphs in the scene"); Debug.LogError(path.errorLog); return; } path.Claim(astar); // Will increment p.state to PathState.PathQueue ((IPathInternals)path).AdvanceState(PathState.PathQueue); if (pushToFront) { astar.pathProcessor.queue.PushFront(path); } else { astar.pathProcessor.queue.Push(path); } // Outside of play mode, all path requests are synchronous. // However, inside a job we cannot check this, because Unity will throw an exception. // But luckily pretty much all jobs will run in game mode anyway. So we assume that if we are in a job, we are in game mode. if (!assumeInPlayMode && !Unity.Jobs.LowLevel.Unsafe.JobsUtility.IsExecutingJob && !Application.isPlaying) { BlockUntilCalculated(path); } } /// /// Cached NNConstraint to avoid unnecessary allocations. /// This should ideally be fixed by making NNConstraint an immutable class/struct. /// internal static readonly NNConstraint NNConstraintClosestAsSeenFromAbove = new NNConstraint() { constrainWalkability = false, constrainTags = false, constrainDistance = true, distanceMetric = DistanceMetric.ClosestAsSeenFromAbove(), }; /// /// True if the point is on a walkable part of the navmesh, as seen from above. /// /// A point is considered on the navmesh if it is above or below a walkable navmesh surface, at any distance, /// and if it is not above/below a closer unwalkable node. /// /// Note: This means that, for example, in multi-story building a point will be considered on the navmesh if any walkable floor is below or above the point. /// If you want more complex behavior then you can use the GetNearest method together with the appropriate settings for your use case. /// /// This uses the graph's natural up direction to determine which way is up. /// Therefore, it will also work on rotated graphs, as well as graphs in 2D mode. /// /// This method works for all graph types. /// However, for s, this will never return true unless you pass in the exact coordinate of a node, since point nodes do not have a surface. /// /// Note: For spherical navmeshes (or other weird shapes), this method will not work as expected, as there's no well defined "up" direction. /// /// [Open online documentation to see images] /// /// See: to check if a point is on the navmesh of a specific graph. /// /// The point to check public bool IsPointOnNavmesh (Vector3 position) { // We use the None constraint, instead of Walkable, to avoid ignoring unwalkable nodes that are closer to the point. var nearest = GetNearest(position, NNConstraintClosestAsSeenFromAbove); const float MaxHorizontalDistance = 0.01f; const float MaxCostSqr = MaxHorizontalDistance * MaxHorizontalDistance; // TODO: Set a distance threshold in the NNConstraint, to optimize it return nearest.node != null && nearest.node.Walkable && nearest.distanceCostSqr < MaxCostSqr; } /// /// Returns the nearest node to a position. /// This method will search through all graphs and query them for the closest node to this position, and then it will return the closest one of those. /// /// Equivalent to GetNearest(position, NNConstraint.None). /// /// /// // Find the closest node to this GameObject's position /// GraphNode node = AstarPath.active.GetNearest(transform.position).node; /// /// if (node.Walkable) { /// // Yay, the node is walkable, we can place a tower here or something /// } /// /// /// See: Pathfinding.NNConstraint /// public NNInfo GetNearest (Vector3 position) { return GetNearest(position, null); } /// /// Returns the nearest node to a point using the specified NNConstraint. /// /// Searches through all graphs for their nearest nodes to the specified position and picks the closest one. /// The NNConstraint can be used to specify constraints on which nodes can be chosen such as only picking walkable nodes. /// /// /// GraphNode node = AstarPath.active.GetNearest(transform.position, NNConstraint.Walkable).node; /// /// /// /// var constraint = NNConstraint.None; /// /// // Constrain the search to walkable nodes only /// constraint.constrainWalkability = true; /// constraint.walkable = true; /// /// // Constrain the search to only nodes with tag 3 or tag 5 /// // The 'tags' field is a bitmask /// constraint.constrainTags = true; /// constraint.tags = (1 << 3) | (1 << 5); /// /// var info = AstarPath.active.GetNearest(transform.position, constraint); /// var node = info.node; /// var closestPoint = info.position; /// /// /// See: /// /// The point to find nodes close to /// The constraint which determines which graphs and nodes are acceptable to search on. May be null, in which case all nodes will be considered acceptable. public NNInfo GetNearest (Vector3 position, NNConstraint constraint) { // Cache property lookups var graphs = this.graphs; var maxNearestNodeDistanceSqr = constraint == null || constraint.constrainDistance ? this.maxNearestNodeDistanceSqr : float.PositiveInfinity; NNInfo nearestNode = NNInfo.Empty; if (graphs == null || graphs.Length == 0) return nearestNode; // Use a fast path in case there is only one graph. // This improves performance by about 10% when there is only one graph. if (graphs.Length == 1) { var graph = graphs[0]; if (graph == null || (constraint != null && !constraint.SuitableGraph(0, graph))) { return nearestNode; } nearestNode = graph.GetNearest(position, constraint, maxNearestNodeDistanceSqr); UnityEngine.Assertions.Assert.IsTrue(nearestNode.node == null || nearestNode.distanceCostSqr <= maxNearestNodeDistanceSqr); } else { UnsafeSpan<(float, int)> distances; unsafe { // The number of graphs is limited to GraphNode.MaxGraphIndex (256), // and typically there are only a few graphs, so allocating this on the stack is fine. var distancesPtr = stackalloc (float, int)[graphs.Length]; distances = new UnsafeSpan<(float, int)>(distancesPtr, graphs.Length); } // Iterate through all graphs and find a lower bound on the distance to the nearest node. // We then sort these distances and run the full get nearest search on the graphs in order of increasing distance. // This is an optimization to avoid running the full get nearest search on graphs which are far away. int numCandidateGraphs = 0; for (int i = 0; i < graphs.Length; i++) { NavGraph graph = graphs[i]; // Check if this graph should be searched if (graph == null || (constraint != null && !constraint.SuitableGraph(i, graph))) { continue; } var lowerBound = graph.NearestNodeDistanceSqrLowerBound(position, constraint); if (lowerBound > maxNearestNodeDistanceSqr) continue; distances[numCandidateGraphs++] = (lowerBound, i); } distances = distances.Slice(0, numCandidateGraphs); distances.Sort(); for (int i = 0; i < distances.Length; i++) { if (distances[i].Item1 > maxNearestNodeDistanceSqr) break; var graph = graphs[distances[i].Item2]; NNInfo nnInfo = graph.GetNearest(position, constraint, maxNearestNodeDistanceSqr); if (nnInfo.distanceCostSqr < maxNearestNodeDistanceSqr) { maxNearestNodeDistanceSqr = nnInfo.distanceCostSqr; nearestNode = nnInfo; } } } return nearestNode; } /// /// True if there is an obstacle between start and end on the navmesh. /// /// This is a simple api to check if there is an obstacle between two points. /// If you need more detailed information, you can use or (for navmesh/recast graphs). /// Those overloads can also return which nodes the line passed through, and allow you use custom node filtering. /// /// /// var start = transform.position; /// var end = start + Vector3.forward * 10; /// if (AstarPath.active.Linecast(start, end)) { /// Debug.DrawLine(start, end, Color.red); /// } else { /// Debug.DrawLine(start, end, Color.green); /// } /// /// /// Note: Only grid, recast and navmesh graphs support linecasts. The closest raycastable graph to the start point will be used for the linecast. /// Note: Linecasts cannot pass through off-mesh links. /// /// See: /// See: /// See: /// See: linecasting (view in online documentation for working links), for more details about linecasting /// public bool Linecast (Vector3 start, Vector3 end) { var startGraph = ClosestRaycastableGraph(start); return startGraph == null || startGraph.Linecast(start, end); } /// /// True if there is an obstacle between start and end on the navmesh. /// /// This is a simple api to check if there is an obstacle between two points. /// If you need more detailed information, you can use or (for navmesh/recast graphs). /// Those overloads can also return which nodes the line passed through, and allow you use custom node filtering. /// /// /// var start = transform.position; /// var end = start + Vector3.forward * 10; /// if (AstarPath.active.Linecast(start, end, out var hit)) { /// Debug.DrawLine(start, end, Color.red); /// Debug.DrawRay(hit.point, Vector3.up, Color.red); /// } else { /// Debug.DrawLine(start, end, Color.green); /// } /// /// /// Note: Only grid, recast and navmesh graphs support linecasts. The closest raycastable graph to the start point will be used for the linecast. /// Note: Linecasts cannot pass through off-mesh links. /// /// See: /// See: /// See: /// See: linecasting (view in online documentation for working links), for more details about linecasting /// public bool Linecast (Vector3 start, Vector3 end, out GraphHitInfo hit) { var startGraph = ClosestRaycastableGraph(start); if (startGraph == null) { hit = new GraphHitInfo { origin = start, point = start, }; return true; } return startGraph.Linecast(start, end, out hit); } IRaycastableGraph ClosestRaycastableGraph (Vector3 point) { if (data.graphs == null) return null; // Most games have just a single raycastable graph. IRaycastableGraph graph = null; int found = 0; for (int i = 0; i < data.graphs.Length; i++) { if (data.graphs[i] is IRaycastableGraph g) { graph = g; found++; } } // If there's more than one graph that can perform linecasts, // then find the nearest graph to the point. if (found > 1) { var startNode = GetNearest(point); graph = startNode.node?.Graph as IRaycastableGraph; } return graph; } /// /// Returns the node closest to the ray (slow). /// Warning: This function is brute-force and very slow, use with caution /// public GraphNode GetNearest (Ray ray) { if (graphs == null) return null; float minDist = Mathf.Infinity; GraphNode nearestNode = null; Vector3 lineDirection = ray.direction; Vector3 lineOrigin = ray.origin; for (int i = 0; i < graphs.Length; i++) { NavGraph graph = graphs[i]; graph.GetNodes(node => { Vector3 pos = (Vector3)node.position; Vector3 p = lineOrigin+(Vector3.Dot(pos-lineOrigin, lineDirection)*lineDirection); float tmp = Mathf.Abs(p.x-pos.x); tmp *= tmp; if (tmp > minDist) return; tmp = Mathf.Abs(p.z-pos.z); tmp *= tmp; if (tmp > minDist) return; float dist = (p-pos).sqrMagnitude; if (dist < minDist) { minDist = dist; nearestNode = node; } }); } return nearestNode; } /// /// Captures a snapshot of a part of the graphs, to allow restoring it later. /// /// This is useful if you want to do a graph update, but you want to be able to restore the graph to the previous state. /// /// The snapshot will capture enough information to restore the graphs, assuming the world only changed within the given bounding box. /// This means the captured region may be larger than the bounding box. /// /// Limitations: /// - Currently, the and supports snapshots. Other graph types do not support it. /// - The graph must not change its dimensions or other core parameters between the time the snapshot is taken and the time it is restored. /// - Custom node connections may not be preserved. Unless they are added as off-mesh links using e.g. a component. /// - The snapshot must not be captured during a work item, graph update or when the graphs are being scanned, as the graphs may not be in a consistent state during those times. /// /// See: , which uses this method internally. /// See: /// /// Note: You must dispose the returned snapshot when you are done with it, to avoid leaking memory. /// public GraphSnapshot Snapshot (Bounds bounds, GraphMask graphMask) { Profiler.BeginSample("Capturing Graph Snapshot"); var inner = new List(); for (int i = 0; i < graphs.Length; i++) { if (graphs[i] != null && graphMask.Contains(i)) { var s = graphs[i].Snapshot(bounds); if (s != null) inner.Add(s); } } Profiler.EndSample(); return new GraphSnapshot(inner); } /// /// Allows you to access read-only graph data in jobs safely. /// /// You can for example use AstarPath.active.GetNearest(...) in a job. /// /// Using is always safe to use in jobs even without calling this method. /// /// When a graph update, work item, or graph scan would start, it will first block on the given dependency /// to ensure no race conditions occur. /// /// If you do not call this method, then a graph update might start in the middle of your job, causing race conditions /// and all manner of other hard-to-diagnose bugs. /// /// /// var readLock = AstarPath.active.LockGraphDataForReading(); /// var handle = new MyJob { /// // ... /// }.Schedule(readLock.dependency); /// readLock.UnlockAfter(handle); /// /// /// See: /// See: /// public RWLock.ReadLockAsync LockGraphDataForReading() => graphDataLock.Read(); /// /// Aquires an exclusive lock on the graph data asynchronously. /// This is used when graphs want to modify graph data. /// /// This is a low-level primitive, usually you do not need to use this method. /// /// /// var readLock = AstarPath.active.LockGraphDataForReading(); /// var handle = new MyJob { /// // ... /// }.Schedule(readLock.dependency); /// readLock.UnlockAfter(handle); /// /// /// See: /// See: /// public RWLock.WriteLockAsync LockGraphDataForWriting() => graphDataLock.Write(); /// /// Aquires an exclusive lock on the graph data. /// This is used when graphs want to modify graph data. /// /// This is a low-level primitive, usually you do not need to use this method. /// /// /// var readLock = AstarPath.active.LockGraphDataForReading(); /// var handle = new MyJob { /// // ... /// }.Schedule(readLock.dependency); /// readLock.UnlockAfter(handle); /// /// /// See: /// See: /// public RWLock.LockSync LockGraphDataForWritingSync() => graphDataLock.WriteSync(); /// /// Obstacle data for navmesh edges. /// /// This can be used to get information about the edge/borders of the navmesh. /// It can also be queried in burst jobs. Just make sure you release the read lock after you are done with it. /// /// Note: This is not a method that you are likely to need to use. /// It is used internally for things like local avoidance. /// public NavmeshEdges.NavmeshBorderData GetNavmeshBorderData(out RWLock.CombinedReadLockAsync readLock) => hierarchicalGraph.navmeshEdges.GetNavmeshEdgeData(out readLock); }