下文参考：https://www.cnblogs.com/KillerAery/p/10878367.html
游戏编程知识课程 - 四分树(quadtree)_哔哩哔哩_bilibili
利用空间数据结构可以加速计算，是重要的优化思想。空间数据结构常用于场景管理，渲染，物理，游戏逻辑
四叉树 / 八叉树 （Quadtree / Octree ）
四叉树索引的基本思想是将地理空间递归划分成不同层次的树结构
可以将已知范围的空间等分成四个相等的子空间，直到树的层次达到一定深度或者满足某种要求
什么是四叉树：
- 一个四叉树结构是一个存储单元（点，线，或者三角形）
- 每个节点只能有四个子节点或者没有子节点
- 每个节点表示了一块区域，他的四个孩子节点表示这个区域的四分
- 四叉树是二维的概念
- 每个节点在它们的区域中存储一些objects，有一个最大存储值（对于整颗树来说都是一样的，每个块存储的数量都是根据这个值来调整，如果一个节点存储的值多于最大存储值，就把这个节点四分）
- 有一个最大深度值（就是树的深度）
怎么把一个物体添加到 Quadtree 里面
当一个quadtree 第一次初始化时，它只有根节点（表现的是整个空间）
从根节点开始，递归执行下面的方法
如果这个节点是叶子节点：
- 如果递归已经到达最大的深度或者没有达到最大容量，就把这个物体添加到当前节点
- 否则就把这个区域四分，创建四个子节点，用每个子节点对应一块。然后把这个程序再跑一遍
如果节点不是叶子节点
- 如果这个物体只是覆盖现在区域的一个四分之一，在这个节点的四分之一子节点上运行这个程序。否则把这个物体加到现在的节点（因为一个点不能同时被不同的节点存储）
怎么去找我们想要的物体
如果给了一个盒子，我们需要去找所有与这个盒子相交的物体
从根节点开始然后递归调用以下方法：
- 遍历当前节点里面的所有物体，如果与盒子相交，就把这个物体添加到 intersected object list
- 如果当前节点不是叶子节点：遍历每个孩子节点，如果盒子和这个区域相交，再孩子节点上执行这个方法
如何 remove 物体从 Quadtree
从根节点开始递归调用下面的方法：
如果节点是叶子节点：
- 如果这个节点有这个物体，就把这个物体移除
如果节点不是叶子节点：
-- 如果这个物体只覆盖当前节点区域的一个四分区域
- 使用这个四分区域对应的子节点运行这个程序，然后优化一下
-- 否则如果这个节点有这个物体就从当前节点移除这个物体
如何去优化节点
如果当前节点的孩子节点不是叶子节点，就 return
计算当前节点以及它的四个孩子节点的所有物体数量，如果小于最大容量，就摧毁掉孩子节点然后将物体都添加到当前节点上
代码来自 chatgpt
using System;
using System.Collections.Generic;
// 表示一个矩形区域
public class Rectangle
{
public float xMin, xMax, yMin, yMax;
public Rectangle(float x, float y, float width, float height)
{
xMin = x;
xMax = x + width;
yMin = y;
yMax = y + height;
}
// 判断点是否在矩形内部
public bool Contains(float x, float y)
{
return x >= xMin && x <= xMax && y >= yMin && y <= yMax;
}
}
// 表示四叉树节点
public class QuadTreeNode<T>
{
public Rectangle boundary; // 节点代表的矩形区域
public List<T> objects; // 存储在当前节点中的对象
public QuadTreeNode<T>[] children; // 子节点
public QuadTreeNode(Rectangle rect)
{
boundary = rect;
objects = new List<T>();
children = new QuadTreeNode<T>[4];
}
}
// 四叉树类
public class Quadtree<T>
{
private QuadTreeNode<T> root; // 根节点
private int maxObjectsPerNode = 10; // 每个节点最多存储的对象数量
private int maxLevels = 5; // 最大递归深度
public Quadtree(Rectangle bounds)
{
root = new QuadTreeNode<T>(bounds);
}
// 插入对象
public void Insert(T obj, float x, float y)
{
Insert(obj, root, x, y, 0);
}
// 递归插入对象
private void Insert(T obj, QuadTreeNode<T> node, float x, float y, int level)
{
if (node.children[0] != null) // 如果有子节点
{
int index = GetIndex(node, x, y); // 获取对象应该插入的子节点索引
if (index != -1) // 如果对象属于子节点
{
Insert(obj, node.children[index], x, y, level + 1);
return;
}
}
node.objects.Add(obj); // 将对象添加到当前节点
if (node.objects.Count > maxObjectsPerNode && level < maxLevels) // 如果当前节点对象数量超过阈值且还可以递归分割
{
if (node.children[0] == null) // 如果没有子节点，创建子节点
{
SplitNode(node);
}
// 将当前节点的对象重新分配到子节点中
int i = 0;
while (i < node.objects.Count)
{
T item = node.objects[i];
int index = GetIndex(node, x, y);
if (index != -1)
{
node.objects.RemoveAt(i);
node.children[index].objects.Add(item);
}
else
{
i++;
}
}
}
}
// 分割节点
private void SplitNode(QuadTreeNode<T> node)
{
float subWidth = node.boundary.xMax - node.boundary.xMin;
float subHeight = node.boundary.yMax - node.boundary.yMin;
float xMid = node.boundary.xMin + (subWidth / 2);
float yMid = node.boundary.yMin + (subHeight / 2);
// 创建四个子节点
node.children[0] = new QuadTreeNode<T>(new Rectangle(xMid, yMid, subWidth, subHeight));
node.children[1] = new QuadTreeNode<T>(new Rectangle(node.boundary.xMin, yMid, subWidth, subHeight));
node.children[2] = new QuadTreeNode<T>(new Rectangle(node.boundary.xMin, node.boundary.yMin, subWidth, subHeight));
node.children[3] = new QuadTreeNode<T>(new Rectangle(xMid, node.boundary.yMin, subWidth, subHeight));
}
// 获取对象应该插入的子节点索引
private int GetIndex(QuadTreeNode<T> node, float x, float y)
{
int index = -1;
float xMid = node.boundary.xMin + (node.boundary.xMax - node.boundary.xMin) / 2;
float yMid = node.boundary.yMin + (node.boundary.yMax - node.boundary.yMin) / 2;
bool topQuadrant = (y >= yMid);
bool bottomQuadrant = (y < yMid);
bool leftQuadrant = (x < xMid);
bool rightQuadrant = (x >= xMid);
if (leftQuadrant)
{
if (topQuadrant)
{
index = 0;
}
else if (bottomQuadrant)
{
index = 2;
}
}
else if (rightQuadrant)
{
if (topQuadrant)
{
index = 1;
}
else if (bottomQuadrant)
{
index = 3;
}
}
return index;
}
// 查询区域内的对象
public List<T> QueryRange(Rectangle range)
{
List<T> result = new List<T>();
QueryRange(root, range, result);
return result;
}
// 递归查询区域内的对象
private void QueryRange(QuadTreeNode<T> node, Rectangle range, List<T> result)
{
if (!node.boundary.Contains(range.xMin, range.yMin) && !node.boundary.Contains(range.xMax, range.yMax))
{
return;
}
foreach (T obj in node.objects)
{
if (range.Contains(range.xMin, range.yMin))
{
result.Add(obj);
}
}
if (node.children[0] != null)
{
foreach (QuadTreeNode<T> child in node.children)
{
QueryRange(child, range, result);
}
}
}
}
// 示例使用
class Program
{
static void Main(string[] args)
{
Rectangle bounds = new Rectangle(0, 0, 100, 100);
Quadtree<int> quadtree = new Quadtree<int>(bounds);
// 插入对象
quadtree.Insert(1, 10, 10);
quadtree.Insert(2, 20, 20);
quadtree.Insert(3, 30, 30);
quadtree.Insert(4, 40, 40);
quadtree.Insert(5, 50, 50);
quadtree.Insert(6, 60, 60);
quadtree.Insert(7, 70, 70);
quadtree.Insert(8, 80, 80);
quadtree.Insert(9, 90, 90);
quadtree.Insert(10, 100, 100);
// 查询区域内的对象
Rectangle queryRange = new Rectangle(25, 25, 30, 30);
List<int> result = quadtree.QueryRange(queryRange);
foreach (int obj in result)
{
Console.WriteLine("对象：" + obj);
}
}
}
遗憾，执行出来的结果是错误的
将就看个大概吧
八叉树
