QuadTree?QuadTree - это структура данных, которая используется для разбиения двумерного пространства на более мелкие области. Каждый узел дерева представляет собой квадратную область (ячейку) внутри основной области. Если ячейка слишком большая, то она разбивается на четыре одинаковых подъячейки, каждая из которых может быть либо пустой, либо содержать объекты.В
QuadTree каждая нода может иметь до четырех потомков, которые представляют собой разделенную ячейку.Для добавления объектов в
QuadTree необходимо сперва знать, какой ячейке они принадлежат. Каждый объект добавляется в самую мелкую ячейку, которая полностью охватывает его. Если ячейка становится слишком заполненной, то она разбивается на более мелкие. Проще говоря, нужно делать rect.Contains() несколько раз, чтобы понять куда отнести элемент.Поиск объектов в
QuadTree осуществляется путем перебора узлов дерева. Начиная с корня, мы проверяем, находится ли ячейка, в которой мы ищем объект, в пределах текущей ячейки узла. Если да, то мы переходим к следующему уровню дерева и продолжаем поиск в ячейках потомков. Если нет, то мы переходим к следующему соседнему узлу.Преимущества
QuadTree заключаются в том, что он позволяет быстро находить объекты в двумерном пространстве, а также быстро выполнять операции вставки и удаления объектов. Недостатком может быть то, что при неправильном выборе размера ячеек и глубины дерева, может возникнуть слишком большая структура, что негативно скажется на производительности.На практике мы такое используем для поиска целей для атаки.
Существует еще и
Octree для 3D, алгоритм работы по сути ничем не отличается.#datastructures #algorithms