Meta Crush Saga: игра, выполняемая во время компиляции

В процессе движения к долгожданному титулу Lead Senior C++ Over-Engineer, в прошлом году я решил переписать игру, которую разрабатываю в рабочее время (Candy Crush Saga), с помощью квинтэссенции современного C++ (C++17). И так родилась Meta Crush Saga: игра, которая выполняется на этапе компиляции. Меня очень сильно вдохновила игра Nibbler Мэтта Бирнера, в которой для воссоздания знаменитой «Змейки» с Nokia 3310 использовалось чистое метапрограммирование на шаблонах.

«Что ещё за игра, выполняемая на этапе компиляции?», «Как это выглядит?», «Какой функционал C++17 ты использовал в этом проекте?», «Чему ты научился?» — подобные вопросы могут прийти к вам в голову. Чтобы ответить на них, вам придётся или прочитать весь пост, или смириться со своей внутренней ленью и посмотреть видеоверсию поста — мой доклад с Meetup event в Стокгольме:

Примечание: ради вашего психического здоровья и из-за того, что errare humanum est, в этой статье приведены некоторые альтернативные факты.

Игра, которая выполняется на этапе компиляции?

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

Жизненный цикл обычной игры:

Как обычный разработчик игр с обычной жизнью, работающий на обычной работе с обычным уровнем психического здоровья, вы обычно начинаете с написания игровой логики на любимом языке (на C++, конечно же!), а затем запускаете компилятор для преобразования этой, слишком часто похожей на спагетти, логики в исполняемый файл. После двойного щелчка на исполняемом файле (или запуске из консоли) операционной системой порождается процесс. Этот процесс будет выполнять игровую логику, которая в 99,42% времени состоит из цикла игры. Цикл игры обновляет состояние игры в соответствии с некими правилами и вводом пользователя, рендерит новое вычисленное состояние игры в пиксели, снова, и снова, и снова.

Жизненный цикл игры, выполняемой в процессе компиляции:

Как переинженер (over-engineer), создающий свою новую крутую игру процесса компиляции, вы по-прежнему используете свой любимый язык (по-прежнему C++, разумеется!) для написания игровой логики. Затем по-прежнему идёт фаза компиляции, но тут происходит поворот сюжета: вы выполняете свою игровую логику на этапе компиляции. Можно назвать это «выполняцией» (compilutation). И здесь C++ оказывается очень полезен; у него есть такие функции, как Template Meta Programming (TMP) и constexpr, позволяющие выполнять вычисления в фазе компиляции. Позже мы рассмотрим функционал, который можно для этого использовать. Поскольку на этом этапе мы выполняем логику игры, то нам в этот момент нужно также вставить ввод игрока. Очевидно, наш компилятор по-прежнему будет создавать на выходе исполняемый файл. Для чего его можно использовать? Исполняемый файл больше не будет содержать цикл игры, но у него есть очень простая миссия: вывод нового вычисленного состояния. Давайте назовём этот исполняемый файл рендерером, а выводимые им данные — рендерингом. В нашем рендеринге не будут содержаться ни красивые эффекты частиц, ни тени ambient occlusion, он будет представлять из себя ASCII. Рендеринг в ASCII нового вычисленного состояния — это удобное свойство, которое можно легко продемонстрировать игроку, но кроме того, мы копируем его в текстовый файл. Почему текстовый файл? Очевидно потому, что его можно каким-то образом комбинировать с кодом и повторно выполнить все предыдущие шаги, получив таким образом цикл.

Как вы уже можете понять, выполняемая в процессе компиляции игра состоит из цикла игры, в котором каждый кадр игры — это этап компиляции. Каждый этап компиляции вычисляет новое состояние игры, которое можно показать игроку и вставить в следующий кадр / этап компиляции.

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

Прежде чем мы перейдём к подробностям реализации такого цикла, я уверен, что вы хотите задать мне единственный вопрос…

«Зачем вообще этим заниматься?»

Вы действительно думаете, что разрушите мою идиллию метапрограммирования на C++ таким фундаментальным вопросом? Да ни за что в жизни!

