c#四叉树效率
本文关键字：效率 四叉树 | 更新日期: 2023-09-27 18:13:33
我对unity比较陌生，所以我决定开始用c#编写一个小的平台物理引擎，其中主要的属性结构是四叉树。不幸的是，我的生成代码非常慢，花了4秒多的时间才为10K个对象(普通的c#对象，而不是GameObjects)构建一个四叉树。
代码与普通的四叉树略有不同;与将重叠区域的对象存储在根节点中不同，引用存储在包含该对象的每个子节点中。由于我所有的对象都是相对相同的大小，并且节点的最小大小是这个大小的两倍，因此以这种方式构建树可以将碰撞算法的效率从~O(N^(3/2))提高到~O(N)。
我的简单四叉树类如下所示:
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System;
public class QuadTree {
public QuadTree parent = null;
public QuadTree[] childern = null;
public List<PPObject> objectList = null;
public BBox bbox = null;
public bool leaf = true;
public float minSize = 1.0f;
public float maxObjs = 4;
public float width;
public float height;
public Vector3 position;
public int level;
public QuadTree(QuadTree parent, BBox bbox, int level)
{
this.parent = parent;
this.bbox = bbox;
this.level = level;
width = bbox.xmax - bbox.xmin;
height = bbox.ymax - bbox.ymin;
position = new Vector3(bbox.xmin + width * 0.5f, bbox.ymin + height * 0.5f, 0.0f);
objectList = new List<PPObject>();
}
public void Subdivide()
{
Profiler.BeginSample("Subdivide");
float x1 = bbox.xmin;
float x2 = bbox.xmin + 0.5f * width;
float x3 = bbox.xmax;
float y1 = bbox.ymin;
float y2 = bbox.ymin + height * 0.5f;
float y3 = bbox.ymax;
Profiler.BeginSample("allocate new quadtrees");
childern = new QuadTree[4];
QuadTree tl = new QuadTree(this, new BBox(x1, x2, y2, y3), level + 1);
QuadTree tr = new QuadTree(this, new BBox(x2, x3, y2, y3), level + 1);
QuadTree br = new QuadTree(this, new BBox(x2, x3, y1, y2), level + 1);
QuadTree bl = new QuadTree(this, new BBox(x1, x2, y1, y2), level + 1);
childern[0] = tl;
childern[1] = tr;
childern[2] = br;
childern[3] = bl;
Profiler.EndSample();
PushToChildern();
leaf = false;
Profiler.EndSample();
}
public void PushToChildern()
{
Profiler.BeginSample("pushToChildern");
foreach (QuadTree child in childern)
{
foreach (PPObject obj in objectList)
{
child.AddObject(obj);
}
}
objectList = null;
Profiler.EndSample();
}
public void AddObject(PPObject obj)
{
Profiler.BeginSample("addObject");
if (childern == null)
{
if (obj != null)
{
float x1 = obj.position.x;
float w1 = obj.bbox.xmax - obj.bbox.xmin;
float y1 = obj.position.y;
float h1 = obj.bbox.ymax - obj.bbox.ymin;
float dx = Math.Abs(x1-position.x);
float dy = Math.Abs(y1-position.y);
if (dx < ((width+w1) * 0.5f) && dy < (height + h1) *0.5f )
{
objectList.Add(obj);
}
}
if (objectList.Count > maxObjs && width > minSize && height > minSize)
{
Subdivide();
}
} else {
foreach (QuadTree child in childern)
{
child.AddObject(obj);
}
}
Profiler.EndSample();
}
}
这里BBox和PPObject只是包含位置，边界，速度等的简单类。前面提到的4秒执行时间是在没有详细的对象稀疏性分析器的情况下执行的，对象稀疏性在0.99到0.4之间。如果有人能帮我理解为什么这么慢，那就太好了。大概有100K个函数调用，20K个实例化，总共3.4 Mb。也许我只是太习惯用Fortran编写了，但这对于在~10 GFlop的核心上运行似乎很荒谬。
谢谢!
基本上，我首先实例化了树的深度，而不是宽度。这导致我制作了许多额外的(基本上是未起诉的)相关列表副本。下面的代码在我的机器上执行大约50ms，减少了100倍。经过一些调整，它应该适合在游戏引擎中使用。
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System;
public class QuadTree
{
public QuadTree parent = null;
public QuadTree[] childern = null;
public List<PPObject> objectList = null;
public BBox bbox = null;
public bool leaf = true;
public float minSize = 1.0f;
public float maxObjs = 4;
public float width;
public float height;
public Vector3 position;
public int level;
public QuadTree(QuadTree parent, BBox bbox, List<PPObject> objectList, int level)
{
this.parent = parent;
this.bbox = bbox;
this.level = level;
width = bbox.xmax - bbox.xmin;
height = bbox.ymax - bbox.ymin;
position = new Vector3(bbox.xmin + width * 0.5f, bbox.ymin + height * 0.5f, 0.0f);
this.objectList = objectList;
BuildTree();
}
public QuadTree(QuadTree parent, BBox bbox, int level)
{
this.parent = parent;
this.bbox = bbox;
this.level = level;
width = bbox.xmax - bbox.xmin;
height = bbox.ymax - bbox.ymin;
position = new Vector3(bbox.xmin + width * 0.5f, bbox.ymin + height * 0.5f, 0.0f);
objectList = new List<PPObject>();
}
public void Subdivide()
{
if (objectList.Count > maxObjs && childern == null && width > minSize && height > minSize)
{
float x1 = bbox.xmin;
float x2 = bbox.xmin + 0.5f * width;
float x3 = bbox.xmax;
float y1 = bbox.ymin;
float y2 = bbox.ymin + height * 0.5f;
float y3 = bbox.ymax;
childern = new QuadTree[4];
BBox tlBBox = new BBox(x1, x2, y2, y3);
BBox trBBox = new BBox(x2, x3, y2, y3);
BBox brBBox = new BBox(x2, x3, y1, y2);
BBox blBBox = new BBox(x1, x2, y1, y2);
QuadTree tl = new QuadTree(this, tlBBox, level + 1);
QuadTree tr = new QuadTree(this, trBBox, level + 1);
QuadTree br = new QuadTree(this, brBBox, level + 1);
QuadTree bl = new QuadTree(this, blBBox, level + 1);
foreach (PPObject obj in objectList)
{
tl.AddObject(obj);
tr.AddObject(obj);
br.AddObject(obj);
bl.AddObject(obj);
}
childern[0] = tl;
childern[1] = tr;
childern[2] = br;
childern[3] = bl;
objectList = new List<PPObject>();
leaf = false;
}
else if (childern != null)
{
PushToChildern();
}
}
public void PushToChildern()
{
foreach (QuadTree child in childern)
{
foreach (PPObject obj in objectList)
{
child.AddObject(obj);
}
}
objectList = null;
}
public bool CheckBounds(PPObject obj, BBox region)
{
float x1 = obj.position.x;
float w1 = obj.bbox.xmax - obj.bbox.xmin;
float y1 = obj.position.y;
float h1 = obj.bbox.ymax - obj.bbox.ymin;
float dx = Math.Abs(x1 - position.x);
float dy = Math.Abs(y1 - position.y);
if (dx < ((width + w1) * 0.5f) && dy < (height + h1) * 0.5f)
{
return true;
}
return false;
}
/*
* Make this faster by building the list to push here
*/
public void AddObject(PPObject obj)
{
if (obj != null)
{
if (CheckBounds(obj, bbox))
{
objectList.Add(obj);
}
}
}
public void BuildTree()
{
Subdivide();
if (childern != null)
{
foreach(QuadTree child in childern)
{
child.BuildTree();
}
}
}
}