Предыдущая часть:
Карта состоит из клеток. Содержимое каждой клетки можно описать неким числом. Например,
- 0 – ничего нет (пустота)
- 1 – стена
- 2 – пол
- 3 – лестница вниз
- ...
Далее, можно вписать в клетки монстров. Например 10 – жаба, 11 – гадюка и т.д. Не знаю как сделано в оригинале, ибо не смотрю туда принципиально, но там реально можно сделать содержимое клетки равным какому-нибудь монстру или предмету. Потому что по умолчанию, если монстр или предмет исчезают из этой клетки, в ней остаётся значение "пол".
Планируется, что пол, по которому ходит герой, будет обладать разными свойствами. Это может быть вода, болото, лава и т.д. Поэтому, если в клетке будет записано значение "вода", я могу туда записать монстра. Но когда монстр покинет клетку, я уже не узнаю, что туда записать обратно. Пол? Или воду? Или лаву?
Можно сделать так: монстры имеют право размещаться только на клетке типа "пол", тогда всегда будет известно, на что её менять. Или так: монстр, записанный в клетку, сохраняет у себя её состояние, а когда освобождает клетку, то восстанавливает это состояние. Оба варианта рабочие, но есть другая проблема. Это количество возможных чисел, которые можно записать в клетку.
Допустим, одна клетка занимает в памяти один байт. Тогда какое-то количество чисел потратится на разнообразные элементы местности, и какое-то количество чисел уйдёт на кодирование монстров. Например, если в игре 128 плиток местности, то остаётся 127 чисел для кодирования монстров (на самом деле есть ещё предметы, оружие, еда и т.п.)
И то и другое вроде бы много (в оригинальной игре всего 26 монстров). Но я не хочу рисковать, и поэтому хочу отдать весь байт исключительно на кодирование территории.
К тому же монстры обладают некоторым интеллектом и должны совершать ходы. А это значит, что у сервера должен быть список монстров как объектов. Если они будут записаны в клетки, придётся перебирать все клетки уровня, чтобы найти монстра. Имея же список, мы перебираем список напрямую.
Итак, первое решение:
- клетка территории кодируется одним байтом, количество значений ограничено 256
- монстры хранятся отдельным списком, и количество их типов вообще не ограничено
Размеры карты
Если сделать карту размером 4096 * 4096 клеток, этого было бы более чем достаточно (оригинальная игра происходит всего лишь на одном экране размером 80*25 клеток). Вся карта при этом занимала бы 16 мегабайт, что по современным меркам вполне приемлемо.
Но здесь также возникают две проблемы. Первая и главная – возможность передачи карты с клиента на сервер. Пересылать в каждый ход по 16 мегабайт было бы... неприлично.
Вторая проблема вытекает из первой. Большая часть карты на самом деле не используется:
То есть будет храниться огромное количество пустых клеток. И пересылаться тоже.
В идеале хотелось бы и хранить, и пересылать только используемые клетки. Предположим, сервер хранит все, но должен передавать клиенту только изменённые клетки.
Для этого придётся составить список изменённых клеток, причём они могут находиться в совершенно разных местах.
Вместе с клеткой придётся передавать её координаты. Потребуется по два байта на каждую координату (0..4095) и один байт на саму клетку. Итого 5 байт.
Чтобы немного оптимизировать передачу, вместо отдельных координат (X, Y) можно использовать адрес клетки в массиве карты. Максимальный адрес для размера 4096*4096 это 16777215, и занимает ровно 3 байта. Трёхбайтовых типов данных у нас нет, но вполне можно передавать три отдельных байта и потом их соединять. Итого 4 байта на клетку.
Можно ли передавать меньше?
На помощь приходит коан о дереве, которое падает в лесу, но никто этого не слышит. Изменения могут происходить где угодно, но те, которые нужны клиенту, должны находиться в поле зрения игрока. А это, можно смело сказать, не более чем -128..+127 клеток в любую сторону.
Стало быть, раз сервер знает положение игрока, он может передавать координаты клеток относительно игрока. И тогда каждая координата будет размером 1 байт, а на клетку потребуется три байта.
Если же сократить видимость до -8..+7 клеток (что, покривя душой, можно тоже назвать достаточным), то обе координаты можно упаковать в один байт и тогда потребуется всего два байта на клетку.
Можно ли сделать лучше?
Предположим, кровь из носа понадобилось передать изменённые клетки где-то за пределами поля зрения игрока. Тогда предыдущее решение окажется проблемой. Но можно заметить, что если координаты клетки передаются относительно координат игрока, то можно выбрать любые другие базовые координаты.
Значит, сервер может передавать базовые координаты (три байта) и затем список клеток относительно этих координат. Затем новые базовые координаты, и опять список клеток относительно этих координат. И т.д.
Объём передачи увеличивается на 3 байта на каждую переданную группу клеток (плюс один байт-разделитель групп, или счётчик клеток внутри группы, иначе не сможем отделять группы друг от друга). Жертва, на которую можно пойти, учитывая, что теперь можно реально сделать группу размером 16*16 клеток, передавать сколько угодно таких групп, и расстояние от игрока уже не играет роли.
Можно ли хранить меньше?
Клиенту на локальной машине вполне можно иметь буфер размером 16 мегабайт. На сервере же, учитывая, что к нему будут подключаться сотни (да что уж там, тысячи) клиентов, выделять по 16 мегабайт на каждого клиента уже немного неприлично.
Учитывая, что большая часть пространства 16 мегабайт не используется, сервер мог бы хранить только те куски карты, в которых что-то есть. Так как уже озвучена идея использовать группы 16*16 клеток, карту сервера можно хранить не в виде массива 4096*4096, а в виде массива таких групп.
Группу клеток 16*16 назовём суперклеткой.
Карта размером 4096*4096 клеток делится на 256*256 суперклеток.
Значит, для хранения суперклеток нужен массив размером 65 килобайт (и ещё умножить на размер указателя), в общем полмегабайта. Но это только структура хранения. Сами клетки будут занимать по 256 байт + служебная структура объекта, допустим 16 64 байта. Да, я проверил, и к сожалению у Питона огромный расход памяти на каждый отдельный объект, поэтому данная стратегия может и не окупиться.
Тем не менее, если в карте будет заполнена примерно половина суперклеток, это всё займёт порядка 9-10 мегабайт.
Это всё ещё много, но надо учесть, что и карта по сути получается огромная.
Связный список
Можно вообще отказаться от матрицы и хранить клетки в виде списка. Тогда храниться реально будет только то, что нужно.
Список должен быть связным. То есть, у каждой суперклетки должны быть 8 ссылок на окружающие её соседние суперклетки. Если в каком-то направлении соседних клеток нет, то ссылка будет пустой.
Но по сути не нужен и список. Так как у каждой клетки есть адрес, то адрес становится ключом в словаре. Если мы хотим узнать, если ли у клетки сосед сверху, допустим, то мы просто вычисляем адрес соседа и ищем его в словаре. И либо находим, либо нет.
Поиск в словаре должен иметь практически ту же скорость, что и прямая ссылка.
Sparse vs. Dense
В результате я буду пробовать реализацию с суперклетками в словаре, но сравню её эффективность по памяти с другими вариантами. Это выливается в одно требование к клиенту и серверу – они не должны знать, как хранятся клетки. Для клиента и сервера должна существовать только клетка по координатам (X,Y) и возможность её прочитать и записать. Хранение клетки внутри карты возьмёт на себя отдельный класс, который можно назвать хранилищем клеток. И значит, я смогу написать несколько разных хранилищ и использовать то, которое лучше подходит. В том числе даже использовать своё хранилище для каждого отдельного уровня.
Разве это нужно?
Можно представить, что в зависимости от тематического оформления (пещера, лес, равнина и т.д.) некоторые уровни будут иметь лишь немного использованных клеток, а некоторые – почти все.
Например, подземелье это длинные узкие коридоры и небольшие комнаты, клеток используется немного. Это sparse-структура (то есть прореженная). В то же время какой-нибудь лес или город могут быть сплошным массивом деревьев или домов, и будут использованы практически все клетки карты. Это dense-структура (то есть плотная). Попытка разбить dense-структуру на подструктуры приведёт лишь к дополнительному расходу памяти.
Естественно, на всё это можно наплевать, мы же всего лишь делаем посредственную игрушку. Но эта наша прогулка нужна в первую очередь для того, чтобы от души попроектировать.
Читайте дальше: