Я создаю quadtree для 2D-игры на С#, чтобы ускорить рендеринг. Некоторые объекты (планеты) движутся, и поэтому я создал метод под названием removeAndUpdate
для обновления дерева путем удаления и повторной вставки определенного объекта из листьев (то есть не из корня), как я уже читал в ссылка. К сожалению, я получил System.OutOfMemoryException
через некоторое время при перепрошивке. Я совершенно уверен, что у метода removeAndUpdate
есть некоторые проблемы.
Может быть, стоит упомянуть, что при разделении квадрацикла (в случае, когда емкость квадроцикла заполнена), контент не будет распределяться между сабквадами. Я сделал этот способ, чтобы улучшить производительность. Однако я не думаю, что это имеет какую-то связь с проблемой выше.
Я предполагаю, что где-то есть бесконечный цикл, который приводит к нехватке памяти. Если я вставляю новые объекты из корня, проблем нет.
Я написал комментарий к тому месту, где возникает исключение.
Здесь вы можете увидеть важные части класса QuadTree:
public class QuadTree
{
BoundingBox boundary;
int capacity;
List<WorldObject> leafContent;
public QuadTree parent;
bool divided;
public List<QuadTree> childQuadTrees;
public QuadTree(BoundingBox _boundary, int _capacity, QuadTree _parent)
{
this.boundary = _boundary;
this.capacity = _capacity;
this.leafContent = new List<WorldObject>();
this.childQuadTrees = new List<QuadTree>();
this.divided = false;
this.parent = _parent;
}
// Subdividing the quad, if its storing capacity is full.
public void subdivide()
{
// North-East
this.childQuadTrees.Add(new QuadTree(new BoundingBox(new Vector3(boundary.Center.X, 0, boundary.Min.Z),
new Vector3(boundary.Max.X, 0, boundary.Center.Z)), this.capacity, this));
// North-West
this.childQuadTrees.Add(new QuadTree(new BoundingBox(new Vector3(boundary.Min.X, 0, boundary.Min.Z),
new Vector3(boundary.Center.X, 0, boundary.Center.Z)), this.capacity, this));
// South-East
this.childQuadTrees.Add(new QuadTree(new BoundingBox(boundary.Center, boundary.Max), this.capacity, this));
// South-West
this.childQuadTrees.Add(new QuadTree(new BoundingBox(new Vector3(boundary.Min.X, 0, boundary.Center.Z), new Vector3(boundary.Center.X, 0, boundary.Max.Z)), this.capacity, this));
this.divided = true;
}
public void insert(WorldObject wO)
{
// Checking, whether the quad contains the box at all.
if (!this.ContainOrOverlap(wO.BoundingBox))
{
return;
}
// If there is space, insert the box.
if (this.leafContent.Count < this.capacity && this.divided == false)
{
/*This is the instruction, where System.OutOfMemoryException occures*/
this.leafContent.Add(wO); // <-------
return;
}
// If not, subdivide the quad then insert the obj to the subquads.
else
{
if (this.divided == false)
{
this.subdivide();
}
this.childQuadTrees[0].insert(wO);
this.childQuadTrees[1].insert(wO);
this.childQuadTrees[2].insert(wO);
this.childQuadTrees[3].insert(wO);
}
}
/* Here is the method to update the moving objects bounding volume.
It first removes the element from the tree, updates the boundingbox, then reinsert the object from the leaves*/
public void removeAndUpdate(WorldObject obj, Vector3 displacement)
{
if (!this.ContainOrOverlap(obj.BoundingBox))
{
return;
}
if (this.divided)
{
this.childQuadTrees[0].removeAndUpdate(obj, displacement);
this.childQuadTrees[1].removeAndUpdate(obj, displacement);
this.childQuadTrees[2].removeAndUpdate(obj, displacement);
this.childQuadTrees[3].removeAndUpdate(obj, displacement);
}
/* if the obj is found, remove it, the try to reinsert it to its parent. If its parent does not contain it, move upwards in the hierarchy and try again to insert*/
if (leafContent.Contains(obj))
{
this.leafContent.Remove(obj);
QuadTree q = this.parent;
while (q.ContainOrOverlap(obj.BoundingBox) == false)
{
q = q.parent;
}
obj.BoundingBox.Translate(displacement);
q.insert(obj);
}
}
public void query(BoundingBox range, List<WorldObject> resultList)
{
if (!this.ContainOrOverlap(range))
{
return;
}
if (this.divided)
{
this.childQuadTrees[0].query(range, resultList);
this.childQuadTrees[1].query(range, resultList);
this.childQuadTrees[2].query(range, resultList);
this.childQuadTrees[3].query(range, resultList);
}
resultList.AddList(this.leafContent);
}
}
Вот некоторая информация из отладки при разрыве исключения: