Реализация KnownList

[Alay]

Вопрос к думающим людям.
В процессе разработки эмулятора на C# подошел к тому, что пора реализовать KnownList - списки всех объектов, находящихся в определенном радиусе от персонажа\моба.
Пока что решил реализовать его следующим образом.

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

        private void Player_EnterWorld(Player player)
        {
            var ownerPosition = Owner.CurrentPosition;
            if (player.ObjectId == Owner.ObjectId)//Логика действий, если текущий персонаж входит в мир
            {
                var ownerPlayer = Owner as Player;
                OnlinePlayers.Locker.EnterReadLock();
                foreach (var playerInGame in OnlinePlayers.GetAllOnlinePlayers)
                {
                    if (!ownerPosition.CheckIfInRange(KnownListConfigs.PlayersKnownListRange, playerInGame) || playerInGame.ObjectId == ownerPlayer?.ObjectId) continue;
                    AddPlayerWithLock(playerInGame);
                    playerInGame.KnownContaineer.AddPlayerWithLock(ownerPlayer);//Добавляем текущего игрока в кновн лист игрока из списка
                }
                OnlinePlayers.Locker.ExitReadLock();
            }
            else//Логика действий, если другие персонажи входят в мир, но не данный объект.
            {
                if (!ownerPosition.CheckIfInRange(KnownListConfigs.PlayersKnownListRange, player)) return;
                AddPlayerWithLock(player);//Для других
            }
        }

То что чекать весь онлайн - это х*евая затея это я и так понимаю, но об этом позже.

И так теперь нужно подумать, ведь персонаж передвигается и соответственно kownlist должен постоянно изменятся.
По этому реализовал следующий статический метод.

        public static void RecalcKnownPlayersList(Player ownerPlayer)
        {
            var ownerPosition = ownerPlayer.CurrentPosition;
            var ownerKnownListLocker = ownerPlayer.KnownContaineer.KnownPlayerLocker;
            var deletedPlayersIdList = new List<int>();
            ownerKnownListLocker.EnterReadLock();
            foreach (var knownPlayer in ownerPlayer.KnownContaineer.KnownPlayers.Values)
            {
                if (ownerPosition.CheckIfInRange(KnownListConfigs.PlayersKnownListRange, knownPlayer)) continue;
                deletedPlayersIdList.Add(knownPlayer.ObjectId);
                knownPlayer.KnownContaineer.RemovePlayerWithLock(ownerPlayer.ObjectId);
            }
            ownerKnownListLocker.ExitReadLock();
            var addedPlayersList = new List<Player>();
            OnlinePlayers.Locker.EnterReadLock();
            foreach (var playerInGame in OnlinePlayers.GetAllOnlinePlayers)
            {
                if (!ownerPosition.CheckIfInRange(KnownListConfigs.PlayersKnownListRange, playerInGame) || playerInGame.ObjectId == ownerPlayer.ObjectId) continue;
                addedPlayersList.Add(playerInGame);
                playerInGame.KnownContaineer.AddPlayerWithLock(ownerPlayer);//Добавляем текущего игрока в кновн лист игрока из списка
            }
            OnlinePlayers.Locker.ExitReadLock();
            ownerKnownListLocker.EnterWriteLock();
            foreach (var addedPlayer in addedPlayersList)
                ownerPlayer.KnownContaineer.AddPlayerWithoutLock(addedPlayer);
            foreach (var deletedPlayerId in deletedPlayersIdList)
                ownerPlayer.KnownContaineer.RemovePlayerWithoutLock(deletedPlayerId);
            ownerKnownListLocker.ExitWriteLock();
        }

данный метод опять же чекает список онлайна и удаляет\добавляет персонажей если нужно всем сразу так сказать.
На реализацию удаления из листа овнера далеких игроков не обращать внимания, позже сделаю покрасивее через итератор.

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


А вот собственно вопрос. Когда запускать пересчет данного листа?.
приатачил его к приходу пакета MoveToLock. но фиг его знает.
PS. На сервере который я разрабатываю инстанс зон не будет.
PSS. По поводу локеров. Используется ReadWriteLockSlim - самый быстрый из доступных локеров в .net

