前言
在游戏制作过程中会经常遇到碰撞检测，假设在二维平面上有n个物体，那么检测每个物体的碰撞都要检测n-1次，如果要检测所有物体的碰撞，那么需要计算n*(n-1)/2次，时间复杂度为n的平方，四叉树算法可以将物体分到不同的区域，从而减少计算次数。关于四叉树 的概念可以参考文章四叉树与八叉树
四叉的实现
下面是用C#代码实现的四叉树算法,需要注意的是构造函数的pBounds参数，不能直接使用RectTransform.rect，这里使用的rect的参数x和y需要特殊处理，具体可以看末尾函数public static Rect GetRect(RectTransform rectTransform)。
using System.Collections;using System.Collections.Generic;using UnityEngine;public class QuadTree{//节点内允许的最大对象private int MAX_OBJECTS = 1;//最大层级private int MAX_LEVELS = 3;//当前层级private int level;//当前层级内的对象public List<RectTransform> rectTrans;//rect范围private Rect bounds;//子节点private List<QuadTree> childs;public QuadTree(Rect pBounds, int pLevel = 0, int maxObjs = 1, int maxLevel = 3){level = pLevel;rectTrans = new List<RectTransform>();bounds = pBounds;childs = new List<QuadTree>();MAX_OBJECTS = maxObjs;MAX_LEVELS = maxLevel;}/// <summary>/// 清理四叉树/// </summary>public void Clear(){rectTrans.Clear();for (int i = 0; i < childs.Count; i++){childs[i].Clear();}}/// <summary>/// 分割四叉树/// </summary>public void Split(){float halfWidth = bounds.width / 2;float halfHeight = bounds.height / 2;float x = bounds.x;float y = bounds.y;childs.Add(new QuadTree(new Rect(x, y + halfHeight, halfWidth, halfHeight), level + 1, MAX_OBJECTS, MAX_LEVELS));childs.Add(new QuadTree(new Rect(x + halfWidth, y + halfHeight, halfWidth, halfHeight), level + 1, MAX_OBJECTS, MAX_LEVELS));childs.Add(new QuadTree(new Rect(x, y, halfWidth, halfHeight), level + 1, MAX_OBJECTS, MAX_LEVELS));childs.Add(new QuadTree(new Rect(x + halfWidth, y, halfWidth, halfHeight), level + 1, MAX_OBJECTS, MAX_LEVELS));//对象下沉for (int i = 0; i < rectTrans.Count; i++){Insert(rectTrans[i]);}rectTrans.Clear();}/// <summary>/// 寻找对象所在节点列表/// </summary>/// <param name="rect">对象的rect</param>/// <returns></returns>public List<QuadTree> GetIndexes(Rect rect){List<QuadTree> ret = new List<QuadTree>();FindQuad(rect, ret);return ret;}/// <summary>/// 插入对象/// </summary>/// <param name="go"></param>public void Insert(RectTransform go){Rect rect = GetRect(go);List<QuadTree> tempList = GetIndexes(rect);for (int i = 0; i < tempList.Count; i++){QuadTree quad = tempList[i];quad.rectTrans.Add(go);//判断对象是否可以分割if (quad.rectTrans.Count > MAX_OBJECTS && quad.level < MAX_LEVELS){quad.Split();}}}/// <summary>/// 判断两个矩形是否重合/// </summary>/// <param name="rect1"></param>/// <param name="rect2"></param>/// <returns></returns>public static bool RectCollision(Rect rect1, Rect rect2){float minx = Mathf.Max(rect1.x, rect2.x);float miny = Mathf.Max(rect1.y, rect2.y);float maxx = Mathf.Min(rect1.x + rect1.width, rect2.x + rect2.width);float maxy = Mathf.Min(rect1.y + rect1.height, rect2.y + rect2.height);if (minx > maxx || miny > maxy) return false;return true;}/// <summary>/// 寻找Rect所在的节点列表/// </summary>/// <param name="point"></param>/// <returns></returns>public void FindQuad(Rect rect,List<QuadTree> quadTrees){if (bounds.Overlaps(rect)){if (childs.Count == 0){quadTrees.Add(this);}else{for (int i = 0; i < childs.Count; i++){childs[i].FindQuad(rect, quadTrees);}}}}/// <summary>/// 获取与对象go相交的对象/// </summary>/// <param name="go"></param>/// <returns></returns>public List<RectTransform> GetCollisions(RectTransform go){HashSet<RectTransform> set = new HashSet<RectTransform>();Rect rect = GetRect(go);var tempList = GetIndexes(rect);for (int i = 0; i < tempList.Count; i++){for (int j = 0; j < tempList[i].rectTrans.Count; j++){if (tempList[i].rectTrans[j] != go && !set.Contains(tempList[i].rectTrans[j])){Rect rect1 = GetRect(tempList[i].rectTrans[j]);if (rect1.Overlaps(rect)){set.Add(tempList[i].rectTrans[j]);}}}}return new List<RectTransform>(set);}/// <summary>/// 获取所有相交的对象/// </summary>/// <returns></returns>public Dictionary<RectTransform, HashSet<RectTransform>> GetAllCollisions(){Dictionary<RectTransform, HashSet<RectTransform>> ret = new Dictionary<RectTransform, HashSet<RectTransform>>();List<QuadTree> leafs = new List<QuadTree>();GetAllLeaf(leafs);for (int i = 0; i < leafs.Count; i++){for (int j = 0; j < leafs[i].rectTrans.Count; j++){for (int k = j + 1; k < leafs[i].rectTrans.Count; k++){if (ret.ContainsKey(leafs[i].rectTrans[j]) && ret[leafs[i].rectTrans[j]].Contains(leafs[i].rectTrans[k])) continue;if (ret.ContainsKey(leafs[i].rectTrans[k]) && ret[leafs[i].rectTrans[k]].Contains(leafs[i].rectTrans[j])) continue;Rect rect1 = GetRect(leafs[i].rectTrans[j]);Rect rect2 = GetRect(leafs[i].rectTrans[k]);if (rect1.Overlaps(rect2)){if (!ret.ContainsKey(leafs[i].rectTrans[j])){ret.Add(leafs[i].rectTrans[j], new HashSet<RectTransform>());}ret[leafs[i].rectTrans[j]].Add(leafs[i].rectTrans[k]);}}}}return ret;}/// <summary>/// 获取所有叶子节点/// </summary>/// <param name="ret"></param>public void GetAllLeaf(List<QuadTree> ret){if (childs.Count == 0){if (rectTrans.Count > 1)ret.Add(this);}else{for (int i = 0; i < childs.Count; i++){childs[i].GetAllLeaf(ret);}}}/// <summary>/// 获取对象的rect/// </summary>/// <param name="rectTransform"></param>/// <returns></returns>public static Rect GetRect(RectTransform rectTransform){Rect rect = rectTransform.rect;return new Rect(rectTransform.position.x + rect.x, rectTransform.position.y + rect.y, rect.width, rect.height);}}
测试
写好四叉树算法后，需要在实际场景进行测试
测试环境：
Unity .3 Win10 CPU:i5-10400F
创建一个需要碰撞检测的预制体
这里创建一个Image,附加一个让其自由移动的脚本。
public class RandomMove : MonoBehaviour{float stopTime;float moveTime;float vel_x, vel_y, vel_z;//速度/// <summary>/// 最大、最小飞行界限/// </summary>public float maxPos_x = 500;public float maxPos_y = 300;public float minPos_x = -500;public float minPos_y = -300;int curr_frame;int total_frame;float timeCounter1;float timeCounter2;// int max_Flys = 128;// Use this for initializationvoid Start(){Change();}// Update is called once per framevoid Update(){timeCounter1 += Time.deltaTime;if (timeCounter1 < moveTime){transform.Translate(vel_x, vel_y, 0, Space.Self);}else{timeCounter2 += Time.deltaTime;if (timeCounter2 > stopTime){Change();timeCounter1 = 0;timeCounter2 = 0;}}Check();}void Change(){stopTime = Random.Range(1, 5);moveTime = Random.Range(1, 20);vel_x = Random.Range(-10, 10) * 0.01f;vel_y = Random.Range(-10, 10) * 0.01f;}void Check(){//如果到达预设的界限位置值，调换速度方向并让它当前的坐标位置等于这个临界边的位置值if (transform.localPosition.x > maxPos_x){vel_x = -vel_x;transform.localPosition = new Vector3(maxPos_x, transform.localPosition.y, 0);}if (transform.localPosition.x < minPos_x){vel_x = -vel_x;transform.localPosition = new Vector3(minPos_x, transform.localPosition.y, 0);}if (transform.localPosition.y > maxPos_y){vel_y = -vel_y;transform.localPosition = new Vector3(transform.localPosition.x, maxPos_y, 0);}if (transform.localPosition.y < minPos_y){vel_y = -vel_y;transform.localPosition = new Vector3(transform.localPosition.x, minPos_y, 0);}}}
在场景中加载200个碰撞体，并检测碰撞
为了实时表现碰撞，在两个碰撞的对象之间画一条红线
public class TestQuad : MonoBehaviour{public GameObject Image;QuadTree quadTree;List<RectTransform> rectTransforms;List<LineRenderer> lineRenderers;public int cNums = 200;private void Start(){rectTransforms = new List<RectTransform>();lineRenderers = new List<LineRenderer>();Rect sc = Screen.safeArea;quadTree = new QuadTree(sc,0,2,5);for(int i = 0; i < cNums; i++){GameObject go = Instantiate(Image);RectTransform rectT = go.GetComponent<RectTransform>();//随机生成位置float x = Random.Range(0,sc.width);float y = Random.Range(0,sc.height);rectT.position = new Vector3(x, y, 0);go.transform.SetParent(transform);var move = go.GetComponent<RandomMove>();move.maxPos_x = sc.width / 2;move.maxPos_y = sc.height / 2;move.minPos_x = -move.maxPos_x;move.minPos_y = -move.maxPos_y;rectTransforms.Add(rectT);}}private void Update(){//清理树quadTree.Clear();//插入节点for (int i = 0; i < rectTransforms.Count; i++){quadTree.Insert(rectTransforms[i]);}//获取所有交集var temps = quadTree.GetAllCollisions();List<Vector3> point = new List<Vector3>();int linet = 0;//画线foreach (var kv in temps){if (linet == lineRenderers.Count){GameObject go = new GameObject("line_"+linet);lineRenderers.Add(go.AddComponent<LineRenderer>());}LineRenderer lineRenderer = lineRenderers[linet++];lineRenderer.gameObject.SetActive(true);lineRenderer.positionCount = 0;foreach (var v in kv.Value){//显示线条(z为-1,才能显示出来)lineRenderer.SetPosition(lineRenderer.positionCount++, kv.Key.position + new Vector3(0,0,-1));lineRenderer.SetPosition(lineRenderer.positionCount++, v.position + new Vector3(0,0,-1));}}while (linet < lineRenderers.Count){lineRenderers[linet++].gameObject.SetActive(false);}}}
运行结果如下
与暴力法的性能对比
现将Update内的代码，修改如下
int linet = 0;for (int i = 0; i < rectTransforms.Count; i++){if (linet == lineRenderers.Count){GameObject go = new GameObject("line_" + linet);lineRenderers.Add(go.AddComponent<LineRenderer>());}LineRenderer lineRenderer = lineRenderers[linet++];lineRenderer.gameObject.SetActive(true);lineRenderer.positionCount = 0;for (int j = i + 1; j < rectTransforms.Count; j++){Rect rect1 = QuadTree.GetRect(rectTransforms[i]);Rect rect2 = QuadTree.GetRect(rectTransforms[j]);if (rect1.Overlaps(rect2)){lineRenderer.SetPosition(lineRenderer.positionCount++, rectTransforms[i].position + new Vector3(0, 0, -1));lineRenderer.SetPosition(lineRenderer.positionCount++, rectTransforms[j].position + new Vector3(0, 0, -1));}}}while (linet < lineRenderers.Count){lineRenderers[linet++].gameObject.SetActive(false);}
运行结果如下
