Тема закрыта
Список изменений сервера
Уважаемые игроки, представляем вашему вниманию список изменений, правок и обновлений, произошедших на сервере за последнее время.
Скрытый текст
В этом обновлении была предпринята вторая попытка реализовать новую очередь для Поиска Подземелий.
Принцип
Новый алгоритм принципиально отличается от старого методикой подбора, главная его цель - избавиться от перебора комбинаций между абсолютно всеми игроками в очереди (на что тратится непомерное количество времени и памяти) и тем самым устранить критический недостаток прошлой реализации. Недостаток этот заключался в том, что при определённых обстоятельствах проверка комбинаций могла досрочно завершаться, исключая многих игроков из проверок и вызывая этим их "застревание" в очереди. Если же этот недостаток исправить сам по себе, то на первый план выходит фатальная ошибка в дизайне самой системы очереди - тот самый перебор комбинаций. При 50 игроках в очереди количество допустимых комбинаций уже превышает 2 миллиона и растёт в геометрической прогрессии с каждым новым игроком, быстро выходя из-под контроля и вызывая зависания сервера.
Новый алгоритм представляет другой подход к организации очереди. Вместо одной большой кучи, в которую скидываются все игроки, мы теперь имеем много отдельных очередей, каждая - в своё конкретное подземелье. Каждая очередь представляет собой набор "вёдер" ("buckets"), в которых находятся игроки и группы, вставшие в очередь. В каждом ведре могут находиться только 1 танк, 1 хил и 3 ДД.
Когда новый игрок или группа входят в очередь, сервер попытается их добавить в самое ближайшее к началу очереди ведро (при этом проверяя совместимость с уже находящимися в ведре игроками: между ними не должно быть игноров, суммарное количество не должно превышать размер группы, количество всех ролей не должно превышать вышеупомянутые 1/1/3, две ПП группы не могут находиться в одном ведре и всё такое). Если же подходящего ведра не нашлось - в конец очереди добавится новое ведро, в которое и будет вкинут игрок/группа.
Таким образом, сохраняется, собственно, сам смысл очереди: игроки, ждущие дольше всего, находятся в передних вёдрах, а нововошедшие - в задних.
Когда игрок/группы выходит из очереди, он удаляется из своего ведра, и на его месте образуется "вакуум", который должен быть заполнен. Для этого сервер попытается подтянуть игроков из следующих вёдер. Он по очереди пройдётся по всем вёдрам от текущего до конца очереди и попытается затянуть в ведро с вакуумом первых попавшихся игроков. А первыми попавшимися, как уже стало известно выше, будут те, которые раньше всех попали в эти вёдра, таким образом сохраняя порядок очереди. Разумеется, затягивание игроков из других вёдер ведёт к образованию вакуума в тех вёдрах, откуда игроков заберут, поэтому эти действия будут повторяться до тех пор, пока все игроки не будут перетащены с конца поближе к началу очереди.
Как только ведро заполнится полностью - мы имеем готовую группу, которую можно отправлять в подземелье. В случае, если не все подтвердят роль, ведро будет возвращено в начало очереди и сервер попытается насильно в него затащить игроков.
Плюсы
В этом обновлении была предпринята вторая попытка реализовать новую очередь для Поиска Подземелий.
Принцип
Новый алгоритм принципиально отличается от старого методикой подбора, главная его цель - избавиться от перебора комбинаций между абсолютно всеми игроками в очереди (на что тратится непомерное количество времени и памяти) и тем самым устранить критический недостаток прошлой реализации. Недостаток этот заключался в том, что при определённых обстоятельствах проверка комбинаций могла досрочно завершаться, исключая многих игроков из проверок и вызывая этим их "застревание" в очереди. Если же этот недостаток исправить сам по себе, то на первый план выходит фатальная ошибка в дизайне самой системы очереди - тот самый перебор комбинаций. При 50 игроках в очереди количество допустимых комбинаций уже превышает 2 миллиона и растёт в геометрической прогрессии с каждым новым игроком, быстро выходя из-под контроля и вызывая зависания сервера.
Новый алгоритм представляет другой подход к организации очереди. Вместо одной большой кучи, в которую скидываются все игроки, мы теперь имеем много отдельных очередей, каждая - в своё конкретное подземелье. Каждая очередь представляет собой набор "вёдер" ("buckets"), в которых находятся игроки и группы, вставшие в очередь. В каждом ведре могут находиться только 1 танк, 1 хил и 3 ДД.
Когда новый игрок или группа входят в очередь, сервер попытается их добавить в самое ближайшее к началу очереди ведро (при этом проверяя совместимость с уже находящимися в ведре игроками: между ними не должно быть игноров, суммарное количество не должно превышать размер группы, количество всех ролей не должно превышать вышеупомянутые 1/1/3, две ПП группы не могут находиться в одном ведре и всё такое). Если же подходящего ведра не нашлось - в конец очереди добавится новое ведро, в которое и будет вкинут игрок/группа.
Таким образом, сохраняется, собственно, сам смысл очереди: игроки, ждущие дольше всего, находятся в передних вёдрах, а нововошедшие - в задних.
Когда игрок/группы выходит из очереди, он удаляется из своего ведра, и на его месте образуется "вакуум", который должен быть заполнен. Для этого сервер попытается подтянуть игроков из следующих вёдер. Он по очереди пройдётся по всем вёдрам от текущего до конца очереди и попытается затянуть в ведро с вакуумом первых попавшихся игроков. А первыми попавшимися, как уже стало известно выше, будут те, которые раньше всех попали в эти вёдра, таким образом сохраняя порядок очереди. Разумеется, затягивание игроков из других вёдер ведёт к образованию вакуума в тех вёдрах, откуда игроков заберут, поэтому эти действия будут повторяться до тех пор, пока все игроки не будут перетащены с конца поближе к началу очереди.
Как только ведро заполнится полностью - мы имеем готовую группу, которую можно отправлять в подземелье. В случае, если не все подтвердят роль, ведро будет возвращено в начало очереди и сервер попытается насильно в него затащить игроков.
Плюсы
- Застреваний в очередях больше быть не должно.
- Иконка возле миникарты будет более правдоподобно отображать состояние сбора вашей группы, ведь теперь она будет показывать именно количество игроков в вашем ведре. Содержание ведра, правда, может меняться, поэтому не удивляйтесь, если их вдруг станет меньше.
Минусы
- Большие группы (из 3, 4 игроков) наверняка начнут ждать в очереди дольше, чем раньше. Раньше для них проверялись комбинации ровно с таким же приоритетом, как и для соло игроков, сейчас же они начнут чаще оказываться в конце очереди. Если ни в одном из вёдер в начале очереди для них не нашлось места (что должно быть довольно распространённым случаем, ибо теоретически чем ближе к началу очереди, тем больше игроков должно быть в вёдрах и тем меньше шанс, что в них найдётся место сразу 3-им или 4-ым игрокам из группы).
- Делал я эту очередь также и в надежде на то, что она пойдёт на панды и будет служить для тамошнего ЛФР, но, к сожалению, она тоже оказалась неподходящей для очередей такого масштаба. Уже на 20 игроках в очереди сервер, можно сказать, зависал.
Возможные проблемы
- Краши. Их может быть много. Я везде натыкал принудительные краши сервера в случае отклонений поведения очереди от нормы, дабы как можно оперативнее найти и исправить проблемы, а не прятать и игнорировать их и потом собирать флэш рояль из багов.
- На сей раз я тестировал алгоритм автоматизированными тестами, и при 1000 игроков в очереди в 10 подземелий со случайными ролями и 20% шансом, что они находятся в группе из 2-4 участников, примерно 950 из них было условно "отправлено в подземелья", но какая будет ситуация на реальном сервере я не могу предсказать. "В полевых условиях" я смог протестить очередь только в 6 окон, больше мой компьютер не выдерживал.
Эта очередь может быть очень чувствительна к оффлайн игрокам. В старой системе мне приходилось делать затычки, чтобы оффлайн игроки игнорировались при переборе комбинаций. Это свидетельствовало о том, что имелись случаи, когда игрок оказывался оффлайн, но при этом не удалялся из очереди. Первопричину этому я тогда искать не стал, и теперь, если баг всё ещё остался, мне придётся её искать, ибо чем чреваты оффлайн игроки в этой очереди я даже боюсь предсказывать.
- Возможно ничего не выйдет и придётся вернуться к старому варианту. Куда же без этого.
- неискренне ваш, ZEUStiger
Закрыть