preface

As a front end siege lion, write a fake front end Topic, what the hell? You say a good front end does not do, make what fake front end?

FBI WARNING: Authentic front-end knowledge moving column in the next big god series

FBI WARNING

If you want authentic front-end knowledge, get out and turn left, see Lao Wang.

In this Topic series, I will try my best to talk about some interesting things that may not be related to front-end knowledge. I hope to share with you some logic problems and algorithm problems encountered in my practice as well as some other knowledge.

Mine clearance

In the spare time, have the habit of extracurricular development. The goal is to get yourself out of repetitive business code and do something interesting. One of my favorite games as a child was minesweeper, which led to the first article in this series, The Minesweeper of The Fake Front.

Rules of the summary

After I wrote this thing, I asked some students to play:

“Mine clearance ~~ no ~”

“Do not know how to play ~~ before are blind point.”

In view of this, popular some rules, familiar students skip:

Minesweeper is a grid!!

Of course, there is a trick: the grid number represents how many mines are hidden in a circle of eight cells.

Accidentally exposed the hand speed of being single for 20 years ~

Initialize the game implementation

Many students use canvas to implement games for the convenience of data rendering view and refresh of game state.

For this series of minesweeper, I used vUE to synchronize my data and view, why not canvas? Fake front-end series will have a large wave of canvas articles in the future, not here for the time being.

A grid

In this step, consider what data structure we will use to represent the entire game minefield.

That’s right, a two-dimensional array. But can we just do it with a one-dimensional array? Absolutely. So let’s do this with a two-dimensional array, intuitive.

const SAFE_CELL = 0 export default { // ... // Generate a 15-row, 10-column two-digit array data () {return {dataList: (new Array(15)) .fill(0) .map( it => (new Array(10)) .fill(SAFE_CELL) ) } } // ... }Copy the code

We set const SAFE_CELL = 0 as the default padding, which means there are no mines around, so a blank mine area appears.

Tiling algorithm

In the game, the distribution of mines is completely random. You have to use some logic to figure it out. Here, I chose const MINE_CELL = 9 as the mine identifier because 1 to 8 is used to identify the number of mines in the vicinity. This number is the number of mines in the vicinity.

So, how do we randomly distribute a certain number of mines across the entire two-dimensional array?

The requirement for a random distribution here is simple:

  1. The amount of thunder is fixed
  2. Each cell has the same probability of being a ray

Perhaps the first thing that comes to mind is the substitution method: Randomly pick out any cell in this two-dimensional array that is not a mine and replace it with a mine.

That seems like a good plan. Actually, there is a problem. What’s the problem?

If the density of mines reaches a certain height, it is very difficult to pick a cell that is not a mine. For example, a 10 * 10 minefield contains 99 mines. Then it is very difficult for the 99th mine to find the remaining two safe_cells. Not only is it time consuming, but it’s easy to get into a loop, and the solution has to be abandoned.

So if I don’t make the substitution, is there another way?

[Insert method], generate a SAFE_CELL number of one-dimensional array, randomly insert thunder into the array, and then split into a two-dimensional array. For example, there are 10 mines in a 10 * 10 minefield, and my husband’s 90 degree size is an array. Then he randomly inserts 10 mines into the array, and finally splits it into a 10 * 10 two-dimensional array.

It looks like a perfect solution to the problem of infinite looping, but we know that adding and deleting elements in an array is very costly. We add or subtract one element in the array, and the table below each element after that has to be shifted accordingly.

Here, I introduce my tiling idea:

Generate a one-dimensional ordered array containing all mines and empty areas, shuffle the array out of order, and finally split it into a two-dimensional array.

const SAFE_CELL = 0 const MINE_CELL = 9 export default { methods: { //... InitData () {const rows = 15 const cols = 10 const mines = 10 const safeCellNum = rows * cols-mines const safeArea = (new Array(safeCellNum)).fill(SAFE_CELL) const mineArea = (new Array(mines)).fill(MINE_CELL) let totalArea = Safearea.concat (mineArea) totalArea = this.mineshuffle (totalArea) // Shuffling this.datalist = totalArea.reduce((Memo, curr, index) => { if (index % cols === 0) memo.push([curr]) else memo[memo.length - 1].push(curr) return memo }, []) } } }Copy the code

This involves a shuffling algorithm, and I’ll briefly introduce it. Predecessors implemented a variety of shuffling algorithms, performance and effect are different. Here, I choose the Fisher-Yates Shuffle algorithm with excellent performance and effect and very simple implementation. If you’ve noticed the LoDash source code, shuffle in LoDash is also implemented using this algorithm

The idea is to swap the unscrambled element from the tail with a random unscrambled remaining element until all the elements in the array are scrambled.

Here is my implementation:

export default { methods: { //... // Fisher -- Yates shuffle algorithm mineShuffle (array, mine = array.length) { let count = mine let index while (count) { index = Math.floor(Math.random() * count--) ; [array[count], array[index]] = [array[index], array[count]] } return array } } }Copy the code

In the code, element transposition takes advantage of ES6’s deconstructive assignment, and there are no performance issues since the element’s value is transposed in place.

It can be clearly seen from the comparison in the figure that the Fisher-Yates shuffling algorithm is stable at about 70 ms in the browser environment for the million-length array. However, the same O(n) time complexity of the insertion algorithm, when dealing with the same length of the array, the performance lags far behind!

After shuffling, we split the array into two-dimensional arrays for VUE to render. At this point, our view renders:

Computing environment numbers

With a mine, it is time to calculate the number of mines in the environment around the mine. The meaning of this number is to identify how many mines are hidden around this number, as explained in the rules section.

Calculating the ambient number is easy. Loop through the two-dimensional array. If the cell is a landmine, add the digits of all surrounding words +1. Notice the edges of the grid.

const AROUND = [ [-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1] ] const MINE_CELL = 9 export default { methods: { // ... SetEnvNum () {this.datalist. ForEach ((row, rowIndex) => {row.foreach ((cell, colIndex) => { if (cell === MINE_CELL) { AROUND.forEach(offset => { const row = rowIndex + offset[0] const col = colIndex + offset[1] if ( this.dataList[row] && this.dataList[row][col] ! == undefined && this.dataList[row][col] ! == MINE_CELL ) this.dataList[row][col]++ }) } }) }) } } }Copy the code

At this time:

A small summary

At this point, we have finally generated an initial mine field with randomly distributed mines and the correct numbers around them.

In the process of implementation, let’s summarize:

  1. Think before you act.
  2. Always consider the logical margins of your code and how it might break.
  3. Get the details right

Next, we need to add various states to the grid in the minefield to hide the mines. At the same time, tie events to the grid.

In the process of binding events, there is fun to think about. Look forward to it.