H5 Game development: Snake

The difference between eating and colliding is that eating collides with food and colliding with a wall. The author thinks that “eating” and “collision” belong to two branches of three possible results of a snake “movement”. The three possible outcomes of snake movement are “forward”, “feeding” and “collision”.

Look back at the pseudo-code for snake movement:

function move(next) {
	snake.pop() & snake.unshift(next); 
}Copy the code

Next in the code represents the index of the cell the snake head is about to enter. The snake can only “advance” if the cell is 0, “collide” itself when the cell is S, and eat when the cell is F.

I don’t think I hit the wall? In the design process, the author did not design the wall in the stage matrix, but through the index out of the way to represent the wall. Next === -1 means out of bounds and into the wall.

The following pseudocode represents the entire movement of the snake:

// let cell = -1 === next? B : zone[next]; Switch (cell) {// eat case F: eat(); break; Case S: Collision (S); break; Case B: Collision (B): break; // forward default: move; }Copy the code

Random feeding means that an index value of the stage is randomly selected to map the location of the food. This seems simple enough to write like this:

// pseudo-code food = math.random (zone.length) >> 0;Copy the code

If you take into account the premise of feeding without overlapping with the snake, you can see that the random code above does not guarantee that feeding does not overlap with the snake. Because of the security of this algorithm with gambling nature, and it is called “gambling algorithm”. In order to ensure the safety of feeding, the author extended the algorithm:

Function feed() {let index = math.random (zone.length) >> 0; // Is the current location occupied return zone[index] === S? feed() : index; } food = feed();Copy the code

Although the above code can guarantee the absolute safety of feeding in theory, but the author called this algorithm “desperate gambler algorithm”, because the above algorithm has a fatal BUG — super-long recursion or infinite loop.

In order to solve the above fatal problem, the author designed the following algorithm to do random feeding:

Function feed() {let len = zone.length - snake. Length; If (len === 0) return; RND = math.random () * count >> 0 + 1; // Count Spaces while(count! Zone [index++] === 0 && ++count; } return index - 1; } food = feed();Copy the code

The average complexity of this algorithm is O(n/2). Since feeding is a low-frequency operation, O(n/2) complexity does not present any performance problems. However, I think the complexity of this algorithm is a little too high. If you go back to the original “gambling algorithm,” it was a pretty unreliable idea, but it had one advantage — time complexity of O(1).

Probability of “gambling algorithm” = (zone.length – snake. Length)/zone.length. Snake. Length is a dynamic value that ranges from 0 to zone.length. The average reliable probability of “gambling algorithm” is deduced as follows:

The average probability of “gambling algorithm” being correct = 50%

It seems that “gambling algorithms” can be exploited. So the author redesigned an algorithm:

Function bet() {let RND = math.random () * zone.length >> 0; return zone[rnd] === 0 ? rnd : -1; } function feed() { ... } food = bet(); if(food === -1) food = feed();Copy the code

The average complexity of the new algorithm can be effectively reduced to O(n/4), life sometimes needs a bit of luck:).

In View, you can choose a game rendering engine according to your preferences. The author chose PIXI as the game rendering engine in View layer.

View has two main tasks:

1. Draw the interface of the game;
2. Render various data structures in the Model

In other words, a View is the process of restoring the design using a rendering engine. The purpose of this article is to introduce the “snake” implementation ideas, how to use a rendering engine is not the scope of this article, the author would like to introduce is: “how to improve the efficiency of rendering”.

Displaying a Model snake in a View can be as simple as this pseudocode:

View.snake. Clean (); Model.snake. ForEach ((node) => {let viewNode = createViewNode(node); // Combine a new snake with view.snake. Push (viewNode); });Copy the code

The time complexity of the above code is O(n). As mentioned above, snake movement is a high-frequency activity, so we should avoid running O(n) code at high frequencies. To analyze the snake’s three activities: “moving”, “feeding” and “bumping”. First, the Model has a “crash”, and the View should simply pause rendering the state in the Model, the game is dead, and Control takes care of the rest. The snake in the Model does two things in a single “move” : inserts a new node into the top of the table and removes an old node from the bottom of the table; Snakes only do one thing at a time: insert a new node into the head of the list.

If differentiation check is performed on Model’s snake list in View and the View only incrementally updates the difference part, the time complexity of the algorithm can be reduced to O(1) ~ O(2). Here is the optimized pseudocode:

let snakeA = model.snake, snakeB = view.snake; While (snakeb.length <= snakea.length) {headA = snakea.next (); // The head node matches if(heada.data === headb.data) break; If (snakea. HEAD === heada.index) {snakeb. unshift(heada.data); } // Insert a second node into snakeB else snakeb. insertAfter(0, heada.data); }} // Let tailA = snakea. last(), tailB; while(snakeB.length ! == 0) { tailB = snakeB.last(); // If (taila. data === tailb. data) break; // Do not match else snakeb.pop (); }Copy the code

Control does three things:

1. The interaction between the game and the user
2. Driver Model
3. Synchronize View and Model

“Game user interaction” refers to the APIs and events that are available externally to the game process. The APIs planned by the authors are as follows:

The events are as follows:

Events are mounted under the Event object of the game instance.

On ("countdown", (time) => console.log(" countdown: ", time));Copy the code

“Driving Model” does only one thing — updates the orientation of the Model’s snake to that specified by the user. “Synchronize View with Model” is also relatively simple. Check whether the Model is updated, and notify the View to update the game interface if there is an update.

Here is the qr code of the online DEMO of snake introduced by this article:

The source code of the game is hosted at: github.com/leeenx/snak…

Thank you for reading this article patiently. This article only represents the author’s personal views, if there is anything inappropriate, please feel free to comment.

Convex laboratory
Aotu. IO/notes / 2017 /…

Last update: 2017-09-27 14:05:21