實作三角視線測敵, Triangular field of view via BoxOverlap + Raycast

實作三角視線測敵, Triangular field of view via BoxOverlap + Raycast

很久以前寫過一篇 二分法, 障礙物邊沿查找 & 資源管理 結果好像不小心誤導了一些網友以為這是正常的做法….
不會喇~~ 跟著做一定被主管打槍, 太浪費資源咯.
所以最近有機會寫一下 Behavior tree 的底層代碼, 需要重新教 NPC 走路…
順帶需要實現三角視線測敵的方式,又要保持性能優化,今次就來實現一個比較簡單的實作方式.
構想很簡單

  • 訂好可視的最遠距離 & 角度
  • 先用 OverlapBox 把範圍內可以看到的東西統統記下來
  • 再 for..loop 逐個檢查是不是能由NPC 眼睛直接 “看到”對方
  • 把結果暫存下來給其他程序訪問.

化成要求大概是這樣.

  1. 先用 OverlapBoxNonAlloc 來檢定範圍來的目標
  2. 使用 Overlap 的回傳結果對目標進行篩選, 並使用 Raycast剔除角度及距離外的目標, 只留下適合的目標.
  3. 只在 FixedUpdate 中算時間, 執行間隔優化 (to 初心, 因為我們不介意物件在 < 1 秒的間隔之間是否進入視角範圍,別浪費資源)
  4. 額外 : 利用三角定理自動算出 Overlap Box 的位置 (為了躲懶更直觀的用距離+角度來設定)

實作心得 – 執行間隔優化

一個常用的小技巧對一些無需每秒執行 60次的代碼進行定期更新的寫法 periodic update. 好像沒有寫過文就順便這裡寫寫.

// 希望更新的間隔(可調)
public float m_Interval = 0.5f; 


// 防止同一幀內執行多次 FixedUpdate
private int m_FrameCount = 0;
// 紀錄上次執行時間
private float m_LastPeepTime = 0f;

private void FixedUpdate()
{
	if (m_FrameCount != Time.frameCount &&
		Time.timeSinceLevelLoad - m_LastPeepTime >= m_Interval)
	{
		m_LastPeepTime = Time.timeSinceLevelLoad;
		m_FrameCount = Time.frameCount;
		
		TakeALook(); // 希望進行的動作.
	}
}

實作心得 – 視角範圍檢測

在製作上由於希望自動算出 OverlapBox 的最小範圍我使用以下的辦法.
1) 查找 Box 的垂直中心, 由眼晴到最遠距離, 由於 Vector3.Lerp 的特性我們直接以 0.5f 就可以找取垂直的距離
2) 查找 Box 的橫向距離, 以人物的眼晴作為圓心, 最遠視距當半徑, 可視角度則以三角函數用查找對邊, 從而得知橫向闊度
3) 至此 Overlap Box 的中心, 長寬, 旋轉角 資訊齊備.

前向 180 度的計算

4)當視角超過 180 度的時候以另一種解法, 前半由於圓型半徑關係已經得知最長寬度是 Radius * 2f
5)把超過的角度減一個 90 度又可以再使用同樣手法查找餘下一半的最短長度.
6)然後與前面的半徑相加即可取得這個 Overlap Box 的長寬

成品 – 壓力測試

成品的壓力測試.

粗略的創建 50 個這種形的 Agent, 在 Deep Profile 的測試下.
總合的 AvatarEye.Peep() 即本程序 50 次用了 13.07ms, 0gc
其中
Raycast call 359 次,用了 1.29ms, 0gc
OverlapBox call 50 次,用了 0.65ms, 0gc
即是 Raycast 的成本只佔整體的 20% 其餘就是運算 vector 及 hashset 的分佈.
個人覺得成績還是不錯的畢竟還是在 main thread 上運作.
可以再進一步的壓縮就是略去那堆計算 OverlapBox size 的 vector projection 應該可以更進一步壓縮時間,
但考慮到過於繁複的設定, 以及使用者設定出錯所衍生的問題… 嗯, 能令我懶惰的選擇就是好選擇.

