How to create a three elimination game

This article was first published on WeChat public “Shopee Technical team ”.

Abstract

Various styles “ Xiaoxiaole ” The game must be familiar to everyone , The secret of customs clearance is to pair and eliminate three or more identical elements , Usually we call this kind of game “ Three elimination ” game .Shopee Three elimination games embedded in the shopping platform Shopee Candy It is also loved by many users , This article will take you from the origin of the project 、 Learn how to create such a small three elimination game from the aspects of game architecture and project toolset .

1. Project Origin

1.1 Introduction to the game

Shopee Candy It is a three consumer leisure product for multi regional markets H5 game , Users can get Shopee Coins、 Merchant shopping coupons and other preferential rewards , It can not only enhance user stickiness , Encourage users to consume , It can also drain water for businesses . meanwhile , Share and receive awards 、 Mechanisms such as friend leaderboards enhance the sociality of the game , It has played a new role for the platform . Besides ,H5 The game is simple 、 Light weight 、 The characteristics of high adaptation and Shopee The user's usage habits fit very well , You can click and play , The participation threshold is low while taking into account the interest .

2020 year 6 month ,Shopee Candy stay Shopee The whole market goes online , Introduction iOS And the official version of Android . Since launch ,Shopee Candy Perform brilliantly in daily and promotional activities , The user's activity and online time have reached record highs .

Shopee Candy The theme of colorful and lovely candy elements is used in the style ; The playing method is mainly to limit the number of operation steps at the same time , Set the number of collected elements as the customs clearance condition . Inside the level , Users exchange adjacent candy , Connect three or more candies of the same color , Can trigger the elimination of ; According to the number and shape of eliminated candy, prop elements with special elimination ability can also be generated ; The mode includes level mode and endless mode .

1.2 Project brief introduction

As the project continues to evolve ,Shopee Candy Functional iterations can be clearly divided into four categories . The first is all kinds of business function modules （ Props Mall 、 Task system and exchange store ）; The second is the algorithm responsible for eliminating logic , score 、 Algorithm library of level progress （Algorithm SDK） And the animation system responsible for eliminating the effect ; Finally, there are various tools to serve the game , Including the liberation of design level productivity Map Editor Level editor , Can quantify the difficulty of the level Score Runner The running separator and the device that can operate the reset Replayer Playback tools, etc .

2. Game structure

2.1 Algorithm library （Algorithm SDK）

As a three elimination game with rich elements ,Shopee Candy The algorithm part of is very important and complex . As early as the beginning of the project , Algorithm and animation are coupled together . With the launch of products and the increase of elimination types , We slowly find that the cost of project maintenance is getting higher and higher ; At the same time, the algorithm itself is independent , It doesn't depend on animation and business , So the algorithm part is pulled out .

2.1.1 Algorithm SDK Realization

Algorithm SDK There are three main parts to realize ：Map、Operator as well as Logic Processing.

Map （Map）

Map Managed map objects and element objects in game levels . According to the characteristics of each element, we carry out the upper 、 in 、 Three levels of Management , This element layered architecture mode can meet the addition of new elements with different special effects . The elements of each layer restrict each other 、 interact , Complement each other in the elimination process , Complete the gorgeous 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(/* ... */);
  }
}

operation （Operator）

Operator Manage all feasible operations of the algorithm , As a whole Algorithm SDK A bridge for external communication , Be responsible for receiving external exchange 、 Double click and other operation signals , Call the corresponding algorithm . stay Shopee Candy In the call of the main process ,Operator Will collect animation data , And communicate with the animation system .

//  Element exchange 
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
}

Logical operations （Logic Processing）

Algorithm Yes Algorithm SDK Manage all logical operations , Include ： There is a solution at the beginning, guarantee 、 Solution detection 、 eliminate 、 Drop, etc , As a whole Algorithm SDK At the heart of .

When elements in the process eliminate multiple loops , There may be a problem that the logic execution takes too long , Cause the user to lose the frame during operation . To avoid that , We divide logical operations into segments , Asynchronous computing , Send data to animation execution in advance , The subsequent operations are completed in different frames .

2.1.2 Algorithm SDK unit testing

In terms of implementation, we have achieved separation and decoupling as much as possible , But for a huge algorithm library , Light is conventional Code Review It's not enough , Front end testing is very important .

Unit test introduction

Many people say that front-end testing is a waste of time and has little effect , Regular front-end businesses do change frequently , Include Shopee Candy The business view of is also constantly changing . But thanks to the separation and independence of the algorithm library , We can do it without UI、 Pure logic unit testing .

Unit test application

