Erlang по-русски. Форум Тема: Какую структуру данных выбрать?

dmitriid "Какую структуру данных выбрать?"

dmitriid — Mon, 01 Oct 2007 14:29:25 +0000

Интересно. С этого момента мне уже сложно что-либо посоветовать, так как увы, в геймдеве, а темболее в MMO гемдеве более, чем несведущ :)

Но интересно будет узнать, как оно будет дальше развиваться. Блог о похождениях планируется? :)

Кстати, я вспомнил/нашел вот такие ссылки:

A Virtual World Distributed Server developed in Erlang as a Tool for analysing Needs of Massively Multiplayer Online Game Servers
Is Erlang adapted to a massively multi-player online role game (MMPORG)?
REI: An Online Video Gaming platform (к сожалению, проект более не существует, но идеи из презентации, думаю, можно будет почерпнуть)

И еще я знаю, что MMORPG Vendetta Online переписали код AI своих NPC на Эрланге, правда деталей они особо не сообщали (по ссылке см. новости за 25 июня, 18 июля, 4 августа, 18 августа).

В общем, чем богаты... :)

architect "Какую структуру данных выбрать?"

architect — Sat, 29 Sep 2007 13:31:55 +0000

Сам игрок это уже несколько объектов: физический, объёма V1, обасть видимости, объёма V2, область чата, объёма V3, дальность использования предмета в руках, объём V4. И этот список можно продолжить. Кроме игроков двигаются и другие предметы - мобы, НПЦ, просто ящики/бочки, если их пнуть. У меня похожая на вашу идея реализации, там каждый объект объёма V содержит список всех объектов которые в него попали целиком и список тех объектов, с которыми он пересекается. Можно добавить даже ячейки, это просто будет недвижимый объект, имеющий объём - и он будет включать все мелкие объекты, а саму ячейку будет как ты сказал "всасывать" любой крупный объект. + у меня там сортировка для бытрого определения соседних объектов, она после каждого перемещения делается.
Требования про 2 мкс из первого поста - это с учётом всех этих оптимизаций, считал для 1000 игроков. 60 млн объектов - это в основном ландшафт. Локация 4 на 4 км, изменение высоты каждый метр = 16 млн объектов. Делаем 20 млн для учёта игроков, деревьев и всего остального. Раскладываем по 3-м осям пространства (x, y, z) - и того 60 млн объектов).
Потом я решил вынести ландшафт в отдельную структуру, в карту высот. Но тогда мне нужны массивы, а их нету в эрланге. В общем похоже физику я буду делать на сях.

dmitriid "Какую структуру данных выбрать?"

dmitriid — Fri, 28 Sep 2007 13:56:44 +0000

> И мы будем иметь 10 000 локальных списков, каждый под свою ячейку, каждый из которых надо обрабатывать. И в сумме это даст тот же самый объём объёктов, и даже больше

Объем-объемом, но каждый из этих списков будет обрабатываться не одним процессом, а, скажем, тысячью. Да еще в дереве каком-нить, например:

- глобальный супервизор района | - супервизор кластера ячеек | - супервизор ячейки

где глобальный супервизор занимается только регистрацией входящих/исходящих из района игроков

его worker'ы - это супервизоры кластеров ячеек, коорые отслеживают состояние каких-либо перемещающихся объектов в пределах кластера

их worker'ы собственно занимаются обработкой объектов непосредственно в ячейке - обработка всех необходимых collisions и проч.

Это если максимально упростить. Можно представить себе "плавающий супервизор", привязаный к игроку, который всасывает в себя ячейки по мере перемещения из pool'а ячеек (ну и забывает о ненужных ячейках по мере продвижения).

Ячейки могут быть произвольно большими - например, на расстояние выстрела из лука.

architect "Какую структуру данных выбрать?"

architect — Fri, 28 Sep 2007 13:37:13 +0000

