二分法, 障礙物邊沿查找 & 資源管理

本次項目,主要概念從這裡得到啟發 : https://tedsieblog.wordpress.com/2017/02/22/field-of-view/

對 Ray 及 RaycastHit 進行擴建, 並整合自己常用的工具,達到有效開發為前題,來實現這次的項目。

畢竟,二分法射線這種現實可用的技巧還是有其實驗價值。

 

二分法很簡單的達成,但問題是如何快速進行運算, 實作的時候又進一步了解到 Raycast 的運作,其實真正要處理是如何在大量資料處理時有效分配資源。

簡單說就是資源分配。

二分法射線並不應該直接用在遊戲中,在 Unity 中還提供更快的 SphereCast, SphereCastAll, BoxCast …等等,
Ref : https://docs.unity3d.com/ScriptReference/Physics.SphereCastAll.html

 

直接上影像.

以下是整合 Ray 及 RaycastHit 的 Struct 這部份需留意(並不是class) ,這有助大量資訊操作的處理。

RayData.cs

using System;
using UnityEngine;

namespace Kit.Physic
{
	public struct RayData : IEquatable<RayData>
	{
		public static RayData NONE { get { return default(RayData); } }

		#region Core & constructor
		private Ray m_Ray;
		public Vector3 origin { get { return m_Ray.origin; } set { m_Ray.origin = value; } }
		public Vector3 direction { get { return m_Ray.direction; } set { m_Ray.direction = value; } }
		public Quaternion rotation
		{
			get { return Quaternion.Euler(m_Ray.direction); }
			set { m_Ray.direction = value * Vector3.forward; }
		}
		public float distance;
		public RaycastHit hit;
		public bool hitted { get { return hit.transform != null; } }
		
		public RayData(Ray ray, float distance)
		{
			m_Ray = ray;
			this.distance = distance;
			hit = new RaycastHit();
		}
		
		public RayData(Vector3 origin, Vector3 direction, float distance)
			: this(new Ray(origin, direction), distance)
		{ }
		#endregion

		#region Util tools
		public static bool IsNullOrEmpty(RayData obj)
		{
			return ReferenceEquals(null, obj) || obj.Equals(RayData.NONE);
		}

		/// <summary>Reuse the RayData for something else instead of alloc new memory</summary>
		/// <param name="_origin"></param>
		/// <param name="_direction"></param>
		/// <param name="_distance"></param>
		/// <param name="reset"></param>
		public void Update(Vector3 _origin, Vector3 _direction, float _distance)
		{
			origin = _origin;
			direction = _direction;
			distance = _distance;
		}

		/// <summary>Reuse the RayData for something else instead of alloc new memory</summary>
		/// <param name="other"></param>
		/// <param name="hitReferences">include the RaycastHit reference.</param>
		public void Update(RayData other, bool hitReferences = false)
		{
			Update(other.origin, other.direction, other.distance);
			if (hitReferences)
				hit = other.hit;
		}

		public void Reset()
		{
			origin = direction = Vector3.zero;
			distance = 0f;
			hit = new RaycastHit();
		}

		/// <summary>Physics.Raycast</summary>
		/// <param name="layerMask">default = Everything</param>
		/// <param name="queryTriggerInteraction">default = UseGlobal</param>
		/// <returns>return true when hitted.</returns>
		public bool Raycast(int layerMask = Physics.DefaultRaycastLayers, QueryTriggerInteraction queryTriggerInteraction = QueryTriggerInteraction.UseGlobal)
		{
			return Physics.Raycast(m_Ray, out hit, distance, layerMask, queryTriggerInteraction);
		}
		
		/// <summary>Compare with hit result are hitting same object</summary>
		/// <param name="raycastHit"></param>
		/// <param name="includeNull"></param>
		/// <returns></returns>
		public bool IsHittingSameObject(RaycastHit raycastHit, bool includeNull = false)
		{
			return (includeNull || hitted) ? hit.transform == raycastHit.transform : false;
		}