Manual testing can only ensure that the code does not report errors and the layout is good after operation , However, many situations such as incorrect number or score of eliminated elements cannot be found . A move or double-click operation of a user in a project , Control the same layout , Finally, the same result is obtained . This result includes the data of the final map 、 User scores 、 The number of elements collected or destroyed, etc , Ensure stability in 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');
      //  Score comparison 
      expect(data1.score).equal(data2.score).equal(150);
      //  Step comparison 
      expect(data1.passStep).equal(data2.passStep).equal(14);
    });
});

2.2 Animation system （Animation）

After the animation is separated from the algorithm , Animation alone as a system , This has the following advantages ：

• High cohesion and low coupling ： Both algorithm and animation have high complexity , After separation, the system complexity is reduced , At the same time, the module is more cohesive ;
• high efficiency ： The execution of the algorithm does not have to wait for the animation , It improves the calculation efficiency ;
• High flexibility ： After the algorithm removes the dependence on animation , Can well support skipping Bonus、 Requirements such as running separator .

2.2.1 The project design

After separating the animation system , Need to establish a communication mechanism with the algorithm , To ensure that the elimination result of the algorithm has corresponding animation playback . The implementation of communication is as follows ：

• Establish an event mechanism , Algorithm and animation communicate with each other through events ;
• Define the animation data structure , Distinguish animation by defining different animation types , For example, elimination and falling animation , At the same time, define complete animation information , The animation system parses and plays the corresponding animation .

For animation playback , We introduced a set of 「 Animation queue 」 The process of . Add the animation data parsed by the algorithm to the queue , Recursive playback queue , Until the queue is empty , End the animation .

When playing a single animation from a queue , In order to ensure that the animation of each element does not affect each other , The animation system adopts 「 The strategy pattern 」 Design , Different elimination strategies are implemented according to the type of animation , Animate the element 「 cohesion 」 Into their respective strategies and methods .

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

// Acquisition strategy 
function getStrategy(elementType):IElementStrategy{
    return animStrategyCfg.get(elementType);
}

// Execution strategy 
function executeStrategy(elementType){
    const strategy = getStrategy(elementType);
    return strategy.execute();
}

The algorithm is responsible for calculating the elimination logic , The animation system is responsible for playing the corresponding animation , In addition to playing special effects such as keel , You can also manipulate the size of chessboard elements 、 Location and display . Under normal circumstances, the state of the chessboard and the algorithm state should be consistent after the animation is played , But in rare cases, it may be due to equipment performance and other reasons , Cause timing 、 Timer exception and other problems , This leads to the inconsistency between the two states , For example, elements are not displayed or misplaced .

therefore , After the animation , need 「 The underlying logic 」 Get the algorithm status in real time , Check and correct chessboard status , Match it , Avoid presentation mistakes . meanwhile , To avoid performance problems , This is not a full calibration correction , But only for error prone middle-level elements .

2.2.2 Solve callback hell

The game engine's own animation library uses callback to execute the logic after the animation is completed , In the case of complex animation , Callback nesting is often used , Makes logic difficult to understand and maintain . In order to solve the problem of callback to hell , We encapsulate... On the prototype chain of the animation library promise Method , So you can use it async/await Synchronous writing .

function animation(callback: Function) {
    tweenA.call(() => {
        tweenB.call(() => {
            tweenC.call(() => {
                sleep.call(callback);
            });
        });
    });
}

async function animation() {
    await tweenA.promise();
    await tweenB.promise();
    await tweenC.promise();
    await sleep.promise();
}

The above shows the effect of changing from callback writing to synchronous writing , You can see that the synchronous writing method is more intuitive , Solved the problem of callback to hell , Easier code maintenance .

3. Project Toolset

Previously, I introduced Shopee Candy Algorithm library and animation system , In fact, our team has also made a lot of tools .

3.1 Map Editor

stay Shopee Candy At the beginning of the game , We need to make a tool that can not only flexibly configure levels, but also test level playability and clearance rate .

In daily work , Drag and drop 、 Keyboard shortcuts can quickly configure level chessboard elements .

At present, chessboard elements have developed to 30 Multiple , There are complex mutually exclusive coexistence rules between various elements ：

• coexistence ：A Elements and B Elements can appear on a grid at the same time ;
• Mutually exclusive ：A Elements and B Elements cannot appear on a grid at the same time ;
• Big mutual exclusion ：A Elements and B Elements cannot appear on a chessboard at the same time .

Facing the relationship between so many elements , It is not appropriate to manually handle the mutual exclusion relationship when configuring the level by relying solely on planning ,

Therefore, a relational mutex table is needed to maintain the relationship between elements . We go through Map Editor The server pulls the data of this table , Return it to Web End , Give some wrong feedback while doing a good job in relationship constraints .