2 ЗВЕР. Я тебя понял, но я делаю ММОРПГ. Игроки могут разбрестись по всей карте, и в идеале они даже должны так сделать - если на карте есть незаполненые игроками места - это плохая карта. А раз они все разбрелись, то заполнили все ячейки. И мы будем иметь 10 000 локальных списков, каждый под свою ячейку, каждый из которых надо обрабатывать. И в сумме это даст тот же самый объём объёктов, и даже больше (ведь 1 объёкт попадёт в списки всех соседних по отношению к нему ячеек, т.е. будет 9 копий этього объекта).
Я придумал более сложную систему сортировки, т.к. эрланг позволяет создавать очень сложные структуры из-за своей безтиповости.
Но всё равно у меня есть ландшафт и дял него есть карта высот. А карта высот это двумертый массив, в котором x и y индексы, а z получаемое значение. Вот и жалею что в эрланге нету массивов(

dmitriid "Какую структуру данных выбрать?"

dmitriid — Fri, 28 Sep 2007 09:26:54 +0000

> Буду надеятся что nth работает достаточно быстро

К сожалению, nth - это линейный поиск, то есть на больших списках он буде дико тормозить :)

Кстати, есть же другие способы ранения объектов - двоичные деревья, например.

3BEP "Какую структуру данных выбрать?"

3BEP — Fri, 28 Sep 2007 00:16:05 +0000

Наверно я плохо объяснил свою мысль. Попробую поподробнее.
Вместо глобального списка использовать набор локальных списков, каждый из которых считается в своем потоке. Для построения таких локальных списков карту разделить на ячейки. Ячейки могут быть как пассивные - сообщают список находящихся в них объектов по запросу, так и активные - рассылают подписавшимся объектам события входа/выхода.
Для примера, предположим что квадратная карта разделена на 100х100 ячеек. "Поле зрения" каждого из объектов не более одной ячейки. Тогда объект находящийся в центре одной из ячеек может "увидеть" только объекты в своей и восьми соседних ячейках. Если объекты распределены равномерно по всей карте - то локальный список будет составлять только 9/10000 от общего числа объектов. Остальные объекты в этот список просто не попадут. Меняя размер ячейки и радиус "поля зрения" можно регулировать размеры этого локального списка. И соответственно время отклика. Так как для каждого игрока создается свой локальный список и обрабатывается этот список независимо от остальных, то получаем фиксированное время отклика и прекрасно масштабируемую систему.

architect "Какую структуру данных выбрать?"

architect — Thu, 27 Sep 2007 18:29:31 +0000

Сетка на карте конечно будет. Но количество объектов это не поменяет). Буду надеятся что nth работает достаточно быстро. Если он пробегает весь список до индекса - это плохо.

dmitriid "Какую структуру данных выбрать?"

dmitriid — Mon, 24 Sep 2007 07:23:21 +0000

> Теперь мне надо найти аналог массива в эрланге, т.е. доступ по индексу чтоб был. Есть такое?

lists:nth/2 - доступ к элементам списка по индексу:

L = [a, b, c], lists:nth(2, L). %% вернет b

3BEP "Какую структуру данных выбрать?"

3BEP — Sat, 22 Sep 2007 22:05:53 +0000

Я бы предложил набросить на карту сетку с большим размером ячейки. Каждую ячейку выделить в отдельный объект, знающий кто в ней находится и знающий ближайшие соседи-ячейки. Тогда при входе в ячейку игровой объект регистрируется сам - только свой идентификатор (возможно PID). При выходе из ячейки - сообщает об этом. Ну и может запросить список зарегистрированных в ячейке объектов. Игровой объект может сам определять свою траекторию и опрашивать близкие к ней ячейки. А всего остального для такого объекта не существует - микровселенная.

architect "Какую структуру данных выбрать?"

architect — Sat, 22 Sep 2007 19:12:27 +0000

Да, но как определить какие объекты ему нужны для взаимодействия? Вот для этого и создано общее индексированое хранилище. Потом во время взаимодействия для объектов создаётся свой процесс и уже в этом процессе они локально обсчитываются.
Я решил убрать из хранилища землю. Тогда конечно появляются неприятности с подземными ходами/тоннелями, но зато экономия памяти весьма значительна.
Теперь мне надо найти аналог массива в эрланге, т.е. доступ по индексу чтоб был. Есть такое?

