This article was first published on the wechat public account “Shopee Technical Team”.

Abstract

Everyone is familiar with a variety of “match-3” games, where the trick is to match three or more of the same elements to eliminate, often referred to as “match-3” games. Shopee Candy, a match-3 game embedded in the Shopee shopping platform, is also popular with many users. This article will take you through the origins of the project, the game structure and the toolset of the project to learn how to create a match-3 game.

1. Project origin

1.1 Introduction to the Game

Shopee Candy is a three-consumer casual H5 game for multi-regional markets. Users can get preferential rewards such as Shopee Coins and merchant shopping vouchers in the game, which can not only enhance user stickiness and motivate users to consume, but also attract merchants. At the same time, sharing awards, friends leaderboards and other mechanisms enhance the social nature of the game, play a new role for the platform. In addition, the features of SIMPLE, lightweight and highly adaptable H5 games are very consistent with the usage habits of Shopee users. It can be played on the spot, and the participation threshold is low while taking into account the fun.

In June 2020, Shopee Candy launched its official iOS and Android versions on Shopee. Since its launch, Shopee Candy has performed brilliantly in daily and promotional activities, and users’ activity and online duration have repeatedly hit new highs.

Shopee Candy uses colorful and lovely Candy element theme in style; In terms of gameplay, the number of collected elements is set as the condition for completing the game while limiting the number of operation steps. Within the level, the user can trigger elimination by exchanging adjacent candies to connect three or more candies of the same color. Item elements with special elimination abilities can be generated based on the number and shape of the eliminated candy. Modes related to card mode and endless mode, etc.

1.2 Project Introduction

As the project evolves, Shopee Candy’s functional iterations can be clearly divided into four categories. Firstly, various business function modules (prop mall, mission system and exchange store, etc.); The Algorithm SDK is responsible for eliminating logical algorithms, calculating scores and level progress, and the animation system is responsible for eliminating effects. Finally, there are tools for games, including the Map Editor, a level Editor that frees up the productivity of designing levels, the Score Runner, which quantifies the difficulty of levels, and the Replayer playback tool, which allows you to replay actions.

2. Game architecture

2.1 Algorithm SDK

As a match-3 game with a wide variety of elimination elements, Shopee Candy’s algorithmic part is important and complex. From the beginning of the project, the algorithm and animation were coupled together. With the increase of product launches and elimination categories, we gradually found that project maintenance costs were getting higher and higher; At the same time, the algorithm itself is independent and has no dependence on animation and business, so the algorithm part is removed from it.

2.1.1 Algorithm SDK implementation

The Algorithm SDK consists of three parts: Map, Operator and Logic Processing.

Map

A Map manages Map objects and element objects in a game level. According to the characteristics of each element, we manage the elements in three layers: upper, middle and lower. This layered architecture mode can meet the needs of adding new elements with different effects. Each layer of elements interact and influence each other, complementing each other in the elimination process to achieve the magnificent elimination effect in the game.

export default class Grid {
  public middle: CellModel;
  public upper: Upper;
  public bottom: Bottom;

  constructor(info: ICellInfo) {
    const { type } = info;

    this.upper = new Upper(/ *... * /);
    this.middle = new CellModel(/ *... * /);
    this.bottom = new Bottom(/ *... * /); }}Copy the code

Operator

Operator manages all feasible operations of the Algorithm, serves as a bridge for the communication between the whole Algorithm SDK and the outside, and is responsible for receiving external switching, double-clicking and other operation signals, and calling the corresponding Algorithm. In the invocation of the Shopee Candy main flow, the Operator collects animation data and communicates with the animation system.

// Element swap
export function exchange(startPos, endPos) :IAnimationData {
  // ... logic process
  // returns animation data
}

// Double-click the element
export function doubleClick(pos) :IAnimationData {
  // ... logic process
  // returns animation data
}
Copy the code

Logic Processing

Algorithm manages all logical operations of the Algorithm SDK, including: deployment with solution guarantee, solution detection, elimination, drop, etc., which is the core of the whole Algorithm SDK.

When elements in the process are eliminated multiple times, the logic can take too long to execute, causing frames to be lost during user actions. To avoid this, we split the logical operation into multiple segments, make the calculation asynchronous, send the data to the animation ahead of time, and do the rest in different frames.

2.1.2 Algorithm SDK unit test

In terms of implementation, we have achieved separation and decoupling as much as possible. However, for the huge algorithm base, the routine Code Review alone is far from enough, and the front-end test is very important.

Introduction to Unit Tests

Many people say that front-end testing is a waste of time and ineffective, and the normal front end business does change a lot, including Shopee Candy’s business view. But thanks to the separation and independence of the algorithm library, we can do uI-free, purely logical unit tests on it.