3.2 Score Runner

In the early stage of Launch , One of the problems encountered is that the speed of level planning can not catch up with the speed of user clearance , Users often rush to change checkpoints . The design amount of a three elimination game is often thousands of levels , For any team, it is a huge difficulty in R & D work . among , The most troublesome and time-consuming thing in planning a level is the difficulty of level testing and adjustment , Each adjustment should be repeated manually for many times , Then count the customs clearance rate .Score Runner It is a tool that can solve the red boring and time-consuming process in the figure .

Score Runner Realization

Let's first look at the layout of one of the levels , There are many possibilities for operations that can be eliminated on the field , If you think of these possibilities as a network of data , Simulating the operation of users is nothing more than these possibilities .

that , What's next ？ There are different layouts behind these possible operations , There will be more different possibilities . The process is as follows ：

• Traverse the map to obtain the possibility of each operation ;
• According to each operation , Continue to acquire the possibility of the next step until the last step （ Pass or fail ）;
• Get all the steps , You can get the maximum and minimum clearance scores .

As you can see from the diagram , Every possibility can come to the end , But in fact, there are many possibilities that users will not operate , For example, those who score less , Operations that do not eliminate meaning, etc , It is unscientific for customs clearance rate , And it's very inefficient for computing .

So we joined Smart strategy , Calculate the data set of possibility elimination to obtain the operation weight order . The operation with the highest weight is the best possibility , Prune the current huge network of possibilities , Get a more consistent Customs clearance rate .

example ：

checkpoint	Average customs clearance rate （100 Time ）	Customs clearance records （%）
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 customs clearance success rate , It can reduce the verification time of planning for the difficulty of the level .

3.3 Replayer

stay Score Runner after , We use Replayer Playback the running process , To verify the correctness of running points .

During playback , The first problem is to ensure that every random result is consistent with the running time . How to ensure ？

Random seeds Is the answer to this question . Random seed is a kind of seed that takes random number as the object , With a true random number （ seeds ） Is a random number with initial conditions . Simply put, it is to set a fixed seed , Output result 、 Pseudorandom methods in exactly the same order .

To access random seeds , We adopt a new random number strategy , This strategy can set random seeds , And every time we use the random number as the seed calculation result based on the last random number result .

This strategy ensures that every random number in the whole game is recorded , Every random result can be obtained at any time .

At the same time, this strategy also has the following benefits ：

• Traceability of logical algorithm execution ;
• Traceability of random numbers after disconnection and reconnection ;
• The feasibility of the whole game steps of users on the double disk online ;
• Very little data storage .

4. The future planning

This paper starts from the origin of the project 、 The game architecture and project toolset are introduced Shopee Candy The game .

“Rome wasn't built in a day”, after “ demand —— restructure —— go online ” The cycle of can create a more perfect project , In the follow-up, we will face from the following aspects Shopee Candy Perfect and optimize ：

1） Realize configuration development for new elements , Reduce development costs

At present, the development of new elements still needs to invest more manpower , Plan to combine algorithm library （Algorithm SDK） And Map Editor Implement element attribute classification 、 Layered and other configuration development , The development of new elements can be realized only by adding configuration algorithm and element animation .

2） Provide a smoother game experience for low-end devices

Shopee Candy It is a strong game project , Pay special attention to game performance and operation feel . Due to the uneven performance of mobile devices on the market , We need to pay more attention to the user experience of low-end devices . Subsequently, optimization strategies for logic and view performance will be formulated for low-end devices , Provide users with a smoother game experience .

3） Operational behavior verification , Avoid cheating

The front end increases the cracking cost by means of confusion or encryption , But it can't completely prevent cheating . at present , The project is developing operation behavior verification service , Combine existing Replyer The function performs secondary operation verification for suspicious settlement behavior , So as to ensure the fairness of the game .

4） Using machine learning for level design

at present ,Shopee Candy Thousands of levels have been developed . In order to improve the efficiency of level configuration , The follow-up plan combines machine learning and Score Runner Statistical clearance rate for model training , Only a small amount of manual configuration is required to automatically generate levels .

The author of this article Shopee Games - Candy The front-end team .

Join us We will not only make some game marketing tools , And play real games ！ business 、 To develop 、 checkpoint 、AR、PVP etc. , Up to dozens and increasing .“ interesting ” Is our original intention and goal of playing the game , Because we believe , Games can build emotions 、 Close up , Bring happiness to users , Create value for the platform . At present, a large number of iOS、 front end 、 Back end 、 test 、 Big data development job vacancy , Interested students can send their resume to ：[email protected]（ Please indicate the subject of the email ：Shopee Games - From the technology blog ）.