ecs, dynvtbl, логические потоки и Фараон

В конце 90-х годов историческая серия градостроев от Sierra была на вершине популярности, получала отличные отзывы и породила немало последователей и подражателей, начиная от Сhildren of Nile и не заканчиваясь в Banished (2014), Pharaoh: A New Era(2023), Nebuchadnezzar (2021), Builders if Egypt(к сожалению закрытая) став фактически дедушкой жанра. Фараон появился в 1999 году после двух лет разработки, вслед за любимой многими Caesar III. Это была первая игра серии, которая перенесла сеттинг из Древнего Рима в Древний же Египет и предложила (хотя на самом деле фактически повторила, реальным шагом по механикам стал Зевс) сложный игровой процесс, не завязанный однаком на микроменеджменте зданий и жителей. Собственно многие и помнят эти игры, благодаря сотням проваленных миссий, когда император в гневе присылал войска или королевство отзывало титул изза долгов. До первой игр от "пароходов" еще целый год, да и жанры и сеттинги достаточно далекие, так что 1999 и 2000 Фараон собирает лавры и сливки с продаж, а Simon Bradbury ^[1], главный технический гений студии и душа проекта, покидает команду и основывает свою Firefly Studios, чтобы подарить нам Stronghold.

В процессе кодоархеологических раскопок бинарника, что Цезаря, что Фараона было найдено немало интересных окаменелостей легаси технических решений, многие из которых я видел в других проектах и не только игровых. Возможно это дремучее легаси (хотя и не такое дремучее как AoE1/2) может показаться топорным, но красота решений определенно есть, и учтите что игры запускались и выдавали неплохие фпс (15-30), работая на разных первых пеньках, 586, атлонах с 32 мб памяти всего, а не только кеша. И работали быстро, красиво и на одном ядре.

Все скриншоты в статье взяты из opensource версии игры.

Возвращаясь к теме статьи, все новомодные (относительно конечно новомодные, первые открытые реализации ECS фреймворков стали популярны где-то после 14 года, а массовый ENTT c 17) использовались в играх и ранее, но были обычно фишками домашних движков или ноу-хау студии. Так и с ECS реализацией в движке цезаря и фараона, как отдельная система или фреймворк она выделена не была, но сами принципы работы уже четко оформились и стали массово копироваться между подсистемами игры, что позволяло вытаскивать те самые 15-20 фпс на самых слабых машинах. Это сейчас на gpu мы можем позволить себе рендерить фрейм с нуля каждый раз, но подобное было очень затратно на API того времени и использовались разные трюки вроде обновления только изменившейся части экрана или разбивки на рабочик зоны с шахматным обновлением. Это я немного поворчать, видя как сейчас UE5.1 пустую сцену открывает 2 минуты в 12 тредов, и съев 6 гигов оперативки.

Древнеегипетский ECS

Как это все относится к современным ECS фреймворкам? Расскажу немного что такое Entity Component System (ECS) идея - сам я сторонник классического SceneGraph ^[2]подхода и считаю, что при должном умении он ничем не уступает по скорости ECS, особенно если озаботиться нормальной разбивкой по потокам.

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

Это пример для разных объектов на карте, для самой карты надо знать тип тайла (вода, земля, деревья, дюны и т.д.), но с таким подходом есть проблемы: первая это негибкое наследования для комбинированных типов и расширение функционала таких объектов, если мы решим создать камни на которых могут располагаться здания, то дерево наследования поломается и придется придумывать обходные решения, или здания которые могут располагаться на берегу - берег это вода, на воде строить нельзя. Но иногда можно.

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

struct Tile {
    // Основные параметры тайла
    int i;                  // Координаты тайла
    int j;                  // Координаты тайла
    int resources;          // Количество ресурсов в тайле
    int state;              // Состояние тайла
    bool isOccupied;        // Занят ли тайл юнитом
  ....

Но при обновлении такого объекта данные рядом с нужными полями тоже попадают в кеш, занимают место и время на выборку и обновление. Это огромное расточительство, которое никак не победить классическими способами.

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

Что придумали гениальные отцы игростроя, хотя тут уже больше подходит - деды - Saimon Bradbury и Mike Gingevich в 1998 году. Игровые сущности, о которых было написано выше размещаются в массивах, индексом является номер тайла на карте. Максимальный размер карты составляет 228х228 и он всегда фиксирован, но визуально карта может быть меньше, тогда часть карты забита условно -1, чтобы понимать что такие данные обрабатывать не надо. Так например выглядят в коде и в игре система обработки желательности, воды и анимаций.

struct grid_xx {
    int initialized;
    e_grid_data_type datatype[2];
    size_t size_field;
    int size_total;

