новости сообщество форум вики
Erlang по-русски. Форум » Erlang »

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

(20 posts)

  1. Мне надо обрабатывать очень боль?ой массив однотипных структур - всего их порядка 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, остальные просто ждут). Вопрос: как мне организовать такой массив?

    Отправлено 6 года(лет) назад #
  2. Предположу, что используя ets/dets или mnesia.

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

    Отправлено 6 года(лет) назад #
  3. ЗЫ. В качестве полного оффтопа :)

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

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

    Отправлено 6 года(лет) назад #
  5. > Нет, я не знаю этого сайта

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

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

    в общем, на РСДН сказали, что надо писать на С :) 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.

    Отправлено 6 года(лет) назад #
  6. Вот еще ответ:

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

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

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

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

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

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


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

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

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

    Отправлено 6 года(лет) назад #
  13. > Буду надеятся что nth работает достаточно быстро

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

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

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

    Отправлено 6 года(лет) назад #
  15. > ? мы будем иметь 10 000 локальных списков, каждый под свою ячейку, каждый из которых надо обрабатывать. ? в сумме это даст тот же самый объём объёктов, и даже боль?е

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


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

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

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

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

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

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

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

    Отправлено 6 года(лет) назад #
  17. ?нтересно. С этого момента мне уже сложно что-либо посоветовать, так как увы, в геймдеве, а темболее в MMO гемдеве более, чем несведущ :)

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

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

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

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

    Отправлено 6 года(лет) назад #
  18. всем привет

    знаю что тема стара но все же ре?ил написать так как стояла передо мной та же проблема
    ММО с детектом коллизий и кучей интерактивности между игроками и трехмерньім миром

    я делаю емулятор world of warcraft и там карт много, поетому на каждую карту я наложил сетку
    процесов организированньіх в oct-tree структуру

    карта грузится как одна клетка с единьім масивом обьектов. как только количество обьектов
    превьі?ает некоторьій уровень - клетка делиться на 8 клеток а сама мутирует в мета-клетку

    задача клетки - передавать сообщения между игроками и обьектами и следить/уведомлять других
    об изменении их координат

    броадкаст сообщения которьіе вьіходят за рамки клетки передаються мета-клетке которая
    рещает какие клетки затронутьі радиусом и дублирует сообщение для каждой из них таким
    образом сообщения рекурсивно вспльівают вверх на уровень целой картьі

    P.S. для детектора коллизий конечно луч?е использовать С/С++ - ерланг умрет
    P.P.S. кому интересно - сурсьі здесь http://github.com/keymone/wower

    Отправлено 5 года(лет) назад #
  19. В последнем эрланге появились массивы, я пользуюсь ими. При этом массив используется ли?ь для определения видимости, каждая клетка как один неделимый видимый элемент. В нём расположены объекты с указанием координат и атрибутами, необходимыми для показа. Таким образом под визуальзацию задействован только один процесс и код совсем лёгкий получился. Коллизии тоже на С++ сделал, эрланг для этого не подходит никак.
    При боль?ом перемещении игроков система с восьмеричным деревом может загнуться. Но вообще идея мне нравится!

    Отправлено 5 года(лет) назад #
  20. при боль?ом перемещении любая система может загнуться :)

    вообще я ре?ил завернуть все в дерево процесов потому что

    1. специфика пакетов в вов такова, что для группьі обьектов можно сгенерировать один пакет об их общем перемещении, тоесть легче посчитать ето в одном месте чем считать отдельно в процессе каждого игрока

    2. как сказал армстронг - processes are cheap, spawn them as many as you can :D

    Отправлено 5 года(лет) назад #

RSS экспорт этой темы

Отправить сообщение

Вы должны войти в систему, чтобы оставлять сообщения.

 
 

так же

Популярные тэги



Currently online

No Members around.

сообщество

http://groups.google.com/group/erlang-russian/feed/rss_v2_0_msgs.xml