Про 3D базу данных.

Как-то так получается – что сложные алгоритмы становится писать все сложнее и ленивее. Ходишь, думаешь, как написать проще. Приходят мысли – неплохо бы нанять студента, чтобы написал сложный алгоритм, ибо самому лень.

Вот давече посмотрел в свой код, где “пространственная база данных” для рендера и сам удивился – как там все просто. О простом можно написать. 

Задача стоит простая – есть объекты в трехмерном пространстве, которые имеют центр и некий размер.  Надо уметь помещать объекты туда, вытаскивать объекты, которые пересекаются с каким-то кубиком. Для разных целей – декали наложить к примеру. Надо еще делать отсечение по пирамиде видимости ( aka frustrum cull ). Удалять объекты надо быстро из этой самой базы данных.

Начнем с начала. Позиция у объекта – это на самом деле пара { int3, vec3 }.  Непрерывный мир для MMO, большой.  Позиции образуют аффинное пространство – их можно вычитать и получать обычные трехмерные вектора. Ну и прибавлять обычный трехмерный вектор к позиции тоже можно.

Далее. Наш игровой мир – он двумерный и плоский. Есть такой двумерный массивчик, размерности 32 по каждой из компонент, элементы массивчика – списки объектов ( естественно, не совсем списки, ну да ладно ).  Каждой ячейке соответствует квадратик 64×64 метра в плоскости xy. Чтобы положить объект в нашу базу данных – мы берем его целочисленную часть координат по x, y, делим на 64, потом берем остаток от деления на 32. Нашли ячейки, которые объект задевает. Объекты, разнесенные на величину кратную 2 километрам по координатам - попадают в одну ячейку. Но нас это не волнует, у нас подгруженная часть мира сильно меньше. Привязывать и отвязывать объекты у нас сильно быстро. Тем более что перепривязка осуществляется только если положение объекта изменилось сильно.

Операции типа ”наложи декол” стали сильно быстрые – потому что по позиции мы имеем сразу годный список объектов. Берем целочисленную часть координат, делим на 64, берем остаток от деления на 32.

Оверхед на хранение объекта в нескольких ячейках невелик. Сейчас объект хранится в среднем в 1.3 ячейках что ли.

Отсечение по пирамиде видимости делаю тоже очень просто. Выполняю тест для всей ячейки целиком. Надеюсь, что объект не рисуется в среднем 1.3 раза :). Из-за того, что подгруженная часть мира меньше 2 километров – ячейка локализована с точностью до 64 метров. Как кубик в пространстве. Точнее – как квадратик на плоскости с крышечкой “сверху” и “снизу”.