    void* items_xx;
};

void map_grid_init(grid_xx* grid) {
    grid->size_field = gr_sizes[grid->datatype[GAME_ENV]];
    grid->size_total = grid->size_field * GRID_SIZE_TOTAL;
    grid->items_xx = malloc(grid->size_total);
    grid->initialized = 1;
}

Карта и массив данных для желательности земли:

Этот же массив в более репрезентативном виде как это было в игре.

Карта и массив данных для доступности воды.

Он же в удобном для просмотра виде.

Массив анимаций для каждого тайла. В этом случае имеем обратную ситуацию, при рендере текстуры в тайле информация берется из этого массива, и меняя эти значения в массиве можно безопасно и быстро обновлять данные на карте и менять её отображение.

Как реализован алгоритм обновления карты (пример для желательности тайла, нужен чтобы поднять уровень дома):

grid_xx g_desirability_grid = {0, {FS_INT8, FS_INT8}};

void map_grid_add(grid_xx* grid, uint32_t at, uint32_t v) {
    if (at >= GRID_SIZE_TOTAL)
        return;

    ((uint8_t*)grid->items_xx)[at] += v;
}

void desirability_t::update_buildings() {
    int max_id = building_get_highest_id();
    for (int i = 1; i <= max_id; i++) {
        building* b = building_get(i);
        if (b->state != BUILDING_STATE_VALID) {
            continue;
        }
        
        const model_building* model = model_get_building(b->type);
        map_grid_add(&g_desirability_grid, grid_offset, model->desirabilty);
        ...
    }
}

Обновление желательности тайла и обращение к данным превращаются в доступ по индексам в массиве, вместо перебора объектов и их свойств. Еще одним положительным свойством такого решения будет быстрое сохранение и загрузка бинарным блоком, который не требует перебора и обновления объектов.

Ancient DynVMT

Напомню, что движок был написан на чистом C, история его создания берет свое начало в 1991 году c выходом Caesar I. Судя по коментариям в ресурсах и разным константам из бинарника, которые вытащило сообщество, к моменту релиза Фараона движок имел версию 6.4 (в Цезаре было 6.1).

Никаких плюшек в виде виртуальных функций (Virtual Method Table ^[3]) понятное дело не было, но похожий механизм поддерживался разработчиками и был реализован с помощью колбеков. VMT или dynamic dispatching или позднее связывание в контексте языка C++ означает вызов правильной функции, которая может быть определена несколькими способами для родителя и потомка. В общем случае, когда вы определяете метод внутри класса, то компилятор запоминает его пределение (адрес) и выполняет его всякий раз, когда возникает обращение к этому методу.

struct A {
  void foo() { printf("A::foo"); }
}

Здесь компилятор создаст метод A::foo() и запомнит его адрес. На данный момент существует только одна реализация этого метода класса и она является общей для всех экземпляров этого класса и его потомков. Это называет статической диспетчиризацией или ранним связыванием, потому что компилятор всегда знает во время компиляции какой метод конкретно будет вызван во время обращения.

struct B {
  virtual void bar() { printf("B::bar"); }
  virtual void qux() { printf("B::qux"); }
}

struct C : public B {
  virtial void bar() override { printf("C::bar"); }
}

B* b = new C();
b->bar();

В случае появления в классе виртуальных функций компилятор не может знать, какая реализация метода будет правильной во время работы. Если бы мы продолжали использовать статическую диспетчеризацию, то вызов b->bar() пришелся был на B::bar, поскольку с точки зрения компилятора на это указывает текущий тип объекта, хотя он фактически другой.

Учитывая, что виртуальные методы могут быть переопределены в потомках - вычислить правильную реализацию на момент компиляции нельзя (за исключением нескольких явных случаев), поэтому надо найти эту информацию во время выполнения, это и называется динамической диспетчеризацией или поздним связыванием.

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

Разработчики оригинальной игры сделали VMT на минималках, структуру с колбеками, которые устанавливались при инициализации окна (конструктор).

struct window_type {
    e_window_id id;
    void (*draw_background)() = nullptr;
    void (*draw_foreground)() = nullptr;
    void (*handle_input)(const mouse* m, const hotkeys* h) = nullptr;
    void (*get_tooltip)(tooltip_context* c) = nullptr;
    void (*draw_refresh)() = nullptr;
}

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

void window_file_dialog_show(file_type type, file_dialog_type dialog_type) {
    static window_type window = {       <<< VMT
        WINDOW_FILE_DIALOG,             <<< header
        window_draw_underlying_window,  <<< functions
        draw_foreground,
        handle_input
    };

    init(type, dialog_type);     <<< ctor
    window_show(&window);        <<< new window
}

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

Логические потоки из прошлого века

Традиционно в игровой разработке последние лет двадцать для выполнения нескольких задач используется несколько потоков, где каждый выполняет свою работу. Переключением между потоками занимается ОС и берет на себя сохранение контекста и другие "мелочи". Но до середины нулевых большинство игр такой возможности не имели, а потоки использовались в основном для тяжелых вычислений вроде проигрывания звука, загрузки и распаковки текстур, но не для игровой логики.

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

Между тем необходимость в переключении межда задачами никуда не пропадала и приходилось решать её с помощью очереди задач или логических потоков, которые и были реализованы в Фараоне. Суть этого решения в том, что игровой цикл разбивается на шаги, например обновление вероятности пожара, рост деревьев, генерация жителей, влияние колодцев и т.д.

Каждый шаг запускается последовательно друг за другом на каждом фрейме (есть еще вариант с приоритетами), пока не будут выполнены все. Игровой цикл таким образом растягивается на количество таких шагов, при этом гарантируется исполнение каждого шага, а общее время цикла размывается между ними и вместо условных 140мс + время на рендер на один фрейм и 7fps, получаем условные 140мс / 10 = 14мс + время на рендер на один апдейт или нужные 20-30fps. За десять фреймов игра проходит полный игровой цикл, но для игрока такое разбиение не заметно, потому что анимации объектов происходят с прежней скоростью на каждом фрейме, эту часть в логический тред вынести не получится.

Как эта часть была реализована в игре - код уже немного изменен, но не глобально, так что структура должна быть понятна:

void game_t::update_city(int ticks) {
    g_city.buildings.update_tick(game.paused);

    switch (gametime().tick) {
    case 1:
        g_city.religion.update();
        g_city.coverage_update();
        break;
    case 2:
        g_sound.music_update(false);
        break;
    case 3:
        widget_minimap_invalidate();
        break;
    case 4:
        g_city.kingdome.update();
        break;
    case 5:
        formation_update_all(false);
        break;
    case 6:
        map_natives_check_land();
        break;
    ....

GodObject и нехватка памяти

Вообще `god class/object` — это антипаттерн в программировании, который заключается в создании класса или структуры данных, выполняющего слишком много задач. Я еще не видел игрового движка, которому бы удалось избежать появления такого объекта, все стараются максимально уменьшить влияние его на архитектуру, с переменным успехом это удается.

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

Экономия памяти заключается в том, что мы можем разместить наборы данных через union упаковав их без неоходимости раздувать структуры данных. На этом пожайлуй заканчиваются плюсы такого подхода, и дальше начинаются только проблемы, потому что `god object` на то и god, что реально начинает делать все, а по ночам еще и немножечко кораптит память.

Как например реализован житель города (пример того как делать не надо), но у кодоархелоогии порою свои правила и чтобы не сломать игру совсем, приходится мириться с временными неудобствами (https://github.com/dalerank/Akhenaten/blob/master/src/figure/figure.h ^[4]):

class figure {
public:
    e_resource resource_id;
    uint16_t resource_amount_full; // full load counter

    uint16_t home_building_id;
    uint16_t immigrant_home_building_id;
    uint16_t destination_building_id;

    uint16_t id;
    uint16_t sprite_image_id;
    uint16_t cart_image_id;
    animation_context anim;
    ....

    bool use_cross_country;
    bool is_friendly;
    uint8_t state;
    uint8_t faction_id; // 1 = city, 0 = enemy
    uint8_t action_state_before_attack;
    uint8_t direction;

    ...

      union {
        struct {... } herbalist;
        struct {... } taxman;
        struct {... } flotsam;
        struct {... } fishpoint;
        ....
    } local_data;

Вечные пирамиды

С пирамидами пока все плохо, все никак не получается выделить время разобраться с тем месивом асма, что представляет из себя логика их постройки. Но с чем то попроще прогресс уже есть, мастабы движок строить уже умеет ^[5].

Благодарю что дочитали до конца! Надеюсь было интересно. Если вас заинтересовал проект, приходите в правильный telegram канал github repo ^[6], будем вместо строить пирамиды.