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

Question

[Quark]

Здравствуйте.У меня еть необходимость определить для каждого юнита всех юнитов,которых он видит.Изначально я использовал обычный брутфос(по порядку брал каждый юнит и проверяли).Однако такой способ приводит к огрмоному количеству необходимых вычислений.Для 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/Дерево_квадрантов#Пс...

Comments

[Wataru]

Вы опишите словами вашу задачу. Что значит "видимость"? Вам надо получить все точки в заданном прямоугольнике?

[Quark]

Wataru, Да.У каждого юнита есть область,в который он может заметить других юнитов.Этим алгоритмом я пытался убрать лишние вычисления(когда юниты стоят слишком далеко друг от друга и никак не могут друг друга увидить.Соответсвенно не нужно для них проверять,могут ли они увидить друг друга).

Answer 1

[mikhanoid]

Возможно, время пожирается рекурсией. Вы множество раз пересобираете массив found из кусочков. Это можно полечить, если found сделать параметром-аккумулятором в рекурсии.

Comments

[Quark]

Можете более подробно описать свои мысли?Я не совмес понял,что вы имеете ввиду под " found сделать параметром-аккумулятором в рекурсии"

[mikhanoid]

Quark_Hell, сделайте интерфейс query примерно такого вида query(Recatngle range, vector &found), и просто собирайте в этот массив found найденные Unit. Не нужно на каждом уровне рекурсии конструировать новый массив found, просто передавайте ссылку на один и тот же массив.

Ну, и вообще, у вас же Си++, имеет смысл range тоже передавать по ссылке.

[Quark]

mikhanoid, Если я вас правильна понял,то вы хотите,чтобы я сделал так:

vector<Unit> query(Rectangle range, vector<Unit> found = vector<Unit>(0)) {
        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);
                //found.insert(found.end(), NWfound.begin(), NWfound.end());

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

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

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

Однако теперь при функция query возвращает почти пустой массив(там всего 1-2 точки,когда их должно быть несколько сотен)

[mikhanoid]

Quark_Hell, не так. found надо передавать по ссылке:

void query(const Rectangle &range, vector<Unit> &found)

. Сейчас у вас push_back происходит в копиях found, которые создаются при вызове функции.

[Quark]

mikhanoid, что вы предлагаете сделать с push_back ?

[mikhanoid]

Quark_Hell, пока ничего. Вам нужно просто правильные ссылки передавать в процессе рекурсивного вычисления. Если скорость после исправления кода не будет устраивать, можно дальше будет оптимизировать.

[Quark]

mikhanoid, А,извините.Я вас понял.
Это всё,что мне нужно было сделать?Просто программа стала работать ещё медленнее
Вот как это выглядит у меня:

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);
                //found.insert(found.end(), NWfound.begin(), NWfound.end());

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

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

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

vector<Unit> unitInRangeView;
quadTree.query(range, unitInRangeView);//Все юниты,которые находятся в радиусе обзора юнита

[mikhanoid]

Quark_Hell, сейчас у Вас куча копий found создаётся в return. Этот вектор теперь больше и копируется дольше. Просто ничего не возвращайте из query.
void query( ... ) ...

И вызов

vector<Unit> found;
tree.query(..., found);

[Quark]

mikhanoid, Действительно,это в некотором смысле решило мою проблему.Теперь дерево в однопотоке работает так-же,как и брутфорс в многопотоке(даже чуть быстрее).Однако применение многопотока на алгоритм квадрантового дерева практически никак не отражается на производительности,что очень странно,ведь я таким способом надеялся понизить время выполнения в 2-3 раза.В любом случае спасибо за помощь.Эту уже другая история)))

[Wataru]

Quark_Hell, координаты игроков часто меняются?

[Quark]

Wataru, Нет.Юниты на данный момент статичны.

[Quark]

Wataru, Скорее всего так и останется

Answer 2

[Wataru]

Это дерево квадрантов (оно же 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 дерева, где вы можете сразу же закончить поиск, если очевидно, что в ответе ничего нет. Зато в худшем случае будет работать быстрее.