		/// <summary>Compare with hit result are hitting same object</summary>
		/// <param name="raycastHit"></param>
		/// <param name="includeNull"></param>
		/// <returns></returns>
		public bool IsHittingSameObject(RayData raydata, bool includeNull = false)
		{
			return IsHittingSameObject(raydata.hit, includeNull);
		}

		/// <summary>Compare angle based on normal</summary>
		/// <param name="normal">World Up</param>
		public float AngleBetweenDirectionSigned(RayData rayB, Vector3 normal = default(Vector3))
		{
			return AngleBetweenDirectionSigned(rayB.m_Ray, normal);
		}

		/// <summary>Compare angle based on normal</summary>
		/// <param name="normal">World Up</param>
		public float AngleBetweenDirectionSigned(Ray otherRay, Vector3 normal = default(Vector3))
		{
			if (normal == default(Vector3))
				normal = Vector3.up;
			return Mathf.Rad2Deg * Mathf.Atan2(Vector3.Dot(normal, Vector3.Cross(m_Ray.direction, otherRay.direction)), Vector3.Dot(m_Ray.direction, otherRay.direction));
		}

		public void DrawGizmos(Color color = default(Color), Color hitColor = default(Color))
		{
			if (color == default(Color))
				return;
			Color cache = Gizmos.color;
			if (hitted)
			{
				if (hitColor == default(Color))
				{
					hitColor = color;
					color.a = Mathf.Lerp(0f, color.a, .5f);
				}
			}

			Gizmos.color = color;
			Gizmos.DrawLine(m_Ray.origin, m_Ray.origin + m_Ray.direction * distance);
#if UNITY_EDITOR
			Gizmos.DrawWireCube(m_Ray.origin, Vector3.one * 0.1f * UnityEditor.HandleUtility.GetHandleSize(m_Ray.origin));
#endif
			if (hitted)
			{
				Gizmos.color = hitColor;
				Gizmos.DrawLine(m_Ray.origin, hit.point);
			}
			Gizmos.color = cache;
		}
		#endregion

		#region overload methods
		public override string ToString()
		{
			return (hitted) ?
				string.Format("{0}, Distance: {1:F2}, Hit: {2} ({3:F2})", m_Ray.ToString("F2"), distance, hit.transform.name, hit.point) :
				string.Format("{0}, Distance: {1:F2}, Hit: None", m_Ray.ToString("F2"), distance);
		}

		public override int GetHashCode()
		{
			return m_Ray.GetHashCode();
		}
		public override bool Equals(object obj)
		{
			return Equals(NONE) ? obj == null : Equals((RayData)obj);
		}

		/// <summary>Approximately Equal, based on Ray and distance, exclude hit result.</summary>
		/// <param name="other"></param>
		/// <returns></returns>
		public bool Equals(RayData other)
		{
			if (GetHashCode() != other.GetHashCode())
				return false;
			else
			{
				return
					Mathf.Approximately(distance, other.distance) &&
					Mathf.Approximately(m_Ray.origin.x, other.origin.x) &&
					Mathf.Approximately(m_Ray.origin.y, other.origin.y) &&
					Mathf.Approximately(m_Ray.origin.z, other.origin.z) &&
					Mathf.Approximately(m_Ray.direction.x, other.direction.x) &&
					Mathf.Approximately(m_Ray.direction.y, other.direction.y) &&
					Mathf.Approximately(m_Ray.direction.z, other.direction.z);
			}
		}
		#endregion
	}
}

以上的 RayData.cs, 用來存  position, direction, distance, raycasthit 等的資料.

它是一個 struct 架構,優勢則在於資源管理.

Ref: Choosing Between Class and Struct
https://msdn.microsoft.com/en-us/library/ms229017(v=vs.110).aspx

用圖片看就很簡單易明, 這是 Array of Class
Array of a reference type

以下則是 Array of struct

Array of a value type

因為處理物理邊沿時需要大量處理這類的物理資訊,如果大量的建立 object 必然需要吃掉相對應的內存。