• Первое и самое главное — выполняемая на этапе компилирования игра будет иметь потрясающую скорость времени выполнения, потому что основная часть вычислений выполняется в фазе компиляции. Скорость времени выполнения — ключ к успеху нашей AAA-игры с ASCII-графикой!
• Вы снижаете вероятность того, что в вашем репозитории появится какое-то ракообразное и попросит переписать игру на Rust. Его хорошо подготовленная речь развалится, как только вы объясните ему, что недействительный указатель не может существовать во время компиляции. Самоуверенные программисты на Haskell даже могут подтвердить безопасность типов в вашем коде.
• Вы завоюете уважение хипстерского королевства Javascript, в котором может править любой переусложнённый фреймворк с сильным NIH-синдромом, при условии, если ему придумали крутое название.
• Один мой друг поговаривал, что любую строку кода программы на Perl де-факто можно использовать как очень сильный пароль. Я уверен, что он ни разу не пробовал генерировать пароли из C++ времени компиляции.

Ну как? Довольны вы моими ответами? Тогда возможно ваш вопрос должен звучать так: «Как тебе это вообще это удаётся?».

На самом деле я очень хотел поэкспериментировать с функционалом, добавленным в C++17. Довольно многие возможности предназначены в нём для повышения эффективности языка, а также для метапрограммирования (в основном constexpr). Я подумал, что вместо написания небольших примеров кода гораздо интереснее будет превратить всё это в игру. Пет-проекты — отличный способ для изучения концепций, которые не так часто приходится использовать в работе. Возможность выполнения базовой логики игры во время компиляции снова доказывает, что шаблоны и constepxr являются Тьюринг-полными подмножествами языка C++.

Meta Crush Saga: обзор игры

Игра жанра Match-3:

Meta Crush Saga — это игра в соединение плиток, похожая на Bejeweled и Candy Crush Saga. Ядро правил игры заключается в соединении трёх плиток с одинаковым рисунком для получения очков. Вот беглый взгляд на состояние игры, которое я «сдампил» (дамп в ASCII получить чертовски просто):

R"(
    Meta crush saga      
------------------------  
|                        | 
| R  B  G  B  B  Y  G  R | 
|                        | 
|                        | 
| Y  Y  G  R  B  G  B  R | 
|                        | 
|                        | 
| R  B  Y  R  G  R  Y  G | 
|                        | 
|                        | 
| R  Y  B  Y (R) Y  G  Y | 
|                        | 
|                        | 
| B  G  Y  R  Y  G  G  R | 
|                        | 
|                        | 
| R  Y  B  G  Y  B  B  G | 
|                        | 
------------------------  
> score: 9009
> moves: 27
)"

Сам по себе геймплей этой игры Match-3 не особо интересен, но как насчёт архитектуры, на которой всё это работает? Чтобы вы поняли её, я попытаюсь объяснить каждую часть жизненного цикла этой игры времени компиляции с точки зрения кода.

Инъекция состояния игры:

Если вы страстный любитель C++ или педант, то могли заметить, что предыдущий дамп состояния игры начинается со следующего паттерна: R"(. По сути, это необработанный строковый литерал C++11, означающий, что мне не нужно экранировать специальные символы, например перевод строки. Необработанный строковый литерал хранится в файле под названием current_state.txt.

Как нам выполнить инъекцию этого текущего состояния игры в состояние компиляции? Давайте просто добавим его в loop inputs!

// loop_inputs.hpp

constexpr KeyboardInput keyboard_input = KeyboardInput::KEYBOARD_INPUT; // Получаем текущий клавиатурный ввод как макрос

constexpr auto get_game_state_string = []() constexpr
{
    auto game_state_string = constexpr_string(
        // Включаем необработанный строковый литерал в переменную
        #include "current_state.txt"
    );
    return game_state_string;
};

Будь это файл .txt или файл .h, директива include из препроцессора C будет работать одинаково: она копирует содержимое файла в своё местоположение. Здесь я копирую необработанный строковый литерал состояния игры в ascii в переменную с названием game_state_string.

Заметьте, что файл заголовка loop_inputs.hpp также раскрывает клавиатурный ввод текущему кадру/этапу компиляции. В отличие от состояния игры, состояние клавиатуры довольно мало и его можно запросто получить как определение препроцессора.

Вычисление нового состояния во время компиляции:

Теперь, когда мы собрали достаточно данных, мы можем вычислить новое состояние. И наконец мы достигли точки, в которой нам нужно написать файл main.cpp:

// main.cpp
#include "loop_inputs.hpp" // Получаем все данные, необходимые для вычислений.

// Начало: вычисления во время компиляции.

constexpr auto current_state = parse_game_state(get_game_state_string); // Парсим состояние игры в удобный объект.

