小游戏算法

---

Canvas-Magic：Canvas + ES6 实现经典小游戏和案例，Bilibili配套视频讲解

五子棋（逐行手敲代码视频讲解）

核心思路：

1. 从当前落子的位置作为切入点，切勿遍历整个棋盘（除非做AI需要）
2. 从落子点向上下、左右、正斜、反斜共4组方向进行查找，判断是否有五子连线
3. 发现从落子点向各个方向查询时坐标的变化规律，查询时记录相同颜色是否达到5

代码实现：

// 判断游戏胜负，(x, y)当前下棋坐标，role：黑1白2，chess：棋盘信息
const isWin = (x, y, role, chess) => [[1, 0], [0, 1], [1, 1], [1, -1]].some(([dx, dy]) => {
  let count = 1, i = 0, j = 0;
  while(count < 5 && chess[x + dx * ++i]?.[y + dy * i] === role) count++
  while(count < 5 && chess[x - dx * ++j]?.[y - dy * j] === role) count++
  return count === 5 && (i = 4 -j, drawLine(x + dx * i, y + dy * i, x - dx * j, y - dy * j, WIN_LINE_WIDTH, WIN_LINE_COLOR), true)
})

2048（逐行手敲代码视频讲解）

核心思路：

1. 先解决一列或一行移动时合并的算法
2. 二维数组通过行列转换算法，将每一列的合并转换成每一行，合并之后再列转回行（PS：毫无疑问，这种解决方法非最优的算法，因为使用了多次转换，但却是最简单的方法，当你解决了一行，就可以解决多行，通过行列转换，就可以解决多列）

代码实现：

// （单行）移动时算法，如[-1,2,1,1] → [-1,-1,2,2]
const move = list => {
  let temp = [], isMerge = false;
  for (let i = list.length - 1; i >= 0; i--) {
    if (list[i] === -1) continue
    if (isMerge && list[i] === temp[0]) {
      maxVal = Math.max(++temp[0], maxVal)
      isMerge = false;
    } else {
      temp.unshift(list[i]);
      isMerge = true
    }
  }
  return new Array(list.length - temp.length).fill(-1).concat(temp)
}

// 二维数组行列转换
const convert = arr => arr[0].map((_, colIndex) => arr.map(row => row[colIndex]))

// 上下左右移动，返回值：新的二维数组
const toUp = data => data.map(row => move(row.reverse()).reverse())
const toDown = data => data.map(row => move(row))
const toLeft = data => convert(convert(data).map(row => move(row.reverse()).reverse()))
const toRight = data => convert(convert(data).map(row => move(row)))

连连看（逐行手敲代码视频讲解）

核心思路：

1. 先判断两点是否在同一条直线上，且是否可连接
2. 由于连连看的规则限制只能拐两次弯，更新移动的位置即可确定P3中间点（如果没有只能拐两次弯的规则，那么就变成很出名的迷宫问题了，很多人把连连看当做迷宫问题来解是错的）

代码实现：

const checkLine = (p1, p4) => {
  let { x: x1, y: y1 } = p1, { x: x4, y: y4 } = p4;
  if (x1 === x4) {
    if (y1 > y4) [y1, y4] = [y4, y1];
    return data[x1].slice(y1 + 1, y4).every(v => v === -1)
  } else if (y1 === y4) {
    if (x1 > x4) [x1, x4] = [x4, x1]
    return data.slice(x1 + 1, x4).every(row => row[y1] === -1)
  }
  return false
}

const checkAll = (p1, p4) => {
  let { x: x1, y: y1 } = p1, { x: x4, y: y4 } = p4;
  for (let [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
    let i = 0, x2 = x1, y2 = y1, p2 = {}, p3 = {};
    while (data[x2 = x1 + dx * ++i]?.[y2 = y1 + dy * i] === -1) {
      p2 = { x: x2, y: y2 };
      p3 = dx === 0 ? { x: x4, y: y2 } : { x: x2, y: y4 };
      // 拐1次弯
      if ((p3.x === x4 && p3.y === y4) && checkLine(p2, p4)) return true
      // 拐2次弯
      if (data[p3.x][p3.y] === -1 && checkLine(p2, p3) && checkLine(p3, p4)) return true
    }
  }
  return false
}

const check = (p1, p4) => {
  if (data[p1.x][p1.y] !== data[p4.x][p4.y]) return false
  // 在同一条直线上
  if (checkLine(p1, p4)) return true;
  // 1次拐弯或2次拐弯
  return checkAll(p1, p4)
}

中国象棋（逐行手敲代码视频讲解）

核心思路：（几乎所有的棋子类的游戏都适用，比如国际象棋，斗兽棋等）

1. 获取被点击棋子的可落子（点位）范围，根据点位判断是否可以落子、是否形成将军等
2. 判断胜负条件：当防守方所有的棋子的所有可子的点位都模拟完毕之后，仍然被攻击方将军，那么判负