И вот собственно методы добавления удаления

        private void AddPlayerWithLock(Player player)
        {
            KnownPlayerLocker.EnterWriteLock();
            if (IsPlayerExists(player.ObjectId))
            {
                KnownPlayerLocker.ExitWriteLock();
                return;
            }
            KnownPlayers.Add(player.ObjectId, player);
            KnownPlayerLocker.ExitWriteLock();
            if (Owner.ObjType != GameObject.ObjectType.Player) return;
            var ownerPlayer = Owner as Player;
            ownerPlayer?.SendPacket(new PlayerInfoPacket(ownerPlayer.GameClientConnection, player));
        }
        private void AddPlayerWithoutLock(Player player)
        {
            if (IsPlayerExists(player.ObjectId)) return;
            KnownPlayers.Add(player.ObjectId, player);
            if (Owner.ObjType != GameObject.ObjectType.Player) return;
            var ownerPlayer = Owner as Player;
            ownerPlayer?.SendPacket(new PlayerInfoPacket(ownerPlayer.GameClientConnection, player));
        }
        private void RemovePlayerWithLock(int playerObjectId)
        {
            KnownPlayerLocker.EnterWriteLock();
            if (!IsPlayerExists(playerObjectId))
            {
                KnownPlayerLocker.ExitWriteLock();
                return;
            }
            KnownPlayers.Remove(playerObjectId);
            KnownPlayerLocker.ExitWriteLock();
            if (Owner.ObjType != GameObject.ObjectType.Player) return;
            var ownerPlayer = Owner as Player;
            ownerPlayer?.SendPacket(new DeleteObjectPacket(ownerPlayer.GameClientConnection, playerObjectId));
        }
        private void RemovePlayerWithoutLock(int playerObjectId)
        {
            if (!IsPlayerExists(playerObjectId)) return;
            KnownPlayers.Remove(playerObjectId);
            if (Owner.ObjType != GameObject.ObjectType.Player) return;
            var ownerPlayer = Owner as Player;
            ownerPlayer?.SendPacket(new DeleteObjectPacket(ownerPlayer.GameClientConnection, playerObjectId));
        }

- Сразу уведомляют клиента об изменении.

[gmred123]

1. При входе в игру добавляешь объект в регион (учитывая возможно инстанс зоны если такие будут)
2. Отправляешь игроку информацию об объектах его региона и соседних 8 (если по примеру, то взгляни на num клаву, регион игрока это цифра 5, цифры 1,2,3,4,6,7,8,9 - соседние регионы) опять учитывая инстансы, а так же отправляешь информацию плеерам этих регионов инфу о игроке.

3. при смене региона игроком, изменяются соседние регионы, к примеру на нашей nym клавиатуре игрок пошел прямо и попал с региона №5 в регион №8 инфу нужно удалить инфу об объектах с регионов 1,2,3 и послать информацию об обектах новых соседних регионов Num Lock, /, * ...тут же не забываем обновлять информацию про нашего игрока у игроков регионов с которых он выбежал и куда забежал.

Не знаю понятно ли я объяснил, надеюсь да.

[Alay]

Сообщение от gmred123

1. При входе в игру добавляешь объект в регион (учитывая возможно инстанс зоны если такие будут)
2. Отправляешь игроку информацию об объектах его региона и соседних 8 (если по примеру, то взгляни на num клаву, регион игрока это цифра 5, цифры 1,2,3,4,6,7,8,9 - соседние регионы) опять учитывая инстансы, а так же отправляешь информацию плеерам этих регионов инфу о игроке.

3. при смене региона игроком, изменяются соседние регионы, к примеру на нашей nym клавиатуре игрок пошел прямо и попал с региона №5 в регион №8 инфу нужно удалить инфу об объектах с регионов 1,2,3 и послать информацию об обектах новых соседних регионов Num Lock, /, * ...тут же не забываем обновлять информацию про нашего игрока у игроков регионов с которых он выбежал и куда забежал.

Не знаю понятно ли я объяснил, надеюсь да.

Вы хотя бы прочитали то что я написал для начала

[n3k0nation]

А нафига Вам реализация кноулистов? Они не требуются в lineage2 и их нет в ретейле, плюс лишняя нагрузка на проц и память. Если нужно, то могу потом объяснить чем черевато использование кноулистов.

:

Свернуть ↑
Вообще, кноулисты нужно обновлять при:

• Передвижении персонажа на N точек
• Телепортации персонажа

Свернуть ↑Развернуть ↓

[pchayka]

Давно уже никто их не использует - пережитки быдлокодинга

[Alay]

Сообщение от n3k0nation

А нафига Вам реализация кноулистов? Они не требуются в lineage2 и их нет в ретейле, плюс лишняя нагрузка на проц и память. Если нужно, то могу потом объяснить чем черевато использование кноулистов.

:

Свернуть ↑
Вообще, кноулисты нужно обновлять при:

• Передвижении персонажа на N точек
• Телепортации персонажа

Свернуть ↑Развернуть ↓

на счет того были они в ретейле я не знал. Дело в том что хотел упростить боардкаст и прочие вытикающие. И чтобы аи мобов работали только из кноун листов. Тобишь чтобы просто так не гонять тики если рядом нет ни единого персонажа. На мой взгляд очень удобная штука при разработке. Дабы не разбегались глаза где че фиксить, а все было так сказать в одном месте.... Не знаю понятно ли я выразился.
Кноунлист - четкое представление того что видит клиент.
Допусим послал клиент Action c objectId - и дабы быстро понять что хотел клиент можно было пробежаться по его кноунлисту. И если в его кноун листе такого нет - значит наш игрок балуется с пакетами. и все в таком духе.
А по поводу нагрузки... при тесте из 1000 мобов в локации и 20 персонажей. (мобы добавляются в другй кноун лист) при пересчете кноун листа и отсылке изменений всем этим 20ти окнам серверу нужно в среднем 294622 наносекунд. Примерно 0,00029 сек. чтобы просчитать все ближайшие регеоны, подготовить, зашифровать и отправить все эти 20 пакетов. (при Release сборке с оптимизацией). Честно говоря я вообще не ожидал что скорость будет настолько высокая.
А пересчет для кноунлиста с 1000 мобами вообще занимает 0,000138 секунд.... Лирическое отступление - похоже я близок к тому чтобы убрать фризы при осадах (нет)
А если выпилить из клиента стандартную шифрацию\дешифрацию то эти дела будут работать еще быстрее чуть ли не в разы, ибо процесс дешифрации пакетов на сервере занимает чуть ли не половину всего времени жизни потока пришедшего пакета.

