Я решил сделать игру на языке Rust, но только при условии, что сначала разберусь со всеми проблемами. Какая конкретно это будет игра, пока не важно, так как проблемы общего плана.
В предыдущей части удалось разобрать несколько вопросов:
Там в подробностях описаны концепции и структуры данных, а тут я вкратце напомню, что игровый объект типа GameObject имеет у себя индекс элемента массива, в котором хранятся объекты типа StageObject, отвечающие за отображение на экране.
Массив объектов stage_objects должен отвечать определённым требованиям.
- Все объекты отображаются на экране в том порядке, в котором они идут в массиве.
- Порядок отрисовки важен, поэтому при добавлении или удалении объектов порядок оставшихся объектов не должен меняться.
- При добавлении или удалении объектов нельзя никуда перемещать остальные объекты, потому что их индексы изменятся, а индексы являются уникальными идентификаторами объектов всё время их жизни.
Я буду делать компонент STOList (StageObjectList), который обеспечит все эти требования.
Размещение в памяти
Очевидно, что список должен быть динамический, так как объекты будут добавляться и удаляться.
Но также очевидно, что игра не может иметь больше объектов, чем в неё заложено. Например, в игре Apple было всего два объекта. В игре типа Space Invaders может быть порядка 100 объектов, но никак не 1000.
Мы всегда знаем этот предел при проектировании игры.
А раз мы знаем этот предел, то допускаем, что в какой-то момент в игре появится, например, 1000 объектов одновременно. Значит, если список будет динамический, в этот момент он вырастет до 1000 элементов. Значит, в этот момент ему нужно будет вот столько памяти. А потом не нужно.
Но давайте подумаем: если уж нам потребовалось столько памяти в какой-то момент, то зачем от неё отказываться, пока игра работает? Можно сразу выделить максимально необходимый объём памяти и не париться с дальнейшими динамическими изменениями. Тем более что этот объём в простых играх всё равно несущественный, порядка нескольких килобайт.
Значит, для экранных объектов можно просто сделать фиксированный массив из 128 элементов, к примеру. А актуальную длину этого массива отслеживать чисто по счётчику активных объектов.
В Rust нельзя создать массив фиксированной длины, не заполнив при этом сразу все его элементы.
Конечно, можно просто заполнить массив какими-нибудь условно-пустыми объектами, но есть и другое решение:
Vec
Это вектор, который может динамически менять свою длину. Но постойте, ведь нам это не нужно, ведь при динамическом изменении длины будет динамически перевыделяться память?
Да, но можно создать вектор с заранее указанным размером. Тогда, если мы не превысим этот размер (а мы его не превысим), память перевыделяться не будет.
При этом размер вектора не то же самое, что его длина. При размере 128 вектор может иметь длину 0, то есть содержать 0 элементов. Поэтому его не надо сразу заполнять.
Что касается внутреннего представления вектора, это обычный массив. Так что никакого особенного усложнения там нет. Вектор сам обрабатывает добавление и удаление элементов, при этом перемещая элементы массива, чтобы закрывать пустые места.
Но перемещение элементов нам как раз не нужно, потому что оно изменит индексы элементов.
Проверим:
Тут мы создали вектор с типом TestObject, и с заранее указанным размером 128. Далее добавили в него три объекта TestObject, у которых различается аргумент x. Далее удалили элемент с индексом 0. Остальные элементы стянутся влево, чтобы закрыть разрыв. Таким образом, элемент с индексом 1 переместится на индекс 0, и если мы распечатаем значение x по индексу 0, то получим 1.
Такой расклад нарушает идентичность элементов, поэтому из вектора мы удалять ничего не будем никогда. И правда, зачем, если всё равно там не может быть одновременно больше объектов, чем определено нами?
Тогда нужно сделать удаление самостоятельно, при этом не нарушая порядка элементов и не двигая их.
Для этой цели подойдёт двунаправленный связный список.
Каждый элемент вектора, помимо полезной нагрузки, будет иметь два атрибута: prev (индекс предыдущего элемента) и next (индекс следующего элемента). Все элементы в списке будут связаны друг с другом через prev и next.
При удалении элемента мы просто исключаем его из цепочки, связывая элемент до удаляемого с элементом после удаляемого. Порядок не нарушается, и элементы не двигаются.
Но при вставке новых элементов в список мы не можем постоянно добавлять их в конец списка, так как упрёмся в максимальный размер вектора.
Поэтому надо переиспользовать удалённые элементы, ведь они свободны и просто занимают место в векторе. Но они разбросаны в разных местах вектора, поэтому надо вести их учёт.
Нужно сделать ещё один вектор, в котором хранить индексы свободных элементов как в стеке. Для этого вектор отлично подходит, так как имеет методы push() и pop(). Помещая индекс свободного элемента на верхушку стека, мы затем при необходимости забираем его.
Тогда общий план при добавлении элемента такой:
- Если в списке свободных есть элементы, взять индекс свободного оттуда. Если нет, то создать новый индекс, равный текущей длине списка занятых.
- Если это новый индекс, то добавить элемент через push() в конец списка занятых. Если уже использованный, то перезаписать данные по индексу.
- Перенастроить цепочку: в последнем элементе списка обновляем next, чтобы он показывал на свежедобавленный индекс, а свежедобавленный индекс помечаем как последний элемент (сохраняем в переменной last).
Вот структура STOEntry для хранения в списке:
Она имеет полезную нагрузку sto и атрибуты prev и next.
Далее структура списка STOList:
Она содержит вектор used_list для хранения объектов STOEntry, вектор free_list для хранения свободных индексов, и атрибуты capacity (вместимость), cnt (счётчик объектов), first (индекс первого элемента списка) и last (индекс последнего элемента списка).
Реализуем метод-конструктор create(), куда передаётся аргумент capacity, задающий максимальный размер списка:
Конструировать будем так:
let mut sto_list = STOList::create(128);
Теперь нужен метод для добавления элемента по вышеутверждённому плану:
Метод возвращает индекс добавленного элемента, который является его уникальным идентификатором в течение всей его жизни. Этот индекс будет сохраняться в GameObject. Стоит обратить внимание на корявую конструкцию
if let Some(val) = self.free_list.pop()
Дело в том, что метод free_list.pop() может дать ошибку, если в free_list нет элементов. А Rust очень безопасный язык.
Поэтому pop() возвращает не обычный результат, а Option, это спецтип, который может содержать либо Some(value), либо None в случае ошибки, и мы должны это обработать.
Обработать можно через unwrap() или через match, я это всё уже описывал в статье про игру Apple. А вышеуказанная корявая конструкция это тоже один из способов обработки, когда мы точно знаем, что None нам обрабатывать не надо.
Короче говоря, мы получаем от pop() значение Some(val) и используем val. А условие if требуется, чтобы данная конструкция срабатывала только в случае, когда мы получили Some(val). В других случаях мы просто ничего не делаем.
Если уж на то пошло, то и возвращать индекс надо в виде Option, так как добавление может быть неудачным. Пока что замнём этот вопрос.
Далее делаем метод для удаления объекта:
Удаляем по индексу, так как индекс это уникальный неизменяемый идентификатор, помните?
Удаляемый элемент может оказаться первым или последним. Тогда, если он первый, надо сделать первым следующий за ним элемент, а если последний, то надо сделать последним предыдущий.
Удалённый индекс конечно не забываем поместить в список удалённых.
В обоих методах я опустил проверки валидности индекса и переполнения списка и изменение счётчиков и прочее второстепенное. В боевом коде всё будет.
Теперь можно сделать компонент Stage со списком объектов:
Ничем особенным он пока не обладает, и я добавил атрибуты w и h, чтобы они как бы обозначали размеры сцены (которые кстати могут отличаться от размеров экрана).
Реализую методы добавления и удаления объекта:
Они также ничем не выделяются, а просто служат для доступа к методам внутреннего списка.
И метод отрисовки всех объектов в списке:
Здесь проходим по связному списку, начиная с индекса first и далее переходя на next у каждого элемента, пока не достигнем индекса last.
Сделаем проверку, создав Stage, добавив туда объекты и отрисовав их:
Получаем результат:
drawing Bitmap 5
drawing Rect 10x10
Оба добавленных объекта отрисовались.
Удалим первый объект и снова отрисуем сцену:
stage.remove_child(0);
stage.draw(&mut renderer);
И в результате рисуется только второй объект:
drawing Rect 10x10
В общем, всё более-менее получилось. Дальше буду разрабатывать уже непосредственно игру.
Здесь я выложил весь написанный до сих пор код в виде простой программы, которую можно скомпилировать без всяких зависимостей:
Читайте дальше:
