![[Pasted image 20230925083845.png]]
Quadtree — это способ организации данных в двухмерном пространстве, когда каждый "квадрат" делится на четыре меньших квадрата. Это удобно для быстрого поиска объектов на карте.
Используется в 2D-пространстве.
Квадродерево разделяет пространство на четыре равные узлы (квадранты), отсюда и название "квадро" (четыре).
### Для чего используется
1. Отрисовка: рисуем только то, что видно на экране.
2. Столкновения: проверяем [[Пересечение|пересечение]] объектов быстрее, не сравнивая каждый с каждым.
### Принцип работы
1. **Инициализация**: Сначала создается корневой узел, который охватывает всю интересующую область.
2. **Вставка**: При добавлении нового объекта (точки, фигуры и т. д.) дерево проверяет, в каком квадранте (из 4 возможных) объект находится относительно корневого узла. Если в этом квадранте уже есть объекты и лимит заполненности превышен, квадрант делится на четыре новых подквадранта. Объект помещается в соответствующий подквадрант.
3. **Поиск**: Поиск происходит рекурсивно, начиная от корневого узла и двигаясь вниз по дереву, проверяя только те квадранты, которые [[Пересечение|пересекаются]] с заданной областью поиска.
4. **Удаление и обновление**: При удалении объекта дерево перестраивается. Если после удаления в родительском узле остается меньше, чем определенное количество объектов, его дочерние узлы удаляются, и все объекты переносятся обратно в родительский узел.
### Производительность
- Допустим, в игре на карте будут сотни юнитов. Для каждого юнита нужно искать ближайших врагов. В таком случае, нам придется запускать для каждого юнита поиск врагов в желаемом радиусе в каждом тике.
- Добавление и удаление объектов: работает быстро, примерно как логарифм числа объектов [[Asymptotic Complexity и Time Complexity (Асимптотическая сложность и Временная сложность)|O(log N)]], где N обозначает количество объектов, которые хранятся в данной структуре данных.
- Поиск объектов: также быстрый, O(\log N).
Использование quadtree может ускорить вашу игру, но стоит помнить, что если объекты часто двигаются, обновление quadtree может занять время.
### Пример реализации QuadTree в C\#
В этой реализации `QuadTree` есть нюанс.
Прямоугольники, которые не попадают полностью ни в один из четырех квадрантов узла (то есть частично или полностью пересекают границы между квадрантами), будут храниться в самом узле.
При вызове метода `Retrieve` для поиска пересекающихся прямоугольников все такие "граничные" прямоугольники всегда будут добавлены в итоговый список.
##### Производительность
- Выбор констант `MaxObjects` и `MaxLevels` влияет на глубину дерева и, соответственно, на производительность. Слишком большие или маленькие значения могут ухудшить производительность.
```csharp
using System;
using System.Collections.Generic;
// Класс для представления прямоугольника или зоны
public class Rectangle
{
// `x` и `y` - глобальные координаты левого нижнего угла прямоугольника
public float X, Y;
public float Width, Height;
// Другие методы и свойства
}
public class QuadTree
{
// Максимальное количество объектов в одном узле
private const int MaxObjects = 4;
// Максимальное количество уровней дерева
private const int MaxLevels = 5;
// Текущий уровень узла
private int level;
// Список объектов в узле
private List<Rectangle> objects;
// Прямоугольная зона, которую представляет узел
private Rectangle bounds;
// Поддеревья
private QuadTree[] nodes;
// Конструктор
public QuadTree(int level, Rectangle bounds)
{
this.level = level;
this.objects = new List<Rectangle>();
this.bounds = bounds;
this.nodes = new QuadTree[4];
}
// Очистка дерева
public void Clear()
{
objects.Clear();
for (int i = 0; i < nodes.Length; i++)
{
if (nodes[i] != null)
{
nodes[i].Clear();
nodes[i] = null;
}
}
}
// Разделение узла на 4 поддерева
private void Split()
{
float subWidth = bounds.Width / 2;
float subHeight = bounds.Height / 2;
float x = bounds.X;
float y = bounds.Y;
nodes[0] = new QuadTree(level + 1, new Rectangle { X = x + subWidth, Y = y, Width = subWidth, Height = subHeight });
nodes[1] = new QuadTree(level + 1, new Rectangle { X = x, Y = y, Width = subWidth, Height = subHeight });
nodes[2] = new QuadTree(level + 1, new Rectangle { X = x, Y = y + subHeight, Width = subWidth, Height = subHeight });
nodes[3] = new QuadTree(level + 1, new Rectangle { X = x + subWidth, Y = y + subHeight, Width = subWidth, Height = subHeight });
}
// Вставка объекта (прямоугольника) в узел или поддеревья
// Если прямоугольник не умещается полностью в один из квадрантов
// (поддеревьев), то прямоугольник останется в текущем узле и не будет перемещён в поддерево.
public void Insert(Rectangle rect)
{
// Если в этом узле уже есть поддеревья
if (nodes[0] != null)
{
int index = GetIndex(rect);
// Если index != -1, то прямоугольник полностью умещается в одном из поддеревьев
if (index != -1)
{
nodes[index].Insert(rect);
return;
}
}
// Если квадрантов нет или прямоугольник не уместился в поддеревьях, то добавляем в текущий узел.
objects.Add(rect);
// Если количество объектов превышает максимум и уровень не максимальный
if (objects.Count > MaxObjects && level < MaxLevels)
{
// Создаем поддеревья, если их еще нет
if (nodes[0] == null)
{
Split();
}
// Перемещаем объекты в поддеревья, если это возможно
int i = 0;
while (i < objects.Count)
{
int index = GetIndex(objects[i]);
if (index != -1)
{
nodes[index].Insert(objects[i]);
objects.RemoveAt(i);
}
else
{
i++;
}
}
}
}
// Метод получает все объекты (returnObjects), которые пересекаются с заданным прямоугольником (rect) или находятся внутри заданного прямоугольника (rect).
public void Retrieve(List<Rectangle> returnObjects, Rectangle rect)
{
int index = GetIndex(rect);
if (index != -1 && nodes[0] != null)
{
nodes[index].Retrieve(returnObjects, rect);
}
returnObjects.AddRange(objects);
}
// Метод определяет местоположение прямоугольника в одном из четырех
// квадрантов (поддеревьев) и возвращает индекс квадранта
// Если прямоугольник не умещается полностью в один из квадрантов, метод вернёт `-1`
private int GetIndex(Rectangle rect)
{
int index = -1;
float verticalMidpoint = bounds.X + (bounds.Width / 2);
float horizontalMidpoint = bounds.Y + (bounds.Height / 2);
bool topQuadrant = rect.Y < horizontalMidpoint && rect.Y + rect.Height < horizontalMidpoint;
bool bottomQuadrant = rect.Y > horizontalMidpoint;
if (rect.X < verticalMidpoint && rect.X + rect.Width < verticalMidpoint)
{
if (topQuadrant)
{
index = 1;
}
else if (bottomQuadrant)
{
index = 2;
}
}
else if (rect.X > verticalMidpoint)
{
if (topQuadrant)
{
index = 0;
}
else if (bottomQuadrant)
{
index = 3;
}
}
return index;
}
}
```
### Пример использования QuadTree
- Операция извлечения объектов (`Retrieve`) имеет временную сложность `O(log N)`, что делает ее достаточно эффективной для больших наборов данных.
- Операция вставки (`Insert`) также имеет временную сложность `O(log N)`.
```csharp
class Program
{
static void Main(string[] args)
{
// Создаем корневой узел QuadTree с заданными границами
QuadTree quadTree = new QuadTree(0, new Rectangle { X = 0, Y = 0, Width = 100, Height = 100 });
// Добавляем несколько прямоугольников
quadTree.Insert(new Rectangle { X = 10, Y = 10, Width = 2, Height = 2 });
quadTree.Insert(new Rectangle { X = 20, Y = 20, Width = 2, Height = 2 });
quadTree.Insert(new Rectangle { X = 30, Y = 30, Width = 2, Height = 2 });
// Создаем прямоугольник для поиска пересечений
Rectangle searchRect = new Rectangle { X = 15, Y = 15, Width = 10, Height = 10 };
// Извлекаем все прямоугольники, которые пересекаются с заданным
List<Rectangle> foundRects = new List<Rectangle>();
quadTree.Retrieve(foundRects, searchRect);
// Выводим найденные прямоугольники
Console.WriteLine("Found rectangles:");
foreach (var rect in foundRects)
{
Console.WriteLine(
quot;X: {rect.X}, Y: {rect.Y}, Width: {rect.Width}, Height: {rect.Height}");
}
}
}
```
### Производительность
- Операция извлечения объектов (`Retrieve`) имеет временную сложность `O(log N)`, что делает ее достаточно эффективной для больших наборов данных.
- Операция вставки (`Insert`) также имеет временную сложность `O(log N)`.