constexpr auto new_state = game_engine(current_state) // Передаём движку проанализированное состояние,
    .update(keyboard_input);                          // Обновляем движок, чтобы получить новое состояние.


constexpr auto array = print_game_state(new_state); // Преобразуем новое состояние в вид std::array<char>.

// Конец: вычисления во время компиляции.

// Время выполнения: просто рендерим состояние.
for (const char& c : array) {  std::cout << c; }

Странно, но этот код C++ не выглядит таким запутанным, с учётом того, что он делает. Основная часть кода выполняется в фазе компиляции, однако следует традиционным парадигмам ООП и процедурного программирования. Только последняя строка — рендеринг — является препятствием для того, чтобы полностью выполнять вычисления во время компиляции. Как мы увидим ниже, вбросив в нужных местах немного constexpr, мы можем получить достаточно элегантное метапрограммирование на C++17. Я нахожу восхитительной ту свободу, которую даёт нам C++, когда дело доходит до смешанного выполнения во время выполнения и компиляции.

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

Склеиваем всё вместе:

Если у вас вызывают отвращение мои трюки с C++, то надеюсь вы не будете против узреть мои навыки Bash. На самом деле, мой цикл игры — это ничто иное, как скрипт на bash, постоянно выполняющий компиляцию.

# Это цикл! Хотя постойте, это же цикл игры!!!
while; do :
    # Начинаем этап компиляции с помощью G++
    g++ -o renderer main.cpp -DKEYBOARD_INPUT="$keypressed"

    keypressed=get_key_pressed()

    # Очищаем экран.
    clear

    # Получаем рендеринг
    current_state=$(./renderer)
    echo $current_state # Показываем рендеринг игроку

    # Помещаем рендеринг в файл current_state.txt file и оборачиваем его в необработанный строковый литерал.
    echo "R"(" > current_state.txt
    echo $current_state >> current_state.txt
    echo ")"" >> current_state.txt
done

На самом деле у меня возникли небольшие затруднения с получением клавиатурного ввода из консоли. Изначально я хотел получать параллельно с компиляцией. После множества проб и ошибок мне удалось получить что-то более-менее работающее с помощью команды read из Bash. Я никогда не осмелюсь сразиться с кудесником Bash на дуэли — этот язык слишком уж зловещ!

Итак, нужно признать, что для управления циклом игры мне пришлось прибегнуть к другому языку. Хотя технически ничто не мешало мне написать эту часть кода на C++. К тому же это не отменяет того факта, что 90% логики моей игры выполняется внутри команды компиляции g++, что довольно-таки потрясающе!

Немного геймплея, чтобы дать отдохнуть вашим глазам:

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

Этот пикселизированный gif — запись того, как я играю в Meta Crush Saga. Как видите, игра работает достаточно плавно, чтобы быть играбельной в реальном времени. Очевидно, что она не настолько привлекательна, чтобы я мог стримить её Twitch и стать новым Pewdiepie, но зато она работает!

Один из забавных аспектов хранения состояния игры в файле .txt — это возможность жульничать или очень удобно тестировать предельные случаи.

Теперь, когда я вкратце познакомил вас с архитектурой, мы углубимся в функционал C++17, используемый в этом проекте. Я не буду подробно рассматривать игровую логику, потому что она относится исключительно к Match-3, а вместо этого расскажу об аспектах C++, которые можно применить и в других проектах.

Мои уроки о C++17:

В отличие от C++14, который в основном содержал незначительные исправления, новый стандарт C++17 может предложить нам многое. Были надежды, что наконец-то появятся уже давно ожидаемые возможности (модули, корутины, концепции...), но… в общем… они не появились; это расстроило многих из нас. Но сняв траур, мы обнаружили множество небольших неожиданных сокровищ, которые всё-таки попали в стандарт.

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

Constepxr во все поля:

Как предсказывали Бен Дин и Джейсон Тёрнер в своём докладе о C++14, C++ позволяет быстро улучшить вычисления значений во время компиляции благодаря всемогущему ключевому слову constexpr. Располагая это ключевое слово в нужных местах, можно сообщить компилятору, что выражение является константой и его можно вычислить непосредственно во время компиляции. В C++11 мы уже могли написать такой код:

constexpr int factorial(int n) // Комбинирование функции с constexpr делает её потенциально вычисляемой во время компиляции.
{
    return n <= 1? 1 : (n * factorial(n - 1));
}

int i = factorial(5); // Вызов constexpr-функции.
// Хороший компилятор может заменить это так:
// int i = 120;

Хотя ключевое слово constexpr и очень мощное, оно имеет довольно много ограничений на использование, что затрудняло написание подобным образом выразительного кода.

C++14 намного снизил требования к constexpr и стал намного более естественным в использовании. Нашу предыдущую функцию факториала можно переписать следующим образом:

constexpr int factorial(int n)
{
    if (n <= 1) {
        return 1;
    }

    return n * factorial(n - 1);
}

C++14 избавился от правила, гласящего, что constexpr-функция должна состоять из только одного оператора возврата, что заставляло нас использовать в качестве основного строительного блока тернарный оператор. Теперь C++17 принёс ещё больше областей применения ключевого слова constexpr, которые мы можем исследовать!

Ветвление во время компиляции:

Попадали ли вы когда-нибудь в ситуацию, когда нужно получить разное поведение в зависимости от параметра шаблона, которым вы манипулируете? Допустим, нам нужна параметризированная функция serialize, которая будет вызывать .serialize(), если объект его предоставляет, а в противном случае прибегает к вызову для него to_string. Как более подробно объяснено в этом посте о SFINAE, скорее всего вам придётся писать такой инопланетный код:

template <class T>
std::enable_if_t<has_serialize_v<T>, std::string> 
serialize(const T& obj) {
    return obj.serialize();
}

template <class T>
std::enable_if_t<!has_serialize_v<T>, std::string> 
serialize(const T& obj) {
    return std::to_string(obj);
}

Только во сне вы могли переписать этот уродливый трюк со SFINAE trick на C++14 в такой величественный код:

// has_serialize - это constexpr-функция, проверяющая serialize на объекте.
// См. мой пост о SFINAE, чтобы понять, как написать такую функцию. 
template <class T>
constexpr bool has_serialize(const T& /*t*/);

template <class T>
std::string serialize(const T& obj) { // Мы знаем, что constexpr можно располагать перед функциями.
    if (has_serialize(obj)) {
        return obj.serialize();
    } else {
        return std::to_string(obj);
    }
}

К сожалению, когда вы просыпались и начинали писать реальный код на C++14, ваш компилятор изрыгал неприятное сообщение о вызове serialize(42);. В нём объяснялось, что объект obj типа int не имеет функции-члена serialize(). Как бы вас это ни бесило, но компилятор прав! При таком коде он всегда будет пытаться скомпилировать обе ветви — return obj.serialize(); и
return std::to_string(obj);. Для int ветвь return obj.serialize(); вполне может оказаться каким-то мёртвым кодом, потому что has_serialize(obj) всегда будет возвращать false, но компилятору всё равно придётся компилировать его.

Как вы наверно догадались, C++17 избавляет нас от такой неприятной ситуации, потому что в нём появилась возможность добавления constexpr после оператора if, чтобы «принудительно выполнить» ветвление во время компиляции и отбросить неиспользуемые конструкции:

// has_serialize...
// ...

template <class T>
std::string serialize(const T& obj)
    if constexpr (has_serialize(obj)) { // Теперь мы можем поместить constexpr непосредственно в 'if'.
        return obj.serialize(); // Эта ветвь будет отброшена, а потому не скомпилируется, если obj является int.
    } else {
        return std::to_string(obj);branch
    }
}

