Match-3 Butler Engine, or What Every Mobile Game Developer Does
As you know, game developers are divided into two types: those who make AAA and those who make extremely simple match-3s. Here I will tell you in chronological order how I optimized the simplest genre in the world. I will try to further reduce the amount of irony. Interested persons are invited to familiarize themselves with my path
background
At a previous job we were developing a match-3 battler on unity (empires and puzzles in references), I was given the task of making an engine for it. Since each match had to be checked on the server, I had determinism in the requirements and 5 milliseconds to simulate the match. Unfortunately, the company did not survive the loss of an investor, and before closing, I asked permission to show the code and tell about my work so that my work would not sink into oblivion
game loop
The game goes like this:
The player can move the chip if after that a row of 3 or more chips has formed (hereinafter referred to as a match), they start flying up the field, hitting the first enemy that gets in the way, if there is one. At this moment, the playing field fills up with new chips, which can also form a match and fly up. This continues until no more chips form a match.
The player has heroes with mana. When full, they can use skills before dragging tokens.
Next, the enemies’ turn counter is updated, and if it is their turn, they will attack the player’s heroes. After that, everything repeats.
Since I’m not a game designer, I don’t have the skill to describe mechanics, but I hope I conveyed the general meaning.
Start of development
For several days I spent RnD of publicly available match-3 works, there even came across very nice options on async, but, alas, all of them were not very suitable for simulation on the server, because they were made for unity, and no one even talked about serious optimization Did not think. I wouldn’t think so either if it was only about the client.
First of all, I decided to start with the problem of creating a field and checking the possibility of a move, since it would be stupid to create a field without moves, as well as a field with a ready combination. To do this, I started an enumeration with directions and cells, in which there was a dictionary with a key – an enumeration, and a value – a neighboring cell, and also proceeded to generate these cells and check the existence of possible moves. After watching lectures from MY.GAMES about match-3 on graphs, I decided to do something similar.
Alas, I do not have the exact code of my first tests, so I’ll just draw what happened during the test. Here I am going to draw a lot.
If at least one match was found, true is returned, otherwise the same actions are performed in other directions, then the same process is repeated with all cells until a match is found or unchecked cells run out.
Here I made a terrible mistake – I took Stopwatch instead of the benchmark, deciding that it could show the result with sufficient accuracy. The result came out about 0.6 milliseconds, which is extremely long. This is probably a bug in Stopwatch itself, and a benchmark would have shown the result much better, but at that moment I did not use it. You can also immediately notice that such a check and a dictionary in each cell is not the fastest solution, and there are a lot of allocations in this version.
First optimizations
I started by throwing out the dictionary, leaving only an enumeration to determine the neighbors, and put it all in a two-dimensional array, against which checks were already made. It got faster. Around this point, I threw out Stopwatch, replacing it with BenchmarkDotNet, because I began to suspect that the result of Stopwatch on small values is far from accurate. The result turned out to be about 8 microseconds, which was already pleasing, but there were ideas how to make it even faster.
First, I expanded the two-dimensional array into a one-dimensional one. This greatly increased the speed. Then I wanted to do without an array at all, placing the entire list of cells on the stack. To do this, I took Span and tried to create a stackalloc array. At the same time, I found out that stackalloc needs a fixed size of objects, so the string Id for cells is no longer suitable, I had to replace it with an int (it would have been possible with a byte, given that there are only five colors in the original game).
Then he replaced the method of determining the existence of moves from the movement of the cell to the side to the movement of the neighbor to the position of the cell.
Thus, it turned out to speed up the creation and check for the presence of moves up to 1 microsecond.
Player turn, match after it and data transfer further
With the player’s turn, everything is quite trivial – 2 cells are temporarily swapped, each is checked in 3 directions, excluding the directions opposite to the direction of the change of cells. If there is a match, then the cells are swapped for “permanent”, and all the cells involved in the match are somehow marked. In this case, I wanted to have some fixed-sized data in which the result would be marked. Adding this information to the cell seemed inconvenient to me. For this I took an array of bytes. It would be possible to simply take an array (span), equal in size to an array of cells, but I wanted to make it more interesting. Therefore, for my 7 by 5 field, I took an array of size 7, where each byte is a vertical line on the field. And in it I already marked the necessary bits with ones.
Shift and fill
Since there was a ready-made system for indicating what was happening on the field, these two functionalities were rather trivial. The top cells were moved to the places of the ones, and the ones were moved up, so that new ones would appear in their places.
After generating the cells, it was necessary to check the presence of the match again, as well as to mark the cells participating in the match. In order not to check the entire field, I decided to check the area in which the cells moved, increased by two cells in each direction.
Enemy mechanics
Enemies stand on three horizontal lines: near, middle, far.
Enemies can occupy from two to five cells, while the enemy model may not occupy the entire cell, and the number of enemies varies from one to five.
In one match, there can be several waves of enemies with their own location and size.
The enemy takes damage if it is hit by the cells flying up with which the match took place.
If two enemies fall on one row of chips, then the damage is divided between them
Enemies have a color, just like chips. Flowers have a rock-paper-scissors damage multiplier system.In one match, chips can only attack the enemy in one row.
Enemies attack the player once every n turns.Some enemies have mana that refills when that unit takes damage. Filled mana allows you to perform a special attack regardless of the turn counter.
Playing field with enemies
From the playing field to the enemies, I foresaw a lot of pain in advance. Firstly, there can be a different number of enemies, secondly, they can be of different sizes, and thirdly, an enemy of the same size (judging by the screenshots) can take damage from two or three lines of chips. At the same time, I still wanted to do without allocations. Of course, at that moment I was quite confused by the visual, I had to immediately forget about it.
The first thing that came to mind was to double the horizontal field relative to the field of cells (enemy models can be the center both on the cell and between the cells), and store the delta in the enemy in both directions. The idea, I must admit, turned out to be such itself.
After that, I took the leftmost row, which could deal damage to the enemy, and the width of the enemy. Thanks to this, it was possible to throw out the positions between the cells, since they turned out to be unnecessary.
In order not to create a Span every time with the number of enemies needed for a particular wave (since it lies on the stack, I couldn’t just overwrite the old one with a new size, but I would put the new one on top), I immediately took the maximum number of them – five. This created a problem – I needed to know what enemies exist and where they stand.
To solve the problem, I again took an array of bytes. This time I took three bytes, and in each byte I marked bits equal to the index of enemies in Span. I hope the picture explains it better.
After that, it was possible both to deal damage to single enemies, and to check if there were two enemies on the same line. Since units are always generated from left to right, to check for collisions, it was necessary to take the next non-zero bit in the row (if any). If the starting position of this unit coincides with the rightmost cell of the current unit, then the damage is divided between them.
In conclusion
I don’t remember the intermediate benchmark numbers well, but in the final version, simulating 1000 moves took about 0.7 milliseconds on my not the fastest laptop. The result is quite far ahead of the requirements. When adding mechanics, the result, of course, will be worse, but the stock still remains quite large.
Buffs / debuffs were written by a colleague, and since at this point in development we lost the publisher, I did not have time to fully implement them. But I have some ideas about this. Since buffs and debuffs were classes (a colleague did not want to continue my madness), I suggested simply creating a pool of these effects so that you could at least not pull the GC and create them every time the need arose. I also bypassed the generation of special chips and the formulas for calculating the damage of enemies / on enemies, but some of this functionality can be viewed on the gita.
Since I got permission to show only my work, and not the whole team, the git version from unity will not be included, which I did at the end and which fixed many bugs that exist in the posted version (in the end I stopped pushing actual changes to console version). Also, the part with skills will not be included. I also want to apologize to those who get into git for their naming and rather large methods that need refactoring.