Unit test application

Manual testing can only ensure that the code does not report errors after operation and that the layout is nice and messy, but it cannot detect and eliminate many cases such as incorrect element count or score. In the project, a user’s movement or double click operation, controlling the same layout, finally get the same result. This result includes data from the final map, points earned by the user, and the number of elements collected or destroyed, ensuring stability over multiple iterations.

describe('BOMB'.() = > {
    it('Exchange each other should be the same crush'.() = > {
      const source = { row: 0.col: 3 };
      const target = { row: 1.col: 3 };
      const wrapper = mapDecorator(operator);
      const data1 = wrapper({ key: CRUSH_TYPE.BOMB }, source, target);
      const data2 = wrapper({ key: CRUSH_TYPE.BOMB }, target, source);
      // Map comparison
      expect(JSON.stringify(data1.map)).equal(JSON.stringify(data2.map)).equal('xxx');
      // Compare scores
      expect(data1.score).equal(data2.score).equal(150);
      // Compare steps
      expect(data1.passStep).equal(data2.passStep).equal(14);
    });
});
Copy the code

2.2 Animation system

After animation and algorithm are separated, animation is used as a separate system, which has the following advantages:

  • High cohesion and low coupling: both the algorithm and animation have high complexity. After separation, the system complexity is reduced, and the modules are more cohesive.
  • High efficiency: the execution of the algorithm does not need to wait for animation, which improves the calculation efficiency;
  • High flexibility: The algorithm supports skipping Bonus, runners, and other requirements nicely without the dependency on animation.

2.2.1 Scheme design

After the separation of the animation system, a communication mechanism needs to be established with the algorithm to ensure that the elimination results performed by the algorithm have corresponding animation playback. The communication is implemented as follows:

  • The algorithm and animation communicate with each other through the event mechanism.
  • Define animation data structure, distinguish animation by defining different animation types, such as elimination and falling animation, and define complete animation information, which is parsed by animation system to play the corresponding animation.

For animation playback, we introduced a set of “animation queue” process. The animation data parsed by the algorithm is added to the queue, and the queue is recursively played until the queue is empty and the animation is played.

When a single animation is played from the animation queue, in order to ensure that the playback of each element animation does not affect each other, the animation system adopts the “strategy mode” design, executes different elimination strategies according to the type of animation, and “cohesion” the animation of elements into their respective strategy methods.

// Policy configuration
const animStrategyCfg: Map<TElementType, IElementStrategy> = new Map([
    [AElement, AStrategy],
    [BElement, BStrategy],
    [CElement, CStrategy],
]);

// Get the policy
function getStrategy(elementType) :IElementStrategy{
    return animStrategyCfg.get(elementType);
}

// Execute the policy
function executeStrategy(elementType){
    const strategy = getStrategy(elementType);
    return strategy.execute();
}
Copy the code

The algorithm computes the elimination logic, and the animation system plays the corresponding animation. In addition to playing special effects such as the keel, it also manipulates the size, position and display of the board elements. Under normal circumstances, the state of the checkerboard and the state of the algorithm should be consistent after the animation is played. However, in rare cases, due to equipment performance and other reasons, problems such as timing sequence and timer abnormality may be caused, and then the two states are inconsistent, such as element not displayed or position dislocation.

Therefore, after the animation, the “bottom-of-the-pocket logic” needs to obtain the algorithm state in real time, verify and correct the checkerboard state, make it match with it, and avoid errors on display. Also, in order to avoid performance problems, this is not a full validation fix, but only for error-prone mid-level elements.

2.2.2 Fix callback hell

The animation library of the game engine adopts the callback method to execute the logic after the animation is completed. In the case of complicated animation, the callback nested writing method often appears, which makes the logic difficult to understand and maintain. To solve the callback hell problem, we wrapped the Promise method on the prototype chain of the animation library so that we could write async/await synchronously.

function animation(callback: Function) {
    tweenA.call(() = > {
        tweenB.call(() = > {
            tweenC.call(() = > {
                sleep.call(callback);
            });
        });
    });
}
Copy the code
async function animation() {
    await tweenA.promise();
    await tweenB.promise();
    await tweenC.promise();
    await sleep.promise();
}
Copy the code

This shows the effect of switching from callback to synchronous, which is more intuitive, eliminates callback hell, and makes code maintenance easier.

3. Project toolset

The algorithm library and animation system of Shopee Candy were introduced earlier. In fact, our team also made many tools.

3.1 the Map Editor

At the beginning of The Shopee Candy game, we needed to create a tool that could flexibly configure levels as well as test their playability and completion rates.

In everyday work, level board elements can be quickly configured by dragging and dropping and keyboard shortcuts.