Очевидно, что это огромный прогресс по сравнению с трюком со SFINAE, который нам приходилось применять раньше. После этого у нас стало появляться такое же пристрастие, как у Бена с Джейсоном — мы начали использовать constexpr везде и всегда. Увы, есть ещё одно место, где бы подошло ключевое слово constexpr, но пока не используется: constexpr-параметры.

Constexpr-параметры:

Если вы внимательны, то могли заметить в предыдущем примере кода странный паттерн. Я говорю о loop inputs:

// loop_inputs.hpp

constexpr auto get_game_state_string = []() constexpr // Почему?
{
    auto game_state_string = constexpr_string(
        // Включаем необработанный строковый литерал в переменную
        #include "current_state.txt"
    );
    return game_state_string;
};

Почему переменная game_state_string инкапсулируется в constexpr-лямбду? Почему она не делает её глобальной переменной constexpr?

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

constexpr int parse_board_size(const char* game_state_string);

constexpr auto parse_board(const char* game_state_string)
{
    std::array<GemType, parse_board_size(game_state_string)> board{};
    //                                       ^ ‘game_state_string’ - это не выражение-константа
    // ...  
}

parse_board(“...something...”);

Если мы идём таким путём, то ворчливый компилятор начнёт жаловаться то, что параметр game_state_string не является выражением-константой. Когда я создаю мой массив плиток, мне нужно напрямую вычислить его фиксированную ёмкость (мы не можем использовать векторы во время компиляции, потому что для них требуется выделение памяти) и передавать его как аргумент шаблона значения в std::array. Поэтому выражение parse_board_size(game_state_string) должно быть выражением-константой. Хотя parse_board_size явно помечено как constexpr, game_state_string им не является И не может им быть! В этом случае нам мешают два правила:

