四叉树是一种树状数据结构，在每一个节点上会有四个子区块。四叉树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。
四叉树在游戏中常常用于减少遍历的次数：
1.比如，地图上有N个怪，玩家砍了一刀，会砍到哪些怪？
2.再如，碰撞检测。
我们做个碰撞检测的对比测试。二维空间内有300对象，对象可以移动，可以碰撞。所以每帧要遍历300*300=90000次。使用四叉树后，可以减少这个遍历次数，以提高效率。
先看效果图：
每一幅图：四叉树深度为0，相当于没用四叉树。
遍历次数为：90000，fps为：25
第二幅图：四叉树深度为4，当前情况下的较为合理的深度
遍历次数约为：6500，fps为：60
以上对比结束已经说明了四叉树的用处。也可以自己手动对比：http://baaoo.com/qt/
下面上代码：
辅助类：四叉树包围盒
namespace GameBase.QT
{
/// <summary>
/// 四叉树的包围盒
/// </summary>
public struct AABB
{
public AABB(float xMin, float xMax, float yMin, float yMax)
{
this.xMin = xMin;
this.xMax = xMax;
this.yMin = yMin;
this.yMax = yMax;
this.xCenter = xMin + (xMax - xMin) * 0.5f;
this.yCenter = yMin + (yMax - yMin) * 0.5f;
}
public float xMin;
public float xMax;
public float yMin;
public float yMax;
public float xCenter;
public float yCenter;
public bool Contains(AABB aabb)
{
if (aabb.xMin > this.xMin && aabb.xMax < this.xMax && aabb.yMin > this.yMin && aabb.yMax < this.yMax)
{
return true;
}
return false;
}
public bool Intersect(AABB aabb)
{
if (aabb.xMin > this.xMax || aabb.xMax < this.xMin || aabb.yMin > this.yMax || aabb.yMax < this.yMin)
{
return false;
}
return true;
}
}
}
辅助类：四叉树包围盒接口
namespace GameBase.QT
{
public interface IAABB
{
AABB aabb { get; }
}
}
核心类：四叉树
using System.Collections.Generic;
namespace GameBase.QT
{
/// <summary>
/// y
/// ^
/// |
/// |
/// ② | ①
/// ---------|-------->x
/// ③ | ④
/// |
/// |
/// 象限标识及坐标方向
/// </summary>
/// <typeparam name="T"></typeparam>
public class QuadTree<T> where T : IAABB
{
#region 缓存节点(QuadTree)以减少GC,销毁时把所有的节点(QuadTree)存在root节点下。
private Queue<QuadTree<T>> _cacheQTQueue;
private QuadTree<T> CreateQT(QuadTree<T> parent, AABB aabb)
{
if(_root._cacheQTQueue != null && _root._cacheQTQueue.Count > 0)
{
QuadTree<T> result = _root._cacheQTQueue.Dequeue();
result.Reset(parent, aabb, _depthMax);
return result;
}
return new QuadTree<T>(parent, aabb, _depthMax);
}
private void DestroyQT(QuadTree<T> qt)
{
if (_root._cacheQTQueue == null)
{
_root._cacheQTQueue = new Queue<QuadTree<T>>();
}
_root._cacheQTQueue.Enqueue(qt);
}
#endregion
private int _depthMax;
public int DepthMax
{
get
{
return _depthMax;
}
set
{
_depthMax = value;
}
}
private int _depth;
private QuadTree<T> _parent;
private QuadTree<T> _root;
private QuadTree<T>[] _children;
public QuadTree<T>[] Children
{
get
{
return _children;
}
}
private AABB _aabb;
public AABB aabb
{
get
{
return _aabb;
}
}
private List<T> _objectList;
public List<T> ObjectList
{
get
{
return _objectList;
}
}
public QuadTree(QuadTree<T> parent, AABB aabb)
{
Reset(parent, aabb, 4);
}
public QuadTree(QuadTree<T> parent, AABB aabb, int depthMax)
{
Reset(parent, aabb, depthMax);
}
private void Reset(QuadTree<T> parent, AABB aabb, int depthMax)
{
_parent = parent;
_depthMax = depthMax;
_root = _parent == null ? this : parent._root;
if(_children == null)
{
_children = new QuadTree<T>[4];
}
else
{
if(_children[0] != null)
{
_children[0] = null;
_children[1] = null;
_children[2] = null;
_children[3] = null;
}
}
_aabb = aabb;
_depth = parent != null ? parent._depth + 1 : 0;
if(_objectList == null)
{
_objectList = new List<T>();
}
else
{
_objectList.Clear();
}
}
private void Split()
{
_children[0] = CreateQT(this, new AABB(_aabb.xCenter, _aabb.xMax, _aabb.yCenter, _aabb.yMax));
_children[1] = CreateQT(this, new AABB(_aabb.xMin, _aabb.xCenter, _aabb.yCenter, _aabb.yMax));
_children[2] = CreateQT(this, new AABB(_aabb.xMin, _aabb.xCenter, _aabb.yMin, _aabb.yCenter));
_children[3] = CreateQT(this, new AABB(_aabb.xCenter, _aabb.xMax, _aabb.yMin, _aabb.yCenter));
}
/// <summary>
/// 返回第几象限，0代表1象限，1代表2象限，2代表3象限，3代表4象限 -1代码
/// </summary>
/// <param name="aabb"></param>
/// <returns></returns>
private int GetQuadrantIndex(AABB aabb)
{
int result;
bool isLeft = aabb.xMax < _aabb.xCenter;
bool isRight = aabb.xMin > _aabb.xCenter;
bool isTop = aabb.yMin > _aabb.yCenter;
bool isBottom = aabb.yMax < _aabb.yCenter;
if (isTop && isRight)
{
result = 0;
}
else if (isTop && isLeft)
{
result = 1;
}
else if (isBottom && isLeft)
{
result = 2;
}
else if (isBottom && isRight)
{
result = 3;
}
else
{
result = -1;
}
return result;
}
public void Insert(T t)
{
if (_depth < _depthMax && _aabb.Contains(t.aabb))
{
int index = GetQuadrantIndex(t.aabb);
if(index == -1)
{
_objectList.Add(t);
}
else
{
if (_children[0] == null)
Split();
_children[index].Insert(t);
}
}
else
{
_objectList.Add(t);
}
}
/// <summary>
/// 只清除存储的对象，不清除子节点
/// </summary>
/// <param name="t"></param>
/// <returns></returns>
public bool Remove(T t)
{
if (t == null)
return false;
if(_objectList.Contains(t))
{
_objectList.Remove(t);
return true;
}
if (_children[0] != null)
{
if (_children[0].Remove(t)) return true;
if (_children[1].Remove(t)) return true;
if (_children[2].Remove(t)) return true;
if (_children[3].Remove(t)) return true;
}
return false;
}
/// <summary>
/// 只清除存储的对象，不清除子节点
/// </summary>
public void RemoveAll()
{
_objectList.Clear();
if (_children[0] != null)
{
_children[0].RemoveAll();
_children[1].RemoveAll();
_children[2].RemoveAll();
_children[3].RemoveAll();
}
}
/// <summary>
/// 清除对象及子节点
/// </summary>
public void Clear()
{
_objectList.Clear();
if (_children[0] != null)
{
_children[0].Clear();
DestroyQT(_children[0]);
_children[0] = null;
_children[1].Clear();
DestroyQT(_children[1]);
_children[1] = null;
_children[2].Clear();
DestroyQT(_children[2]);
_children[2] = null;
_children[3].Clear();
DestroyQT(_children[3]);
_children[3] = null;
}
}
public void Retrieve(List<T> result, AABB aabb)
{
Retrieve(result, aabb, null);
}
public void Retrieve(List<T> result, AABB aabb, System.Func<T, bool> filter)
{
int index = GetQuadrantIndex(aabb);
if(_children[0] != null)
{
if (index == -1)
{
_children[0].Retrieve(result, aabb, filter);
_children[1].Retrieve(result, aabb, filter);
_children[2].Retrieve(result, aabb, filter);
_children[3].Retrieve(result, aabb, filter);
}
else
{
_children[index].Retrieve(result, aabb, filter);
}
}
if(filter != null)
{
for(int i = 0, count = _objectList.Count; i < count; i++)
{
T t = _objectList[i];
if (filter(t))
{
result.Add(t);
}
}
}
else
{
result.AddRange(_objectList);
}
}
}
}
以上是整个四叉树的代码
下面上个用法的代码：
物体类：要实现 IAABB接口
using UnityEngine;
namespace GameBase.QT.Demo
{
public class QTElement : MonoBehaviour, IAABB
{
private float halfW;
private float halfH;
public static QTElement CreateQTElement(float x, float y, float width, float height)
{
UnityEngine.GameObject go = UnityEngine.Object.Instantiate(QTDemo.Instance.qtElementModel);
go.SetActive(true);
go.transform.localScale = new UnityEngine.Vector3(width, height, 1f);
go.transform.localPosition = new UnityEngine.Vector3(x, y, 0);
go.transform.SetParent(QTDemo.Instance.transform);
QTElement qtElement = go.GetComponent<QTElement>();
qtElement.halfW = width * 0.5f;
qtElement.halfH = height * 0.5f;
qtElement._aabb = new AABB(x - qtElement.halfW, x + qtElement.halfW, y - qtElement.halfH, y + qtElement.halfH);
return qtElement;
}
private AABB _aabb;
public AABB aabb
{
get
{
Vector2 pos = transform.localPosition;
_aabb.xMin = pos.x - halfW;
_aabb.xMax = pos.x + halfW;
_aabb.yMin = pos.y - halfH;
_aabb.yMax = pos.y + halfH;
return _aabb;
}
}
private const float SPEED_MIN = 0.05f;
private const float SPEED_MAX = 0.20f;
private Vector2 _speed;
private void Awake()
{
float speedX = UnityEngine.Random.Range(SPEED_MIN, SPEED_MAX);
float speedY = UnityEngine.Random.Range(SPEED_MIN, SPEED_MAX);
if(UnityEngine.Random.Range(0, 2) > 0)
{
speedX = -speedX;
}
if (UnityEngine.Random.Range(0, 2) > 0)
{
speedY = -speedY;
}
_speed = new Vector2(speedX, speedY);
}
private Material _mat;
public void SetColor(Color color)
{
if(_mat == null)
_mat = GetComponent<MeshRenderer>().material;
_mat.color = color;
}
public void ResetColor()
{
if (_mat == null)
_mat = GetComponent<MeshRenderer>().material;
_mat.color = Color.white;
}
private void Update()
{
Vector2 pos = transform.localPosition;
Vector2 newPos = pos + _speed;
if (newPos.x - halfW < QTDemo.X_MIN || newPos.x + halfW > QTDemo.X_MAX)
{
_speed = new Vector2(-_speed.x, _speed.y);
}
if (newPos.y - halfH < QTDemo.Y_MIN || newPos.y + halfH > QTDemo.Y_MAX)
{
_speed = new Vector2(_speed.x, -_speed.y);
}
newPos = pos + _speed;
transform.localPosition = newPos;
}
}
}
用法类：具体怎么用这个QT
using System.Collections.Generic;
using UnityEngine;
namespace GameBase.QT.Demo
{
public class QTDemo : MonoBehaviour
{
public const float X_MIN = 0;
public const float X_MAX = 120;
public const float Y_MIN = 0;
public const float Y_MAX = 80;
private QuadTree<QTElement> _qt;
private List<QTElement> _allElement;
public GameObject qtElementModel;
private static QTDemo _instance;
public static QTDemo Instance
{
get
{
return _instance;
}
}
private void Awake()
{
if (_instance != null)
throw new System.Exception("QTDemo must be singleton");
_instance = this;
_qt = new QuadTree<QTElement>(null, new AABB(X_MIN, X_MAX, Y_MIN, Y_MAX));
_allElement = new List<QTElement>();
Application.targetFrameRate = 60;
int count = 100;
while (count-- > 0)
{
AddElement();
}
}
private bool _showQTGrid = true;
private bool _showObjOwner = true;
private int _maxDepth;
private int _cycleCount;
private void OnGUI()
{
UnityEngine.GUILayout.BeginVertical();
UnityEngine.GUILayout.BeginHorizontal();
if (UnityEngine.GUILayout.Button("AddElement"))
{
AddElement();
}
if (UnityEngine.GUILayout.Button("AddElement10"))
{
int count = 10;
while (count-- > 0)
{
AddElement();
}
}
if (UnityEngine.GUILayout.Button("AddElement100"))
{
int count = 100;
while (count-- > 0)
{
AddElement();
}
}
UnityEngine.GUILayout.EndHorizontal();
UnityEngine.GUILayout.BeginHorizontal();
if (UnityEngine.GUILayout.Button("Remove"))
{
if (_allElement.Count <= 0)
return;
RemoveElement();
}
if (UnityEngine.GUILayout.Button("Remove10"))
{
int count = 10;
while (count-- > 0)
{
if (_allElement.Count <= 0)
break;
RemoveElement();
}
}
if (UnityEngine.GUILayout.Button("Remove100"))
{
int count = 100;
while (count-- > 0)
{
if (_allElement.Count <= 0)
break;
RemoveElement();
}
}
UnityEngine.GUILayout.EndHorizontal();
UnityEngine.GUILayout.BeginHorizontal();
if (UnityEngine.GUILayout.Button("Clear"))
{
_qt.Clear();
for (int i = 0, count = _allElement.Count; i < count; i++)
{
UnityEngine.Object.Destroy(_allElement[i].gameObject);
}
_allElement.Clear();
}
UnityEngine.GUILayout.EndHorizontal();
_showQTGrid = GUILayout.Toggle(_showQTGrid, "显示网格:");
_showObjOwner = GUILayout.Toggle(_showObjOwner, "显示对象所在网格:");
GUILayout.BeginHorizontal();
_maxDepth = (int)GUILayout.HorizontalSlider(_maxDepth, 0f, 10.1f);
if (UnityEngine.GUILayout.Button("confirm"))
{
_qt.DepthMax = _maxDepth;
}
GUILayout.EndHorizontal();
GUILayout.Space(50);
GUILayout.Label("当前对像数：" + _allElement.Count.ToString());
GUILayout.Label("四叉树深度：" + _qt.DepthMax.ToString());
GUILayout.Label(" 遍历次数：" + _cycleCount.ToString());
UnityEngine.GUILayout.EndVertical();
}
List<QTElement> _possibleElementList = new List<QTElement>();
HashSet<QTElement> _intersectSet = new HashSet<QTElement>();
private int calCycleCountFrame = 0;
private bool calCycleCount = true;
private void LateUpdate()
{
if (calCycleCountFrame-- < 0)
{
calCycleCountFrame = 30;
calCycleCount = true;
}
else
{
calCycleCount = false;
}
_qt.Clear();
for (int i = 0, count = _allElement.Count; i < count; i++)
{
_qt.Insert(_allElement[i]);
}
_intersectSet.Clear();
if (calCycleCount) _cycleCount = 0;
for (int i = 0, count = _allElement.Count; i < count; i++)
{
QTElement qtEleA = _allElement[i];
qtEleA.ResetColor();
QTElement qtEleB;
_possibleElementList.Clear();
//_qt.Retrieve(_possibleElementList, qtEleA.aabb, (qtEle) => { return qtEle != qtEleA; });
_qt.Retrieve(_possibleElementList, qtEleA.aabb);
for (int j = 0, countJ = _possibleElementList.Count; j < countJ; ++j)
{
qtEleB = _possibleElementList[j];
if (calCycleCount) _cycleCount++;
if (qtEleA == qtEleB)
continue;
if (qtEleA.aabb.Intersect(qtEleB.aabb))
{
_intersectSet.Add(qtEleB);
_intersectSet.Add(qtEleA);
}
}
}
foreach (var e in _intersectSet)
{
e.SetColor(Color.red);
}
}
private void AddElement()
{
QTElement element = QTElement.CreateQTElement(UnityEngine.Random.Range(X_MIN + 5, X_MAX - 5), UnityEngine.Random.Range(Y_MIN + 5, Y_MAX - 5), UnityEngine.Random.Range(1, 3), UnityEngine.Random.Range(1, 3));
_allElement.Add(element);
_qt.Insert(element);
}
private void RemoveElement()
{
if (_allElement.Count <= 0)
return;
QTElement qte = _allElement[_allElement.Count - 1];
_qt.Remove(qte);
UnityEngine.Object.Destroy(qte.gameObject);
_allElement.RemoveAt(_allElement.Count - 1);
}
private void OnDrawGizmos()
{
DrawQuadTree(_qt);
}
private void DrawQuadTree(QuadTree<QTElement> quadTree)
{
if (quadTree == null)
return;
DrawAABB(quadTree.aabb);
Gizmos.color = Color.black;
for (int i = 0, count = quadTree.Children.Length; i < count; i++)
{
DrawQuadTree(quadTree.Children[i]);
if (!_showObjOwner)
continue;
if (quadTree.ObjectList.Count > 0)
{
for (int j = 0, countJ = quadTree.ObjectList.Count; j < countJ; j++)
{
var qtEle = quadTree.ObjectList[j];
Vector3 center = new Vector3(qtEle.aabb.xMin + (qtEle.aabb.xMax - qtEle.aabb.xMin) * 0.5f, qtEle.aabb.yMin + (qtEle.aabb.yMax - qtEle.aabb.yMin) * 0.5f);
Gizmos.DrawLine(center, new Vector3(quadTree.aabb.xMin, quadTree.aabb.yMin));
Gizmos.DrawLine(center, new Vector3(quadTree.aabb.xMax, quadTree.aabb.yMin));
Gizmos.DrawLine(center, new Vector3(quadTree.aabb.xMin, quadTree.aabb.yMax));
Gizmos.DrawLine(center, new Vector3(quadTree.aabb.xMax, quadTree.aabb.yMax));
}
}
}
}
private void DrawAABB(AABB aabb)
{
if (!_showQTGrid)
return;
Gizmos.color = Color.cyan;
Gizmos.DrawLine(new Vector3(aabb.xMin, aabb.yMin), new Vector3(aabb.xMax, aabb.yMin));
Gizmos.DrawLine(new Vector3(aabb.xMax, aabb.yMin), new Vector3(aabb.xMax, aabb.yMax));
Gizmos.DrawLine(new Vector3(aabb.xMax, aabb.yMax), new Vector3(aabb.xMin, aabb.yMax));
Gizmos.DrawLine(new Vector3(aabb.xMin, aabb.yMax), new Vector3(aabb.xMin, aabb.yMin));
}
}
}