基于四叉树的场景管理

场景管理"/>

基于四叉树的场景管理

一、解决的问题

在游戏地图中有很多对象，根据视野范围内的区域，并把这些区域的对象显示出来，其它不在视野范围的不显示。

效果如下：

二、四叉树原理

在数据结构中，树常常用于层级管理，就像我们国家行政单位一样，从国家-->省-->市-->县（区）-->街道（村）

这样每个人属于哪个地方就很清楚了。

同样我们在游戏场景中也可以对游戏地图做类似的分类，基于地图的形状样式，使用四分法会比较方便，且层次又不会太多，所以我们选用四叉树来对场景进行管理。

三、使用四叉树创建地图分区

1.先定义一个完整的树

maxChildCount 即为使用四叉树，maxDepth 为我们树划分层数，同时使用Bounds把划分的区域绘制出来。

public class Tree : INode
{public Bounds bound { get; set; }//包围盒private Node root;public int maxDepth { get; set; } //最大深度public int maxChildCount { get; set; }//最大叶子数public Tree(Bounds bound)//构造函数 构造树{this.bound = bound;this.maxDepth = 5;this.maxChildCount = 4;root = new Node(bound, 0, this);}public void InsertObj(ObjData obj){root.InsertObj(obj);}public void TriggerMove(Camera camera){root.TriggerMove(camera);}public void DrawBound(){root.DrawBound();}
}

2.定义节点

objList用来管辖当前节点的物体

这里使用InsertObj() 的递归来把物体逐步分到底层节点，当一个物体同时属于两个或多个子节点，则划到当前节点。

public class Node : INode
{public Bounds bound { get; set; }//包围盒private int depth;//深度private Tree belongTree;//所属子树private Node[] childList;//当前树节点的子节点private List<ObjData> objList;//节点中的物体public Node(Bounds bound, int depth, Tree belongTree){this.belongTree = belongTree;this.bound = bound;this.depth = depth;//childList = new Node[belongTree.maxChildCount];objList = new List<ObjData>();}public void InsertObj(ObjData obj)//插入对象{Node node = null;bool bChild = false;if(depth < belongTree.maxDepth && childList == null)//如果深度小于数的最大子节点数    并且没有子节点{//如果还没到叶子节点，可以拥有儿子且儿子未创建，则创建儿子CerateChild();}if(childList != null){for (int i = 0; i < childList.Length; ++i){Node item = childList[i];if (item == null){break;}if (item.bound.Contains(obj.pos)){if (node != null){bChild = false;break;}node = item;bChild = true;}}}if (bChild){//只有一个儿子可以包含该物体，则该物体node.InsertObj(obj);}else{objList.Add(obj);}}public void TriggerMove(Camera camera){//刷新当前节点for(int i = 0; i < objList.Count; ++i){//进入该节点中意味着该节点在摄像机内，把该节点保存的物体全部创建出来ResourcesManager.Instance.LoadAsync(objList[i]);}if(depth == 0){ResourcesManager.Instance.RefreshStatus();}//刷新子节点if (childList != null){for(int i = 0; i < childList.Length; ++i){if (childList[i].bound.CheckBoundIsInCamera(camera)){childList[i].TriggerMove(camera);}}}}private void CerateChild()//创建孩子{childList = new Node[belongTree.maxChildCount];int index = 0;for(int i = -1; i <= 1; i+=2){for(int j = -1; j <= 1; j+=2){Vector3 centerOffset = new Vector3(bound.size.x / 4 * i, 0, bound.size.z / 4 * j);Vector3 cSize = new Vector3(bound.size.x / 2, bound.size.y, bound.size.z / 2);Bounds cBound = new Bounds(bound.center + centerOffset, cSize);childList[index++] = new Node(cBound, depth + 1, belongTree);}}}public void DrawBound()//绘制包围盒{if(objList.Count != 0)//范围内有物体就画蓝色{Gizmos.color = Color.blue;Gizmos.DrawWireCube(bound.center, bound.size - Vector3.one * 0.1f);}else//没有就画红色{Gizmos.color = Color.green;Gizmos.DrawWireCube(bound.center, bound.size - Vector3.one * 0.1f);}if(childList != null)//孩子节点也是一样的绘制{for(int i = 0; i < childList.Length; ++i){childList[i].DrawBound();}}}
}

3.场景启动类

objList为场景中所有的物体

[System.Serializable]
public class Main : MonoBehaviour
{[SerializeField]public List<ObjData> objList = new List<ObjData>();//可观察物体列表public Bounds mainBound;//主包围盒(最大的范围)private Tree tree;//构建树private bool bInitEnd = false;//是否初始化完成private Role role;//人物(主角)public bool isDebug;public void Awake(){tree = new Tree(mainBound);//创建树根节点for(int i = 0; i < objList.Count; ++i)//把可观察的这些物体都插入到对应的树节点去{tree.InsertObj(objList[i]);}role = GameObject.Find("Role").GetComponent<Role>();bInitEnd = true;}private void Update(){if (role.bMove){tree.TriggerMove(role.mCamera);}}private void OnDrawGizmos(){if (!isDebug){return; }if (bInitEnd){tree.DrawBound();}else{Gizmos.DrawWireCube(mainBound.center, mainBound.size);//画出一个最大的包围盒}}}

四、判断区域是否在相机范围内

对bound来说，它有8个点，当它的8个点同时处于摄像机裁剪块上方/下方/前方/后方/左方/右方，那么该bound不与摄像机可视范围交叉

public static class Expand 
{public static bool CheckBoundIsInCamera(this Bounds bound, Camera camera)//检测物体是否在摄像机范围内{System.Func<Vector4, int> ComputeOutCode = (projectionPos) =>{int _code = 0;if (projectionPos.x < -projectionPos.w) _code |= 1;if (projectionPos.x > projectionPos.w) _code |= 2;if (projectionPos.y < -projectionPos.w) _code |= 4;if (projectionPos.y > projectionPos.w) _code |= 8;if (projectionPos.z < -projectionPos.w) _code |= 16;if (projectionPos.z > projectionPos.w) _code |= 32;return _code;};Vector4 worldPos = Vector4.one;int code = 63;for (int i = -1; i <= 1; i += 2){for (int j = -1; j <= 1; j += 2){for (int k = -1; k <= 1; k += 2){worldPos.x = bound.center.x + i * bound.extents.x;worldPos.y = bound.center.y + j * bound.extents.y;worldPos.z = bound.center.z + k * bound.extents.z;code &= ComputeOutCode(camera.projectionMatrix * camera.worldToCameraMatrix * worldPos);}}}return code == 0 ? true : false;}
}