ПрограммированиеФорумОбщее

Алгоритм поиска ближайших объектов в радиусе от игрока. (2 стр)

Страницы: 1 2 3 4 5 6 7 Следующая »
#15
19:37, 27 окт 2024

iw4nna.rock
> А если объект большой
то всегда можно логически разбить на N маленьких. Иными словами это вообще не проблема.

#16
19:39, 27 окт 2024

iw4nna.rock
> то есть просто пустая карта будет весить 1 Гб.
Зачем тебе хранить пустую карту?

А если у тебя в каждой 8х8х8 ячейке хотя бы по 100 байт объектов это уже 12 Гб данных, 1 Гб оверхеда на таблицу не так много.

#17
19:42, 27 окт 2024

iw4nna.rock
> Если мир маленький, то можно разбить его на подпространства. Например в мире размером 64х64х64 М³ будет 512 подпространств размером 8х8х8 М³. Потом можно найти какие объекты попали в подпространства и сделать список индексов этих объектов для каждого подпространства.
А можно просто отсортировать объекты по XYZ и выбирать только те, которые попадают в заданный интервал.

#18
19:46, 27 окт 2024

Eugene
> Зачем тебе хранить пустую карту?
а что вы предлагаете, хранить только ячейки с объектами, а если игрок выйдет за границы, тогда показать надпись "ВЫ НЕ МОЖЕТЕ СЮДА ИДТИ" ? )
Да и просто это будет мешать размещать объекты, нужно будет учитывать наличие ячейки в месте, где хочется разместить объект.

#19
19:53, 27 окт 2024

totoro
> А можно просто отсортировать объекты по XYZ и выбирать только те, которые попадают в заданный интервал
А если объектов сотни тысяч? Уйдёт много времени на такие расчёты. Кроме того как поступать всё с тем же поездом? Оригин поезда может быть в километре от вас, а последний вагон всего лишь в 1 метре. То есть поезд не попал в радиус, но тем не менее он перед носом игрока.

Будете использовать вспомогательные оригины для больших объектов?

#20
(Правка: 20:10) 20:03, 27 окт 2024

iw4nna.rock
> А если объектов сотни тысяч? Уйдёт много времени на такие расчёты.
При отсечении невидимых объектов в любом случае будет затрачено время, вопрос лишь в том как его минимизировать. Если заранее отсортировать неподвижные объекты по удалению от начала координат, то поиск объекта будет иметь логарифмическую сложность, что явно предпочтительнее, чем линейный поиск, и при этом затраты по памяти будут минимальные, т.к. не нужно разбивать пространство на узлы и хранить информацию о них.

iw4nna.rock
> Кроме того как поступать всё с тем же поездом?
А откуда вдруг поезд нарисовался, в вопросе топикстартера про него нет ни слова :)

iw4nna.rock
> Будете использовать вспомогательные оригины для больших объектов?
Случай с поездом, это отдельный случай и решать его нужно отдельно. В зависимости от контекста задачи решений может быть множество, например моно помечать такие объекты специальным флажком always visible и не учитывать при отсечении пространства, либо помещать в отдельный список объектов.

#21
20:19, 27 окт 2024

totoro
> Если заранее отсортировать неподвижные объекты по удалению от начала координат
Но такое сгодится для маленьких радиусов. А что делать если мы в лесу и нам надо отключить рисование дерева, которое оказалось за границей рисования деревьев? А если таких деревьев тысячи? Для каждого дерева теперь пробегать по всему циклу? Не проще ли отключить от рисования сразу всю ячейку, которая оказалось слишком далеко от камеры, не перебирая всё её содержимое.

#22
20:28, 27 окт 2024

iw4nna.rock
> Но такое сгодится для маленьких радиусов. А что делать если мы в лесу и нам надо отключить рисование дерева, которое оказалось за границей рисования деревьев? А если таких деревьев тысячи?
Не вижу проблемы. Определяем координаты игрока и размер области вокруг него (точка минимума и максимума в формате XYZ), из которой хотим сделать выборку объектов по их координатам. Далее находим нижнюю и верхнюю границы диапазона объектов, которые удовлетворяют критериям выборки, и простым перебором итерируемся по этим объектам, определяя имеют ли их ограничивающие сферы пересечения со сферой заданного радиуса вокруг игрока.

#23
20:49, 27 окт 2024

totoro
> Не вижу проблемы. Определяем ...
Ок 👍. Надеюсь, что endeavor_rt поймёт, что вы имеете в виду.

Лично мне больше нравится концепция с ячейками-подпространствами.

#24
20:54, 27 окт 2024

iw4nna.rock
> Надеюсь, что endeavor_rt поймёт, что вы имеете в виду.
Вот пример кодом того о чем я говорю:

struct Object;

struct Point
{
    float x, y, z;

    inline bool operator < (const struct Point& rhs) const
    {
        if (x < rhs.x)
        {
            return true;
        }
        else if (x == rhs.x && y < rhs.y)
        {
            return true;
        }
        else if (x == rhs.x && y == rhs.y)
        {
            return z < rhs.z;
        }
        return false;
    }
};

std::map<struct Point, struct Object*> objects;

void QueryObjects(const Point& min, const Point& max, std::vector<struct Object*>& result)
{
    auto first = objects.lower_bound(min);
    auto last = objects.upper_bound(max);
    std::transform(first, last, result.end(),
    [](const std::pair<Point, struct Object*>& src)->Object*
    {
        return src.second;
    });
}
#25
21:01, 27 окт 2024

iw4nna.rock
> а что вы предлагаете, хранить только ячейки с объектами, а если игрок выйдет за границы, тогда показать надпись "ВЫ НЕ МОЖЕТЕ СЮДА ИДТИ" ? )
> Да и просто это будет мешать размещать объекты, нужно будет учитывать наличие ячейки в месте, где хочется разместить объект.

Почему у файловой системы нет этой проблемы, а у тебя есть?

#26
21:03, 27 окт 2024

Eugene
> Почему у файловой системы нет этой проблемы
У файловой системы есть таблица с "ячейками".

#27
21:15, 27 окт 2024

totoro
> У файловой системы есть таблица с "ячейками".
Ага. И файловая система выделяет ячейки только под те файлы, которые существуют. А под файлы, которых не существует — не выделяет.

Если файловая система может выделять только ячейки под существующие объекты, почти никак не ограничивая пользователя в выборе "координат" файла, то почему iw4nna.rock это сделать не может?

#28
(Правка: 21:19) 21:16, 27 окт 2024

Eugene
> Ага. И файловая система выделяет ячейки только под те файлы, которые существуют.
А под таблицу не выделяет? Из чего таблица-то состоит, не из ячеек ли? :)

#29
(Правка: 22:04) 22:00, 27 окт 2024

Eugene
Сравнили линейную файловую систему с трёхмерным пространством. И удивляетесь почему я не могу что-то сделать...

Во-вторых, файловая система работает с диском, а не с виртуальной памятью, там само железо выступает в роли уже выделенного буфера.

Страницы: 1 2 3 4 5 6 7 Следующая »
ПрограммированиеФорумОбщее