popo

unity-doc-四叉树管理场景

Posted on Edited on

介绍

当场景元素过多时，需要实时的显示及隐藏物体使得性能提示，但是物体那么多，怎么知道哪些物体需要显示，哪些物体不需要显示的。当然，遍历物体判断该物体是否可以显示是最容易想到的方法，但是每次更新要遍历所有物体的代价很高。

假设场景是一维的，所有物体从左到右排成一条线，那么用二分法就可以快速找出距离自己一定范围内的物体。

同样四叉树的原理像二分一样，只是二分法处理的是一维世界， 四叉树处理的是二维世界，再往上三维世界用八叉树处理。

根节点是整个场景区域，然后分成四块：左上右上左下右下，分别作为根节点的儿子，然后每个儿子又分成四块重复之前步骤，这就是一棵四叉树。对于某些物体比较大，刚好在多个块的边界上，将这些物体放在所属块的父亲节点上去管理。

实战

例子运行图
QuadTree.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
using System.Collections.Generic;
using UnityEngine;

public interface INode
{
    Bounds Bound { get; set; }
    void InsertObj(SceneGoSaveInfo obj);
    void TriggerMove(Camera camera);
    void DrawBound();
}

public class Node : INode
{
    public Bounds Bound { get; set; }       
    
    private int depth;              // 节点的深度
    private QuadTree belongTree;    // 节点所属的树
    private Node[] arrChildNode;    // 子节点集合
    
    private List<SceneGoSaveInfo> listSaveInfo;     // 节点包含的物件存储信息列表
    
    public Node(Bounds bound, int depth, QuadTree belongTree)
    {
        this.belongTree = belongTree;
        this.Bound = bound;
        this.depth = depth;
        listSaveInfo = new List<SceneGoSaveInfo>();
    }
    
    public void InsertObj(SceneGoSaveInfo obj)
    {
        Node node = null;
        bool bChild = false;
        
        if(depth < belongTree.MaxDepth && arrChildNode == null)
        {
            // 如果还没到叶子节点，可以拥有儿子且儿子未创建，则创建儿子
            CerateChild();
        }
        if(arrChildNode != null)
        {
            for (int i = 0; i < arrChildNode.Length; ++i)
            {
                Node item = arrChildNode[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
        {
            listSaveInfo.Add(obj);
        }
    }

    public void TriggerMove(Camera camera)
    {
        // 刷新当前节点
        for(int i = 0; i < listSaveInfo.Count; ++i)
        {
            // 进入该节点中意味着该节点在摄像机内，把该节点保存的物体全部创建出来
            ResourcesManager.Instance.LoadAsync(listSaveInfo[i]);
        }

        if(depth == 0)
        {
            ResourcesManager.Instance.RefreshStatus();
        }

        // 刷新子节点
        if (arrChildNode != null)
        {
            for(int i = 0; i < arrChildNode.Length; ++i)
            {
                if (Help.IsBoundInCameraView(arrChildNode[i].Bound, camera))
                {
                    arrChildNode[i].TriggerMove(camera);
                }
            }
        }
    }
 
    private void CerateChild()
    {
        arrChildNode = 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);
                arrChildNode[index++] = new Node(cBound, depth + 1, belongTree);
            }
        }
    }
    
    public void DrawBound()
    {
        if(listSaveInfo.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(arrChildNode != null)
        {
            for(int i = 0; i < arrChildNode.Length; ++i)
            {
                arrChildNode[i].DrawBound();
            }
        }
        
    }
}

public class QuadTree : INode
{
    public Bounds Bound { get; set; }
    public int MaxDepth { get; }
    public int MaxChildCount { get; }
    
    private Node root;      // 根节点

    public QuadTree(Bounds bound)
    {
        this.Bound = bound;
        this.MaxDepth = 5;
        this.MaxChildCount = 4;
        
        root = new Node(bound, 0, this);
    }

    public void InsertObj(SceneGoSaveInfo obj)
    {
        root.InsertObj(obj);
    }

    public void TriggerMove(Camera camera)
    {
        root.TriggerMove(camera);
    }

    public void DrawBound()
    {
        root.DrawBound();
    }
}
ResourcesManager.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public enum SceneObjStatus
{
    OLD,        // 这次刷新没有加载
    LOADING,    // 加载中
    NEW,        // 这次刷新加载
}


public class SceneObj
{
    public SceneGoSaveInfo SaveInfo;    // 摆放存储信息
    public SceneObjStatus Status;       // 物件状态
    public GameObject GoInst;           // 物件实例