這時候如果重用變量 (reuse variables) 就變得相對嚴格。

 

接下來就是本次的主角 EdgeFinder, 使用二分法搜尋對象的邊沿。

EdgeFinder.cs

//#define BULLET_TIME
// ^ enable this if you want to visualize the progress with delay.

using UnityEngine;
using System.Collections;

namespace Kit.Physic
{
	public class EdgeFinder : MonoBehaviour
	{
		[Header("Ray Setting")]
		[SerializeField]
		int m_Density = 150;
		[SerializeField]
		float m_Distance = 10f;
		[SerializeField]
		float m_Threshold = float.Epsilon;
		const float MAX_THRESHOLD = 1f;

		[Header("Physics")]
		[SerializeField]
		LayerMask m_LayerMask = Physics.DefaultRaycastLayers;
		[SerializeField]
		QueryTriggerInteraction m_QueryTriggerInteraction = QueryTriggerInteraction.UseGlobal;

		[Header("Debug")]
		[SerializeField]
		Color m_Color = Color.white;
		[SerializeField]
		Color m_HitColor = Color.red;
#if BULLET_TIME
	[SerializeField] bool m_PreviewInEditor = false;
	[Range(-float.Epsilon, 0.1f)]
	[SerializeField] float m_WaitSec = 0.1f;
#endif

		RayData[] m_Sensors;
		RayData m_Finder;

		void OnValidate()
		{
			m_Density = Mathf.Clamp(m_Density, 0, int.MaxValue);
			m_Distance = Mathf.Clamp(m_Distance, 0f, float.MaxValue);
			m_Threshold = Mathf.Clamp(m_Threshold, float.Epsilon, MAX_THRESHOLD);
			Init();
		}

		void Awake()
		{
			Init();
		}

		void Init()
		{
			m_Sensors = new RayData[m_Density];
#if BULLET_TIME && UNITY_EDITOR
		if (m_PreviewInEditor)
		{
			StopAllCoroutines();
			Start();
		}
#else
			GetBisectionEdge(transform.position, transform.forward, transform.up, m_Threshold);
#endif
		}

		public void OnDrawGizmos()
		{
			if (!Application.isPlaying)
				Init();

			for (int i = 0; i < m_Sensors.Length; i++)
			{
				if (!RayData.IsNullOrEmpty(m_Sensors[i]))
					m_Sensors[i].DrawGizmos(m_Color, m_HitColor);
			}
		}

#if BULLET_TIME
	public void Start()
	{
		StartCoroutine(IntervalTrigger());
	}
	private IEnumerator IntervalTrigger()
	{
		while (true)
		{
			yield return GetBisectionEdge(transform.position, transform.forward, transform.up, m_Threshold);
		}
	}
#else
		void FixedUpdate()
		{
			GetBisectionEdge(transform.position, transform.forward, transform.up, m_Threshold);
		}
#endif

		private void CacheRayResult(Vector3 point, Vector3 startDirection, Vector3 normal, bool raycastTest = false)
		{
			Vector3 dir;
			float currAngle = 0f;
			float angleStep = 360f / m_Density;
			for (int i = 0; i < m_Density; i++)
			{
				dir = Quaternion.AngleAxis(currAngle, normal) * startDirection;
				m_Sensors[i].Update(point, dir, m_Distance);
				if (raycastTest)
					m_Sensors[i].Raycast(m_LayerMask, m_QueryTriggerInteraction);
				currAngle += angleStep;
			}
		}


#if BULLET_TIME
	private IEnumerator GetBisectionEdge(Vector3 point, Vector3 startDirection, Vector3 normal, float threshold)
#else
		private void GetBisectionEdge(Vector3 point, Vector3 startDirection, Vector3 normal, float threshold)
#endif
		{
			CacheRayResult(point, startDirection, normal, true);

			if (m_Density <= 1)
			{
				Debug.Log(GetType().Name + " at least two Raycast are required.");
			}
			else if (m_Density > 2)
			{
				int pt = m_Density, nextPt;
				while (pt-- > 0)
				{
					nextPt = Mathf.CeilToInt(Mathf.Repeat(pt - 1, m_Density));
					if (!m_Sensors[pt].hitted)
					{
						m_Sensors[pt] = RayData.NONE;
					}
					else if (!RayData.IsNullOrEmpty(m_Sensors[nextPt]))
					{
						// let's find the edge in between
						TryLocateBisectionEdge(ref m_Sensors[pt], ref m_Sensors[nextPt], ref m_Finder, m_LayerMask, m_QueryTriggerInteraction, threshold);
					}

#if BULLET_TIME
				if (m_WaitSec > 0f)
					yield return new WaitForSeconds(m_WaitSec);
#endif
				}
			}
#if BULLET_TIME
		yield return null;
#endif
		}

