StarEscort/Unity/Assets/Plugins/AstarPathfindingProject/Modifiers/FunnelModifier.cs

using UnityEngine;
using System.Collections.Generic;
using Pathfinding.Util;

namespace Pathfinding {
	[AddComponentMenu("Pathfinding/Modifiers/Funnel")]
	[System.Serializable]
	/// <summary>
	/// Simplifies paths on navmesh graphs using the funnel algorithm.
	/// The funnel algorithm is an algorithm which can, given a path corridor with nodes in the path where the nodes have an area, like triangles, it can find the shortest path inside it.
	/// This makes paths on navmeshes look much cleaner and smoother.
	/// [Open online documentation to see images]
	///
	/// The funnel modifier also works on grid graphs however since it only simplifies the paths within the nodes which the original path visited it may not always
	/// simplify the path as much as you would like it to. The <see cref="Pathfinding.RaycastModifier"/> can be a better fit for grid graphs.
	/// [Open online documentation to see images]
	///
	/// See: http://digestingduck.blogspot.se/2010/03/simple-stupid-funnel-algorithm.html
	/// </summary>
	[HelpURL("http://arongranberg.com/astar/documentation/stable/class_pathfinding_1_1_funnel_modifier.php")]
	public class FunnelModifier : MonoModifier {
		/// <summary>
		/// Determines if twists and bends should be straightened out before running the funnel algorithm.
		/// If the unwrap option is disabled the funnel will simply be projected onto the XZ plane.
		/// If the unwrap option is enabled then the funnel may be oriented arbitrarily and may have twists and bends.
		/// This makes it possible to support the funnel algorithm in XY space as well as in more complicated cases, such
		/// as on curved worlds.
		///
		/// Note: This has a performance overhead, so if you do not need it you can disable it to improve
		/// performance.
		///
		/// [Open online documentation to see images]
		///
		/// See: <see cref="Pathfinding.Funnel.Unwrap"/> for more example images.
		///
		/// Note: This is required if you want to use the funnel modifier for 2D games (i.e in the XY plane).
		/// </summary>
		public bool unwrap = true;

		/// <summary>
		/// Insert a vertex every time the path crosses a portal instead of only at the corners of the path.
		/// The resulting path will have exactly one vertex per portal if this is enabled.
		/// This may introduce vertices with the same position in the output (esp. in corners where many portals meet).
		/// [Open online documentation to see images]
		/// </summary>
		public bool splitAtEveryPortal;

#if UNITY_EDITOR
		[UnityEditor.MenuItem("CONTEXT/Seeker/Add Funnel Modifier")]
		public static void AddComp (UnityEditor.MenuCommand command) {
			(command.context as Component).gameObject.AddComponent(typeof(FunnelModifier));
		}
#endif

		public override int Order { get { return 10; } }

		public override void Apply (Path p) {
			if (p.path == null || p.path.Count == 0 || p.vectorPath == null || p.vectorPath.Count == 0) {
				return;
			}

			List<Vector3> funnelPath = ListPool<Vector3>.Claim();

			// Split the path into different parts (separated by custom links)
			// and run the funnel algorithm on each of them in turn
			var parts = Funnel.SplitIntoParts(p);

			if (parts.Count == 0) {
				// As a really special case, it might happen that the path contained only a single node
				// and that node was part of a custom link (e.g added by the NodeLink2 component).
				// In that case the SplitIntoParts method will not know what to do with it because it is
				// neither a link (as only 1 of the 2 nodes of the link was part of the path) nor a normal
				// path part. So it will skip it. This will cause it to return an empty list.
				// In that case we want to simply keep the original path, which is just a single point.
				return;
			}

			for (int i = 0; i < parts.Count; i++) {
				var part = parts[i];
				if (!part.isLink) {
					var portals = Funnel.ConstructFunnelPortals(p.path, part);
					var result = Funnel.Calculate(portals, unwrap, splitAtEveryPortal);
					funnelPath.AddRange(result);
					ListPool<Vector3>.Release(ref portals.left);
					ListPool<Vector3>.Release(ref portals.right);
					ListPool<Vector3>.Release(ref result);
				} else {
					// non-link parts will add the start/end points for the adjacent parts.
					// So if there is no non-link part before this one, then we need to add the start point of the link
					// and if there is no non-link part after this one, then we need to add the end point.
					if (i == 0 || parts[i-1].isLink) {
						funnelPath.Add(part.startPoint);
					}
					if (i == parts.Count - 1 || parts[i+1].isLink) {
						funnelPath.Add(part.endPoint);
					}
				}
			}

			UnityEngine.Assertions.Assert.IsTrue(funnelPath.Count >= 1);
			ListPool<Funnel.PathPart>.Release(ref parts);
			// Pool the previous vectorPath
			ListPool<Vector3>.Release(ref p.vectorPath);
			p.vectorPath = funnelPath;
		}
	}
}