Divide and Conquer: Deterministic and Scripted Match3 Engine

Introduction

This is a story about how we separated simulation from presentation to make the code execution predictable, test the functionality as much as possible, and free the core from custom logic.

I am Pavel Schevaev, CTO at BIT.GAMES studio, part of international gaming brand MY.GAMES. Here we are focusing on our new project – Storyngton Hall. This is a Match 3 game with a plot where beautiful ladies solve riddles, decorate rooms, try on dresses, throw a ball, and eventually get married.

In our previous article about a test farm with Android devices, I repeatedly mentioned the Deterministic Match3 engine, which helped us test the game thoroughly without impairing the life and health of the QA team.

Of course, this is not the only reason why we went down the path of creating a Deterministic engine. In this article, I will describe in detail the logic of our choices, mistakes, and what they ultimately led to.

A Little Backstory

We have already developed games with elements from Match3 before the Storyngton Hall project. But it was a long time ago and none of the titles had their codebase fit the new project. We faced the following problems:

• Lack of determinism and the possibility of replay: there is no way to track bugs in a player's session and understand what happened;
• The model is tightly intertwined with presentation: you cannot turn off visual elements and “rewind” the simulation;
• The core contains highly custom gameplay logic. Classes such as Honey, Ferret, or Rose.

The initial plan

• Create a small functional core base on C# with a compact API;
• Conduct development through testing;
• Isolate the simulation from the presentation as much as possible;
• Introduce the concept of determinism into the simulation;
• Make sure that all custom gameplay logic is implemented using scripts. In our case, BHL.

What is BHL

BHL is an interpreted scripting language that contains:

• Convenient primitives for code pseudo-parallelism;
• Hot reload support;
• Support for downloading bytecode from the server, which enables implementation of various patches and fixes without having to download the application to the store.

We wrote BHL ourselves some time ago, and this is the language gameplay programmers at BIT.GAMES. actively use. 

Conceptual Separation

We decided to separate simulation from presentation, which prompts an analogy with client-server programming, where:

• The server is a Deterministic simulation with its own “ticks”, while the simulation provides an opportunity to subscribe to all significant events;
• The client is a presentation that affects the server using input from the player;
• The presentation and the server live separately in their own ticks.

Determinism

If the engine is Deterministic:

1. You get the ability to replay the player's session;
2. You can control the difficulty of Match3. For example, game designers will be able to choose various seeds with simplified and normal gameplay in order to aid players depending on certain conditions.

Technical Details of Development

One of the most popular ways to implement determinism is to use the Random Seed technique.

Random Seed is a certain number used as a randomizer parameter. During the player's session, all queries to the randomizer will return some pseudo-random sequence of numbers. In subsequent game sessions, queries to a randomizer using the same Random Seed will return an identical sequence of numbers.

Test-Driven Development

Our mandatory requirement was that any functionality implemented in the core be covered by tests. Here is an example of a simple test case, where we test the effect of gravity on chips:

What we do here:

• Create a simulation object;
• Place the chips;
• Make sure they are in certain positions;
• Tick our simulation until it goes idle – TickUntilIdle;
• Make sure that a chip that was placed above others falls and lies in the same row with them.

We have already passed several thousand such tests.

Simulation. Plug-in Model

We planned to organize the simulation as a plug-in model in which any component can be replaced with a different implementation. Using interfaces is a proven way to accomplish this. We could have tried ECS, but we did not do it at the time – we have decided to be careful and follow the beaten path.

The simulation receives external input in two ways: input from the player and an interval request for an update (in other words, a “tick”).

The simulation allows subscribing to all significant events, and there are quite a few of those.

What happens in the simulation tick?

We go through all components of the simulation in a strict order, so we have a clear understanding of what is being addressed and when. Below you can see how we “tick” cell objects, spawners, matching, gravity, and more.

The simulation provides us with many events with the possibility of subscribing: spawns, new chips, landing, destruction, or the fact that a chip has destroyed a wall, etc.

First Debugging UI

At first, one person was involved in the development: we had neither an artist nor a layout designer. But we had a debugging UI in Unity. It was still primitive after a couple of weeks, but it worked.

These were the preliminary results:

• The simulation worked with the discrete movement of chips. All calculations were integer: chips moved between cells in one tick and they had no intermediate position in space. Because of this, there were no non-Deterministic floating-point calculations to worry about;
• The debugging UI was playable, the tests worked fine and validated the model. It seemed that we just had to add a beautiful visualization to this model. But...

The problems started as soon as the first real UI appeared.

This video shows that each chip slows down when passing over the cells under the influence of gravity. The reason turned out to be simple: the absence of an intermediate position of the chips in space and discrete movement. Trying to somehow fix it using only visualization means seemed extremely time-consuming, so it was decided to deal with it differently.

How we fixed it:

1. Introduced an intermediate position of the chips in the space between the cells;
2. The simulation began to tick more often per unit of time. We have empirically selected a value of 20 Hz;
3. We made the presentation interpolate the model at the maximum frame rate.

The problem was that we have decided to implement the intermediate position of the chips in space using a float, and, as you know, floating-point math is not good at dealing with determinism, since it gives varying results on different hardware.

We have ultimately settled on a standard solution – Fixed-Point Math based on integer calculations.

We have found certain drawbacks in the Fixed-Point Math implementation:

• Accuracy suffered;
• Not as fast as float-based;
• Limited functionality: add, mul, sqrt, abs, cos, sin, atan.