3BEP "Какую структуру данных выбрать?"

3BEP — Thu, 20 Sep 2007 01:39:45 +0000

А единое хранилище такой большой емкости действительно необходимо?
Может имеет смысл отказаться от единой сцены в пользу концепции "каждый объект - пуп своей вселенной". Маленькой такой вселенной, куда входят только те объекты с которыми возможно взаимодействие в ближайшие несколько секунд. И хранить для каждого объекта только его собственную вселенную.

dmitriid "Какую структуру данных выбрать?"

dmitriid — Wed, 19 Sep 2007 13:14:54 +0000

Вот еще ответ:

здесь: http://rsdn.ru/forum/message/2662478.1.aspx
и продолжение: http://rsdn.ru/forum/message/2662503.1.aspx

dmitriid "Какую структуру данных выбрать?"

dmitriid — Wed, 19 Sep 2007 07:58:20 +0000

> Нет, я не знаю этого сайта

просто у вас на сайте он есть :)

> Тоже склоняюсь к мнезии, но хотел знать, может что получше по производительности есть.

в общем, на РСДН сказали, что надо писать на С :) http://rsdn.ru/forum/message/2661952.aspx:

Такое очень сложно сделать без мутируемых структур — говорю по опыту

Проще взять и написать модуль на С++, с использованием Boost.MultiIndex. Естественно, все должно хранится в памяти.

В erlang-questions же предложили использовать BerkleyDB (где-то в рассылке пробегала ссылка на драйвера к BDB). Говорят, что появится нативный драйвер к BDB от SleepyCat/Oracle.

В общем, хз :)

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

Вот еще получил такое вот письмо:

You'd need fragmented mnesia tables. If you want to put this all on
one node, you have to use 64-bit erlang. You'll need a lot more than
3GB as you need space for the index tables for all other columns.
Forget about dets if you need read access in 2us. You have to use
mnesia disc_copies.

architect "Какую структуру данных выбрать?"

architect — Tue, 18 Sep 2007 18:28:23 +0000

Нет, я не знаю этого сайта. Я хочу писать сервак для ММОРПГ на эрлаанге. 60 миллионов объектов - это для обнаружения коллизий (тут и физика, и поле видимости, и чат и вообще всё что можно придумать о взаимодействии объектов в пространстве). Сейчас думаю над архитектурой и читаю про библиотеки разные. Тоже склоняюсь к мнезии, но хотел знать, может что получше по производительности есть.

dmitriid "Какую структуру данных выбрать?"

dmitriid — Tue, 18 Sep 2007 17:53:48 +0000

ЗЫ. В качестве полного оффтопа :)

Не знаю, имеешь ли ты отношение непосредственно к heroez.net, но я там когда-то давно был зарегистрирован и даже активно участвовал на самой заре под ником Illiarian. Если вдруг знакомы будет интересно (8 миллиардов сайтов и тут на тебе - знакомые :) )

dmitriid "Какую структуру данных выбрать?"

dmitriid — Tue, 18 Sep 2007 17:49:28 +0000

Предположу, что используя ets/dets или mnesia.

Продублировал этот вопрос на RSDN, http://rsdn.ru/forum/message/2661663.1.aspx и в erlang-questions. Посмотрим, что ответят гуру :)

architect "Какую структуру данных выбрать?"

architect — Tue, 18 Sep 2007 16:36:35 +0000

Мне надо обрабатывать очень большой массив однотипных структур - всего их порядка 60 миллионов. Каждая структура вида {PID, type (atom), direct (atom), index (Integer), nextind (Integer), prevind (Integer), position (Integer)}. Я думаю такая структура займёт около 50 байт, и того на весь массив надо 60 * 50 = 3 ГБ. А это значит массив желательно должен частично сбрасываться на диск. Плюс нужен быстрый доступ по полям PID, index, nextind, prevind: время поиска нужной структуры по этим полям должно составлять около 2 мкс, время их записи - столько же. Запись и чтение часто идёт в одни и те же структуры (обчно их всего около 30 000, остальные просто ждут). Вопрос: как мне организовать такой массив?