In the process of moving to the long-awaited title of
Lead Senior C ++ Over-Engineer , last year I decided to rewrite the game that I develop during working hours (Candy Crush Saga), using the quintessence of modern C ++ (C ++ 17). And so
Meta Crush Saga was born: a
game that is executed at the compilation stage . I was very inspired by the game
Nibbler by Matt Byrneer, in which to recreate the famous “Snake” with the Nokia 3310, pure template metaprogramming was used.
“What kind of
game is performed at the compilation stage ?”, “What does it look like?”, “What functionality did you use in
C ++ 17 in this project?”, “What did you learn?” - such questions can come to your mind . To answer them, you will have to either read the entire post, or come to terms with your inner laziness and watch the video version of the post - my report to the
Meetup event in Stockholm:
Note: for the sake of your mental health and due to the fact that
errare humanum est , this article provides some alternative facts.
A game that runs at compile time?
I think that in order to understand what I mean by the “concept” of a
game that is executed at the compilation stage , you need to compare the life cycle of such a game with the life cycle of a regular game.
The life cycle of an ordinary game:
As an ordinary game developer with a normal life, working in a normal job with a normal level of mental health, you usually start by writing
game logic in your favorite language (in C ++, of course!), And then run the
compiler to convert this, too often similar to spaghetti , logic to
executable file . After double clicking on the
executable file (or running from the console), the operating system spawns the
process . This
process will perform the
game logic , which in 99.42% of the time consists of a
game cycle .
The game cycle updates the state of the game in accordance with certain rules and
user input ,
renders a new calculated game state in pixels, again, and again, and again.
The life cycle of the game being executed during the compilation process:
As an over-engineer, creating your own awesome compilation game, you still use your favorite language (still C ++, of course!) To write
game logic . Then the
compilation phase is still going
on , but here the plot rotates: you
execute your
game logic at the compilation stage. You can call this “compilation”. And here C ++ is very useful; it has functions such as
Template Meta Programming (TMP) and
constexpr , which allow you to perform
calculations in the
compilation phase . Later we will consider the functionality that can be used for this. Since at this stage we are performing the
logic of the game, at this moment we also need to insert the
player’s input . Obviously, our compiler will still create an
executable file on output. What can it be used for? The executable file will no longer contain
a game loop , but it has a very simple mission: output a new
computed state . Let's call this
executable file a renderer , and
the data it displays is
rendering . In our
rendering, neither beautiful particle effects nor ambient occlusion shadows will be contained; it will be ASCII.
Rendering in ASCII of a newly computed
state is a convenient feature that can be easily demonstrated to the player, but in addition, we copy it to a text file. Why a text file? Obviously, because it can somehow be combined with the
code and re-execute all the previous steps, thus obtaining a
cycle .
As you can already understand, the game
executed during the compilation process consists of a
game cycle , in which each
frame of the game is a
compilation stage . Each
compilation step calculates a new game
state that can be shown to the player and inserted into the next
frame /
compilation step .
You can contemplate this magnificent diagram as long as you like until you understand what I have just written:
Before we go into the details of the implementation of such a cycle, I am sure that you want to ask me a single question ...
“Why bother to do this at all?”
Do you really think that ruining my C ++ metaprogramming idyll is such a fundamental question? No way in life!
- The first and most important thing is that the game executed at the compilation stage will have an amazing runtime speed, because the main part of the calculations is performed in the compile phase . Runtime speed is the key to the success of our AAA games with ASCII graphics!
- You reduce the likelihood that some crustacean will appear in your repository and ask you to rewrite the game on Rust . His well-prepared speech will fall apart as soon as you explain to him that an invalid pointer cannot exist at compile time. Self-confident Haskell programmers can even confirm the type safety in your code.
- You will win the respect of the hipster kingdom of Javascript , in which any pereuslozhenny framework with a strong NIH-syndrome can rule, provided that he came up with a cool name.
- A friend of mine said that any line of Perl program code could de facto be used as a very strong password. I am sure that he never tried to generate passwords from C ++ compile time .
Well, how? Are you satisfied with my answers? Then maybe your question should be: “How do you do it at all?”
In fact, I really wanted to experiment with the functionality added in
C ++ 17 . Quite a few features are designed in it to improve the efficiency of the language, as well as for metaprogramming (mainly constexpr). I thought that instead of writing small code examples, it would be much more interesting to turn it all into a game. Pet projects are a great way to explore concepts that are not so often used in work. The ability to perform the basic logic of the game at compile time again proves that the templates and constepxr are
Turing-complete subsets of the C ++ language.
Meta Crush Saga: Game Review
Match-3 game:
Meta Crush Saga is a
tile mix game similar to
Bejeweled and
Candy Crush Saga . The core of the rules of the game is to combine three tiles with the same pattern to get points. Here's a quick look at the
state of the game , which I “dumped” (a dump in ASCII is pretty darn simple):
R "(Meta crush saga ------------------------ | | | RBGBBYGR | | | | | | YYGRBGBR | | | | | | | RBYRGRYG | | | | | | | RYBY (R) YGY | | | | | | BGYRYGGR | | | | | | | RYBGYBBG | | | ------------------------ > score: 9009> moves: 27) "
By itself, the gameplay of this game Match-3 is not particularly interesting, but what about the architecture on which it all works? So that you understand it, I will try to explain every part of the life cycle of this game
compilation time in terms of code.
Injection of game state:
If you are a passionate C ++ amateur or a pedant, you may have noticed that the previous dump of the game state begins with the following pattern:
R "( . In fact, this is a
raw C ++ 11 string literal , meaning that I do not need to escape special characters, for example,
strings .The raw string literal is stored in a file called
current_state.txt .
How do we inject this current state of the game into a compilation state? Let's just add it to the loop inputs!
Whether it is a
.txt file or a
.h file, the
include directive from the C preprocessor will work the same way: it copies the contents of the file to its location. Here I am copying the raw game state literal string in ascii to a variable called
game_state_string .
Note that the header file
loop_inputs.hpp also reveals the keyboard entry for the current frame / compilation step. Unlike the state of the game, the state of the keyboard is quite small and can be easily obtained as a definition of a preprocessor.
Calculating the new state at compile time:
Now that we have collected enough data, we can calculate the new state. Finally, we have reached the point where we need to write the
main.cpp file:
Strange, but this C ++ code doesn't look so confusing, considering what it does. The main part of the code is executed in the compilation phase, but follows the traditional paradigms of OOP and procedural programming. Only the last line - rendering - is an obstacle to fully perform calculations at compile time. As we will see below, by throwing a little constexpr in the right places, we can get a rather elegant metaprogramming in C ++ 17. I find the delightful freedom that C ++ gives us when it comes to mixed execution at runtime and compilation.
You will also notice that this code executes only one frame; there is no
game loop here. Let's solve this question!
We glue everything together:
If you are disgusted with my tricks with
C ++ , I hope you will not mind to see my skills
Bash . In fact, my
game loop is nothing more than a
bash script that constantly compiles.
In fact, I had a little trouble getting keyboard input from the console. Initially, I wanted to get in parallel with the compilation. After a lot of trial and error, I managed to get something more or less working with the
read command from
Bash . I never dare to fight with the wizard
Bash in a duel - this language is too ominous!
So, I have to admit that in order to control the cycle of the game I had to resort to another language. Although technically nothing prevented me from writing this part of the C ++ code. In addition, this does not negate the fact that 90% of the logic of my game is executed within the
g ++ compilation command, which is quite amazing!
A bit of gameplay to give your eyes a rest:
Now that you have experienced the torment of explaining the architecture of the game, it is time for eye-catching pictures:
This pixelated gif is a recording of how I play
Meta Crush Saga . As you can see, the game runs smoothly enough to be playable in real time. Obviously, she is not so attractive that I could stream her Twitch and become a new Pewdiepie, but it works!
One of the fun aspects of storing
game status in a
.txt file is the ability to cheat or very conveniently test marginal cases.
Now that I’ve briefly introduced you to architecture, we’ll delve into the C ++ 17 functionality used in this project. I will not look at the game logic in detail, because it applies exclusively to Match-3, and instead I will talk about aspects of C ++ that can be applied in other projects.
My lessons on C ++ 17:
Unlike C ++ 14, which mostly contained minor fixes, the new C ++ 17 standard can offer us a lot. There were hopes that the long-awaited opportunities (modules, modules, concepts ...) would finally emerge, but ... well ... they did not appear; it upset many of us. But removing the mourning, we found many small unexpected treasures, which still fell into the standard.
I dare say that loving metaprogramming kids this year too spoiled! Separate minor changes and additions to the language now allow you to write code that looks very similar at compile time and after run time.
Constepxr to all fields:
As Ben Dean and Jason Turner predicted in their
C ++ 14 report , C ++ allows you to quickly improve the compile value computation thanks to the all-powerful keyword
constexpr . By placing this keyword in the right places, you can tell the compiler that the expression is constant and
can be calculated directly at compile time. In
C ++ 11, we could already write such code:
constexpr int factorial(int n)
Although the
constexpr keyword is very powerful, it has quite a few restrictions on usage, making it difficult to write expressive code in a similar way.
C ++ 14 greatly reduced the requirements for
constexpr and became much more natural to use. Our previous factorial function can be rewritten as follows:
constexpr int factorial(int n) { if (n <= 1) { return 1; } return n * factorial(n - 1); }
C ++ 14 got rid of the rule that the
constexpr function should consist of only one return statement, which made us use the
ternary operator as the main building block. Now
C ++ 17 brings even more
constexpr keyword
scopes that we can explore!
Compile branching:
Have you ever been in a situation where you need to get different behavior depending on the parameter of the template that you are manipulating? Suppose we need a parameterized
serialize function that will call
.serialize() if the object provides it, and otherwise resorts to
to_string it
to_string . As explained in more detail in this
post about SFINAE , you will most likely have to write such alien code:
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); }
Only in a dream could you rewrite this ugly
trick with SFINAE trick in
C ++ 14 into such magnificent code:
Unfortunately, when you woke up and started writing real
C ++ 14 code , your compiler spewed an unpleasant call message about
serialize(42); . It explained that the object
obj type
int does not have a member function
serialize() . No matter how infuriated you are, the compiler is right! With this code, it will always try to compile both branches -
return obj.serialize(); and
return std::to_string(obj); . For
int branch
return obj.serialize(); it may well turn out to be some kind of dead code, because
has_serialize(obj) will always return
false , but the compiler will still have to compile it.
As you probably guessed,
C ++ 17 relieves us of such an unpleasant situation, because it has the ability to add
constexpr after an if statement to “forcefully execute” branching during compilation and discard unused constructs:
Obviously, this is a huge improvement
over the SFINAE trick that we had to use earlier. After that, we started to have the same addiction as Ben and Jason - we started using
constexpr everywhere and always. Alas, there is another place where the
constexpr keyword is
appropriate , but not yet used:
constexpr-parameters .
Constexpr parameters:
If you are attentive, you might have noticed a strange pattern in the previous code example. I'm talking about loop inputs:
Why is the
game_state_string variable encapsulated in a constexpr-lambda? Why doesn't it make it
global constexpr ?
I wanted to pass this variable and its contents deep into some functions. For example, my
parse_board needs to be passed to it and used in some constant expressions:
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{};
If we go this way, then the grumbling compiler will start complaining that the
game_state_string parameter
is not a constant expression. When I create my tile array, I need to directly calculate its fixed capacity (we cannot use vectors during compilation, because they require memory allocation) and pass it as an argument to the value template in
std :: array . Therefore, the expression
parse_board_size (game_state_string) must be a constant expression. Although
parse_board_size is explicitly marked as
constexpr ,
game_state_string is not, and cannot be! In this case, two rules bother us:
- The constexpr arguments are not constexpr!
- And we can not add constexpr in front of them!
It all boils down to the fact that
constexpr-functions MUST be applicable in calculations and runtime, and compile time. If we assume the existence of
constexpr-parameters , then this will not allow using them at runtime.
Fortunately, there is a way to level this problem. Instead of accepting a value as a normal function parameter, we can encapsulate this value in a type and pass this type as a template parameter:
template <class GameStringType> constexpr auto parse_board(GameStringType&&) { std::array<CellType, parse_board_size(GameStringType::value())> board{};
In this code example, I create a
GameString structured type that has a static constexpr
value () member function that returns a string literal that I want to pass to
parse_board . In
parse_board, I get this type through the
GameStringType template parameter using the template argument extraction rules. Having
GameStringType , due to the fact that
value () is constexpr, I can simply call the static member function
value () at the right time to get a string literal even in those places where constant expressions are needed.
We managed to encapsulate the literal to somehow pass it to the
parse_board using constexpr. However, it is very annoying to define a new type every time you need to send a new
parse_board literal: "... something1 ...", "... something2 ...". To solve this problem in
C ++ 11 , it was possible to use some kind of ugly macro and indirect addressing using an anonymous union and lambda. Mikael Park explained this topic well in
one of his posts .
In
C ++ 17, the situation is even better. If we list the requirements for passing our string literal, we get the following:
- Generated function
- That is constexpr
- With a unique or anonymous name
These requirements should give you a hint about something. What we need is
constexpr-lambda ! And in
C ++ 17 , the possibility of using the
constexpr keyword for lambda functions was added quite naturally. We can rewrite our sample code as follows:
template <class LambdaType> constexpr auto parse_board(LambdaType&& get_game_state_string) { std::array<CellType, parse_board_size(get_game_state_string())> board{};
Believe me, this already looks much more convenient than the previous hacking on
C ++ 11 using macros. I discovered this amazing trick thanks to
Björn Fachler , a member of the C ++ mitapest group in which I participate. Read more about this trick in his
blog . It is also worth considering that in fact the
constexpr keyword is
not necessary in this case: all
lambdas with the possibility of becoming
constexpr will be their default. Explicit adding
constexpr is a signature that simplifies our search for errors.
Now you need to understand why I was forced to use
constexpr- lambda to send down a line representing the state of the game. Look at this lambda function, and you will have another question again. What is the
constexpr_string type that I also use to wrap the stock literal?
constexpr_string and constexpr_string_view:
When working with strings, you should not process them in the C style. You need to forget all these annoying algorithms that perform raw iterations and check for zero completion! The alternative proposed by
C ++ is the almighty
std :: string and
STL algorithms . Unfortunately, heap memory may be required to store its contents in
std :: string (even with Small String Optimization). One or two standards back, we could use
constexpr new / delete or we could pass
constexpr distributors to
std :: string , but now we need to find another solution.
My approach was to write a fixed-capacity
constexpr_string class. This capacity is passed as a value template parameter. Here is a brief overview of my class:
template <std::size_t N>
My class
constexpr_string aims to imitate the
std :: string interface as closely as possible (for the operations I need): we can query the
start and end iterators , get the
size (size) , access the
data (data) ,
delete (erase) their part, get substring using
substr and so on. This
makes it very easy to convert a code snippet from
std :: string to
constexpr_string . You may wonder what will happen when we need to use operations that usually require a selection in
std :: string . In such cases, I was forced to convert them to
immutable operations that create a new instance of
constexpr_string .
Let's take a look at the
append operation:
template <std::size_t N>
You do not need to have a Fields premium to assume that if we have a string of size
N and a string of size
M , then a string of size
N + M will be enough to store their concatenation. We may waste part of the “compile-time store”, since both lines may not use all the capacity, but this is a rather small price for convenience. Obviously, I also wrote a duplicate
std :: string_view , which called
constexpr_string_view .
Having these two classes, I was ready to write elegant code to parse my
game state . Think of something like this:
constexpr auto game_state = constexpr_string(“...something...”);
It was quite simple to circumvent iteratively the jewels on the playing field - by the way, did you notice another precious possibility of
C ++ 17 in this sample code?
Yes! I did not have to explicitly specify the
constexpr_string capacity when constructing it. Previously, when using a
class template , we had to explicitly specify its arguments. To avoid these torments, we create functions
make_xxx , because the parameters
of the function templates can be traced. Take a look at how
tracking class template arguments is changing our lives for the better:
template <int N> struct constexpr_string { constexpr_string(const char(&a)[N]) {}
In some difficult situations you will need to help the compiler to correctly calculate the arguments. If you encounter such a problem, then study the
manuals on user-defined argument calculations .
Free food from STL:
Well, we can always rewrite everything on our own. But perhaps the committee members generously prepared something tasty for us in the standard library?
New auxiliary types:
In
C ++ 17 ,
std :: variant and
std :: optional have been added to standard dictionary types with a
reference to
constexpr . The first one is very interesting, because it allows us to express type-safe unions, but the implementation in the
libstdc ++ library with
GCC 7.2 has problems when using constant expressions. Therefore, I abandoned the idea of adding
std :: variant to my code and use only
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}; }
, « » , boolean
. , !
constexpr :
tuple pair . , , .
,
tuple pair . ,
structured binding, uses parentheses to specify which variables need to store partitioned tuple or pair : std::pair<int, int> foo() { return {42, 1337}; } auto [x, y] = foo();
Very clever! But it is a pity that the members of the committee [could not, did not want, did not find the time, forgot] make them friendly to constexpr . I would expect something like this: constexpr auto [x, y] = foo();
Now we have complex containers and auxiliary types, but how is it convenient for us to manipulate them?Algorithms:
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; }
! ,
constexpr ,
cppreference ,
. ,
. ,
, .
:
AAA- , ?
Speed:
When I managed to create a half working version of Meta Crush Saga , the work went smoother. In fact, I managed to achieve a little more than 3 FPS (frames per second) on my old laptop with i5 overclocked to 1.80 GHz (the frequency is important in this case). As in any project, I quickly realized that previously written code was disgusting, and began to rewrite the parsing of the game state using constexpr_string and standard algorithms. Although this made the code much more convenient to maintain, the changes seriously affected the speed; new ceiling steel 0.5 FPS .Despite the old C ++ proverb, "zero-head abstractions" does not apply to compile-time calculations.. This is quite logical if we consider the compiler as an interpreter of some kind of “compile time code”. Improvements for various compilers are still possible, but there are also opportunities for growth for us, the authors of this code. Here is an incomplete list of observations and hints I found, possibly specific to GCC:- C arrays work much better than std :: array . std :: array is a bit of modern C ++ cosmetics on top of an array in C style and you have to pay a certain price to use it in such conditions.
- , ( ) . , , , . : , , , , ( ) , .
- , . , .
- . GCC. , «».
Bugs:
, . , ?
printf . « » ( , ), , ,
templight .
static_assert , boolean . ,
constexpr , :
#define CONSTEXPR constexpr
With this macro, we can make the logic work at runtime, which means we can attach a debugger to it.Meta Crush Saga II - we strive to complete the gameplay during execution:
,
Meta Crush Saga The Game Awards . ,
. … bash, -
( !). ,
:
saarraz GCC ,
static_print . - . , ,
static_assert , -.
C++17 . —
! -
, . ,
obsolete attribute : template <char... words> struct useless { [[deprecated]] void call() {}
Although the output is obviously present and it can be parsed, unfortunately, the code is not playable! If by coincidence you are a member of a secret society of C ++ programmers who can perform output at compile time, I’m happy to hire you on my team to create the perfect Meta Crush Saga II !Findings:
. , - . , .
SwedenCpp team , . ,
,
Meta Crush Saga .