At present, the board elements have grown to more than 30, and there are complex mutually exclusive coexistence rules between each element:

  • Coexistence: elements A and B can appear on the same grid at the same time;
  • Mutually exclusive: elements A and B cannot appear on the same cell at the same time;
  • Large mutex: Elements A and B cannot appear on the same board.

With so many relationships between elements, it is not appropriate to rely solely on planning to manually handle the mutual exclusion when configuring levels, so a relational mutex table is needed to maintain the relationship between elements. We use the Map Editor server to pull the data from this table and send it back to the Web server to give some error feedback while doing a good job of relationship restriction.

3.2 Score Runner

In the early stage of launch, one of the problems we encountered was that the speed of level planning could not catch up with the speed of users’ clearance, and users often urged more levels. A match-3 game with thousands of levels is a huge challenge for any team. Among them, the most troublesome and time-consuming planning level is the difficulty test and adjustment of the level, each adjustment should be repeated manually for many times, and then statistics of the clearance rate. Score Runner is a tool that can solve the tedious and time-consuming process in red.

Score Runner achieve

Let’s look at the layout of one level. There are many possibilities for the operations that can be eliminated on the field. If you look at these possibilities as a mesh structure of data, there are no more than these possibilities for simulating the operation of the user.

So what’s the next step? With different layouts behind these possibilities, there are more different possibilities. The process is roughly as follows:

  • Traversing the map to capture the possibility of each action;
  • With each action, continue to capture the possibility of the next step until the last step (pass or fail);
  • You get all the steps, and you get the maximum and minimum clearance scores.

As can be seen from the figure, every possibility can come to the end, but in fact, users will not operate many possibilities, such as those with low scores and operations without elimination significance, which are unscientific for clearance rate and very low for computing efficiency.

So we added the cleanness strategy, calculated the data set of possibility elimination to get the operation weight order. Taking the operation with the highest weight as the best possibility, the current huge network of possibilities is pruned to get a more consistent clearance rate.

Ex. :

checkpoint Average clearance rate

(100)		 Customs clearance record

(%)
341 65% 63/62/71
342 68% 65/63/76
343 60% 56/57/67
344 60% 63/64/56
345 47% 46/47/47
346 51% 51/52/49
347 50% 50/52/42
348 47% 51/38/51
349 63% 65/61/62

By analyzing the average success rate of a level, you can reduce the time it takes to validate the difficulty of a level.

3.3 Replayer

After the Score Runner, we used Replayer to replay the scoring process to verify the correctness of the scoring.

In replay, the primary problem is to ensure that each random result is consistent with the run time. How to guarantee?

Random seeds are the answer to this question. Random seed is a random number as the object, with true random number (seed) as the initial condition of random number. In simple terms, it is a pseudo-random method that sets fixed seeds and outputs the results in exactly the same order.

In order to access the random seed, we adopt a new random number strategy, which can set the random seed, and each random number is based on the last random number result as the seed calculation results.

This strategy ensures that every random number is recorded and every random result is readily available throughout the game.

At the same time, this strategy also has the following gains:

  • Traceability of logical algorithm execution;
  • Traceability of random number after reconnection;
  • Feasibility of replicating the whole game steps of online users;
  • Minimal data storage.

Plan for the future

This article introduces Shopee Candy from the perspective of project origin, game structure and project toolset.

“Rome wasn’t built in a day”, a more perfect project can be created through the cycle of “demand — reconstruction — online”. In the future, we will improve and optimize Shopee Candy from the following aspects:

1) Implement configuration development for new elements to reduce development costs

At present, the development of new elements still needs a lot of manpower. We plan to combine Algorithm SDK and Map Editor to achieve the configuration development of element attribute classification and stratification, and only need to add the configuration Algorithm and element animation to achieve the development of new elements.

2) Provide a smoother gaming experience for low-end devices

Shopee Candy is a strong gameplay project with a strong focus on game performance and handling. Due to the uneven performance of mobile devices in the market, more attention needs to be paid to the user experience of low-end devices. In the future, optimization strategies for logic and view performance will be developed for low-end devices to provide users with smoother game experience.

3) Operation behavior verification to avoid cheating

The front-end relies on obfuscation or encryption to increase the cost of cracking, but it cannot completely prevent cheating. Currently, the project is developing an operational behavior verification service, which combines the existing Replyer function to perform a secondary operation verification of suspicious settlement behavior to ensure the fairness of the game.

4) Level design using machine learning

So far, Shopee Candy has developed thousands of levels. In order to improve the efficiency of level configuration, we plan to carry out model training based on machine learning and Score Runner statistics, and only a small amount of manual configuration is required to automatically generate levels.

In this paper, the author

Shopee Games – Candy front end team.