But, given that we were not working on some kind of shooter, we understood that we could deal with it. We found the implementation on Stack Overflow, made some small changes, and were generally happy with everything. 

This implementation was also convenient because it implicitly redefined the basic arithmetic operators, so the previous computation code was practically not rewritten.

For example, below you can see the code that calculates how gravity works and it looks just like math using Unity vectors.

Fixed Ticks and Interpolation

Due to the fact that the simulation “ticks” a fixed number of times per unit of time, we needed to introduce interpolation on the presentation side. The video above clearly shows how it works.

Fixed Ticks and Buffering

We have found another interesting detail. Although the simulation lives separately and knows nothing about the visual, it must reserve some time for various interactions on the presentation side. For example, our chip cannot visually disappear instantly after being damaged, so the simulation allocates a certain number of fixed ticks for the chip to die. During this time interval, the presentation is free to visualize the process of the disappearance of the chip as it pleases.

Scripting

Event Forwarding

We use BHL for scripting and all main events from the simulation are being forwarded to scripts. Various custom effects, visual beauties, voiceover, etc. are already carried out exclusively within scripts.
For example, in the scripting code below a beautiful twitching “coil” begins and a sound effect is played for the chip landing event.

Various Types of Chips

To implement various types of chips, for example, bombs, we could have introduced various types of classes. However, this solution was rather rigid and not very extensible.

We took a different approach and introduced the concept of “activation” – a functionality that could be associated with any type of chip.

In the example below, activation is associated with chip type 14 – there is destruction around it when the chip is tapped.

When we implemented this, it became possible to create various types of “activations” in BHL scripts.

In the example below, you can see the same code as before, but already using BHL: a function starts during activation, which destroys the chips around following a given pattern.

Complex Functionality – Beetle

Now let’s review a logic that is more complex in comparison with ordinary chips. For example, we have a Beetle chip that performs a non-trivial, time-consuming function after activation.

If we disassemble the logic of the “beetle” execution into its building blocks, we can highlight the following stages.

At the simulation level:

1. The target chip is marked as inaccessible;
2. After the time interval, the marked chip is destroyed.

At the same time, a presentation is being displayed where we can see all the “beauty”:

1. The effect of the beetle taking off;
2. Flying along the trajectory;
3. The explosion effect.

This is how it looks with the BHL script:

The green section of the code is responsible for simulation, the red section – for presentation.

Here we start two tasks – for simulation and presentation, respectively. These tasks tick at different frequencies (simulation and presentation) and synchronize using a special synchronization channel. A pattern of this type was borrowed from Go.

You can see how the logic of the simulation and the presentation are being processed in the editor:

In the simulation debug area at the bottom of the screen, you can see that the chip is simply marked and then destroyed, while the visual part and all effects are visible on top in the presentation area.

You probably already noticed that the entire beetle logic was scripted using BHL. The implementation was up to gameplay developers and was completely isolated from the Match3 core.

Complex Functionality – Big Bomb

Another example is the implementation of the Big Bomb.

The implementation is similar to the Beetle:

The following happens in the simulation section: the explosion wave begins following a certain “pattern”. The necessary presentation logic is played out in the red section. All of this is consistent with the already familiar pattern of the synchronization channel.

Pleasant Bonuses

Playable Replay

It works like this:

1. Write down Random Seed;

2. For each player input, we set:

• simulation tick number;
• input type and parameters;
• the checksum for the field state to make sure there is no discrepancy.

And that's it. This is enough for replay. Below you can see an example of a gameplay session and its replay:

The game session starts. The player has been actively interacting with the game for some time. We stop the game and turn on the replay session, which was recorded automatically. A special debugging UI starts, where you can walk through the steps and see what happened at each stage. It is very convenient.

The replay can be saved both in text and in visual form. We usually use text–binary data in the base64 format, which is especially convenient for sending in mail and messengers. The last screenshot of the field is saved visually in PNG format with embedded replay code.

The Farm

The replay allowed us to predictably repeat errors from the Android test farm. You can read all the details here. But in short, every night we start all our levels on ten devices. Bug reports come into Slack. Thus, we have the opportunity to:

• Watch replays with errors;
• Understand what happened;
• Fix everything quickly.

Disconnecting Visual from Simulation

As soon as we managed to separate everything correctly, we were able to do a fair rewind of the simulation to receive rewards at the end of the level and introduce a quick check of the levels by a bot.

Fair Rewind

All Match3 players know there is when a certain sequence of actions that happens after passing a level, which you would want to skip. Bombs explode, rewards are obtained, points are awarded, and so on.

Here we disconnect from the UI, tick until the simulation becomes idle, and then reconnect to it.

Please note: after our main character Jane appears, all “fireworks” are skipped, but at the same time everything is honestly played out in the simulation, all coins are honestly counted and then awarded. This is all done instantly.

Checking Levels Using a Bot

Disconnecting simulation from visuals and determinism allowed us to make a quick bot for basic reviews of the game designers' work.

This is how it looks in the editor:

Let's say a game designer is creating a new level and wants to test how it runs. They run a special bot, which checks, using several dozen various seeds, if the level is beatable based on its heuristics. At the end of the bot’s execution, they can see the run’s statistics with various graphs.

This is where we come to the conclusions. In short.

Pros:

• Separation of the model’s logic and presentation;
• Deterministic simulation;
• Custom logic scripting.

Cons:

• Requires “breaking patterns”, time for adjustment, and discipline;
• It may not make sense to use it in small projects, such as hyper-casuals, due to the costs of labor.

Pavel Schevaev, CTO at BIT.GAMES Studio