Предыдущая часть:
В предыдущей части было предложено несколько вариантов хранения карты. Я возьму в реализацию самый замороченный – чтобы заморочиться, естественно. На больших и слабо заполненных картах он будет давать преимущество по памяти, а на маленьких... на маленьких всё равно.
Плитка
Главный и единственный компонент карты это плитка. Это ячейка памяти, в которой хранится значение того, чем она является. Ноль будет означать, что такой плитки просто нет. Если её нет, то где тогда хранится ноль? На самом деле она физически может быть (к этому ещё вернёмся), но для сервера и клиента ноль будет означать, что в этом месте нет вообще ничего, пусто.
Остальные числа будут кодировать пол, стены, ступеньки, воду, камни и т.д.
Я зафиксировал пространство размером 4096 на 4096 плиток. Первоначально хотел делать настраиваемые размеры, но потом решил, что это нахрен не надо. Весь код, связанный с картой, занимает 45 строк, и их можно полностью переписать в любой момент. Это сразу привело к некоторым упрощениям.
Суперклетка
Карта размером 4096*4096 разбита на 256*256 суперклеток. Каждая суперклетка содержит 16*16 плиток.
Для плитки в программе нет класса, потому это просто число и больше ничего. Для суперклетки написан класс, который хранит плитки и обеспечивает доступ к ним:
Он называется SuperCell16, потому что не поддерживает другие размеры клеток, кроме 16*16. Поэтому, если будет нужен другой размер, я сделаю другой класс с фиксированным размером клетки (например, SuperCell32), или какой-нибудь универсальный класс.
Для хранения плиток суперклетка создаёт байтовый массив длиной 256 элементов bytearray(256), что довольно хорошая фишка в Питоне – данные хранятся в приближенном к сырому виде.
Массив длиной 256 элементов это на самом деле матрица из 16 строк по 16 элементов, записанных подряд. Для адресации клеток внутри массива мы используем преобразование координат (x, y) в адрес:
addr = (y << 4) + x
Координата y это номер строки в матрице. Так как каждая строка содержит 16 клеток, нужно отсчитать от начала y * 16 клеток. Сдвиг числа влево 4 раза это умножение на 16. Ну а координата x это смещение внутри строки, которое мы прибавляем к адресу.
Суперклетка имеет методы чтения и записи плитки по координатам (x, y), но также по адресу. Разница в том, что адрес уже готов и его не надо вычислять. Так как в дальнейшем будет много операций с плитками, то однажды полученный адрес можно будет переиспользовать, не вычисляя его повторно.
Плиткохранилище
Хранилище это класс верхнего уровня, который скрывает своё устройство. Мы можем иметь несколько плиткохранилищ с разной внутренней реализацией, и использовать то, которое нужно на стороне клиента или сервера.
От плиткохранилища требуются два интерфейсных метода: читать и записывать содержимое плитки.
Это get_tile() и set_tile(). Здесь уже используются мировые координаты (x, y), которые меняются от 0 до 4095.
Реализация плиткохранилища такова, что мировые координаты 0..4095 оно преобразует в адрес суперклетки и локальные координаты 0..15 внутри суперклетки.
Суперклетки хранятся в словаре map, где ключом является адрес суперклетки, а значением сама суперклетка.
Первоначально словарь пустой. Хранилище ничего не хранит.
Есть определённое правило: если идёт запрос на чтение плитки, то сначала с помощью метода get_supercell() хранилище ищет суперклетку в словаре. Если суперклетка по соответствующему адресу не существует, то возвращается значение 0 – плитки не существует. И это действительно так. Не нужно ничего хранить для этого.
Если же идёт запрос на запись, то хранилище аналогичным образом ищет суперклетку, и если её нет, то создаёт её с помощью метода add_supercell() и записывает в словарь. Таким образом, для записи одной плитки нужно создать целую суперклетку, и это как раз тот случай, когда вместе с суперклеткой создадутся плитки, которых на карте нет, но память они занимают. В них будет храниться значение 0.
Чтобы получить адрес суперклетки, координата y делится нацело на 16 и умножается на 256 (длина строки матрицы суперклеток). Это достигается двумя сдвигами
(y >> 4) << 8
И далее прибавляется координата x, также делённая нацело на 16:
+ (x >> 4)
Например, для всех x и y от 0 до 15 мы получим адрес суперклетки 0, потому что именно там они и находятся.
Далее, чтобы получить плитку уже в координатах суперклетки, мы используем остаток от деления на 16:
x & 15
y & 15
Битовое "и" с числом 15 (1111) очищает все биты, кроме младших 4-х, что и является остатком от деления на 16.
GameState
Теперь добавлю в GameState хранилище плиток, и можно будет начать строить какие-то настоящие карты. Старую карту (map) я пока оставил, чтобы клиент и сервер не сломались, но скоро она будет удалена совсем.
Хранилище плиток передаётся в конструктор, чтобы при создании GameState мы могли выбрать нужное нам хранилище.
Ну и чуть допилим код сервера, только ради иллюстрации:
Сервер создаёт GameState с хранилищем TileStorage (других всё равно нет), и в качестве теста устанавливает плитку с координатами (1, 1) в значение 1:
game_state.tiles.set_tile(1, 1, 1)
Как мы уже в курсе, при этом должна создаться суперклетка с адресом 0, а внутри неё должна быть записана плитка с координатами (1, 1) (адрес 17).
Git не публикую, так как в игре пока не появилось никаких новых активностей, а над кое-чем ещё надо подумать.
Читайте дальше: