@Quark_Hell
C++ программист

Почему квадрантовое дерево медленнее брутфорса?

Здравствуйте.У меня еть необходимость определить для каждого юнита всех юнитов,которых он видит.Изначально я использовал обычный брутфос(по порядку брал каждый юнит и проверяли).Однако такой способ приводит к огрмоному количеству необходимых вычислений.Для 10 000 юнитов(а у меня именно столько)нужно 100 000 000 раз сделатаь проверку видимости других юнитов.

Дабы сократить время вычисления(а в среднем на один проход уходило 15 секунд) я решил использовать квадрантовое дерево.Однако после его реализации время на один проход удвоилось,и уже составляет 35-40 секунд,причина чего мне неясна.Можете ли вы подсказать как можно ускорить метод query(а ведь именно он и занимает практически всё время на вычисления).Прошу заранее более подробно описать ваши предложения,ведь для меня эта темя до сих пор остаётся загадкой и я не до конца понимаю как это работает.Вот мой код:

class Rectangle {
public:
    float X;
    float Y;
    float W;
    float H;
    Rectangle(float x = 0, float y = 0, float w = 0, float h = 0) {
        X = x;
        Y = y;
        W = w;
        H = h;
    }

    bool Contains(Unit unit) {
        return (
            unit.Position.X >= X - W &&
            unit.Position.X < X + W &&
            unit.Position.Y >= Y - H &&
            unit.Position.Y < Y + H
            );
    }

    bool Intersects(Rectangle range) {
        return !(
            range.X - range.W > X + W ||
            range.X + range.W <X - W ||
            range.Y - range.H > Y + H ||
            range.Y + range.H < Y - H
            );
    }
};
static vector<int> s;
class QuadTree {
     int Capacity;

public:
     Rectangle Boundary;
     vector<Unit> Points;
     bool Divided;

     QuadTree* NorthWest;
     QuadTree* NorthEast;
     QuadTree* SouthWest;
     QuadTree* SouthEast;

    QuadTree(Rectangle boundary, int capacity) {
        Boundary = boundary;
        Capacity = capacity;
        Divided = false;
    }

    void subdivide() {
        auto x = Boundary.X;
        auto y = Boundary.Y;
        auto w = Boundary.W;
        auto h = Boundary.H;
        auto ne = Rectangle(x + w / 2, y - h / 2, w / 2, h / 2);
        NorthEast = new QuadTree(ne, Capacity);
        auto nw = Rectangle(x - w / 2, y - h / 2, w / 2, h / 2);
        NorthWest = new QuadTree(nw, Capacity);
        auto se = Rectangle(x + w / 2, y + h / 2, w / 2, h / 2);
        SouthEast = new QuadTree(se, Capacity);
        auto sw = Rectangle(x - w / 2, y + h / 2, w / 2, h / 2);
        SouthWest = new QuadTree(sw, Capacity);
        Divided = true;
    }

    bool insert(Unit unit) {
        if (!Boundary.Contains(unit)) {
            return false;
        }

        if (Points.size() < Capacity) {
            Points.push_back(unit);
            return true;
        }
        else {
            if (NorthWest == nullptr) {
                subdivide();
            }
            if (NorthWest->insert(unit)) {
                return true;
            }
            else if (NorthEast->insert(unit)) {
                return true;
            }
            else if (SouthWest->insert(unit)) {
                return true;
            }
            else if (SouthEast->insert(unit)) {
                return true;
            }
        }
    }

    vector<Unit> query(Rectangle range) {
        vector<Unit> found;
        if (!Boundary.Intersects(range)) {
            return found;
        }
        else {
            for (size_t i = 0; i < Points.size();i++) {
                if (range.Contains(Points[i])) {
                    found.push_back(Points[i]);
                }
            }
            if (NorthWest == nullptr) {
                return found;
            }
            if (Divided) {
                vector <Unit> NWfound = NorthWest->query(range);
                found.insert(found.end(), NWfound.begin(), NWfound.end());

                vector <Unit> NEfound = NorthEast->query(range);
                found.insert(found.end(), NEfound.begin(), NEfound.end());

                vector <Unit> SWfound = SouthWest->query(range);
                found.insert(found.end(), SWfound.begin(), SWfound.end());

                vector <Unit> SEfound = SouthEast->query(range);
                found.insert(found.end(), SEfound.begin(), SEfound.end());
            }
        }
        return found;
    }
};

Rectangle boundry = Rectangle(0,0, 10, 10);
QuadTree quadTree = QuadTree(boundry, 10);


Сам вызов же происходит именно так:

void Controller(int start,int end) {
    for (size_t i = start; i < end; i++)
    {
        Rectangle range = Rectangle(unit[i].Position.X, unit[i].Position.Y, 5, 5);
        vector<Unit> unitInRangeView = quadTree.query(range);//Все юниты,которые находятся в радиусе обзора юнита

        int CountSeeUnit = 0;
        for (size_t j = 0; j < unitInRangeView.size(); j++)
        {
            if (CheckView(unit[i], unitInRangeView[j].Position)) {
                CountSeeUnit++;
            }
        }
        printf("Unit Number %i sees %i unit(s) \n", i, CountSeeUnit);
    }
}


Материалы,которые я использовал при написании этого кода:
https://youtu.be/OJxEcs0w_kE
https://github.com/CodingTrain/website/tree/main/C...
https://ru.wikipedia.org/wiki/Дерево_квадрантов#Пс...
  • Вопрос задан
  • 143 просмотра
Решения вопроса 1
mikhanoid
@mikhanoid
Возможно, время пожирается рекурсией. Вы множество раз пересобираете массив found из кусочков. Это можно полечить, если found сделать параметром-аккумулятором в рекурсии.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Это дерево квадрантов (оно же kd-дерево) плохо работает для запроса "найди все точки"), если точки в нем лежат кучно и почти все попадают в ответ. В этом случае вы, как и в наивном решении, проверите почти все точки, но при этом потратите в несколько раз больше времени на накладные расходы - проверку пустых листов и обход дерева.

Еще, ваше дерево, если точки лежат кучно, создает очень много пустых вершин. Представьте, что все точки лежат очень близко к левому нижнему углу. Вы разобъете квадрат на 4 части, но 3 из них пусты. Вы повторяете эту операцию, пока квадраты не станут совсем маленькими и не разобьют точки на несколько групп.
Первая оптимизация - не добавлять точки по одной, а обрабатывать их группой. Если в текущей вершине точек слишком много - надо найти медианную точку по горизонтали, а внутри каждой группы медианную по вертикали. И будут у вас 4 прямоугольника на месте изначального, но они не будут выравнены как 4 четверти квадрата. Но зато будут всегда делить пополам.

Вторая оптимизация - если вы видите, что bounding rect текущей вершины лежит целиком в запросе - надо просто вернуть все точки.

Но есть другая структура, которая будет работать лучше в вашем примере, хоть и занимать в log n больше памяти.

Вам нужно дерево отрезков бинарных деревьев поиска (можно использовать std::set).
Заведите дерево отрезков по OX, где каждая вершина будет упорядоченное по OY set всех точек попадающих в данный отрезок по X.

При запросе вы разбиваете отрезок по X запроса на Log n отрезков-вершин в дереве отрезков (это те вершыны, которые надо взять в запрос по ссылке выше) Далее в каждом из этих Logn сетов можно через lower_boundary и upper_boundary получить итераторы начала и конца всех точек в вашем запросе.

Т.е вы можете получить все точки за O(log n). Правда, какая-то обработка их уже будет O(n) в худшем случае - вся ассимптотика портиться. Но если вам нужно только их количество, то вы можете найти расстояния между двумя итераторами за константу и не надо точки никуда копировать в вектор.

Но даже если вам надо будет точки все в прямоугольнике обойти, то тут тоже можно ускорить немного - вы не копируйте точки в vector. Вы так и возвращайте вектор пар итераторв начала и конца в разных set-ах. И, если вам надо будет обойти точки - обходите двумя вложенными циклами - один по вектору пар итераторов, и второй по самим итераторам.

Еще, оптимизация, если у вас lower_bound оказался равен upper_bound, то не надо эту пару итераторов (пустой интервал) класть в массив ответа.

Еще один бонус этой структуры, что можно быстро удалять/добавлять/менять точки и все остается балансированным. Но, в отличии от kd-дерева, оно занимает в log n раз больше памяти и операция поиска всегда занимает O(log n + ответ), что может быть чуть медленее лучшего случая kd дерева, где вы можете сразу же закончить поиск, если очевидно, что в ответе ничего нет. Зато в худшем случае будет работать быстрее.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы