Canvas实现2048最简单的算法

前言

最近新开了一个专栏，纯Canvas实现一些经典的小游戏，如五子棋、2048、连连看等，主打是纯Canvas + 简洁的ES6语法 + 独特的算法。今天我们给大家讲的是2408！

试玩（数字版）：gaoxiaosi.github.io/canvas-magi…

试玩（图片版）：gaoxiaosi.github.io/canvas-magi…

源码地址：github.com/gaoxiaosi/c…

算法

Canvas绘制格子的部分，没有什么难度，感兴趣的可以看我的源码。我们今天直接讲算法。

首先，需要对数据结构进行说明：这里不会使用2、4、8、16去表示格子的值，我们采用0、1、2、3去表示，这样之后如果需要更换成A、B、C、D或者图片之类的会更加方便，空格部分用-1表示。因此我们数据结构是一个4*4的二维数组，并生成一个16宫格的游戏页面，代码及效果如下所示：

let data = Array.from({ length: 4 }, () => Array(4).fill(-1))
data[1][0] = 0;
data[1][1] = 0;
data[2][1] = 1;

当我们向下移动时，本质就是对4列数据分别进行移动合并操作。因此，只要我们解决1列数据就可以解决4列数据，问题就变成一个数组的移动合并，现在开始写这个算法：

const move = list => {
  // 将-1过滤掉
  let result = list.filter(item => item !== -1);
  // 从后往前遍历
  for (let i = result.length - 1; i > 0; i--) {
    // 当后一项 = 前一项时，后一项的值 +1，删除前一项，同时 i-1 跳过前一项
    if (result[i] === result[i - 1]) {
      result[i]++;
      result.splice(--i, 1); 
    }
  }
  // 空的位置用-1补够数组长度即可
  return new Array(list.length - result.length).fill(-1).concat(result)
}

监听键盘按下事件

一般的代码写法，使用switch循环

document.addEventListener('keydown', e => {
  switch (e.key) {
    case 'ArrowDown':
      toDown()
      break;
    case 'ArrowUp':
      toUp()
      break;
    case 'ArrowLeft':
      toLeft()
      break;
    case 'ArrowRight':
      toRight()
      break;
  }
})

这里的话我推荐大家使用策略模式试试（如果参数一样的情况下），更加简洁优雅，代码如下：

document.addEventListener('keydown', e => keydownEvent[e.key]?.())
const keydownEvent = {
  ArrowUp: toUp,
  ArrowDown: toDown,
  ArrowLeft: toLeft,
  ArrowRight: toRight
}

向下

接下来我们先看看向下：

1. 单列算法依次代入4列
2. 将得到的新数据赋值回给data
3. 根据data更新视图

// 向下
const toDown = data => data.map((col, index) => move(col, index))
document.addEventListener('keydown', e => {
  let cb = keydownEvent[e.key]
  cb && (data = cb(JSON.parse(JSON.stringify(data)))
})
const update = （） => {
  // 根据新的data更新视图
  paint(data) {}
}

向上

1. 数组反转代入算法处理
2. 将处理后的数据反转再赋值回给data
3. 根据data重新更新视图

// 向上
const toUp = data => data.map(col => move(col.reverse()).reverse())

二维行列转换方法

至于向左、向右，我们可以运用行列转换的方法，将行的数据转换成列的数据，处理之后再将列转换回行。所以，我们先写一个二维数组行列转换的方法，使用ES6一行代码即可搞定。

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

向右

// 向右（行列转换 → 返回新数据 → 行列转换）
const toRight = data => convert(convert(data).map(col => move(col)))

向左

// 向左（行列转换 → 返回新数据 → 行列转换），再加上数据reverse
const toLeft = data => convert(convert(data).map(col => move(col.reverse()).reverse()))

总结

这不是最优的算法，毕竟对数据进行进行大量的转换处理，但这应该是最简单的思路。只要解决单列数据，其他方向都可以进行适当行列转换和数据反转即可，整体的逻辑还是比较简单的。当然，如果要做动画的话，还是要记录一下点位的变化。完整的代码可以直接看我的源码。这篇文章只要讲一下核心算法思路。

多说2句

这是一个系列，同时有配套的视频，链接在Github上有，毕竟有些东西文字很难讲清楚，尤其是算法部分，大家感兴趣的话可以看看。后续还会有连连看等，希望多多给Star，谢谢！

源码地址：github.com/gaoxiaosi/c…