• Аргументы constexpr-функции не являются constexpr!
• И мы не можем добавить constexpr перед ними!

Всё это сводится к тому, что constexpr-функции ОБЯЗАНЫ быть применимы в вычислениях и времени выполнения, и времени компиляции. Если допустить существование constexpr-параметров, то это это не позволит использовать их во время выполнения.

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

template <class GameStringType>
constexpr auto parse_board(GameStringType&&) {
    std::array<CellType, parse_board_size(GameStringType::value())> board{};
    // ...
}

struct GameString {
    static constexpr auto value() { return "...something..."; }
};

parse_board(GameString{});

В этом примере кода я создаю структурный тип GameString, имеющий статическую функцию-член constexpr value(), возвращающую строковый литерал, который я хочу передать parse_board. В parse_board я получаю этот тип через параметр шаблона GameStringType, воспользовавшись правилами извлечения аргументов шаблонов. Имея GameStringType, благодаря тому, что value() является constexpr, я могу просто вызвать в нужный момент статическую функцию-член value(), чтобы получить строковый литерал даже в тех местах, где необходимы выражения-константы.

Нам удалось инкапсулировать литерал, чтобы каким-то образом передать его в parse_board с помощью constexpr. Однако очень раздражает необходимость определять новый тип каждый раз, когда нужно отправить новый литерал parse_board: "...something1...", "...something2...". Чтобы решить эту проблему в C++11, можно было применить какой-нибудь уродливый макрос и косвенную адресацию с помощью анонимного объединения и лямбды. Микаэль Парк хорошо объяснил эту тему в одном из своих постов.

В C++17 ситуация ещё лучше. Если перечислить требования для передачи нашего строкового литерала, то мы получим следующее:

• Сгенерированная функция
• То есть constexpr
• С уникальным или анонимным названием

Эти требования должны вам кое о чём намекнуть. Что нам нужно — так это constexpr-лямбда! И в C++17 совершенно закономерно добавили возможность использования ключевого слова constexpr для лямбда-функций. Мы можем переписать наш пример кода следующим образом:

template <class LambdaType>
constexpr auto parse_board(LambdaType&& get_game_state_string) {
    std::array<CellType, parse_board_size(get_game_state_string())> board{};
    //                                       ^ В этом контексте допускается вызов constexpr-лямбды.
}

parse_board([]() constexpr -> { return “...something...”; });
//                ^ Делаем нашу лямбду constexpr.

Поверьте мне, это уже выглядит намного удобнее, чем предыдущий хакинг на C++11 с помощью макросов. Я обнаружил этот потрясающий трюк благодаря Бьорну Фахлеру, члену митап-группы по C++, в которой я участвую. Подробнее об этом трюке можно прочитать в его блоге. Стоит также учесть, что на самом деле ключевое слово constexpr необязательно в этом случае: все лямбды с возможностью стать constexpr будут ими по умолчанию. Явное добавление constexpr — это сигнатура, упрощающая нам поиск ошибок.

Теперь вы должны понимать, почему я был вынужден использовать constexpr-лямбду для передачи вниз строки, представляющей состояние игры. Посмотрите на эту лямбда-функцию, и у вас снова появится ещё один вопрос. Что это за тип constexpr_string, который я также использую для оборачивания стокового литерала?

constexpr_string и constexpr_string_view:

При работе со строками не стоит обрабатывать их в стиле C. Нужно забыть все эти назойливые алгоритмы, выполняющие сырые итерации и проверяющие нулевое завершение! Альтернативой, предлагаемой C++, является всемогущий std::string и алгоритмы STL. К сожалению, для хранения своего содержимого std::string может потребоваться выделение памяти в куче (даже со Small String Optimization). Один-два стандарта назад мы могли воспользоваться constexpr new/delete или могли передать распределители constexpr в std::string, но теперь нам нужно найти другое решение.

