| @@ -0,0 +1,4 @@ | ||
|
|
||
| // This file has been removed from the project. Since UnityPackages cannot | ||
| // delete files, only replace them, this message is left here to prevent old | ||
| // files from causing compiler errors |
| @@ -0,0 +1,360 @@ | ||
| using UnityEngine; | ||
|
|
||
| namespace Pathfinding { | ||
| [AddComponentMenu("Pathfinding/GraphUpdateScene")] | ||
| /** Helper class for easily updating graphs. | ||
| * | ||
| * The GraphUpdateScene component is really easy to use. Create a new empty GameObject and add the component to it, it can be found in Components-->Pathfinding-->GraphUpdateScene.\n | ||
| * When you have added the component, you should see something like the image below. | ||
| * \shadowimage{graphUpdateScene.png} | ||
| * The area which the component will affect is defined by creating a polygon in the scene. | ||
| * If you make sure you have the Position tool enabled (top-left corner of the Unity window) you can shift-click in the scene view to add more points to the polygon. | ||
| * You can remove points using shift-alt-click. By clicking on the points you can bring up a positioning tool. You can also open the "points" array in the inspector to set each point's coordinates. | ||
| * \shadowimage{graphUpdateScenePoly.png} | ||
| * In the inspector there are a number of variables. The first one is named "Convex", it sets if the convex hull of the points should be calculated or if the polygon should be used as-is. | ||
| * Using the convex hull is faster when applying the changes to the graph, but with a non-convex polygon you can specify more complicated areas.\n | ||
| * The next two variables, called "Apply On Start" and "Apply On Scan" determine when to apply the changes. If the object is in the scene from the beginning, both can be left on, it doesn't | ||
| * matter since the graph is also scanned at start. However if you instantiate it later in the game, you can make it apply it's setting directly, or wait until the next scan (if any). | ||
| * If the graph is rescanned, all GraphUpdateScene components which have the Apply On Scan variable toggled will apply their settings again to the graph since rescanning clears all previous changes.\n | ||
| * You can also make it apply it's changes using scripting. | ||
| * \code GetComponent<GraphUpdateScene>().Apply (); \endcode | ||
| * The above code will make it apply it's changes to the graph (assuming a GraphUpdateScene component is attached to the same GameObject). | ||
| * | ||
| * Next there is "Modify Walkability" and "Set Walkability" (which appears when "Modify Walkability" is toggled). | ||
| * If Modify Walkability is set, then all nodes inside the area will either be set to walkable or unwalkable depending on the value of the "Set Walkability" variable. | ||
| * | ||
| * Penalty can also be applied to the nodes. A higher penalty (aka weight) makes the nodes harder to traverse so it will try to avoid those areas. | ||
| * | ||
| * The tagging variables can be read more about on this page: \ref tags "Working with tags". | ||
| */ | ||
| [HelpURL("http://arongranberg.com/astar/docs/class_pathfinding_1_1_graph_update_scene.php")] | ||
| public class GraphUpdateScene : GraphModifier { | ||
| /** Points which define the region to update */ | ||
| public Vector3[] points; | ||
|
|
||
| /** Private cached convex hull of the #points */ | ||
| private Vector3[] convexPoints; | ||
|
|
||
| [HideInInspector] | ||
| /** Use the convex hull (XZ space) of the points. */ | ||
| public bool convex = true; | ||
|
|
||
| [HideInInspector] | ||
| /** Minumum height of the bounds of the resulting Graph Update Object. | ||
| * Useful when all points are laid out on a plane but you still need a bounds with a height greater than zero since a | ||
| * zero height graph update object would usually result in no nodes being updated. | ||
| */ | ||
| public float minBoundsHeight = 1; | ||
|
|
||
| [HideInInspector] | ||
| /** Penalty to add to nodes. | ||
| * Be careful when setting negative values since if a node get's a negative penalty it will underflow and instead get | ||
| * really large. In most cases a warning will be logged if that happens. | ||
| */ | ||
| public int penaltyDelta; | ||
|
|
||
| [HideInInspector] | ||
| /** Set to true to set all targeted nodese walkability to #setWalkability */ | ||
| public bool modifyWalkability; | ||
|
|
||
| [HideInInspector] | ||
| /** See #modifyWalkability */ | ||
| public bool setWalkability; | ||
|
|
||
| [HideInInspector] | ||
| /** Apply this graph update object on start */ | ||
| public bool applyOnStart = true; | ||
|
|
||
| [HideInInspector] | ||
| /** Apply this graph update object whenever a graph is rescanned */ | ||
| public bool applyOnScan = true; | ||
|
|
||
| /** Use world space for coordinates. | ||
| * If true, the shape will not follow when moving around the transform. | ||
| * | ||
| * \see #ToggleUseWorldSpace | ||
| */ | ||
| [HideInInspector] | ||
| public bool useWorldSpace; | ||
|
|
||
| /** Update node's walkability and connectivity using physics functions. | ||
| * For grid graphs, this will update the node's position and walkability exactly like when doing a scan of the graph. | ||
| * If enabled for grid graphs, #modifyWalkability will be ignored. | ||
| * | ||
| * For Point Graphs, this will recalculate all connections which passes through the bounds of the resulting Graph Update Object | ||
| * using raycasts (if enabled). | ||
| * | ||
| */ | ||
| [HideInInspector] | ||
| public bool updatePhysics; | ||
|
|
||
| /** \copydoc Pathfinding::GraphUpdateObject::resetPenaltyOnPhysics */ | ||
| [HideInInspector] | ||
| public bool resetPenaltyOnPhysics = true; | ||
|
|
||
| /** \copydoc Pathfinding::GraphUpdateObject::updateErosion */ | ||
| [HideInInspector] | ||
| public bool updateErosion = true; | ||
|
|
||
| [HideInInspector] | ||
| /** Lock all points to Y = #lockToYValue */ | ||
| public bool lockToY; | ||
|
|
||
| [HideInInspector] | ||
| /** if #lockToY is enabled lock all points to this value */ | ||
| public float lockToYValue; | ||
|
|
||
| [HideInInspector] | ||
| /** If enabled, set all nodes' tags to #setTag */ | ||
| public bool modifyTag; | ||
|
|
||
| [HideInInspector] | ||
| /** If #modifyTag is enabled, set all nodes' tags to this value */ | ||
| public int setTag; | ||
|
|
||
| /** Private cached inversion of #setTag. | ||
| * Used for InvertSettings() */ | ||
| private int setTagInvert; | ||
|
|
||
| /** Has apply been called yet. | ||
| * Used to prevent applying twice when both applyOnScan and applyOnStart are enabled */ | ||
| private bool firstApplied; | ||
|
|
||
| /** Do some stuff at start */ | ||
| public void Start () { | ||
| //If firstApplied is true, that means the graph was scanned during Awake. | ||
| //So we shouldn't apply it again because then we would end up applying it two times | ||
| if (!firstApplied && applyOnStart) { | ||
| Apply(); | ||
| } | ||
| } | ||
|
|
||
| public override void OnPostScan () { | ||
| if (applyOnScan) Apply(); | ||
| } | ||
|
|
||
| /** Inverts all invertable settings for this GUS. | ||
| * Namely: penalty delta, walkability, tags. | ||
| * | ||
| * Penalty delta will be changed to negative penalty delta.\n | ||
| * #setWalkability will be inverted.\n | ||
| * #setTag will be stored in a private variable, and the new value will be 0. When calling this function again, the saved | ||
| * value will be the new value. | ||
| * | ||
| * Calling this function an even number of times without changing any settings in between will be identical to no change in settings. | ||
| */ | ||
| public virtual void InvertSettings () { | ||
| setWalkability = !setWalkability; | ||
| penaltyDelta = -penaltyDelta; | ||
| if (setTagInvert == 0) { | ||
| setTagInvert = setTag; | ||
| setTag = 0; | ||
| } else { | ||
| setTag = setTagInvert; | ||
| setTagInvert = 0; | ||
| } | ||
| } | ||
|
|
||
| /** Recalculate convex points. | ||
| * Will not do anything if not #convex is enabled | ||
| */ | ||
| public void RecalcConvex () { | ||
| convexPoints = convex ? Polygon.ConvexHullXZ(points) : null; | ||
| } | ||
|
|
||
| /** Switches between using world space and using local space. | ||
| * Changes point coordinates to stay the same in world space after the change. | ||
| * | ||
| * \see #useWorldSpace | ||
| */ | ||
| public void ToggleUseWorldSpace () { | ||
| useWorldSpace = !useWorldSpace; | ||
|
|
||
| if (points == null) return; | ||
|
|
||
| convexPoints = null; | ||
|
|
||
| Matrix4x4 matrix = useWorldSpace ? transform.localToWorldMatrix : transform.worldToLocalMatrix; | ||
|
|
||
| for (int i = 0; i < points.Length; i++) { | ||
| points[i] = matrix.MultiplyPoint3x4(points[i]); | ||
| } | ||
| } | ||
|
|
||
| /** Lock all points to a specific Y value. | ||
| * | ||
| * \see lockToYValue | ||
| */ | ||
| public void LockToY () { | ||
| if (points == null) return; | ||
|
|
||
| for (int i = 0; i < points.Length; i++) | ||
| points[i].y = lockToYValue; | ||
| } | ||
|
|
||
| /** Apply the update. | ||
| * Will only do anything if #applyOnScan is enabled */ | ||
| public void Apply (AstarPath active) { | ||
| if (applyOnScan) { | ||
| Apply(); | ||
| } | ||
| } | ||
|
|
||
| /** Calculates the bounds for this component. | ||
| * This is a relatively expensive operation, it needs to go through all points and | ||
| * sometimes do matrix multiplications. | ||
| */ | ||
| public Bounds GetBounds () { | ||
| Bounds b; | ||
|
|
||
| if (points == null || points.Length == 0) { | ||
| var coll = GetComponent<Collider>(); | ||
| var rend = GetComponent<Renderer>(); | ||
|
|
||
| if (coll != null) b = coll.bounds; | ||
| else if (rend != null) b = rend.bounds; | ||
| else { | ||
| //Debug.LogWarning ("Cannot apply GraphUpdateScene, no points defined and no renderer or collider attached"); | ||
| return new Bounds(Vector3.zero, Vector3.zero); | ||
| } | ||
| } else { | ||
| Matrix4x4 matrix = Matrix4x4.identity; | ||
|
|
||
| if (!useWorldSpace) { | ||
| matrix = transform.localToWorldMatrix; | ||
| } | ||
|
|
||
| Vector3 min = matrix.MultiplyPoint3x4(points[0]); | ||
| Vector3 max = matrix.MultiplyPoint3x4(points[0]); | ||
| for (int i = 0; i < points.Length; i++) { | ||
| Vector3 p = matrix.MultiplyPoint3x4(points[i]); | ||
| min = Vector3.Min(min, p); | ||
| max = Vector3.Max(max, p); | ||
| } | ||
|
|
||
| b = new Bounds((min+max)*0.5F, max-min); | ||
| } | ||
|
|
||
| if (b.size.y < minBoundsHeight) b.size = new Vector3(b.size.x, minBoundsHeight, b.size.z); | ||
| return b; | ||
| } | ||
|
|
||
| /** Updates graphs with a created GUO. | ||
| * Creates a Pathfinding.GraphUpdateObject with a Pathfinding.GraphUpdateShape | ||
| * representing the polygon of this object and update all graphs using AstarPath.UpdateGraphs. | ||
| * This will not update graphs directly. See AstarPath.UpdateGraph for more info. | ||
| */ | ||
| public void Apply () { | ||
| if (AstarPath.active == null) { | ||
| Debug.LogError("There is no AstarPath object in the scene"); | ||
| return; | ||
| } | ||
|
|
||
| GraphUpdateObject guo; | ||
|
|
||
| if (points == null || points.Length == 0) { | ||
| var coll = GetComponent<Collider>(); | ||
| var rend = GetComponent<Renderer>(); | ||
|
|
||
| Bounds b; | ||
| if (coll != null) b = coll.bounds; | ||
| else if (rend != null) b = rend.bounds; | ||
| else { | ||
| Debug.LogWarning("Cannot apply GraphUpdateScene, no points defined and no renderer or collider attached"); | ||
| return; | ||
| } | ||
|
|
||
| if (b.size.y < minBoundsHeight) b.size = new Vector3(b.size.x, minBoundsHeight, b.size.z); | ||
|
|
||
| guo = new GraphUpdateObject(b); | ||
| } else { | ||
| var shape = new GraphUpdateShape(); | ||
| shape.convex = convex; | ||
| Vector3[] worldPoints = points; | ||
| if (!useWorldSpace) { | ||
| worldPoints = new Vector3[points.Length]; | ||
| Matrix4x4 matrix = transform.localToWorldMatrix; | ||
| for (int i = 0; i < worldPoints.Length; i++) worldPoints[i] = matrix.MultiplyPoint3x4(points[i]); | ||
| } | ||
|
|
||
| shape.points = worldPoints; | ||
|
|
||
| Bounds b = shape.GetBounds(); | ||
| if (b.size.y < minBoundsHeight) b.size = new Vector3(b.size.x, minBoundsHeight, b.size.z); | ||
| guo = new GraphUpdateObject(b); | ||
| guo.shape = shape; | ||
| } | ||
|
|
||
| firstApplied = true; | ||
|
|
||
| guo.modifyWalkability = modifyWalkability; | ||
| guo.setWalkability = setWalkability; | ||
| guo.addPenalty = penaltyDelta; | ||
| guo.updatePhysics = updatePhysics; | ||
| guo.updateErosion = updateErosion; | ||
| guo.resetPenaltyOnPhysics = resetPenaltyOnPhysics; | ||
|
|
||
| guo.modifyTag = modifyTag; | ||
| guo.setTag = setTag; | ||
|
|
||
| AstarPath.active.UpdateGraphs(guo); | ||
| } | ||
|
|
||
| /** Draws some gizmos */ | ||
| public void OnDrawGizmos () { | ||
| OnDrawGizmos(false); | ||
| } | ||
|
|
||
| /** Draws some gizmos */ | ||
| public void OnDrawGizmosSelected () { | ||
| OnDrawGizmos(true); | ||
| } | ||
|
|
||
| /** Draws some gizmos */ | ||
| public void OnDrawGizmos (bool selected) { | ||
| Color c = selected ? new Color(227/255f, 61/255f, 22/255f, 1.0f) : new Color(227/255f, 61/255f, 22/255f, 0.9f); | ||
|
|
||
| if (selected) { | ||
| Gizmos.color = Color.Lerp(c, new Color(1, 1, 1, 0.2f), 0.9f); | ||
|
|
||
| Bounds b = GetBounds(); | ||
| Gizmos.DrawCube(b.center, b.size); | ||
| Gizmos.DrawWireCube(b.center, b.size); | ||
| } | ||
|
|
||
| if (points == null) return; | ||
|
|
||
| if (convex) { | ||
| c.a *= 0.5f; | ||
| } | ||
|
|
||
| Gizmos.color = c; | ||
|
|
||
| Matrix4x4 matrix = useWorldSpace ? Matrix4x4.identity : transform.localToWorldMatrix; | ||
|
|
||
| if (convex) { | ||
| c.r -= 0.1f; | ||
| c.g -= 0.2f; | ||
| c.b -= 0.1f; | ||
|
|
||
| Gizmos.color = c; | ||
| } | ||
|
|
||
| if (selected || !convex) { | ||
| for (int i = 0; i < points.Length; i++) { | ||
| Gizmos.DrawLine(matrix.MultiplyPoint3x4(points[i]), matrix.MultiplyPoint3x4(points[(i+1)%points.Length])); | ||
| } | ||
| } | ||
|
|
||
| if (convex) { | ||
| if (convexPoints == null) RecalcConvex(); | ||
|
|
||
| Gizmos.color = selected ? new Color(227/255f, 61/255f, 22/255f, 1.0f) : new Color(227/255f, 61/255f, 22/255f, 0.9f); | ||
|
|
||
| for (int i = 0; i < convexPoints.Length; i++) { | ||
| Gizmos.DrawLine(matrix.MultiplyPoint3x4(convexPoints[i]), matrix.MultiplyPoint3x4(convexPoints[(i+1)%convexPoints.Length])); | ||
| } | ||
| } | ||
| } | ||
| } | ||
| } |
| @@ -0,0 +1,79 @@ | ||
| using UnityEngine; | ||
|
|
||
| namespace Pathfinding { | ||
| /** Defines a shape for a Pathfinding.GraphUpdateObject. | ||
| * The shape consists of a number of points which it can either calculate the convex hull of (XZ space) or use as a polygon directly. | ||
| * \see Pathfinding.GraphUpdateObject.shape | ||
| */ | ||
| public class GraphUpdateShape { | ||
| Vector3[] _points; | ||
| Vector3[] _convexPoints; | ||
| bool _convex; | ||
|
|
||
| /** Gets or sets the points of the polygon in the shape. | ||
| * Will automatically calculate the convex hull if #convex is set to true */ | ||
| public Vector3[] points { | ||
| get { | ||
| return _points; | ||
| } | ||
| set { | ||
| _points = value; | ||
| if (convex) CalculateConvexHull(); | ||
| } | ||
| } | ||
|
|
||
| /** Sets if the convex hull of the points should be calculated. | ||
| * Convex hulls are faster but non-convex hulls can be used to specify the shape more exactly | ||
| */ | ||
| public bool convex { | ||
| get { | ||
| return _convex; | ||
| } | ||
| set { | ||
| if (_convex != value && value) { | ||
| _convex = value; | ||
| CalculateConvexHull(); | ||
| } else { | ||
| _convex = value; | ||
| } | ||
| } | ||
| } | ||
|
|
||
| private void CalculateConvexHull () { | ||
| if (points == null) { _convexPoints = null; return; } | ||
|
|
||
| _convexPoints = Polygon.ConvexHullXZ(points); | ||
| for (int i = 0; i < _convexPoints.Length; i++) { | ||
| Debug.DrawLine(_convexPoints[i], _convexPoints[(i+1) % _convexPoints.Length], Color.green); | ||
| } | ||
| } | ||
|
|
||
| public Bounds GetBounds () { | ||
| if (points == null || points.Length == 0) return new Bounds(); | ||
| Vector3 min = points[0]; | ||
| Vector3 max = points[0]; | ||
| for (int i = 0; i < points.Length; i++) { | ||
| min = Vector3.Min(min, points[i]); | ||
| max = Vector3.Max(max, points[i]); | ||
| } | ||
| return new Bounds((min+max)*0.5F, max-min); | ||
| } | ||
|
|
||
| public bool Contains (GraphNode node) { | ||
| return Contains((Vector3)node.position); | ||
| } | ||
|
|
||
| public bool Contains (Vector3 point) { | ||
| if (convex) { | ||
| if (_convexPoints == null) return false; | ||
|
|
||
| for (int i = 0, j = _convexPoints.Length-1; i < _convexPoints.Length; j = i, i++) { | ||
| if (VectorMath.RightOrColinearXZ(_convexPoints[i], _convexPoints[j], point)) return false; | ||
| } | ||
| return true; | ||
| } else { | ||
| return _points != null && Polygon.ContainsPointXZ (_points, point); | ||
| } | ||
| } | ||
| } | ||
| } |
| @@ -0,0 +1,123 @@ | ||
| using UnityEngine; | ||
| using System.Collections; | ||
| using System.Collections.Generic; | ||
|
|
||
| namespace Pathfinding { | ||
| [HelpURL("http://arongranberg.com/astar/docs/class_pathfinding_1_1_animation_link.php")] | ||
| public class AnimationLink : NodeLink2 { | ||
| public string clip; | ||
| public float animSpeed = 1; | ||
| public bool reverseAnim = true; | ||
|
|
||
| public GameObject referenceMesh; | ||
| public LinkClip[] sequence; | ||
| public string boneRoot = "bn_COG_Root"; | ||
|
|
||
| [System.Serializable] | ||
| public class LinkClip { | ||
| public AnimationClip clip; | ||
| public Vector3 velocity; | ||
| public int loopCount = 1; | ||
|
|
||
| public string name { | ||
| get { | ||
| return clip != null ? clip.name : ""; | ||
| } | ||
| } | ||
| } | ||
|
|
||
| static Transform SearchRec (Transform tr, string name) { | ||
| int childCount = tr.childCount; | ||
|
|
||
| for (int i = 0; i < childCount; i++) { | ||
| Transform ch = tr.GetChild(i); | ||
| if (ch.name == name) return ch; | ||
| else { | ||
| Transform rec = SearchRec(ch, name); | ||
| if (rec != null) return rec; | ||
| } | ||
| } | ||
| return null; | ||
| } | ||
|
|
||
| public void CalculateOffsets (List<Vector3> trace, out Vector3 endPosition) { | ||
| //Vector3 opos = transform.position; | ||
| endPosition = transform.position; | ||
| if (referenceMesh == null) return; | ||
|
|
||
| GameObject ob = GameObject.Instantiate(referenceMesh, transform.position, transform.rotation) as GameObject; | ||
| ob.hideFlags = HideFlags.HideAndDontSave; | ||
|
|
||
| Transform root = SearchRec(ob.transform, boneRoot); | ||
| if (root == null) throw new System.Exception("Could not find root transform"); | ||
|
|
||
| Animation anim = ob.GetComponent<Animation>(); | ||
| if (anim == null) anim = ob.AddComponent<Animation>(); | ||
|
|
||
| for (int i = 0; i < sequence.Length; i++) { | ||
| anim.AddClip(sequence[i].clip, sequence[i].clip.name); | ||
| } | ||
|
|
||
| Vector3 prevOffset = Vector3.zero; | ||
| Vector3 position = transform.position; | ||
| Vector3 firstOffset = Vector3.zero; | ||
|
|
||
| for (int i = 0; i < sequence.Length; i++) { | ||
| LinkClip c = sequence[i]; | ||
| if (c == null) { | ||
| endPosition = position; | ||
| return; | ||
| } | ||
|
|
||
| anim[c.clip.name].enabled = true; | ||
| anim[c.clip.name].weight = 1; | ||
|
|
||
| for (int repeat = 0; repeat < c.loopCount; repeat++) { | ||
| anim[c.clip.name].normalizedTime = 0; | ||
| anim.Sample(); | ||
| Vector3 soffset = root.position - transform.position; | ||
|
|
||
| if (i > 0) { | ||
| position += prevOffset - soffset; | ||
| } else { | ||
| firstOffset = soffset; | ||
| } | ||
|
|
||
| for (int t = 0; t <= 20; t++) { | ||
| float tf = t/20.0f; | ||
| anim[c.clip.name].normalizedTime = tf; | ||
| anim.Sample(); | ||
| Vector3 tmp = position + (root.position-transform.position) + c.velocity*tf*c.clip.length; | ||
| trace.Add(tmp); | ||
| } | ||
| position = position + c.velocity*1*c.clip.length; | ||
|
|
||
| anim[c.clip.name].normalizedTime = 1; | ||
| anim.Sample(); | ||
| Vector3 eoffset = root.position - transform.position; | ||
| prevOffset = eoffset; | ||
| } | ||
|
|
||
| anim[c.clip.name].enabled = false; | ||
| anim[c.clip.name].weight = 0; | ||
| } | ||
|
|
||
| position += prevOffset - firstOffset; | ||
|
|
||
| GameObject.DestroyImmediate(ob); | ||
|
|
||
| endPosition = position; | ||
| } | ||
|
|
||
| public override void OnDrawGizmosSelected () { | ||
| base.OnDrawGizmosSelected(); | ||
| List<Vector3> buffer = Pathfinding.Util.ListPool<Vector3>.Claim(); | ||
| Vector3 endPosition = Vector3.zero; | ||
| CalculateOffsets(buffer, out endPosition); | ||
| Gizmos.color = Color.blue; | ||
| for (int i = 0; i < buffer.Count-1; i++) { | ||
| Gizmos.DrawLine(buffer[i], buffer[i+1]); | ||
| } | ||
| } | ||
| } | ||
| } |
| @@ -0,0 +1,354 @@ | ||
| //#define ProfileAstar | ||
|
|
||
| using UnityEngine; | ||
| using System.Collections; | ||
| using System.Text; | ||
| using Pathfinding; | ||
|
|
||
| [AddComponentMenu("Pathfinding/Debugger")] | ||
| [ExecuteInEditMode] | ||
| /** Debugger for the A* Pathfinding Project. | ||
| * This class can be used to profile different parts of the pathfinding system | ||
| * and the whole game as well to some extent. | ||
| * | ||
| * Clarification of the labels shown when enabled. | ||
| * All memory related things profiles <b>the whole game</b> not just the A* Pathfinding System.\n | ||
| * - Currently allocated: memory the GC (garbage collector) says the application has allocated right now. | ||
| * - Peak allocated: maximum measured value of the above. | ||
| * - Last collect peak: the last peak of 'currently allocated'. | ||
| * - Allocation rate: how much the 'currently allocated' value increases per second. This value is not as reliable as you can think | ||
| * it is often very random probably depending on how the GC thinks this application is using memory. | ||
| * - Collection frequency: how often the GC is called. Again, the GC might decide it is better with many small collections | ||
| * or with a few large collections. So you cannot really trust this variable much. | ||
| * - Last collect fps: FPS during the last garbage collection, the GC will lower the fps a lot. | ||
| * | ||
| * - FPS: current FPS (not updated every frame for readability) | ||
| * - Lowest FPS (last x): As the label says, the lowest fps of the last x frames. | ||
| * | ||
| * - Size: Size of the path pool. | ||
| * - Total created: Number of paths of that type which has been created. Pooled paths are not counted twice. | ||
| * If this value just keeps on growing and growing without an apparent stop, you are are either not pooling any paths | ||
| * or you have missed to pool some path somewhere in your code. | ||
| * | ||
| * \see pooling | ||
| * | ||
| * \todo Add field showing how many graph updates are being done right now | ||
| */ | ||
| [HelpURL("http://arongranberg.com/astar/docs/class_astar_debugger.php")] | ||
| public class AstarDebugger : MonoBehaviour { | ||
| public int yOffset = 5; | ||
|
|
||
| public bool show = true; | ||
| public bool showInEditor = false; | ||
|
|
||
| public bool showFPS = false; | ||
| public bool showPathProfile = false; | ||
| public bool showMemProfile = false; | ||
| public bool showGraph = false; | ||
|
|
||
| public int graphBufferSize = 200; | ||
|
|
||
| /** Font to use. | ||
| * A monospaced font is the best | ||
| */ | ||
| public Font font = null; | ||
| public int fontSize = 12; | ||
|
|
||
| StringBuilder text = new StringBuilder(); | ||
| string cachedText; | ||
| float lastUpdate = -999; | ||
|
|
||
| private GraphPoint[] graph; | ||
|
|
||
| struct GraphPoint { | ||
| public float fps, memory; | ||
| public bool collectEvent; | ||
| } | ||
|
|
||
| private float delayedDeltaTime = 1; | ||
| private float lastCollect = 0; | ||
| private float lastCollectNum = 0; | ||
| private float delta = 0; | ||
| private float lastDeltaTime = 0; | ||
| private int allocRate = 0; | ||
| private int lastAllocMemory = 0; | ||
| private float lastAllocSet = -9999; | ||
| private int allocMem = 0; | ||
| private int collectAlloc = 0; | ||
| private int peakAlloc = 0; | ||
|
|
||
| private int fpsDropCounterSize = 200; | ||
| private float[] fpsDrops; | ||
|
|
||
| private Rect boxRect; | ||
|
|
||
| private GUIStyle style; | ||
|
|
||
| private Camera cam; | ||
|
|
||
| float graphWidth = 100; | ||
| float graphHeight = 100; | ||
| float graphOffset = 50; | ||
|
|
||
| public void Start () { | ||
| useGUILayout = false; | ||
|
|
||
| fpsDrops = new float[fpsDropCounterSize]; | ||
|
|
||
| cam = GetComponent<Camera>(); | ||
| if (cam == null) { | ||
| cam = Camera.main; | ||
| } | ||
|
|
||
| graph = new GraphPoint[graphBufferSize]; | ||
|
|
||
| for (int i = 0; i < fpsDrops.Length; i++) { | ||
| fpsDrops[i] = 1F / Time.deltaTime; | ||
| } | ||
| } | ||
|
|
||
| int maxVecPool = 0; | ||
| int maxNodePool = 0; | ||
|
|
||
| PathTypeDebug[] debugTypes = new PathTypeDebug[] { | ||
| new PathTypeDebug("ABPath", () => PathPool.GetSize(typeof(ABPath)), () => PathPool.GetTotalCreated(typeof(ABPath))) | ||
| }; | ||
|
|
||
| struct PathTypeDebug { | ||
| string name; | ||
| System.Func<int> getSize; | ||
| System.Func<int> getTotalCreated; | ||
| public PathTypeDebug (string name, System.Func<int> getSize, System.Func<int> getTotalCreated) { | ||
| this.name = name; | ||
| this.getSize = getSize; | ||
| this.getTotalCreated = getTotalCreated; | ||
| } | ||
|
|
||
| public void Print (StringBuilder text) { | ||
| int totCreated = getTotalCreated(); | ||
|
|
||
| if (totCreated > 0) { | ||
| text.Append("\n").Append((" " + name).PadRight(25)).Append(getSize()).Append("/").Append(totCreated); | ||
| } | ||
| } | ||
| } | ||
|
|
||
| public void Update () { | ||
| if (!show || (!Application.isPlaying && !showInEditor)) return; | ||
|
|
||
| int collCount = System.GC.CollectionCount(0); | ||
|
|
||
| if (lastCollectNum != collCount) { | ||
| lastCollectNum = collCount; | ||
| delta = Time.realtimeSinceStartup-lastCollect; | ||
| lastCollect = Time.realtimeSinceStartup; | ||
| lastDeltaTime = Time.deltaTime; | ||
| collectAlloc = allocMem; | ||
| } | ||
|
|
||
| allocMem = (int)System.GC.GetTotalMemory(false); | ||
|
|
||
| bool collectEvent = allocMem < peakAlloc; | ||
| peakAlloc = !collectEvent ? allocMem : peakAlloc; | ||
|
|
||
| if (Time.realtimeSinceStartup - lastAllocSet > 0.3F || !Application.isPlaying) { | ||
| int diff = allocMem - lastAllocMemory; | ||
| lastAllocMemory = allocMem; | ||
| lastAllocSet = Time.realtimeSinceStartup; | ||
| delayedDeltaTime = Time.deltaTime; | ||
|
|
||
| if (diff >= 0) { | ||
| allocRate = diff; | ||
| } | ||
| } | ||
|
|
||
| if (Application.isPlaying) { | ||
| fpsDrops[Time.frameCount % fpsDrops.Length] = Time.deltaTime != 0 ? 1F / Time.deltaTime : float.PositiveInfinity; | ||
| int graphIndex = Time.frameCount % graph.Length; | ||
| graph[graphIndex].fps = Time.deltaTime < Mathf.Epsilon ? 0 : 1F / Time.deltaTime; | ||
| graph[graphIndex].collectEvent = collectEvent; | ||
| graph[graphIndex].memory = allocMem; | ||
| } | ||
|
|
||
| if (Application.isPlaying && cam != null && showGraph) { | ||
| graphWidth = cam.pixelWidth*0.8f; | ||
|
|
||
|
|
||
| float minMem = float.PositiveInfinity, maxMem = 0, minFPS = float.PositiveInfinity, maxFPS = 0; | ||
| for (int i = 0; i < graph.Length; i++) { | ||
| minMem = Mathf.Min(graph[i].memory, minMem); | ||
| maxMem = Mathf.Max(graph[i].memory, maxMem); | ||
| minFPS = Mathf.Min(graph[i].fps, minFPS); | ||
| maxFPS = Mathf.Max(graph[i].fps, maxFPS); | ||
| } | ||
|
|
||
| int currentGraphIndex = Time.frameCount % graph.Length; | ||
|
|
||
| Matrix4x4 m = Matrix4x4.TRS(new Vector3((cam.pixelWidth - graphWidth)/2f, graphOffset, 1), Quaternion.identity, new Vector3(graphWidth, graphHeight, 1)); | ||
|
|
||
| for (int i = 0; i < graph.Length-1; i++) { | ||
| if (i == currentGraphIndex) continue; | ||
|
|
||
| //Debug.DrawLine (m.MultiplyPoint (new Vector3 (i/(float)graph.Length, Mathfx.MapTo (minMem, maxMem, graph[i].memory), -1)), | ||
| // m.MultiplyPoint (new Vector3 ((i+1)/(float)graph.Length, Mathfx.MapTo (minMem, maxMem, graph[i+1].memory), -1)), Color.blue); | ||
|
|
||
| //Debug.DrawLine (m.MultiplyPoint (Vector3.zero), m.MultiplyPoint (-Vector3.one), Color.red); | ||
| //Debug.Log (Mathfx.MapTo (minMem, maxMem, graph[i].memory) + " " + graph[i].memory); | ||
| DrawGraphLine(i, m, i/(float)graph.Length, (i+1)/(float)graph.Length, AstarMath.MapTo(minMem, maxMem, graph[i].memory), AstarMath.MapTo(minMem, maxMem, graph[i+1].memory), Color.blue); | ||
|
|
||
| DrawGraphLine(i, m, i/(float)graph.Length, (i+1)/(float)graph.Length, AstarMath.MapTo(minFPS, maxFPS, graph[i].fps), AstarMath.MapTo(minFPS, maxFPS, graph[i+1].fps), Color.green); | ||
|
|
||
| //Debug.DrawLine (m.MultiplyPoint (new Vector3 (i/(float)graph.Length, Mathfx.MapTo (minFPS, maxFPS, graph[i].fps), -1)), | ||
| // m.MultiplyPoint (new Vector3 ((i+1)/(float)graph.Length, Mathfx.MapTo (minFPS, maxFPS, graph[i+1].fps), -1)), Color.green); | ||
| } | ||
|
|
||
|
|
||
|
|
||
| /*Cross (new Vector3(0,0,1)); | ||
| * Cross (new Vector3(1,1,1)); | ||
| * Cross (new Vector3(0,1,1)); | ||
| * Cross (new Vector3(1,0,1)); | ||
| * Cross (new Vector3(-1,0,1)); | ||
| * Debug.DrawLine (m.MultiplyPoint(Vector3.zero), m.MultiplyPoint(new Vector3(0,0,-5)),Color.blue);*/ | ||
| } | ||
| } | ||
|
|
||
| public void DrawGraphLine (int index, Matrix4x4 m, float x1, float x2, float y1, float y2, Color col) { | ||
| Debug.DrawLine(cam.ScreenToWorldPoint(m.MultiplyPoint3x4(new Vector3(x1, y1))), cam.ScreenToWorldPoint(m.MultiplyPoint3x4(new Vector3(x2, y2))), col); | ||
| } | ||
|
|
||
| public void Cross (Vector3 p) { | ||
| p = cam.cameraToWorldMatrix.MultiplyPoint(p); | ||
| Debug.DrawLine(p-Vector3.up*0.2f, p+Vector3.up*0.2f, Color.red); | ||
| Debug.DrawLine(p-Vector3.right*0.2f, p+Vector3.right*0.2f, Color.red); | ||
| } | ||
|
|
||
|
|
||
| public void OnGUI () { | ||
| if (!show || (!Application.isPlaying && !showInEditor)) return; | ||
|
|
||
| if (style == null) { | ||
| style = new GUIStyle(); | ||
| style.normal.textColor = Color.white; | ||
| style.padding = new RectOffset(5, 5, 5, 5); | ||
| } | ||
|
|
||
| if (Time.realtimeSinceStartup - lastUpdate > 0.5f || cachedText == null || !Application.isPlaying) { | ||
| lastUpdate = Time.realtimeSinceStartup; | ||
|
|
||
| boxRect = new Rect(5, yOffset, 310, 40); | ||
|
|
||
| text.Length = 0; | ||
| text.AppendLine("A* Pathfinding Project Debugger"); | ||
| text.Append("A* Version: ").Append(AstarPath.Version.ToString()); | ||
|
|
||
| if (showMemProfile) { | ||
| boxRect.height += 200; | ||
|
|
||
| text.AppendLine(); | ||
| text.AppendLine(); | ||
| text.Append("Currently allocated".PadRight(25)); | ||
| text.Append((allocMem/1000000F).ToString("0.0 MB")); | ||
| text.AppendLine(); | ||
|
|
||
| text.Append("Peak allocated".PadRight(25)); | ||
| text.Append((peakAlloc/1000000F).ToString("0.0 MB")).AppendLine(); | ||
|
|
||
| text.Append("Last collect peak".PadRight(25)); | ||
| text.Append((collectAlloc/1000000F).ToString("0.0 MB")).AppendLine(); | ||
|
|
||
|
|
||
| text.Append("Allocation rate".PadRight(25)); | ||
| text.Append((allocRate/1000000F).ToString("0.0 MB")).AppendLine(); | ||
|
|
||
| text.Append("Collection frequency".PadRight(25)); | ||
| text.Append(delta.ToString("0.00")); | ||
| text.Append("s\n"); | ||
|
|
||
| text.Append("Last collect fps".PadRight(25)); | ||
| text.Append((1F/lastDeltaTime).ToString("0.0 fps")); | ||
| text.Append(" ("); | ||
| text.Append(lastDeltaTime.ToString("0.000 s")); | ||
| text.Append(")"); | ||
| } | ||
|
|
||
| if (showFPS) { | ||
| text.AppendLine(); | ||
| text.AppendLine(); | ||
| text.Append("FPS".PadRight(25)).Append((1F/delayedDeltaTime).ToString("0.0 fps")); | ||
|
|
||
|
|
||
| float minFps = Mathf.Infinity; | ||
|
|
||
| for (int i = 0; i < fpsDrops.Length; i++) if (fpsDrops[i] < minFps) minFps = fpsDrops[i]; | ||
|
|
||
| text.AppendLine(); | ||
| text.Append(("Lowest fps (last " + fpsDrops.Length + ")").PadRight(25)).Append(minFps.ToString("0.0")); | ||
| } | ||
|
|
||
| if (showPathProfile) { | ||
| AstarPath astar = AstarPath.active; | ||
|
|
||
| text.AppendLine(); | ||
|
|
||
| if (astar == null) { | ||
| text.Append("\nNo AstarPath Object In The Scene"); | ||
| } else { | ||
| if (Pathfinding.Util.ListPool<Vector3>.GetSize() > maxVecPool) maxVecPool = Pathfinding.Util.ListPool<Vector3>.GetSize(); | ||
| if (Pathfinding.Util.ListPool<Pathfinding.GraphNode>.GetSize() > maxNodePool) maxNodePool = Pathfinding.Util.ListPool<Pathfinding.GraphNode>.GetSize(); | ||
|
|
||
| text.Append("\nPool Sizes (size/total created)"); | ||
|
|
||
| for (int i = 0; i < debugTypes.Length; i++) { | ||
| debugTypes[i].Print(text); | ||
| } | ||
| } | ||
| } | ||
|
|
||
| cachedText = text.ToString(); | ||
| } | ||
|
|
||
|
|
||
| if (font != null) { | ||
| style.font = font; | ||
| style.fontSize = fontSize; | ||
| } | ||
|
|
||
| boxRect.height = style.CalcHeight(new GUIContent(cachedText), boxRect.width); | ||
|
|
||
| GUI.Box(boxRect, ""); | ||
| GUI.Label(boxRect, cachedText, style); | ||
|
|
||
| if (showGraph) { | ||
| float minMem = float.PositiveInfinity, maxMem = 0, minFPS = float.PositiveInfinity, maxFPS = 0; | ||
| for (int i = 0; i < graph.Length; i++) { | ||
| minMem = Mathf.Min(graph[i].memory, minMem); | ||
| maxMem = Mathf.Max(graph[i].memory, maxMem); | ||
| minFPS = Mathf.Min(graph[i].fps, minFPS); | ||
| maxFPS = Mathf.Max(graph[i].fps, maxFPS); | ||
| } | ||
|
|
||
| float line; | ||
| GUI.color = Color.blue; | ||
| //Round to nearest x.x MB | ||
| line = Mathf.RoundToInt(maxMem/(100.0f*1000)); // *1000*100 | ||
| GUI.Label(new Rect(5, Screen.height - AstarMath.MapTo(minMem, maxMem, 0 + graphOffset, graphHeight + graphOffset, line*1000*100) - 10, 100, 20), (line/10.0f).ToString("0.0 MB")); | ||
|
|
||
|
|
||
|
|
||
| line = Mathf.Round(minMem/(100.0f*1000)); // *1000*100 | ||
| GUI.Label(new Rect(5, Screen.height - AstarMath.MapTo(minMem, maxMem, 0 + graphOffset, graphHeight + graphOffset, line*1000*100) - 10, 100, 20), (line/10.0f).ToString("0.0 MB")); | ||
|
|
||
|
|
||
| GUI.color = Color.green; | ||
| //Round to nearest x.x MB | ||
| line = Mathf.Round(maxFPS); // *1000*100 | ||
| GUI.Label(new Rect(55, Screen.height - AstarMath.MapTo(minFPS, maxFPS, 0 + graphOffset, graphHeight + graphOffset, line) - 10, 100, 20), (line).ToString("0 FPS")); | ||
|
|
||
|
|
||
|
|
||
| line = Mathf.Round(minFPS); // *1000*100 | ||
| GUI.Label(new Rect(55, Screen.height - AstarMath.MapTo(minFPS, maxFPS, 0 + graphOffset, graphHeight + graphOffset, line) - 10, 100, 20), (line).ToString("0 FPS")); | ||
| } | ||
| } | ||
| } |
| @@ -0,0 +1,14 @@ | ||
| using UnityEngine; | ||
|
|
||
| namespace Pathfinding { | ||
| /** \author http://wiki.unity3d.com/index.php/EnumFlagPropertyDrawer */ | ||
| public class AstarEnumFlagAttribute : PropertyAttribute { | ||
| public string enumName; | ||
|
|
||
| public AstarEnumFlagAttribute() {} | ||
|
|
||
| public AstarEnumFlagAttribute(string name) { | ||
| enumName = name; | ||
| } | ||
| } | ||
| } |
| @@ -0,0 +1,228 @@ | ||
| #define TUPLE | ||
| #pragma warning disable 162 | ||
| #pragma warning disable 429 | ||
|
|
||
| namespace Pathfinding { | ||
| /** Binary heap implementation. | ||
| * Binary heaps are really fast for ordering nodes in a way that | ||
| * makes it possible to get the node with the lowest F score. | ||
| * Also known as a priority queue. | ||
| * | ||
| * This has actually been rewritten as a d-ary heap (by default a 4-ary heap) | ||
| * for performance, but it's the same principle. | ||
| * | ||
| * \see http://en.wikipedia.org/wiki/Binary_heap | ||
| * \see https://en.wikipedia.org/wiki/D-ary_heap | ||
| */ | ||
| public class BinaryHeapM { | ||
| /** Number of items in the tree */ | ||
| public int numberOfItems; | ||
|
|
||
| /** The tree will grow by at least this factor every time it is expanded */ | ||
| public float growthFactor = 2; | ||
|
|
||
| /** | ||
| * Number of children of each node in the tree. | ||
| * Different values have been tested and 4 has been empirically found to perform the best. | ||
| * \see https://en.wikipedia.org/wiki/D-ary_heap | ||
| */ | ||
| const int D = 4; | ||
|
|
||
| /** Sort nodes by G score if there is a tie when comparing the F score */ | ||
| const bool SortGScores = true; | ||
|
|
||
| /** Internal backing array for the tree */ | ||
| private Tuple[] binaryHeap; | ||
|
|
||
| private struct Tuple { | ||
| public uint F; | ||
| public PathNode node; | ||
|
|
||
| public Tuple (uint f, PathNode node) { | ||
| this.F = f; | ||
| this.node = node; | ||
| } | ||
| } | ||
|
|
||
| public BinaryHeapM (int numberOfElements) { | ||
| binaryHeap = new Tuple[numberOfElements]; | ||
| numberOfItems = 0; | ||
| } | ||
|
|
||
| public void Clear () { | ||
| numberOfItems = 0; | ||
| } | ||
|
|
||
| internal PathNode GetNode (int i) { | ||
| return binaryHeap[i].node; | ||
| } | ||
|
|
||
| internal void SetF (int i, uint f) { | ||
| binaryHeap[i].F = f; | ||
| } | ||
|
|
||
| /** Adds a node to the heap */ | ||
| public void Add (PathNode node) { | ||
| if (node == null) throw new System.ArgumentNullException("node"); | ||
|
|
||
| if (numberOfItems == binaryHeap.Length) { | ||
| int newSize = System.Math.Max(binaryHeap.Length+4, (int)System.Math.Round(binaryHeap.Length*growthFactor)); | ||
| if (newSize > 1<<18) { | ||
| throw new System.Exception("Binary Heap Size really large (2^18). A heap size this large is probably the cause of pathfinding running in an infinite loop. " + | ||
| "\nRemove this check (in BinaryHeap.cs) if you are sure that it is not caused by a bug"); | ||
| } | ||
|
|
||
| var tmp = new Tuple[newSize]; | ||
|
|
||
| for (int i = 0; i < binaryHeap.Length; i++) { | ||
| tmp[i] = binaryHeap[i]; | ||
| } | ||
| binaryHeap = tmp; | ||
| } | ||
|
|
||
| var obj = new Tuple(node.F, node); | ||
| binaryHeap[numberOfItems] = obj; | ||
|
|
||
| int bubbleIndex = numberOfItems; | ||
| uint nodeF = node.F; | ||
| uint nodeG = node.G; | ||
|
|
||
| while (bubbleIndex != 0) { | ||
| int parentIndex = (bubbleIndex-1) / D; | ||
|
|
||
| if (nodeF < binaryHeap[parentIndex].F || (nodeF == binaryHeap[parentIndex].F && nodeG > binaryHeap[parentIndex].node.G)) { | ||
| binaryHeap[bubbleIndex] = binaryHeap[parentIndex]; | ||
| binaryHeap[parentIndex] = obj; | ||
| bubbleIndex = parentIndex; | ||
| } else { | ||
| break; | ||
| } | ||
| } | ||
|
|
||
| numberOfItems++; | ||
| } | ||
|
|
||
| /** Returns the node with the lowest F score from the heap */ | ||
| public PathNode Remove () { | ||
| numberOfItems--; | ||
| PathNode returnItem = binaryHeap[0].node; | ||
|
|
||
| binaryHeap[0] = binaryHeap[numberOfItems]; | ||
|
|
||
| int swapItem = 0, parent; | ||
|
|
||
| do { | ||
| if (D == 0) { | ||
| parent = swapItem; | ||
| int p2 = parent * D; | ||
| if (p2 + 1 <= numberOfItems) { | ||
| // Both children exist | ||
| if (binaryHeap[parent].F > binaryHeap[p2].F) { | ||
| swapItem = p2;//2 * parent; | ||
| } | ||
| if (binaryHeap[swapItem].F > binaryHeap[p2 + 1].F) { | ||
| swapItem = p2 + 1; | ||
| } | ||
| } else if ((p2) <= numberOfItems) { | ||
| // Only one child exists | ||
| if (binaryHeap[parent].F > binaryHeap[p2].F) { | ||
| swapItem = p2; | ||
| } | ||
| } | ||
| } else { | ||
| parent = swapItem; | ||
| uint swapF = binaryHeap[swapItem].F; | ||
| int pd = parent * D + 1; | ||
|
|
||
| if (D >= 1 && pd+0 <= numberOfItems && (binaryHeap[pd+0].F < swapF || (SortGScores && binaryHeap[pd+0].F == swapF && binaryHeap[pd+0].node.G < binaryHeap[swapItem].node.G))) { | ||
| swapF = binaryHeap[pd+0].F; | ||
| swapItem = pd+0; | ||
| } | ||
|
|
||
| if (D >= 2 && pd+1 <= numberOfItems && (binaryHeap[pd+1].F < swapF || (SortGScores && binaryHeap[pd+1].F == swapF && binaryHeap[pd+1].node.G < binaryHeap[swapItem].node.G))) { | ||
| swapF = binaryHeap[pd+1].F; | ||
| swapItem = pd+1; | ||
| } | ||
|
|
||
| if (D >= 3 && pd+2 <= numberOfItems && (binaryHeap[pd+2].F < swapF || (SortGScores && binaryHeap[pd+2].F == swapF && binaryHeap[pd+2].node.G < binaryHeap[swapItem].node.G))) { | ||
| swapF = binaryHeap[pd+2].F; | ||
| swapItem = pd+2; | ||
| } | ||
|
|
||
| if (D >= 4 && pd+3 <= numberOfItems && (binaryHeap[pd+3].F < swapF || (SortGScores && binaryHeap[pd+3].F == swapF && binaryHeap[pd+3].node.G < binaryHeap[swapItem].node.G))) { | ||
| swapF = binaryHeap[pd+3].F; | ||
| swapItem = pd+3; | ||
| } | ||
|
|
||
| if (D >= 5 && pd+4 <= numberOfItems && binaryHeap[pd+4].F < swapF) { | ||
| swapF = binaryHeap[pd+4].F; | ||
| swapItem = pd+4; | ||
| } | ||
|
|
||
| if (D >= 6 && pd+5 <= numberOfItems && binaryHeap[pd+5].F < swapF) { | ||
| swapF = binaryHeap[pd+5].F; | ||
| swapItem = pd+5; | ||
| } | ||
|
|
||
| if (D >= 7 && pd+6 <= numberOfItems && binaryHeap[pd+6].F < swapF) { | ||
| swapF = binaryHeap[pd+6].F; | ||
| swapItem = pd+6; | ||
| } | ||
|
|
||
| if (D >= 8 && pd+7 <= numberOfItems && binaryHeap[pd+7].F < swapF) { | ||
| swapF = binaryHeap[pd+7].F; | ||
| swapItem = pd+7; | ||
| } | ||
|
|
||
| if (D >= 9 && pd+8 <= numberOfItems && binaryHeap[pd+8].F < swapF) { | ||
| swapF = binaryHeap[pd+8].F; | ||
| swapItem = pd+8; | ||
| } | ||
| } | ||
|
|
||
| // One if the parent's children are smaller or equal, swap them | ||
| if (parent != swapItem) { | ||
| var tmpIndex = binaryHeap[parent]; | ||
| binaryHeap[parent] = binaryHeap[swapItem]; | ||
| binaryHeap[swapItem] = tmpIndex; | ||
| } else { | ||
| break; | ||
| } | ||
| } while (true); | ||
|
|
||
| //Validate (); | ||
|
|
||
| return returnItem; | ||
| } | ||
|
|
||
| void Validate () { | ||
| for (int i = 1; i < numberOfItems; i++) { | ||
| int parentIndex = (i-1)/D; | ||
| if (binaryHeap[parentIndex].F > binaryHeap[i].F) { | ||
| throw new System.Exception("Invalid state at " + i + ":" + parentIndex + " ( " + binaryHeap[parentIndex].F + " > " + binaryHeap[i].F + " ) "); | ||
| } | ||
| } | ||
| } | ||
|
|
||
| /** Rebuilds the heap by trickeling down all items. | ||
| * Usually called after the hTarget on a path has been changed */ | ||
| public void Rebuild () { | ||
| for (int i = 2; i < numberOfItems; i++) { | ||
| int bubbleIndex = i; | ||
| var node = binaryHeap[i]; | ||
| uint nodeF = node.F; | ||
| while (bubbleIndex != 1) { | ||
| int parentIndex = bubbleIndex / D; | ||
|
|
||
| if (nodeF < binaryHeap[parentIndex].F) { | ||
| binaryHeap[bubbleIndex] = binaryHeap[parentIndex]; | ||
| binaryHeap[parentIndex] = node; | ||
| bubbleIndex = parentIndex; | ||
| } else { | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| } | ||
| } | ||
| } |
| @@ -0,0 +1,10 @@ | ||
| using Pathfinding.Serialization.JsonFx; | ||
|
|
||
| namespace Pathfinding { | ||
| [JsonOptIn] | ||
| /** Defined here only so non-editor classes can use the #target field */ | ||
| public class GraphEditorBase { | ||
| /** NavGraph this editor is exposing */ | ||
| public NavGraph target; | ||
| } | ||
| } |
| @@ -0,0 +1,148 @@ | ||
| using UnityEngine; | ||
|
|
||
| namespace Pathfinding { | ||
| /** GraphModifier for modifying graphs or processing graph data based on events. | ||
| * This class is a simple container for a number of events. | ||
| * | ||
| * \warning Some events will be called both in play mode <b>and in editor mode</b> (at least the scan events). | ||
| * So make sure your code handles both cases well. You may choose to ignore editor events. | ||
| * \see Application.IsPlaying | ||
| */ | ||
| public abstract class GraphModifier : MonoBehaviour { | ||
| /** All active graph modifiers */ | ||
| private static GraphModifier root; | ||
|
|
||
| private GraphModifier prev; | ||
| private GraphModifier next; | ||
|
|
||
| public static void FindAllModifiers () { | ||
| var arr = FindObjectsOfType(typeof(GraphModifier)) as GraphModifier[]; | ||
|
|
||
| for (int i = 0; i < arr.Length; i++) { | ||
| arr[i].OnEnable(); | ||
| } | ||
| } | ||
|
|
||
| /** GraphModifier event type. | ||
| * \see GraphModifier */ | ||
| public enum EventType { | ||
| PostScan = 1 << 0, | ||
| PreScan = 1 << 1, | ||
| LatePostScan = 1 << 2, | ||
| PreUpdate = 1 << 3, | ||
| PostUpdate = 1 << 4, | ||
| PostCacheLoad = 1 << 5 | ||
| } | ||
|
|
||
| /** Triggers an event for all active graph modifiers */ | ||
| public static void TriggerEvent (GraphModifier.EventType type) { | ||
| if (!Application.isPlaying) { | ||
| FindAllModifiers(); | ||
| } | ||
|
|
||
| GraphModifier c = root; | ||
| switch (type) { | ||
| case EventType.PreScan: | ||
| while (c != null) { c.OnPreScan(); c = c.next; } | ||
| break; | ||
| case EventType.PostScan: | ||
| while (c != null) { c.OnPostScan(); c = c.next; } | ||
| break; | ||
| case EventType.LatePostScan: | ||
| while (c != null) { c.OnLatePostScan(); c = c.next; } | ||
| break; | ||
| case EventType.PreUpdate: | ||
| while (c != null) { c.OnGraphsPreUpdate(); c = c.next; } | ||
| break; | ||
| case EventType.PostUpdate: | ||
| while (c != null) { c.OnGraphsPostUpdate(); c = c.next; } | ||
| break; | ||
| case EventType.PostCacheLoad: | ||
| while (c != null) { c.OnPostCacheLoad(); c = c.next; } | ||
| break; | ||
| } | ||
| } | ||
|
|
||
| /** Adds this modifier to list of active modifiers. | ||
| */ | ||
| protected virtual void OnEnable () { | ||
| OnDisable(); | ||
|
|
||
| if (root == null) { | ||
| root = this; | ||
| } else { | ||
| next = root; | ||
| root.prev = this; | ||
| root = this; | ||
| } | ||
| } | ||
|
|
||
| /** Removes this modifier from list of active modifiers */ | ||
| protected virtual void OnDisable () { | ||
| if (root == this) { | ||
| root = next; | ||
| if (root != null) root.prev = null; | ||
| } else { | ||
| if (prev != null) prev.next = next; | ||
| if (next != null) next.prev = prev; | ||
| } | ||
| prev = null; | ||
| next = null; | ||
| } | ||
|
|
||
| /* Called just before a graph is scanned. | ||
| * Note that some other graphs might already be scanned */ | ||
| //public virtual void OnGraphPreScan (NavGraph graph) {} | ||
|
|
||
| /* Called just after a graph has been scanned. | ||
| * Note that some other graphs might not have been scanned at this point. */ | ||
| //public virtual void OnGraphPostScan (NavGraph graph) {} | ||
|
|
||
| /** Called right after all graphs have been scanned. | ||
| * FloodFill and other post processing has not been done. | ||
| * | ||
| * \warning Since OnEnable and Awake are called roughly in the same time, the only way | ||
| * to ensure that these scripts get this call when scanning in Awake is to | ||
| * set the Script Execution Order for AstarPath to some time later than default time | ||
| * (see Edit -> Project Settings -> Script Execution Order). | ||
| * | ||
| * \see OnLatePostScan | ||
| */ | ||
| public virtual void OnPostScan () {} | ||
|
|
||
| /** Called right before graphs are going to be scanned. | ||
| * | ||
| * \warning Since OnEnable and Awake are called roughly in the same time, the only way | ||
| * to ensure that these scripts get this call when scanning in Awake is to | ||
| * set the Script Execution Order for AstarPath to some time later than default time | ||
| * (see Edit -> Project Settings -> Script Execution Order). | ||
| * | ||
| * \see OnLatePostScan | ||
| * */ | ||
| public virtual void OnPreScan () {} | ||
|
|
||
| /** Called at the end of the scanning procedure. | ||
| * This is the absolute last thing done by Scan. | ||
| * | ||
| * \note This event will be called even if Script Execution Order has messed things up | ||
| * (see the other two scan events). | ||
| */ | ||
| public virtual void OnLatePostScan () {} | ||
|
|
||
| /** Called after cached graphs have been loaded. | ||
| * When using cached startup, this event is analogous to OnLatePostScan and implementing scripts | ||
| * should do roughly the same thing for both events. | ||
| * | ||
| * \note This event will be called even if Script Execution Order has messed things up | ||
| * (see the other two scan events). | ||
| */ | ||
| public virtual void OnPostCacheLoad () {} | ||
|
|
||
| /** Called before graphs are updated using GraphUpdateObjects */ | ||
| public virtual void OnGraphsPreUpdate () {} | ||
|
|
||
| /** Called after graphs have been updated using GraphUpdateObjects. | ||
| * Eventual flood filling has been done */ | ||
| public virtual void OnGraphsPostUpdate () {} | ||
| } | ||
| } |
| @@ -0,0 +1,5 @@ | ||
|
|
||
| // This file has been included in a beta release, but is not yet included in a | ||
| // non-beta release. Since UnityPackages cannot delete files, only replace them | ||
| // this file is added to avoid old files causing compiler errors if a user upgrades | ||
| // from a beta it has been included in, to this version |
| @@ -0,0 +1,350 @@ | ||
| using UnityEngine; | ||
|
|
||
| namespace Pathfinding { | ||
| /** Holds a coordinate in integers */ | ||
| public struct Int3 { | ||
| public int x; | ||
| public int y; | ||
| public int z; | ||
|
|
||
| //These should be set to the same value (only PrecisionFactor should be 1 divided by Precision) | ||
|
|
||
| /** Precision for the integer coordinates. | ||
| * One world unit is divided into [value] pieces. A value of 1000 would mean millimeter precision, a value of 1 would mean meter precision (assuming 1 world unit = 1 meter). | ||
| * This value affects the maximum coordinates for nodes as well as how large the cost values are for moving between two nodes. | ||
| * A higher value means that you also have to set all penalty values to a higher value to compensate since the normal cost of moving will be higher. | ||
| */ | ||
| public const int Precision = 1000; | ||
|
|
||
| /** #Precision as a float */ | ||
| public const float FloatPrecision = 1000F; | ||
|
|
||
| /** 1 divided by #Precision */ | ||
| public const float PrecisionFactor = 0.001F; | ||
|
|
||
| private static Int3 _zero = new Int3(0, 0, 0); | ||
| public static Int3 zero { get { return _zero; } } | ||
|
|
||
| public Int3 (Vector3 position) { | ||
| x = (int)System.Math.Round(position.x*FloatPrecision); | ||
| y = (int)System.Math.Round(position.y*FloatPrecision); | ||
| z = (int)System.Math.Round(position.z*FloatPrecision); | ||
| } | ||
|
|
||
| public Int3 (int _x, int _y, int _z) { | ||
| x = _x; | ||
| y = _y; | ||
| z = _z; | ||
| } | ||
|
|
||
| public static bool operator == (Int3 lhs, Int3 rhs) { | ||
| return lhs.x == rhs.x && | ||
| lhs.y == rhs.y && | ||
| lhs.z == rhs.z; | ||
| } | ||
|
|
||
| public static bool operator != (Int3 lhs, Int3 rhs) { | ||
| return lhs.x != rhs.x || | ||
| lhs.y != rhs.y || | ||
| lhs.z != rhs.z; | ||
| } | ||
|
|
||
| public static explicit operator Int3 (Vector3 ob) { | ||
| return new Int3( | ||
| (int)System.Math.Round(ob.x*FloatPrecision), | ||
| (int)System.Math.Round(ob.y*FloatPrecision), | ||
| (int)System.Math.Round(ob.z*FloatPrecision) | ||
| ); | ||
| } | ||
|
|
||
| public static explicit operator Vector3 (Int3 ob) { | ||
| return new Vector3(ob.x*PrecisionFactor, ob.y*PrecisionFactor, ob.z*PrecisionFactor); | ||
| } | ||
|
|
||
| public static Int3 operator - (Int3 lhs, Int3 rhs) { | ||
| lhs.x -= rhs.x; | ||
| lhs.y -= rhs.y; | ||
| lhs.z -= rhs.z; | ||
| return lhs; | ||
| } | ||
|
|
||
| public static Int3 operator - (Int3 lhs) { | ||
| lhs.x = -lhs.x; | ||
| lhs.y = -lhs.y; | ||
| lhs.z = -lhs.z; | ||
| return lhs; | ||
| } | ||
|
|
||
| // REMOVE! | ||
| public static Int3 operator + (Int3 lhs, Int3 rhs) { | ||
| lhs.x += rhs.x; | ||
| lhs.y += rhs.y; | ||
| lhs.z += rhs.z; | ||
| return lhs; | ||
| } | ||
|
|
||
| public static Int3 operator * (Int3 lhs, int rhs) { | ||
| lhs.x *= rhs; | ||
| lhs.y *= rhs; | ||
| lhs.z *= rhs; | ||
|
|
||
| return lhs; | ||
| } | ||
|
|
||
| public static Int3 operator * (Int3 lhs, float rhs) { | ||
| lhs.x = (int)System.Math.Round(lhs.x * rhs); | ||
| lhs.y = (int)System.Math.Round(lhs.y * rhs); | ||
| lhs.z = (int)System.Math.Round(lhs.z * rhs); | ||
|
|
||
| return lhs; | ||
| } | ||
|
|
||
| public static Int3 operator * (Int3 lhs, double rhs) { | ||
| lhs.x = (int)System.Math.Round(lhs.x * rhs); | ||
| lhs.y = (int)System.Math.Round(lhs.y * rhs); | ||
| lhs.z = (int)System.Math.Round(lhs.z * rhs); | ||
|
|
||
| return lhs; | ||
| } | ||
|
|
||
| public static Int3 operator * (Int3 lhs, Vector3 rhs) { | ||
| lhs.x = (int)System.Math.Round(lhs.x * rhs.x); | ||
| lhs.y = (int)System.Math.Round(lhs.y * rhs.y); | ||
| lhs.z = (int)System.Math.Round(lhs.z * rhs.z); | ||
|
|
||
| return lhs; | ||
| } | ||
|
|
||
| public static Int3 operator / (Int3 lhs, float rhs) { | ||
| lhs.x = (int)System.Math.Round(lhs.x / rhs); | ||
| lhs.y = (int)System.Math.Round(lhs.y / rhs); | ||
| lhs.z = (int)System.Math.Round(lhs.z / rhs); | ||
| return lhs; | ||
| } | ||
|
|
||
| public int this[int i] { | ||
| get { | ||
| return i == 0 ? x : (i == 1 ? y : z); | ||
| } | ||
| set { | ||
| if (i == 0) x = value; | ||
| else if (i == 1) y = value; | ||
| else z = value; | ||
| } | ||
| } | ||
|
|
||
| /** Angle between the vectors in radians */ | ||
| public static float Angle (Int3 lhs, Int3 rhs) { | ||
| double cos = Dot(lhs, rhs)/ ((double)lhs.magnitude*(double)rhs.magnitude); | ||
|
|
||
| cos = cos < -1 ? -1 : (cos > 1 ? 1 : cos); | ||
| return (float)System.Math.Acos(cos); | ||
| } | ||
|
|
||
| public static int Dot (Int3 lhs, Int3 rhs) { | ||
| return | ||
| lhs.x * rhs.x + | ||
| lhs.y * rhs.y + | ||
| lhs.z * rhs.z; | ||
| } | ||
|
|
||
| public static long DotLong (Int3 lhs, Int3 rhs) { | ||
| return | ||
| (long)lhs.x * (long)rhs.x + | ||
| (long)lhs.y * (long)rhs.y + | ||
| (long)lhs.z * (long)rhs.z; | ||
| } | ||
|
|
||
| /** Normal in 2D space (XZ). | ||
| * Equivalent to Cross(this, Int3(0,1,0) ) | ||
| * except that the Y coordinate is left unchanged with this operation. | ||
| */ | ||
| public Int3 Normal2D () { | ||
| return new Int3(z, y, -x); | ||
| } | ||
|
|
||
| /** Returns the magnitude of the vector. The magnitude is the 'length' of the vector from 0,0,0 to this point. Can be used for distance calculations: | ||
| * \code Debug.Log ("Distance between 3,4,5 and 6,7,8 is: "+(new Int3(3,4,5) - new Int3(6,7,8)).magnitude); \endcode | ||
| */ | ||
| public float magnitude { | ||
| get { | ||
| //It turns out that using doubles is just as fast as using ints with Mathf.Sqrt. And this can also handle larger numbers (possibly with small errors when using huge numbers)! | ||
|
|
||
| double _x = x; | ||
| double _y = y; | ||
| double _z = z; | ||
|
|
||
| return (float)System.Math.Sqrt(_x*_x+_y*_y+_z*_z); | ||
| } | ||
| } | ||
|
|
||
| /** Magnitude used for the cost between two nodes. The default cost between two nodes can be calculated like this: | ||
| * \code int cost = (node1.position-node2.position).costMagnitude; \endcode | ||
| * | ||
| * This is simply the magnitude, rounded to the nearest integer | ||
| */ | ||
| public int costMagnitude { | ||
| get { | ||
| return (int)System.Math.Round(magnitude); | ||
| } | ||
| } | ||
|
|
||
| /** The magnitude in world units. | ||
| * \deprecated This property is deprecated. Use magnitude or cast to a Vector3 | ||
| */ | ||
| [System.Obsolete("This property is deprecated. Use magnitude or cast to a Vector3")] | ||
| public float worldMagnitude { | ||
| get { | ||
| double _x = x; | ||
| double _y = y; | ||
| double _z = z; | ||
|
|
||
| return (float)System.Math.Sqrt(_x*_x+_y*_y+_z*_z)*PrecisionFactor; | ||
| } | ||
| } | ||
|
|
||
| /** The squared magnitude of the vector */ | ||
| public float sqrMagnitude { | ||
| get { | ||
| double _x = x; | ||
| double _y = y; | ||
| double _z = z; | ||
| return (float)(_x*_x+_y*_y+_z*_z); | ||
| } | ||
| } | ||
|
|
||
| /** The squared magnitude of the vector */ | ||
| public long sqrMagnitudeLong { | ||
| get { | ||
| long _x = x; | ||
| long _y = y; | ||
| long _z = z; | ||
| return (_x*_x+_y*_y+_z*_z); | ||
| } | ||
| } | ||
|
|
||
| public static implicit operator string (Int3 ob) { | ||
| return ob.ToString(); | ||
| } | ||
|
|
||
| /** Returns a nicely formatted string representing the vector */ | ||
| public override string ToString () { | ||
| return "( "+x+", "+y+", "+z+")"; | ||
| } | ||
|
|
||
| public override bool Equals (System.Object o) { | ||
| if (o == null) return false; | ||
|
|
||
| var rhs = (Int3)o; | ||
|
|
||
| return x == rhs.x && | ||
| y == rhs.y && | ||
| z == rhs.z; | ||
| } | ||
|
|
||
| public override int GetHashCode () { | ||
| return x*73856093 ^ y*19349663 ^ z*83492791; | ||
| } | ||
| } | ||
|
|
||
| /** Two Dimensional Integer Coordinate Pair */ | ||
| public struct Int2 { | ||
| public int x; | ||
| public int y; | ||
|
|
||
| public Int2 (int x, int y) { | ||
| this.x = x; | ||
| this.y = y; | ||
| } | ||
|
|
||
| public long sqrMagnitudeLong { | ||
| get { | ||
| return (long)x*(long)x+(long)y*(long)y; | ||
| } | ||
| } | ||
|
|
||
| public static Int2 operator + (Int2 a, Int2 b) { | ||
| return new Int2(a.x+b.x, a.y+b.y); | ||
| } | ||
|
|
||
| public static Int2 operator - (Int2 a, Int2 b) { | ||
| return new Int2(a.x-b.x, a.y-b.y); | ||
| } | ||
|
|
||
| public static bool operator == (Int2 a, Int2 b) { | ||
| return a.x == b.x && a.y == b.y; | ||
| } | ||
|
|
||
| public static bool operator != (Int2 a, Int2 b) { | ||
| return a.x != b.x || a.y != b.y; | ||
| } | ||
|
|
||
| /** Dot product of the two coordinates */ | ||
| public static long DotLong (Int2 a, Int2 b) { | ||
| return (long)a.x*(long)b.x + (long)a.y*(long)b.y; | ||
| } | ||
|
|
||
| public override bool Equals (System.Object o) { | ||
| if (o == null) return false; | ||
| var rhs = (Int2)o; | ||
|
|
||
| return x == rhs.x && y == rhs.y; | ||
| } | ||
|
|
||
| public override int GetHashCode () { | ||
| return x*49157+y*98317; | ||
| } | ||
|
|
||
| /** Matrices for rotation. | ||
| * Each group of 4 elements is a 2x2 matrix. | ||
| * The XZ position is multiplied by this. | ||
| * So | ||
| * \code | ||
| * //A rotation by 90 degrees clockwise, second matrix in the array | ||
| * (5,2) * ((0, 1), (-1, 0)) = (2,-5) | ||
| * \endcode | ||
| */ | ||
| private static readonly int[] Rotations = { | ||
| 1, 0, //Identity matrix | ||
| 0, 1, | ||
|
|
||
| 0, 1, | ||
| -1, 0, | ||
|
|
||
| -1, 0, | ||
| 0, -1, | ||
|
|
||
| 0, -1, | ||
| 1, 0 | ||
| }; | ||
|
|
||
| /** Returns a new Int2 rotated 90*r degrees around the origin. | ||
| * \deprecated Deprecated becuase it is not used by any part of the A* Pathfinding Project | ||
| */ | ||
| [System.Obsolete("Deprecated becuase it is not used by any part of the A* Pathfinding Project")] | ||
| public static Int2 Rotate (Int2 v, int r) { | ||
| r = r % 4; | ||
| return new Int2(v.x*Rotations[r*4+0] + v.y*Rotations[r*4+1], v.x*Rotations[r*4+2] + v.y*Rotations[r*4+3]); | ||
| } | ||
|
|
||
| public static Int2 Min (Int2 a, Int2 b) { | ||
| return new Int2(System.Math.Min(a.x, b.x), System.Math.Min(a.y, b.y)); | ||
| } | ||
|
|
||
| public static Int2 Max (Int2 a, Int2 b) { | ||
| return new Int2(System.Math.Max(a.x, b.x), System.Math.Max(a.y, b.y)); | ||
| } | ||
|
|
||
| public static Int2 FromInt3XZ (Int3 o) { | ||
| return new Int2(o.x, o.z); | ||
| } | ||
|
|
||
| public static Int3 ToInt3XZ (Int2 o) { | ||
| return new Int3(o.x, 0, o.y); | ||
| } | ||
|
|
||
| public override string ToString () { | ||
| return "("+x+", " +y+")"; | ||
| } | ||
| } | ||
| } |
| @@ -0,0 +1,143 @@ | ||
| #if !UNITY_EDITOR | ||
| // Extra optimizations when not running in the editor, but less error checking | ||
| #define ASTAR_OPTIMIZE_POOLING | ||
| #endif | ||
|
|
||
| using System; | ||
| using System.Collections.Generic; | ||
|
|
||
| namespace Pathfinding.Util { | ||
| /** Lightweight List Pool. | ||
| * Handy class for pooling lists of type T. | ||
| * | ||
| * Usage: | ||
| * - Claim a new list using \code List<SomeClass> foo = ListPool<SomeClass>.Claim (); \endcode | ||
| * - Use it and do stuff with it | ||
| * - Release it with \code ListPool<SomeClass>.Release (foo); \endcode | ||
| * | ||
| * You do not need to clear the list before releasing it. | ||
| * After you have released a list, you should never use it again, if you do use it, you will | ||
| * mess things up quite badly in the worst case. | ||
| * | ||
| * \since Version 3.2 | ||
| * \see Pathfinding.Util.StackPool | ||
| */ | ||
| public static class ListPool<T>{ | ||
| /** Internal pool */ | ||
| static readonly List<List<T> > pool = new List<List<T> >(); | ||
|
|
||
| static readonly HashSet<List<T> > inPool = new HashSet<List<T> >(); | ||
|
|
||
| /** When requesting a list with a specified capacity, search max this many lists in the pool before giving up. | ||
| * Must be greater or equal to one. | ||
| */ | ||
| const int MaxCapacitySearchLength = 8; | ||
|
|
||
| /** Claim a list. | ||
| * Returns a pooled list if any are in the pool. | ||
| * Otherwise it creates a new one. | ||
| * After usage, this list should be released using the Release function (though not strictly necessary). | ||
| */ | ||
| public static List<T> Claim () { | ||
| lock (pool) { | ||
| if (pool.Count > 0) { | ||
| List<T> ls = pool[pool.Count-1]; | ||
| pool.RemoveAt(pool.Count-1); | ||
| inPool.Remove(ls); | ||
| return ls; | ||
| } | ||
|
|
||
| return new List<T>(); | ||
| } | ||
| } | ||
|
|
||
| /** Claim a list with minimum capacity | ||
| * Returns a pooled list if any are in the pool. | ||
| * Otherwise it creates a new one. | ||
| * After usage, this list should be released using the Release function (though not strictly necessary). | ||
| * This list returned will have at least the capacity specified. | ||
| */ | ||
| public static List<T> Claim (int capacity) { | ||
| lock (pool) { | ||
| // Loop through the last MaxCapacitySearchLength items | ||
| // and check if any item has a capacity greater or equal to the one that | ||
| // is desired. If so return it. | ||
| // Otherwise take the largest one and expand the capacity | ||
| // to the desired capacity or if there are no lists in the pool | ||
| // then allocate a new one with the desired capacity | ||
| List<T> list = null; | ||
| int listIndex = -1; | ||
| for (int i = 0; i < pool.Count && i < MaxCapacitySearchLength; i++) { | ||
| // ith last item | ||
| var candidate = pool[pool.Count-1-i]; | ||
|
|
||
| if (candidate.Capacity >= capacity) { | ||
| pool.RemoveAt(pool.Count-1-i); | ||
| inPool.Remove(candidate); | ||
| return candidate; | ||
| } else if (list == null || candidate.Capacity > list.Capacity) { | ||
| list = candidate; | ||
| listIndex = pool.Count-1-i; | ||
| } | ||
| } | ||
|
|
||
| if (list == null) { | ||
| list = new List<T>(capacity); | ||
| } else { | ||
| list.Capacity = capacity; | ||
| // Swap current item and last item to enable a more efficient removal | ||
| pool[listIndex] = pool[pool.Count-1]; | ||
| pool.RemoveAt(pool.Count-1); | ||
| inPool.Remove(list); | ||
| } | ||
| return list; | ||
| } | ||
| } | ||
|
|
||
| /** Makes sure the pool contains at least \a count pooled items with capacity \a size. | ||
| * This is good if you want to do all allocations at start. | ||
| */ | ||
| public static void Warmup (int count, int size) { | ||
| lock (pool) { | ||
| var tmp = new List<T>[count]; | ||
| for (int i = 0; i < count; i++) tmp[i] = Claim(size); | ||
| for (int i = 0; i < count; i++) Release(tmp[i]); | ||
| } | ||
| } | ||
|
|
||
| /** Releases a list. | ||
| * After the list has been released it should not be used anymore. | ||
| * | ||
| * \throws System.InvalidOperationException | ||
| * Releasing a list when it has already been released will cause an exception to be thrown. | ||
| * | ||
| * \see Claim | ||
| */ | ||
| public static void Release (List<T> list) { | ||
| list.Clear(); | ||
|
|
||
| lock (pool) { | ||
| if (!inPool.Add(list)) { | ||
| throw new InvalidOperationException("You are trying to pool a list twice. Please make sure that you only pool it once."); | ||
| } | ||
| pool.Add(list); | ||
| } | ||
| } | ||
|
|
||
| /** Clears the pool for lists of this type. | ||
| * This is an O(n) operation, where n is the number of pooled lists. | ||
| */ | ||
| public static void Clear () { | ||
| lock (pool) { | ||
| inPool.Clear(); | ||
| pool.Clear(); | ||
| } | ||
| } | ||
|
|
||
| /** Number of lists of this type in the pool */ | ||
| public static int GetSize () { | ||
| // No lock required since int writes are atomic | ||
| return pool.Count; | ||
| } | ||
| } | ||
| } |
| @@ -0,0 +1,175 @@ | ||
| using UnityEngine; | ||
| using System.Collections; | ||
| using Pathfinding; | ||
| #if UNITY_EDITOR | ||
| using UnityEditor; | ||
| #endif | ||
|
|
||
| namespace Pathfinding { | ||
| [AddComponentMenu("Pathfinding/Link")] | ||
| [HelpURL("http://arongranberg.com/astar/docs/class_pathfinding_1_1_node_link.php")] | ||
| public class NodeLink : GraphModifier { | ||
| /** End position of the link */ | ||
| public Transform end; | ||
|
|
||
| /** The connection will be this times harder/slower to traverse. | ||
| * Note that values lower than one will not always make the pathfinder choose this path instead of another path even though this one should | ||
| * lead to a lower total cost unless you also adjust the Heuristic Scale in A* Inspector -> Settings -> Pathfinding or disable the heuristic altogether. | ||
| */ | ||
| public float costFactor = 1.0f; | ||
|
|
||
| /** Make a one-way connection */ | ||
| public bool oneWay = false; | ||
|
|
||
| /** Delete existing connection instead of adding one */ | ||
| public bool deleteConnection = false; | ||
|
|
||
| public Transform Start { | ||
| get { return transform; } | ||
| } | ||
|
|
||
| public Transform End { | ||
| get { return end; } | ||
| } | ||
|
|
||
| public override void OnPostScan () { | ||
| if (AstarPath.active.isScanning) { | ||
| InternalOnPostScan(); | ||
| } else { | ||
| AstarPath.active.AddWorkItem(new AstarPath.AstarWorkItem(delegate(bool force) { | ||
| InternalOnPostScan(); | ||
| return true; | ||
| })); | ||
| } | ||
| } | ||
|
|
||
| public void InternalOnPostScan () { | ||
| Apply(); | ||
| } | ||
|
|
||
| public override void OnGraphsPostUpdate () { | ||
| if (!AstarPath.active.isScanning) { | ||
| AstarPath.active.AddWorkItem(new AstarPath.AstarWorkItem(delegate(bool force) { | ||
| InternalOnPostScan(); | ||
| return true; | ||
| })); | ||
| } | ||
| } | ||
|
|
||
| public virtual void Apply () { | ||
| if (Start == null || End == null || AstarPath.active == null) return; | ||
|
|
||
| GraphNode startNode = AstarPath.active.GetNearest(Start.position).node; | ||
| GraphNode endNode = AstarPath.active.GetNearest(End.position).node; | ||
|
|
||
| if (startNode == null || endNode == null) return; | ||
|
|
||
|
|
||
| if (deleteConnection) { | ||
| startNode.RemoveConnection(endNode); | ||
| if (!oneWay) | ||
| endNode.RemoveConnection(startNode); | ||
| } else { | ||
| uint cost = (uint)System.Math.Round((startNode.position-endNode.position).costMagnitude*costFactor); | ||
|
|
||
| startNode.AddConnection(endNode, cost); | ||
| if (!oneWay) | ||
| endNode.AddConnection(startNode, cost); | ||
| } | ||
| } | ||
|
|
||
| public void OnDrawGizmos () { | ||
| if (Start == null || End == null) return; | ||
|
|
||
| Vector3 p1 = Start.position; | ||
| Vector3 p2 = End.position; | ||
|
|
||
| Gizmos.color = deleteConnection ? Color.red : Color.green; | ||
| DrawGizmoBezier(p1, p2); | ||
| } | ||
|
|
||
| private void DrawGizmoBezier (Vector3 p1, Vector3 p2) { | ||
| Vector3 dir = p2-p1; | ||
|
|
||
| if (dir == Vector3.zero) return; | ||
|
|
||
| Vector3 normal = Vector3.Cross(Vector3.up, dir); | ||
| Vector3 normalUp = Vector3.Cross(dir, normal); | ||
|
|
||
| normalUp = normalUp.normalized; | ||
| normalUp *= dir.magnitude*0.1f; | ||
|
|
||
| Vector3 p1c = p1+normalUp; | ||
| Vector3 p2c = p2+normalUp; | ||
|
|
||
| Vector3 prev = p1; | ||
| for (int i = 1; i <= 20; i++) { | ||
| float t = i/20.0f; | ||
| Vector3 p = AstarSplines.CubicBezier(p1, p1c, p2c, p2, t); | ||
| Gizmos.DrawLine(prev, p); | ||
| prev = p; | ||
| } | ||
| } | ||
|
|
||
| #if UNITY_EDITOR | ||
| [UnityEditor.MenuItem("Edit/Pathfinding/Link Pair %&l")] | ||
| public static void LinkObjects () { | ||
| Transform[] tfs = Selection.transforms; | ||
| if (tfs.Length == 2) { | ||
| LinkObjects(tfs[0], tfs[1], false); | ||
| } | ||
| SceneView.RepaintAll(); | ||
| } | ||
|
|
||
| [UnityEditor.MenuItem("Edit/Pathfinding/Unlink Pair %&u")] | ||
| public static void UnlinkObjects () { | ||
| Transform[] tfs = Selection.transforms; | ||
| if (tfs.Length == 2) { | ||
| LinkObjects(tfs[0], tfs[1], true); | ||
| } | ||
| SceneView.RepaintAll(); | ||
| } | ||
|
|
||
| [UnityEditor.MenuItem("Edit/Pathfinding/Delete Links on Selected %&b")] | ||
| public static void DeleteLinks () { | ||
| Transform[] tfs = Selection.transforms; | ||
| for (int i = 0; i < tfs.Length; i++) { | ||
| NodeLink[] conns = tfs[i].GetComponents<NodeLink>(); | ||
| for (int j = 0; j < conns.Length; j++) DestroyImmediate(conns[j]); | ||
| } | ||
| SceneView.RepaintAll(); | ||
| } | ||
|
|
||
| public static void LinkObjects (Transform a, Transform b, bool removeConnection) { | ||
| NodeLink connecting = null; | ||
|
|
||
| NodeLink[] conns = a.GetComponents<NodeLink>(); | ||
| for (int i = 0; i < conns.Length; i++) { | ||
| if (conns[i].end == b) { | ||
| connecting = conns[i]; | ||
| break; | ||
| } | ||
| } | ||
|
|
||
| conns = b.GetComponents<NodeLink>(); | ||
| for (int i = 0; i < conns.Length; i++) { | ||
| if (conns[i].end == a) { | ||
| connecting = conns[i]; | ||
| break; | ||
| } | ||
| } | ||
|
|
||
| if (removeConnection) { | ||
| if (connecting != null) DestroyImmediate(connecting); | ||
| } else { | ||
| if (connecting == null) { | ||
| connecting = a.gameObject.AddComponent<NodeLink>(); | ||
| connecting.end = b; | ||
| } else { | ||
| connecting.deleteConnection = !connecting.deleteConnection; | ||
| } | ||
| } | ||
| } | ||
| #endif | ||
| } | ||
| } |