		/// <summary>Locate edge within two ray. limit by angle threshold</summary>
		/// <param name="start">Start arc direction</param>
		/// <param name="end">End arc direction</param>
		/// <param name="finder">Cache Helper</param>
		/// <param name="layerMask"></param>
		/// <param name="queryTriggerInteraction"></param>
		/// <param name="threshold">min angle</param>
		private void TryLocateBisectionEdge(ref RayData start, ref RayData end, ref RayData finder,
			int layerMask = Physics.DefaultRaycastLayers, QueryTriggerInteraction queryTriggerInteraction = QueryTriggerInteraction.UseGlobal,
			float threshold = float.Epsilon)
		{
			if (start.origin != end.origin)
			{
				Debug.LogWarning("Start origin should always equal.", this);
				start.origin = end.origin;
			}

			if (start.IsHittingSameObject(end, includeNull: true))
			{
				// both hit same thing || nothing, may cause by m_Density too low, we don't care at this point.
				finder.Reset();
				return;
			}
			else
			{
				if (!start.hitted && end.hitted)
				{
					// hit something, and one of it are Empty.
					// to combine case, alway making start as Empty. (locate direction will change)
					finder.Update(start, hitReferences: false);
					start.Update(end, hitReferences: false);
					end.Update(finder, hitReferences: false);
				}
				// else hit different object, no change.

				// reach angle threshold.
				threshold = Mathf.Clamp(threshold, float.Epsilon, MAX_THRESHOLD);
				if (threshold > Vector3.Angle(start.direction, end.direction))
				{
					finder.Reset();
					return;
				}

				// Bisection
				// recursive logic : assume origin point of start & end are equal.
				finder.Update(start.origin, Vector3.LerpUnclamped(start.direction, end.direction, .5f), start.distance);
				if (finder.Raycast(layerMask, queryTriggerInteraction))
				{
					// found the object, Move "end" closer
					end.Update(finder, hitReferences: true);
				}
				else
				{
					// not found, Move "start" closer
					end.Update(finder, hitReferences: true);
				}
				TryLocateBisectionEdge(ref start, ref end, ref finder, layerMask, queryTriggerInteraction, threshold);
			}
		}
	}
}

 

使用 Recursive 及 pass by reference 的方式,接近 Zero Garbage collect 來達到目的. 測試可見 360 支射線外加二分搜尋平均花 1.17ms 產生  100kb 拉圾.

主要的 GC 問題完全產生在 GetHashCode() 的配對上(嗯…或許我可以利用 cache 再減少一 30% ? 這有待試驗)

基本的二分法已經是 0 gc.

而本次的測試大概在 密度(Density) 設在 75, 180, 360 有相對佳的 C/P 值.

更多的密度對效果沒有太大提升而且浪費大量的 CPU 資源。

如果有更好或可改進的地方,歡迎留言討論。

Enjoy, happy coding

, ,
2 comments on “二分法, 障礙物邊沿查找 & 資源管理
  1. Wonderful implementation, but what about finding the edge of objects that are above, below – including the visual angles of such?

    Kinda like a 360 degree (or sphere) around the protagonist.

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *

*