Вот примерно так. Уже не умею писать сложно. И oct tree врядли бы рука поднялась написать. 

  • CEMEH

    В TBM кажется тоже грид в качестве контейнера сцены?

  • http://aruslan.livejournal.com/ aruslan

    В Fighter Ace 98 в качестве БД тоже был грид.
    Ибо в чем смысл quadtree/octree если ячеек мало и объекты относительно небольшие – не очень понятно.

  • Dmitry Tyurev

    >Позиция у объекта – это на самом деле пара { int3, vec3 }.
    А что хранится в int’ах и что во float’ах? Видимо, в int’ах координаты куба размером 2048м, а во float’ах – смещение внутри этого куба или как?

  • Sergei_am

    Зачетно, про wrap. Для чисто ‘мира вокруг нас’ самое то.
    Добавлю только, что можно не один, а несколько гридов, один поверх другого, от мелкого к крупному, опять wrap-ом.
    Таким образом обьектъ побольше попадают в более крупнъй грид, а поменьше – в мелкий. Каждъй обьект попадает в одну единственную ячейку, если на границе ячеек – в грид что покрупнее. Для етого конечно, гридъ смещаются на пол-размера ячейки более мелкого чем они грида.
    Есть пейпр по вопросу, (c) Blizzard.

  • IronPeter

    > Видимо, в int’ах координаты куба размером 2048м

    Можно так, а красивее не 2048, a 64. Чтобы играла только целая часть.

  • DigiMind

    > В TBM кажется тоже грид в качестве контейнера сцены?

    Yep.

  • IronPeter

    Да, еще одно маленькое добавление про “естественно, не списки”.

    У нас удобный контейнер, называется chunked_list. Состоит он из массивов типа T и длины N, связаных в список. Имеет контейнер две функции – положить элемент и удалить элемент. Удаление берет и вставляет в дырку последний элемент нашего списка-вектора, так что порядок не гарантируется.

    Контейнер удобный как по скорости итерации, так и по накладным расходам на память.

    Чаще всего контейнер хранит в себе указатели. В этом случае можно сдружить контейнер с префетчем и сделать итератор, который при заходе в чанк префетчит по всем элементам чанка по хранимым указателям. При типичной длине чанка в 16-32 элемента – будет очень здорово.

  • Dmitry Tyurev

    Прошу прощения за занудность, но таки несколько глупых вопросов.

    Почему при вычитании {int3, vec3} будет получаться “обычный трёхмерный вектор”? Если просто вычесть две таких точки покомпонентно, то трёхмерный вектор явно не получится. Получится вектор в таком же формате {int3, vec3}, который при желании можно преобразовать в vec3.

    “Чтобы положить объект в нашу базу данных – мы берем его целочисленную часть координат по x, y, делим на 64, потом берем остаток от деления на 32.”
    Если целая часть координат – это номер 64-метровой ячейки, то чтобы отмэппить координату на массив 32×32, нужно просто взять остаток от деления на 32. Зачем делить на 64? Куда пойдёт результат деления?

    “Но нас это не волнует, у нас подгруженная часть мира сильно меньше.”
    На клиенте она может и меньше, но сервер ведь должен хранить инфу о значительно части игрового мира, как быть с ним? Ведь там описанная структура scene-graph будет сильно неэффективна. Или на сервере у вас всё по-другому?

    “Тем более что перепривязка осуществляется только если положение объекта изменилось сильно.”
    Почему? Объект может вылезти за пределы своей ячейки даже если сдвинулся незначительно. Если данная структура используется для выборки объектов на отрисовку, то объекты могут появляться на экране “скачком” при редких перепривязках. А с коллиженом будет ещё хуже.

    Кстати, в чём бонус использования формата позии {int3, vec3}? Понятно, что мир большой и вдалеке от начала координат будет потеря точности. Но ведь вместо float’а можно использовать double? По идее, физике, логике и рендеру гораздо удобнее работать с double3, чем с {int3, vec3}, который всё время нужно конвертировать.

    В двух наших ММО-проектах координаты – обычный float3. :)

  • Dmitry Tyurev

    Scene-graph для эти же проектов я писал лет 6 назад, это был quad-tree с небольшой глубиной. Одинаковый на клиенте и сервере. Со своей задачей он справился полностью, нареканий на него не было. В движке третьего проекта используются позиции {int3, float3). Зачем – для меня загадка. Имхо, от такого формата больше геморроя. :)

  • Dmitry Tyurev

    > Для етого конечно, гридъ смещаются на пол-размера ячейки более мелкого
    > чем они грида.Есть пейпр по вопросу, (c) Blizzard.

    Зачётно. А можно ссылку на пейпр?

  • DigiMind

    > Почему? Объект может вылезти за пределы своей ячейки даже если сдвинулся незначительно.

    А он может принадлежать двум (трем и т.п.) ячейкам.
    “Нашли ячейки, которые объект задевает.”

  • Dmitry Tyurev

    Это понятно, но ситуацию не меняет. :) Объект может сдвинуться всего на сантиметр, но уже задеть новую ячейку. Если при этом не сделать перепривязку, возможны баги. Например, с коллиженом.

  • Sergei_am

    Dmitry Tyurev:
    >Почему при вычитании {int3, vec3} будет получаться “обычный трёхмерный вектор”?
    Целая + дробная часть. Все точно.

    >На клиенте она может и меньше, но сервер
    Ето только клиент, разумеется. Тут про локальность, подгруженнъй мир, етц.

    >то объекты могут появляться на экране “скачком” при редких перепривязках. А с коллиженом будет ещё хуже.
    Не могут, ибо они будут в нескольких ячейках, там кроме позиции и *размер*! Все точно.

    >Понятно, что мир большой и вдалеке от начала координат будет потеря точности.
    Ну, обьектъ вообще могут приходить со смещеннъми координатами, а не относительно ‘центра мира’. И дальше сплошной float, с полной точностью. Смещение, в одном лиш месте – когда с сервера query въдало обьектъ, сместить их позиции относительно нашего локального центра.

    >Зачем – для меня загадка. Имхо, от такого формата больше геморроя.
    Ну, как по мне суперское решение, мало кода, бъстро.

    А вот в твоем octree как решался проблемм с обьектами, которъе на границе листьев (у меня тоже octree :( )? В верхний узел, в несколько листьев или loose? Самое крутое решение в принципе, ето в один (верхний) узел, однако для етого octree ужаснейшая структура…

  • Dmitry Tyurev

    > Целая + дробная часть. Все точно

    Ага, значит в интах всё-таки целая часть. Тогда понятно деление на 64. Просто я переспрашивал и Пётр сказал, что там координаты 64м кубов. Ну, да ладно, может я не так понял.

    > Ето только клиент, разумеется. Тут про локальность, подгруженнъй мир, етц.

    Угу. Поэтому я и спрашивал – как тогда быть с сервером? Кстати, насчёт клиента и локальной продгуженной части мира. Если мир непрерывный (как у Петра), то по мере движения по миру, нужно быстро подгружать объекты, вновь попадающие в заданную область. А для этого в свою очередь нужно быстро узнавать что это за объекты и где они находятся. Приходим к необходимости более глобального scene-graph, который будет снабжать информацией локальный. В таком случае вопрос – а зачем их разделять?

    > Не могут, ибо они будут в нескольких ячейках, там кроме позиции и *размер*

    Если объект цепляет две смежные клетки, то ссылки на него присутствуют в обоих клетках? Или нет? И что насчёт размера? Поясни, пожалуйста.

    >Ну, обьектъ вообще могут приходить со смещеннъми координатами, а не
    >относительно ‘центра мира’.

    Для динамических объектов – да. У нас, кстати, также. Но кроме динамических есть статические объекты, которые никуда не пересылаются.

    > Ну, как по мне суперское решение, мало кода, бъстро.

    Так чем именно оно суперское? Кода, как раз должно стать гораздо больше и скорость уменьшится. Ведь в сотнях мест кода, где можно было работать с обычным Vect3 придётся работать с шести компонентным типом, который напрямую не подходит ни физике, ни рендеру, ни логике. Везде придётся писать конвертации из шести компонент в три. Или я что-то упускаю? :)

    > А вот в твоем octree как решался проблемм с обьектами, которъе на границе
    > листьев (у меня тоже octree :( )? В верхний узел, в несколько листьев или
    > loose? Самое крутое решение в принципе, ето в один (верхний) узел, однако
    > для етого octree ужаснейшая структура…

    У меня не oct-tree, а quad-tree. Поскольку мир большой и по большому счёту плоский, то oct-tree смысла особого не имеет, только оверхед на лишние аллокации. Объект на границе листьев находится в нескольких листях. Возможно, это не хай-тековое решение, но оно простое, как валенок и работает уже много лет не доставляя проблем. :)

  • IronPeter

    >Ведь в сотнях мест кода, где можно было работать с обычным Vect3 придётся работать с шести компонентным типом, который напрямую не подходит ни физике, ни рендеру, ни логике. Везде придётся писать конвертации из шести компонент в три. Или я что-то упускаю? :)

    Да. Везде, где тебе нужны vec3 – ты берешь разницу между двумя большими координатами. Оператор бинарного минуса. Любое другое использование, как и приведение больших координат к vec3 – missuse, который приводит к потенциальным ошибкам. Потере точности и так далее.

  • Sergei_am

    Dmitry Tyurev:
    >Угу. Поэтому я и спрашивал – как тогда быть с сервером?
    А вот ето вопрос командъ, которая пишет сервер. Я думаю, там все сильно иначе, обьектъ абстрактнее и т.д., нет детайл мешей и декоров всяких, отдельно грид под статику и под динамику, ибо весь мир все таки (или его большой кусок) в одном месте.

    >Приходим к необходимости более глобального scene-graph, который будет снабжать информацией локальный.
    Ето сервер, запросъ к серверу, не более, imho.

    >Если объект цепляет две смежные клетки, то ссылки на него присутствуют в обоих клетках?
    Да.

    >Так чем именно оно суперское? Кода, как раз должно стать гораздо больше и скорость уменьшится.
    Откуда ему стать больше? Наоборот, весь остальной код – тот же.

    >но оно простое, как валенок
    квад три как раз немного сложнее вот данного решения, из-за траверса йерархии, потенциальнъх алокаций, разброса по памяти нодов и сам размер етого квадтри, которое на весь мир, так?

  • Dmitry Tyurev

    >Да. Везде, где тебе нужны vec3 – ты берешь разницу между двумя большими
    >координатами. Оператор бинарного минуса. Любое другое использование, как
    >и приведение больших координат к vec3 – missuse, который приводит к
    >потенциальным ошибкам. Потере точности и так далее.

    Вот у нас есть игровой объект. Любой. Начиная от персонажа и заканчивая распоследним кустиком. У игрового объекта есть поле position. Так вот, это поле у вас vect3 или {int3, vec3}? Если vect3, то относительно какого центра?

  • Dmitry Tyurev

    >>Приходим к необходимости более глобального scene-graph, который будет снабжать >>информацией локальный.
    > Ето сервер, запросъ к серверу, не более, imho

    То есть, когда мы прошли 50 метров вперёд, то сервер нам скажет, что в области нашей видимости появилось 300 новых деревьев и кустиков и пришлёт все их типы и координаты? ;) Умрём на трафике. Причём, сразу. Всё, что касается статики хранится на клиенте и сервер не напрягает никаким образом. А для того, чтобы клиенту узнать какие объекты появились в области его видимости как раз и нужен глобальный scene-graph. На клиенте.

    >>Если объект цепляет две смежные клетки, то ссылки на него присутствуют в обоих >>клетках?
    >Да.

    ok. Но ты поскипал мой вопрос про “размер” и про то каким образом он решит описанную мной проблему. ;)

    >квад три как раз немного сложнее вот данного решения, из-за траверса
    >йерархии, потенциальнъх алокаций, разброса по памяти нодов и сам
    >размер етого квадтри, которое на весь мир, так?

    Верно. Описанное Петром решение действительно проще, эффективнее и изящнее обычного quad-tree. Однако, оно обслуживает лишь локальную область вблизи игрока. А остальной мир на клиенте тоже нужно обслуживать. Значит должна быть какая-то дополнительная система. А в сумме с ней решение будет явно сложнее обычного quad-tree. Всё, имхо, разумеется, потому что деталей их реализации я не знаю.

  • Sergei_am

    Dmitry Tyurev:
    >То есть, когда мы прошли 50 метров вперёд, то сервер нам скажет, что в области нашей видимости появилось 300 новых деревьев
    Ну, статику конечно нет смъсла запрашивать, ее можно вообще простенькими страничками держать, гридом. Обьектъ на границе страниц – в обе + ID, примерно.

    >ok. Но ты поскипал мой вопрос про “размер” и про то каким образом он решит описанную мной проблему. ;)
    Я уже не понимаю. Все ведь просто – точка + размер -> квадратик, он уходит во все клетки, которъе задевает.

    >Однако, оно обслуживает лишь локальную область вблизи игрока.
    Ну, как я понимаю, даннъй пост именно и только про ето.

    >А в сумме с ней решение будет явно сложнее обычного quad-tree.
    Объчное квадтри, мне лично кажется хуже и сложнее, как всякая структура, натянутая на весь (большой) ММО мир. Плоские странички зарулят йерархию, которая там вроде бъ совсем не нужна – фрустум куллинг над ней не делаем (т.е. нет смъсла делать для всего мира), а тест на пересечение с гридом – явно бъстрее, ибо локально как ничто другое. И ети странички отгружаем в такой вот менажер локальной сценъ и все.

  • Dmitry Tyurev

    >Ну, статику конечно нет смъсла запрашивать, ее можно вообще простенькими
    >страничками держать, гридом.

    О необходимости дополнительных структур данных я как раз и говорил. Насчёт грида ниже.

    >>>Если объект цепляет две смежные клетки, то ссылки на него присутствуют в обоих >>>клетках?
    >>Да.
    >Все ведь просто – точка + размер -> квадратик, он уходит во все клетки, которъе >задевает.

    Есть клетка К1 и объект, позиция + размер (BBOX) которого таковы, что он влезает в К1 целиком, то подходит вплотную к самой его границе. Затем объект сдвинулся на 1см в направлении границы клетки. BBOX объекта пересёк границу К1 и залез на К2. Однако, в исходном посте было сказано “перепривязка осуществляется только если положение объекта изменилось сильно”. Не знаю, что такое сильно, но думаю, что 1см – это не сильно, значит перепривязку не делаем. :) В итоге, запрос списка объектов, пересекающих К2, не выдаст среди них наш объект. Так?

    >Плоские странички зарулят йерархию, которая там вроде бъ совсем не нужна
    >

    Сильно зависит от. Если мир относительно небольшой, то сетки достаточно. Если очень большой, а объекты расставлены неравномерно, то quad-tree зарулит сетку, как по числу фрагментов памяти, так и по оптимальности проверок. Собственно, для этого quad-tree и придуман.

  • Sergei_am

    >О необходимости дополнительных структур данных я как раз и говорил. Насчёт грида ниже.
    А как без них-то? Во первъх, нужно что-то легкое и бъстрое для мира вокруг, и что-то большое для всего мира, которое не факт что должно бъть в памяти (скорее даже не место ему там, ибо стриминг). Так что про одно квадтри под все нуждъ – я сильно с етим бъ поспорил.

    >“перепривязка осуществляется только если положение объекта изменилось сильно”.
    Наверное уклон на коггерентность во времени, т.е. старая техника, когда юзаем баундинг волюм, которъй больше реального и перестраиваем/пересчитъваем только когда реальнъй задел етот большой.

    >Сильно зависит от. Если мир относительно небольшой, то сетки достаточно. Если очень большой, а объекты >расставлены неравномерно, то quad-tree зарулит сетку, как по числу фрагментов памяти, так и по >оптимальности проверок. Собственно, для этого quad-tree и придуман.
    Объчно нормальнъй (красивъй) мир достаточно густо обвешан мешами или их вообще нет (моря, океанъ), а где их мало, я бъ не стал делать более большие области из-за етого, ибо их придется подгружать. А нам скорее надо подгружать, но в заданной области, а не заданное количество обьектов.
    По числу фрагментов вообще-то никак не зарулит, даже наоборот, ибо сетку держать будем на диске.
    По оптимальности проверок – тоже самое, имо.

    Т.е. какую-то грубую структуру в памяти держать можно, но дерево для всего мира – не вижу смъсла от.

  • Dmitry Tyurev

    Про то, что мой подход с успехом используется в ММОРПГ уже несколь лет, я писал выше. :) Остаётся подождать, когда ты реализуешь свой подход и расскажешь о том, какие проблемы и бонусы оно дало на практике. ;)