Пока реализовывал WorldRegion назрел следующий вопрос про боардкасты.
Дело в том, что я использую асинхронный сервер, и возможна следующая ситуация- при обновлении knownList допустим при телепортации в другую локацию где много объектов, сервер может просто зафлудить нахрен клиент. В java пакеты идут с минимально возможной задержкой (10мс - слип селектора очереди отправления пакетов(если они не "склеены" в одну посылку)) А при асинхроннике за эти 10 мс клиенту может придти огромное число пакетов, так не сойдет ли он с ума? я просто не знаю как в клиенте устроен процесс чтения пакетов. или же лучше исскуственно делать задержку на отправку.

Добавлено через 2 минуты

Сообщение от pchayka

Давно уже никто их не использует - пережитки быдлокодинга

Честно говоря даже не знаю, возможно вы и правы

Добавлено через 3 минуты

Сообщение от n3k0nation

Если нужно, то могу потом объяснить чем черевато использование кноулистов.

Хотелось бы почитать

Добавлено через 12 минут
Хотя я возможно и сам понимаю чем это черевато. - Блокировки. При большом кол-ве уникальных кноунлистов получается лишний расход цп на их обсчет и получение и ожидания блокировок. Но с другой стороны это дает серверу четкое понимание о "картине" клиента и упрощает разработку. Но на сколько я понял вы имеете ввиду, сейчас все java кодеры отказались от кноунлистов и шлют боардкасты из WorldRegion с учетом координат обьектов?

[Alay]

Сообщение от gmred123

1. При входе в игру добавляешь объект в регион (учитывая возможно инстанс зоны если такие будут)
2. Отправляешь игроку информацию об объектах его региона и соседних 8 (если по примеру, то взгляни на num клаву, регион игрока это цифра 5, цифры 1,2,3,4,6,7,8,9 - соседние регионы) опять учитывая инстансы, а так же отправляешь информацию плеерам этих регионов инфу о игроке.

3. при смене региона игроком, изменяются соседние регионы, к примеру на нашей nym клавиатуре игрок пошел прямо и попал с региона №5 в регион №8 инфу нужно удалить инфу об объектах с регионов 1,2,3 и послать информацию об обектах новых соседних регионов Num Lock, /, * ...тут же не забываем обновлять информацию про нашего игрока у игроков регионов с которых он выбежал и куда забежал.

Не знаю понятно ли я объяснил, надеюсь да.

К тому же, зачем просчитывать все 8 соседних регионов, когда можно высчитать у какого ребра региона находится текущий объект и радиус его видимости и считать смежный регион к данному ребру, а если радиус видимости вообще не пересекает ребра то расчеты можно проводить только в текущем регионе

[n3k0nation]

Сообщение от Alay

Хотелось бы почитать

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

Сообщение от Alay

я просто не знаю как в клиенте устроен процесс чтения пакетов. или же лучше исскуственно делать задержку на отправку.

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

Сообщение от Alay

на счет того были они в ретейле я не знал. Дело в том что хотел упростить боардкаст и прочие вытикающие. И чтобы аи мобов работали только из кноун листов. Тобишь чтобы просто так не гонять тики если рядом нет ни единого персонажа. На мой взгляд очень удобная штука при разработке.

Кноулистов никогда не было на ретейле. Там всегда была региональная сетка. Регионы так же, могут иметь состояние: активное (если в регионе есть игрок), неактивное (в регионе нет игроков).
У меня, к примеру, АИ тикает по регионам, каждый регион тикает отдельно, если статус региона неактивный, то тики пропускаются.

Добавлено через 5 минут

Сообщение от Alay

К тому же, зачем просчитывать все 8 соседних регионов, когда можно высчитать у какого ребра региона находится текущий объект и радиус его видимости и считать смежный регион к данному ребру, а если радиус видимости вообще не пересекает ребра то расчеты можно проводить только в текущем регионе

Радиус видимости настраивается в клиенте и не отсылается на сервер. Во всяком случае на тех версиях клиента, с которыми я работал.

[Alay]

Сообщение от n3k0nation

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

Какой размер у данного буффера - хотя бы примерно чтобы понимать. или буффер зависит не от клиента а от ОС?
Тогда получается что пакеты можно "склеивать" и посылать несколько пакетов за раз, а по идее разделять их будет первые 2байта размера, и клиент их нормально спарсит?

[n3k0nation]

Alay, размер буфера не помню. А пакеты и нужно посылать кучей, пока буфер на сервере не заполнится, либо очередь на отправку не опустеет, а не по одной штуке