Мой подход заключался в том, чтобы написать класс constexpr_string с фиксированной ёмкостью. Эта ёмкость передаётся как параметр шаблона значения. Вот краткий обзор моего класса:

template <std::size_t N> // N - это ёмкость моей строки.
class constexpr_string {
private:
    std::array<char, N> data_; // Резервируем N char для хранения чего-нибудь.  
    std::size_t size_;         // Настоящий размер строки.
public:
    constexpr constexpr_string(const char(&a)[N]): data_{}, size_(N -1) { // копируем в data_   }
    // ...
    constexpr iterator begin() {  return data_;   }       // Указывает на начало хранилища.
    constexpr iterator end() {  return data_ + size_;   } // Указывает на конец хранимой строки.
    // ...
};

Мой класс constexpr_string стремится как можно ближе имитировать интерфейс std::string (для нужных мне операций): мы можем запрашивать итераторы начала и конца, получать размер (size), получать доступ к данным (data), удалять (erase) их часть, получать подстроку с помощью substr и так далее. Благодаря этому очень просто преобразовать фрагмент кода из std::string в constexpr_string. Вы можете задаться вопросом, что произойдёт, когда нам нужно использовать операции, которые обычно требуют выделения в std::string. В таких случаях я был вынужден преобразовывать их в неизменяемые операции, которые создают новый экземпляр constexpr_string.

Давайте взглянем на операцию append:

template <std::size_t N> // N - это ёмкость моей строки.
class constexpr_string {
    // ...
    template <std::size_t M> // M - это ёмкость другой строки.
    constexpr auto append(const constexpr_string<M>& other)
    {

        constexpr_string<N + M> output(*this, size() + other.size());
        //                 ^ Достаточно ёмкости для обеих. ^ Копируем первую строку в output.

        for (std::size_t i = 0; i < other.size(); ++i) {
            output[size() + i] = other[i];
            ^ Копируем вторую строку в output.
        }

        return output; 
    }
    // ...
};

Не нужно иметь Филдсовскую премию, чтобы предположить, что если у нас есть строка размера N и строка размера M, то строки размера N + M будет достаточно для хранения их конкатенации. Мы можем впустую потратить часть «хранилища времени компиляции», поскольку обе строки могут и не использовать всю ёмкость, но это довольно малая цена за удобство. Очевидно, что я также написал дубликат std::string_view, который назвал constexpr_string_view.

Имея эти два класса, я был готов к написанию элегантного кода для парсинга моего состояния игры. Подумайте о чём-то подобном:

constexpr auto game_state = constexpr_string(“...something...”);

// Давайте найдём первое вхождение синего драгоценного камня в моей строке:
constexpr auto blue_gem = find_if(game_state.begin(), game_state.end(), 
    [](char c) constexpr -> { return  c == ‘B’; }
);

Было довольно просто обойти итеративно драгоценности на игровом поле — кстати говоря, заметили ли вы в этом примере кода ещё одну драгоценную возможность C++17?

Да! Мне не пришлось явно указывать ёмкость constexpr_string при его конструировании. Раньше нам приходилось при использовании шаблона класса явно указывать его аргументы. Чтобы избежать этих мук, мы создаём функции make_xxx, потому что параметры шаблонов функций можно проследить. Посмотрите на то, как отслеживание аргументов шаблонов классов меняет нашу жизнь к лучшему:

template <int N>
struct constexpr_string {
    constexpr_string(const char(&a)[N]) {}
    // ..
};

// **** До C++17 ****
template <int N>
constexpr_string<N> make_constexpr_string(const char(&a)[N]) {
    // Создаём шаблон функции для вычисления N           ^ прямо здесь
    return constexpr_string<N>(a);
    //                      ^ Передаём параметр шаблону класса.
}

auto test2 = make_constexpr_string("blablabla");
//                  ^ используем наш шаблон функции для вычисления.
constexpr_string<7> test("blabla");
//               ^ или передаём аргумент непосредственно и молимся, чтобы он был хорошим.


// **** В C++17 ****
constexpr_string test("blabla");
//           ^ Очень удобно в использовании, аргумент вычисляется.

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

Бесплатная еда от STL:

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

Новые вспомогательные типы:

В C++17 к стандартным типам словарей добавлены std::variant и std::optional с расчётом на constexpr. Первый очень интересен, поскольку он позволяет нам выражать типобезопасные объединения, но реализация в библиотеке libstdc++ с GCC 7.2 имеет проблемы при использовании выражений-констант. Поэтому я отказался от идеи добавления в свой код std::variant и использую только std::optional.

При наличии типа T тип std::optional позволяет нам создать новый тип std::optional<T>, который может содержать или значение типа T, или ничего. Это довольно похоже на значимые типы, допускающие неопределенное значение в C#. Давайте рассмотрим функцию find_in_board, которая возвращает позицию первого элемента на поле, который подтверждает правильность предиката. На поле может и не быть такого элемента. Для обработки такой ситуации тип позиции должен быть optional:

template <class Predicate>
constexpr std::optional<std::pair<int, int>> find_in_board(GameBoard&& g, Predicate&& p) {
    for (auto item : g.items()) {
        if (p(item)) { return {item.x, item.y}; } // Возвращаем по значению, если мы нашли такой элемент.
    }
    return std::nullopt; // В противном случае возвращаем пустое состояние.
}

auto item = find_in_board(g, [](const auto& item) { return true; });
if (item) {  // Проверяем, пуст ли optional.
    do_something(*item); // Можем безопасно использовать optional, "пометив" с помощью *.
    /* ... */
}

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

Некоторые уже существующие типы тоже получили поддержку constexpr: tuple и pair. Я не буду подробно объяснять их использование, потому что о них уже многое написано, но поделюсь одним из своих разочарований. Комитет добавил в стандарт синтаксический сахар для извлечения значений, содержащихся в tuple или pair. Этот новый тип объявления, называемый structured binding, использует скобки для задания того, в каких переменных нужно хранить расчленённые tuple или pair:

std::pair<int, int> foo() {
    return {42, 1337};
}

auto [x, y] = foo();
// x = 42, y = 1337.

Очень умно! Но жаль, что члены комитета [не могли, не захотели, не нашли времени, забыли] сделать их дружелюбными к constexpr. Я бы ожидал чего-то такого:

constexpr auto [x, y] = foo(); // OR
auto [x, y] constexpr = foo();

Теперь у нас есть сложные контейнеры и вспомогательные типы, но как нам удобно ими манипулировать?

Алгоритмы:

Апгрейд контейнера для обработки constexpr — довольно монотонная задача. По сравнению с ней, перенос constexpr в немодифицирующие алгоритмы кажется достаточно простым. Но довольно странно, что в C++17 мы не увидели прогресса в этой области, он появится только в C++20. Например, замечательные алгоритмы std::find не получили сигнатуры constexpr.

Но не бойтесь! Как объяснили Бен и Джейсон, можно легко превратить алгоритм в constexpr, просто скопировав текущую реализацию (но не забывайте об авторских правах); неплохо подходит cppreference. Леди и джентльмены, представляю вашему вниманию constexpr std::find:

template<class InputIt, class T>
constexpr InputIt find(InputIt first, InputIt last, const T& value)
// ^ ТАДАМММ!!! Я добавил сюда constexpr.
{
    for (; first != last; ++first) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}

// Спасибо http://en.cppreference.com/w/cpp/algorithm/find

Я уже слышу с трибун крики фанатов оптимизации! Да, простое добавление constexpr перед примером кода, любезно предоставленного cppreference, возможно и не даст нам идеальную скорость во время выполнения. Но если нам и придётся усовершенствовать этот алгоритм, так это понадобится для скорости во время компиляции. Насколько мне известно, когда дело касается скорости компиляции, то лучше всего простые решения.

Скорость и баги:

Разработчики любой AAA-игры должны вложить усилия в решение этих проблем, правда?

Скорость:

Когда мне удалось создать наполовину работающую версию Meta Crush Saga, работа пошла плавнее. На самом деле мне удалось достичь чуть больше 3 FPS (кадров в секунду) на моём старом ноутбуке с i5, разогнанным до 1,80 ГГц (частота в этом случае важна). Как и в любом проекте, я быстро понял, что ранее написанный код отвратителен, и начал переписывать парсинг состояния игры с помощью constexpr_string и стандартных алгоритмов. Хотя это сделало код гораздо более удобным в поддержке, изменения серьёзно повлияли на скорость; новым потолком стали 0,5 FPS.

Несмотря на старую поговорку про C++, «zero-head abstractions» не применимы к вычислениям во время компиляции. Это вполне логично, если рассматривать компилятор как интерпретатор некоего «кода времени компиляции». Всё ещё возможно усовершенствования под различные компиляторы, но также есть возможности роста и для нас, авторов такого кода. Вот найденный мной неполный список наблюдений и подсказок, возможно, специфичный для GCC:

• Массивы C работают значительно лучше, чем std::array. std::array — это немного современной косметики C++ поверх массива в стиле C и приходится платить определённую цену за использование его в таких условиях.
• Мне показалось, что рекурсивные функции имеют преимущество (с точки зрения скорости) по сравнению с написанием функций с циклами. Вполне возможно, причина в том, что написание рекурсивных функций требует другого подхода к решению задач, который проявляет себя лучше. Вставлю свои две копейки: я считаю, что затраты на вызовы времени компиляции могут быть меньше, чем выполнение сложного тела функции, особенно в свете того, что компиляторы (и их авторы) были подвержены многолетнему применению надоедливых рекурсий, которые мы использовали в своём метапрограммировании на шаблонах.
• Также довольно затратным является копирование данных, если иметь дело со значимыми типами. Если бы я хотел ещё больше оптимизировать игру, то в основном сосредоточился бы на этой проблеме.
• Для выполнения работы я использовал только одно ядро ЦП. Наличие только одной единицы компиляции ограничивало меня созданием только одного экземпляра GCC. Не уверен, можно ли распараллелить мою «вычисляцию».

Баги:

Много раз мой компилятор изрыгал ужасные ошибки компиляции, а моя логика кода страдала. Но как найти место, где прячется баг? Без отладчика и printf всё становится сложнее. Если ваша метафорическая «борода программиста» ещё не выросла до колен (и метафорическая, и реальная моя борода ещё далека от этих ожиданий), то, возможно, у вас нет мотивации к использованию templight или к отладке компилятора.

Нашим первым другом будет static_assert, который даёт нам возможность проверить значение boolean времени компилирования. Нашим вторым другом станет макрос, включающий и отключающий constexpr там, где это возможно:

#define CONSTEXPR constexpr  // отладка невозможна во время компиляции

// ИЛИ

#define CONSTEXPR           // Отладка во время выполнения

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

Meta Crush Saga II — стремимся к игровому процессу полностью во время выполнения:

Очевидно, что Meta Crush Saga не выиграет в этом году премию The Game Awards. У неё есть отличный потенциал, но игровой процесс не выполняется полностью во время компиляции. Это может раздосадовать хардкорных геймеров… Я не могу избавиться от скрипта на bash, если только кто-нибудь не добавит клавиатурный ввод и нечистую логику в фазе компиляции (а это откровенное безумие!). Но я верю, что однажды мне удастся полностью отказаться от исполняемого файла рендерера и выводить состояние игры во время компиляции:

Безумный парень с псевдонимом saarraz расширил GCC, чтобы добавить в язык конструкцию static_print. Эта конструкция должна брать несколько выражений-констант или строковых литералов и выводить их на этапе компиляции. Я был бы рад, если бы такой инструмент добавили в стандарт, или хотя бы расширили static_assert, чтобы он принимал выражения-константы.

Однако в C++17 может быть способ добиться такого результата. Компиляторы уже выводят две вещи — ошибки и предупреждения! Если мы сможем как-то управлять или изменить предупреждения под наши нужды, то уже получим достойный вывод. Я попробовал несколько решений, в частности устаревший атрибут:

template <char... words>
struct useless {
    [[deprecated]] void call() {} // Will trigger a warning.
};

template <char... words> void output_as_warning() { useless<words...>().call(); }

output_as_warning<’a’, ‘b’, ‘c’>();

// warning: 'void useless<words>::call() [with char ...words = {'a', 'b', 'c'}]' is deprecated 
// [-Wdeprecated-declarations]

Хотя вывод очевидно присутствует и его можно парсить, к сожалению, код неиграбелен! Если по чистому совпадению вы являетесь членом тайного общества программистов C++, умеющих выполнять вывод во время компиляции, то я с радостью найму вас в свою команду, чтобы создать идеальную Meta Crush Saga II!

Выводы:

Я закончил с продажей вам моей скама игры. Надеюсь, вы найдёте этот пост любопытным и узнаете в процессе его чтения что-то новое. Если найдёте ошибки или способы улучшения статьи, то свяжитесь со мной.

Я хочу поблагодарить SwedenCpp team за то, что они позволили мне провести свой доклад о проекте на одном из их мероприятий. Кроме того, хочу выразить огромную благодарность Александру Гурдееву, который помог мне улучшить значимые аспекты Meta Crush Saga.

Автор: PatientZero

Источник