以下就是視頻版的測試代碼.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace Kit.Avatar
{
    public class AvatarEye : SensorBase, ICanSee
    {
        #region Debug
        [System.Flags]
        public enum eDebugDraw
        {
            Label = 1 << 0,
            VisiableArea = 1 << 1,
            InSightTarget = 1 << 2,
            OverlapSizeDebug = 1 << 3,
            OverlapBox = 1 << 4,
        }
        [System.Serializable]
        public class DebugInfo
        {
            [MaskField(typeof(eDebugDraw))] public eDebugDraw draw = (eDebugDraw)0;
            public Vector2 labelOffset = Vector2.zero;
            public Color areaColor = Color.yellow.CloneAlpha(.1f);
            public Color targetColor = Color.red.CloneAlpha(.4f);
            public Color halfExtendsColor = Color.cyan.CloneAlpha(.5f);
            public Color overlapColor = Color.green.CloneAlpha(.5f);
        }
        [SerializeField] DebugInfo m_Debug = new DebugInfo();
        private void DebugGizmos()
        {
            if ((int)m_Debug.draw == 0)
                return;
            if (!Application.isPlaying)
                Peep();

            Vector3 eyePos, boxCenter, halfExtends;
            Quaternion orientation;

            GetEyePivot(out Transform bone, out eyePos);
            CalculateOverlapBox(eyePos, out boxCenter, out halfExtends, out orientation);

            if (m_Debug.draw.HasFlag(eDebugDraw.VisiableArea))
            {
                Vector3 forward = orientation * Vector3.forward;
                Vector3 up = orientation * Vector3.up;
                GizmosExtend.DrawArc(eyePos, up, forward, m_ViewAngle * 0.5f, m_MaxDistance, m_Debug.areaColor);
                GizmosExtend.DrawArc(eyePos, up, forward, m_ViewAngle * -0.5f, m_MaxDistance, m_Debug.areaColor);
            }

            if (m_Debug.draw.HasFlag(eDebugDraw.InSightTarget))
            {
                foreach (var t in m_TargetsInSight)
                {
                    GizmosExtend.DrawLine(eyePos, t.point, m_Debug.targetColor);
                    GizmosExtend.DrawSphere(t.point, 0.05f, m_Debug.targetColor);
                    if (m_Debug.draw.HasFlag(eDebugDraw.Label))
                    {
                        GizmosExtend.DrawLabel(t.point, t.ToString(), m_Debug.labelOffset);
                    }
                }
            }

            if (m_Debug.draw.HasFlag(eDebugDraw.OverlapBox))
            {
                GizmosExtend.DrawBox(boxCenter, halfExtends, orientation, m_Debug.overlapColor);
            }
        }
        #endregion Debug

        #region Setting
        [Header("Eye Sight")]
        [SerializeField] private bool m_CanSee = false;

        [SerializeField] private bool m_UseHumanoidBone = true;
        [SerializeField] private HumanBodyBones m_HumanBodyBones = HumanBodyBones.Head;
        [SerializeField] private Vector3 m_EyeOffset = Vector3.zero;
        [SerializeField] private Vector3 m_BodyRotationOffset = Vector3.zero;
        [SerializeField] private float m_MaxDistance = 1f;
        [SerializeField, Range(0f, 360f)] float m_ViewAngle = 30f;

        [Header("Optimization")]
        [SerializeField, Range(0.0001f, 0.1f)] private float m_Deviation = 0.05f;
        [Help("Memory alloc for BoxOverlap detection.", eMessageType.Info)]
        [SerializeField] private int m_MemorySize = 5;
        private Collider[] m_OverlapColliders = { };
        private RaycastHit m_DirectHitTest;
        [Tooltip("Based on FixedUpdate.")]
        [SerializeField] private float m_Interval = 0.02f;

        [Header("Physics")]
        [Help("The layers of attackable target.\nE.g. Player, Enemies...etc")]
        [SerializeField] private LayerMask m_TargetMask = Physics.DefaultRaycastLayers;
        [Help("The layers of obstacle, anything that CAN NOT see through\nE.g. Wall, Door", eMessageType.Warning)]
        [SerializeField] private LayerMask m_BlockableMask = Physics.IgnoreRaycastLayer;
        [SerializeField] private QueryTriggerInteraction m_QueryTriggerInteraction = QueryTriggerInteraction.Collide;
        #endregion Setting

        #region System
        protected override void OnEnable()
        {
            base.OnEnable();
            // little hack to distribute see time
            m_LastPeepTime = Time.timeSinceLevelLoad + Random.value;
        }
        private void OnDrawGizmos()
        {
            DebugGizmos();
        }

        private void FixedUpdate()
        {
            if (CanSee() &&
                m_FrameCount != Time.frameCount &&
                Time.timeSinceLevelLoad - m_LastPeepTime >= m_Interval)
            {
                m_LastPeepTime = Time.timeSinceLevelLoad;
                m_FrameCount = Time.frameCount;
                Peep();
            }
        }
        #endregion System

        #region Core
        private HashSet<TargetInSight> m_TargetsInSight = new HashSet<TargetInSight>(new TargetInSightComparer());
        
        public ICollection<TargetInSight> GetTargetsInSight()
        {
            return m_TargetsInSight;
        }
        private float m_LastPeepTime = 0f;
        private int m_FrameCount = 0;

        public bool CanSee()
        {
            return m_CanSee;
        }

        private void Peep()
        {
            // Allocate memory
            if (m_OverlapColliders.Length != m_MemorySize)
                m_OverlapColliders = new Collider[m_MemorySize];
            m_TargetsInSight.Clear(); // clean previous result.

            // Calculate area
            GetEyePivot(out Transform bone, out Vector3 eyePos);
            CalculateOverlapBox(eyePos, out Vector3 boxCenter, out Vector3 halfExtends, out Quaternion orientation);

            // AABB test
            int hitCount = Physics.OverlapBoxNonAlloc(boxCenter, halfExtends, m_OverlapColliders, orientation, m_TargetMask, m_QueryTriggerInteraction);
            for (int i = 0; i < hitCount && i < m_OverlapColliders.Length; i++)
            {
                if (m_OverlapColliders[i].transform.IsChildOf(avatar.transform))
                    continue; // ignore common case to saw owner.
                CheckIfColliderInSight(eyePos, orientation, orientation * Vector3.forward, m_OverlapColliders[i]);
            }
        }
        private void CheckIfColliderInSight(Vector3 eyePos, Quaternion orientation, Vector3 facing, Collider collider)
        {
            Vector3 targetClosestPoint = collider.ClosestPoint(eyePos);
            Vector3 sightVectorProjected = Vector3.ProjectOnPlane(targetClosestPoint - eyePos, orientation * Vector3.up);
            float forwardAngle = Vector3.Angle(facing, sightVectorProjected);
            if (forwardAngle <= m_ViewAngle * 0.5f)
            {
                // Within view angle, check obstacle blocked or not.
                int mix = m_BlockableMask.value | m_TargetMask.value;
                if (Physics.Raycast(eyePos, sightVectorProjected, out m_DirectHitTest, m_MaxDistance, mix, m_QueryTriggerInteraction))
                {
                    // we should either hit obstacle layer, or target itself.
                    if (m_TargetMask.Contain(m_DirectHitTest.transform.gameObject) || // is target
                        m_DirectHitTest.transform.IsChildOf(collider.transform)) // is part of target
                    {
                        m_TargetsInSight.Add((TargetInSight)m_DirectHitTest); // Target in sight.
                    } // else, it's blocked by obstacle.
                }
            }// else, common case, out of range angle / distance
        }
        private void GetEyePivot(out Transform bone, out Vector3 pos)
        {
            bone = transform;
            if (m_UseHumanoidBone)
            {
                var tmp = avatar.avatarAnimator.GetBoneTransform(m_HumanBodyBones);
                if (tmp) // in case fail to locate bone transform
                    bone = tmp;
            }

            pos = bone.position;
            if (m_EyeOffset != Vector3.zero)
                pos = bone.TransformPoint(m_EyeOffset);
        }
        private void CalculateOverlapBox(Vector3 eyePos, out Vector3 boxCenter, out Vector3 halfExtends, out Quaternion orientation)
        {
            orientation = avatar.body.transform.rotation;
            if (m_BodyRotationOffset != Vector3.zero)
                orientation = avatar.body.transform.rotation * Quaternion.Euler(m_BodyRotationOffset);

            float angle = m_ViewAngle * 0.5f;
            Vector3 farPlanePivot = eyePos + orientation * Vector3.forward * m_MaxDistance;
            if (angle < 90f)
            {
#if TAN
                // Since tan version require loopup table, it require CPU cost
                float half = Mathf.Tan(Mathf.Deg2Rad * angle) * m_MaxDistance;
                //DebugExtend.DrawRay(farPlanePivot, orientation * Vector3.right * half, Color.cyan);
                //DebugExtend.DrawRay(farPlanePivot, orientation * Vector3.right * -half, Color.cyan);
#else
                Vector3 angleVector = orientation * Quaternion.Euler(0f, angle, 0f) * new Vector3(0f, 0f, m_MaxDistance);
                Vector3 angleVectorEndPoint = eyePos + angleVector;
                Vector3 projectToRight = Vector3.Project(angleVector, orientation * Vector3.right);
                if (m_Debug.draw.HasFlag(eDebugDraw.OverlapSizeDebug))
                {
                    DebugExtend.DrawPoint(angleVectorEndPoint, m_Debug.halfExtendsColor, 0.5f);
                    DebugExtend.DrawRay(angleVectorEndPoint, -projectToRight, m_Debug.halfExtendsColor);
                }
                float half = projectToRight.magnitude;
#endif           
                half = Mathf.Clamp(half, 0f, m_MaxDistance);
                boxCenter = Vector3.Lerp(farPlanePivot, eyePos, 0.5f);
                halfExtends = new Vector3(half, m_Deviation, m_MaxDistance * 0.5f);
            }
            else
            {
#if TAN
                float angleBehind = angle - 90f;
                float behind = Mathf.Atan(Mathf.Deg2Rad * angleBehind) * m_MaxDistance;
#else
                Vector3 angleVector = orientation * Quaternion.Euler(0f, angle, 0f) * new Vector3(0f, 0f, m_MaxDistance);
                Vector3 angleVectorEndPoint = eyePos + angleVector;
                Vector3 projectToBack = Vector3.Project(angleVector, orientation * Vector3.back);
                if (m_Debug.draw.HasFlag(eDebugDraw.OverlapSizeDebug))
                {
                    DebugExtend.DrawPoint(angleVectorEndPoint, m_Debug.halfExtendsColor, 0.5f);
                    DebugExtend.DrawRay(angleVectorEndPoint, -projectToBack, m_Debug.halfExtendsColor);
                }
                float behind = projectToBack.magnitude;
#endif
                behind = Mathf.Clamp(behind, 0f, m_MaxDistance);
                Vector3 behindPlanePivot = eyePos + orientation * Vector3.back * behind;
                boxCenter = Vector3.Lerp(farPlanePivot, behindPlanePivot, 0.5f);
                halfExtends = new Vector3(m_MaxDistance, m_Deviation, (m_MaxDistance + behind) * 0.5f);
            }
        }
        #endregion Core
    }
}
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace Kit.Avatar
{
    public class SensorBase : AvatarSubset { }

    public struct TargetInSight :
        IEqualityComparer<TargetInSight>,
        IEqualityComparer<RaycastHit>
    {
        public Transform transform;
        public Rigidbody rigidbody;
        public ArticulationBody articulationBody;
        public Collider collider;

        public Vector3 point;
        public Vector3 normal;
        public float distance;

        private bool m_GeneratedHashCode;
        private int hashCode;

        public bool Equals(TargetInSight x, TargetInSight y)
        {
            return x.collider.Equals(y.collider);
        }
        public int GetHashCode(TargetInSight obj)
        {
            if (!m_GeneratedHashCode)
                hashCode = obj.collider.GetHashCode();//Extensions.GenerateHashCode(obj.collider,obj.distance,obj.point);
            return hashCode;
        }

        public bool Equals(RaycastHit x, RaycastHit y)
        {
            return x.collider.Equals(y.collider);
        }
        public int GetHashCode(RaycastHit obj)
        {
            if (!m_GeneratedHashCode)
                hashCode = obj.collider.GetHashCode();
            return hashCode;
        }

        public override int GetHashCode()
        {
            if (!m_GeneratedHashCode)
                hashCode = collider.GetHashCode();
            return hashCode;
        }

        public override string ToString()
        {
            return $"[TargetInSign:{transform}\nPoint:{point}\nDistance:{distance:F2}]";
        }
        public static implicit operator TargetInSight (RaycastHit raycastHit)
        {
            return new TargetInSight
            {
                transform = raycastHit.transform,
                rigidbody = raycastHit.rigidbody,
                articulationBody = raycastHit.articulationBody,
                collider = raycastHit.collider,
                point = raycastHit.point,
                normal = raycastHit.normal,
                distance = raycastHit.distance,
            };
        }
        public static explicit operator Transform(TargetInSight targetInSign)
        {
            return targetInSign.transform;
        }
    }
    public class TargetInSightComparer : IEqualityComparer<TargetInSight>
    {
        public bool Equals(TargetInSight x, TargetInSight y)
        {
            return x.collider.Equals(y.collider);
        }

        public int GetHashCode(TargetInSight obj)
        {
            return obj.collider.GetHashCode();
        }
    }
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。

*

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料