    public SceneObj(SceneGoSaveInfo data)
    {
        this.SaveInfo = data;
        this.GoInst = null;
    }
}

public class ResourcesManager : MonoBehaviour
{
    public static ResourcesManager Instance;

    public float delTime = 2;
    
    private List<string> listTmpDeleteUid = new List<string>(); // 临时列表-存储要移除的物件uid

    /// <summary>
    /// 当前在显示的物件映射
    /// key => 物件uid
    /// val =》物件实例信息
    /// </summary>
    private Dictionary<string, SceneObj> dicActiveObj = new Dictionary<string, SceneObj>();

    /// <summary>
    /// 当前不在显示的物件物件映射
    /// key =》物价uid
    /// val =》物件信息
    /// </summary>
    private Dictionary<string, SceneObj> dicInactiveObj = new Dictionary<string, SceneObj>();

    private void Awake()
    {
        Instance = this;
    }

    private void OnEnable()
    {
        StartCoroutine(IEDelete());
    }

    private IEnumerator IEDelete()
    {
        while (true)
        {
            foreach(var pair in dicInactiveObj)
            {
                Destroy(pair.Value.GoInst);
            }
            
            dicInactiveObj.Clear();
            yield return new WaitForSeconds(delTime);
        }
    }
    
    private IEnumerator IELoad(SceneGoSaveInfo obj)
    {
        SceneObj sceneObj = new SceneObj(obj);
        sceneObj.Status = SceneObjStatus.LOADING;
        dicActiveObj.Add(obj.Uid, sceneObj);
        GameObject resObj = null;
        
        ResourceRequest request = Resources.LoadAsync<GameObject>(obj.Path);
        yield return request;
        resObj = request.asset as GameObject;
        
        CreateObj(resObj, sceneObj);
        sceneObj.Status = SceneObjStatus.NEW;
    }


    public SceneObj CheckIsActive(string sUid)
    {
        SceneObj obj;
        if(dicActiveObj.TryGetValue(sUid, out obj))
        {
            return obj;
        }
        return null;
    }

    private bool MoveToActive(SceneGoSaveInfo obj)
    {
        SceneObj sceneObj;
        if (dicInactiveObj.TryGetValue(obj.Uid, out sceneObj))
        {
            sceneObj.GoInst.SetActive(true);
            sceneObj.Status = SceneObjStatus.NEW;
            dicActiveObj.Add(obj.Uid, sceneObj);
            dicInactiveObj.Remove(obj.Uid);
            return true;
        }
        
        return false;
    }

    public bool MoveToInActive(SceneGoSaveInfo obj)
    {
        SceneObj sceneObj;
        if (dicActiveObj.TryGetValue(obj.Uid, out sceneObj))
        {
            sceneObj.GoInst.SetActive(false);
            dicInactiveObj.Add(obj.Uid, sceneObj);
            dicActiveObj.Remove(obj.Uid);
            return true;
        }
        return false;
    }

    private void CreateObj(GameObject prefab, SceneObj sceneObj)
    {
        sceneObj.GoInst = Instantiate(prefab);
        sceneObj.GoInst.transform.position = sceneObj.SaveInfo.Pos;
        sceneObj.GoInst.transform.rotation = sceneObj.SaveInfo.Rotation;
    }
    
    public void LoadAsync(SceneGoSaveInfo obj)
    {
        if (CheckIsActive(obj.Uid) != null)
        {
            return;
        }
        if (!MoveToActive(obj))
        {
            StartCoroutine(IELoad(obj));
        }
    }

    
    public void RefreshStatus()
    {
        listTmpDeleteUid.Clear();
        
        foreach (var pair in dicActiveObj)
        {
            SceneObj sceneObj = pair.Value;
            if(sceneObj.Status == SceneObjStatus.OLD)
            {
                listTmpDeleteUid.Add(pair.Key);
            }
            else if(sceneObj.Status == SceneObjStatus.NEW)
            {
                sceneObj.Status = SceneObjStatus.OLD;
            }
        }
        
        for(int i = 0; i < listTmpDeleteUid.Count; ++i)
        {
            MoveToInActive(dicActiveObj[listTmpDeleteUid[i]].SaveInfo);
        }
    }
}
Help.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using UnityEngine;

public static class Help 
{
    /// <summary>
    /// 判断某个包围盒子是否在射击视野内
    /// </summary>
    public static bool IsBoundInCameraView(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;
    }
}

代码地址 https://gitee.com/hahafox_0/unity-example-scene-quad-tree