1、node interface
using UnityEngine;
namespace FrameDT
{
public interface INode
{
Bounds m_bound { get; set; }
Node Inside(Bounds bound);
void InsidePush(Bounds bound);
void AddObject(GameObject obj);
void RemoveObject(GameObject obj);
void DrawBound();
}
}
2、node
using System.Collections.Generic;
using UnityEngine;
namespace FrameDT
{
public class Node : INode
{
public Bounds m_bound { get; set; }
private int m_depth;
private Node m_belong;
private Node[] m_childNode;
private List<GameObject> m_objects;
public Node(Bounds bound, int depth, Node belong)
{
m_belong = belong;
m_bound = bound;
m_depth = depth;
Insert();
}
public void Insert()
{
if (m_depth < TreeNode.MaxDepth)
{
if (m_childNode == null)
{
CreateChild();
}
else
{
for (int i = 0; i < m_childNode.Length; ++i)
{
Node item = m_childNode[i];
item.Insert();
}
}
}
else
{
m_objects = new List<GameObject>(16);
}
}
public Node Inside(Bounds bound)
{
Node node = null;
if (m_childNode != null)
{
for (int i = 0; i < m_childNode.Length; ++i)
{
Node item = m_childNode[i];
if (item.m_bound.Intersects(bound))
{
Node child = item.Inside(bound);
if (child != null)
{
node = item.Inside(bound);
break;
}
else
{
node = item;
break;
}
}
}
}
return node;
}
public void InsidePush(Bounds bound)
{
if (m_childNode != null)
{
for (int i = 0; i < m_childNode.Length; ++i)
{
if (m_childNode[i].m_bound.Intersects(bound))
{
m_childNode[i].InsidePush(bound);
}
}
}
if(m_depth == TreeNode.MaxDepth)
{
TreeObjManager.GetInstance().curNodes.Add(this);
}
}
public void AddObject(GameObject obj)
{
if(m_objects != null)
{
m_objects.Add(obj);
}
else
{
Debug.LogError("Container Error!");
}
}
public void RemoveObject(GameObject obj)
{
if (m_objects != null)
{
if(m_objects.Contains(obj))
{
m_objects.Remove(obj);
}
}
else
{
Debug.LogError("Container Error!");
}
}
private void CreateChild()
{
m_childNode = new Node[TreeNode.NodeCount];
int index = 0;
if (m_childNode.Length == 4)
{
for (int x = -1; x <= 1; x += 2)
{
for (int z = -1; z <= 1; z += 2)
{
Vector3 centerOffset = new Vector3(m_bound.size.x / 4 * x, 0, m_bound.size.z / 4 * z);
Vector3 cSize = new Vector3(m_bound.size.x / 2, m_bound.size.y, m_bound.size.z / 2);
Bounds cBound = new Bounds(m_bound.center + centerOffset, cSize);
m_childNode[index++] = new Node(cBound, m_depth + 1, this);
}
}
}
else
{
for (int x = -1; x <= 1; x += 2)
{
for (int y = -1; y <= 1; y += 2)
{
for (int z = -1; z <= 1; z += 2)
{
Vector3 centerOffset = new Vector3(m_bound.size.x / 4 * x, m_bound.size.y / 4 * y, m_bound.size.z / 4 * z);
Vector3 cSize = new Vector3(m_bound.size.x / 2, m_bound.size.y / 2, m_bound.size.z / 2);
Bounds cBound = new Bounds(m_bound.center + centerOffset, cSize);
m_childNode[index++] = new Node(cBound, m_depth + 1, this);
}
}
}
}
}
public Color m_color = Color.green;
public void DrawBound()
{
Gizmos.color = m_color;
Gizmos.DrawWireCube(m_bound.center, m_bound.size);
if (m_childNode != null)
{
for (int i = 0; i < m_childNode.Length; ++i)
{
m_childNode[i].DrawBound();
}
}
}
}
}
3、tree node
using System.Collections.Generic;
using UnityEngine;
namespace FrameDT
{
public class TreeNode : INode
{
public static int MaxDepth;
public static int NodeCount;
public Bounds m_bound { get; set; }
private Node m_root;
public TreeNode(Bounds bound, int maxDepth, bool QuadTree)
{
MaxDepth = maxDepth;
NodeCount = QuadTree ? 4 : 8;
m_bound = bound;
m_root = new Node(bound, 0, null);
}
/// <summary>
/// 查找一个node
/// </summary>
public Node Inside(Bounds bound)
{
return m_root.Inside(bound);
}
/// <summary>
/// 查找范围内的node
/// </summary>
public void InsidePush(Bounds bound)
{
m_root.InsidePush(bound);
}
/// <summary>
/// 碰撞体积添加
/// </summary>
public void AddObject(GameObject obj)
{
Bounds bound = obj.GetComponent<Collider>().bounds;
Node node = m_root.Inside(bound);
node?.AddObject(obj);
}
/// <summary>
/// 碰撞体积移除
/// </summary>
public void RemoveObject(GameObject obj)
{
Bounds bound = obj.GetComponent<Collider>().bounds;
Node node = m_root.Inside(bound);
node?.RemoveObject(obj);
}
public void DrawBound()
{
m_root.DrawBound();
}
}
}
4、测试类
using UnityEngine;
using FrameDT;
using System.Collections.Generic;
/// <summary>
/// 四叉树管理类
/// </summary>
public class TreeObjManager : SingleMonoBase<TreeObjManager>
{
public Bounds bounds;//当前树的大小
public int depth;//树的深度
public bool QuadTree;//四叉树or八叉树
private TreeNode tree;
//test data
public Node curNode;
public GameObject curCube;
public List<Node> curNodes = new List<Node>();
protected override void Awake()
{
tree = new TreeNode(bounds, depth, QuadTree);
}
protected override void Update()
{
if (Input.GetKeyDown(KeyCode.F10))
{
if (curCube != null) return;
Vector3 pos = new Vector3(Random.Range(-(int)bounds.size.x / 2, (int)bounds.size.x / 2),
Random.Range(-(int)bounds.size.y / 2, (int)bounds.size.y / 2),
Random.Range(-(int)bounds.size.z / 2, (int)bounds.size.z / 2));
//查找
curNode = tree.Inside(new Bounds(pos, Vector3.zero));
//添加
curCube = GameObject.CreatePrimitive(PrimitiveType.Cube);
curCube.transform.position = pos;
curCube.transform.localScale = Vector3.one * 1;
curNode.AddObject(curCube);
curNode.m_color = Color.red;
}
else if(Input.GetKeyDown(KeyCode.F11))
{
//删除
curNode.RemoveObject(curCube);
curNode.m_color = Color.green;
Destroy(curCube);
curCube = null;
}
else if (Input.GetKeyDown(KeyCode.F12))
{
Vector3 pos = new Vector3(Random.Range(-(int)bounds.size.x / 2, (int)bounds.size.x / 2),
Random.Range(-(int)bounds.size.y / 2, (int)bounds.size.y / 2),
Random.Range(-(int)bounds.size.z / 2, (int)bounds.size.z / 2));
//查找范围
var obj = GameObject.CreatePrimitive(PrimitiveType.Cube);
obj.transform.position = pos;
obj.transform.localScale = Vector3.one * 30;
curNodes.Clear();
tree.InsidePush(new Bounds(pos, Vector3.one * 30));
Debug.Log("child node num = " + curNodes.Count);
for (int index = 0; index < curNodes.Count; index++)
{
if (curNodes[index] != null) curNodes[index].m_color = Color.blue;
}
}
}
private void OnDrawGizmos()
{
if (tree != null)
{
tree.DrawBound();
}
else
{
Gizmos.color = Color.green;
Gizmos.DrawWireCube(bounds.center, bounds.size);
}
}
}