JavaScript的深度：247字节内的扫雷游戏

"}`+m(t):O,O=64) `` 只需这**247字符的JavaScript代码**，即可在浏览器中运行简化版的扫雷游戏（https://en.wikipedia.org/wiki/Minesweeper_(video_game)）。该版本拥有随机生成的8×8游戏棋盘，支持左键点击打开格子、右键点击标记地雷、递归展开周围没有地雷的格子，并具备基本的获胜检测功能。欢迎在JSFiddle上体验！（https://jsfiddle.net/1jotkx2h/latest/） ## 为什么呢？几年前，出于兴趣，我决定尝试编写一种极简版的扫雷游戏作为代码高尔夫练习（https://en.wikipedia.org/wiki/Code_golf）。我在一个晚上就写出了658字节的版本，随后几周不断优化，最终将代码大小缩减到399字节。那时我以为已经达到极限便停止了进一步优化。最近在整理代码时，我又发现了这个极简版本，觉得值得写篇博客介绍它。随后我立刻找到了进一步压缩代码的方法，接着又是新的方法……我开始在Discord服务器上分享我的进展，**DNEK（https://dnek.net/）**也加入了我的代码高尔夫挑战。经过几个月的共同努力与无数次尝试，我们最终将代码大小压缩到了247字节。 ## 怎么做到的？现在，大家最关心的问题来了：*这究竟是如何做到的？***请注意，这是一篇技术性很强的博客文章，理解它需要一定的**JavaScript**知识——我不可能解释所有细节。欢迎在评论区提出问题！首先，让我们整理一下这段复杂的代码，使其更易阅读：`` b = (e) => document.body.innerHTML = m( 73, e || [~9,..."1172711", ~9].map(j => m[i -= j]? ++e : i).map( j => b(b[i = j] ^ 1 | e), b[i] =!m[C--, i] * ~e ) ); b( m = (t) => t--? `${ t % 9? "*#F"[ x = b[t]??= ( C -= m[t] = Math.random() <.1, 1 ) ]?? ~x : " " }` + m(t) : C, C = 64 ) `` 该代码由两部分组成：负责处理**游戏逻辑**的`b`函数，以及负责**生成用户界面和棋盘**的`m`函数。同时，代码还初始化了`C=64`——这个值用于显示尚未打开的安全格子数量。首先能观察到的优化之一是，`m`实际上是在函数调用`b(m=t=>...,C=64)`内部定义的。在JavaScript中这种方式完全可行，而且相比使用分隔符的写法还能节省1字节：`` - b=...;m=...;b() + b=...;b(m=...) `` ## 棋盘初始化与渲染 让我们看看游戏启动时的流程。代码会调用`b`函数，该函数又会调用`m(73,...)`，并将结果赋值给`document.body.innerHTML`。`m`从`t=73`开始，通过递归方式生成HTML，直到`t`变为0为止，最后还会在末尾加上`C`（即尚未打开的安全格子数量），格式如下：`` t--? ``每个格子都被包裹在``标签中。代码使用`onmouseup`事件来检测左键和右键点击。如您所注意到的，`b`实际上向`m`传递了两个参数，但`m`只接受一个参数！另一个参数会被忽略，其存在只是为了节省2字节：`` - b=e=>{someLogic; m(73)} + b=e=>m(73, someLogic) `` ## HTML的巧妙处理 那么闭合标签呢？原始代码中根本没有``或`，甚至连一个`/`都没有！这是个非常巧妙的技巧，我花了很长时间才发现。浏览器不允许``包含自身，也不允许``包含自身。每当开始一个新的标签时，HTML解析器会自动关闭之前的标签。`` 12 34 12 34 ") + m(t) + `${i%9?... : " "}` + m(t) `` 由于运算符优先级的原因，`a?x:y\+b`会被解释为`a?x:\(y\+b\)`，这显然不是我们想要的结果。如果将三元运算符放在`$\{...\}`之外，就必须用括号包裹整个条件，这样又会多浪费2字节。 ## 打开格子 `b`函数只接受一个参数`e`。任何真值都会通过逻辑或运算`\|\|`直接触发格子打开的逻辑：`` b = (e) => { document.body.innerHTML = m( 73, e ||... ); } `` 这种方式让我们能够以非常简洁的方式控制`b`的行为：假值会直接打开格子并更新棋盘，而真值则仅更新棋盘状态。由于所有未打开的格子初始值都是1，因此将某个格子的值与`1`进行异或运算（例如`b\[i\]^1`）即可判断该格子是否尚未打开（因为`1^1 = 0`）。此外，这种方法还能起到边界检查的作用——访问无效索引时会返回`undefined`，而`undefined^1`的运算结果为`1`；如果将这个值传递给`b`，代码就会直接跳过后续操作。接下来我们来看`m`中的`onmouseup`事件处理逻辑：`` `...` `` 这段代码会将格子的索引赋值给全局变量`i`（后续会被`b`使用），通过将该索引与`event.which`进行异或运算来修改`b\[i\]`的值，最后再使用计算得到的新值作为参数`e`调用`b`函数。`event.which`的取值为`1`（左键点击）、`2`（中键点击）或`3`（右键点击）。基于此逻辑：- 左键点击会将未打开的格子值从`1`改为`1 ^ 1 = 0`。由于`0`属于假值，`b`会执行其核心逻辑来打开该格子。- 右键点击会将未打开的格子值从`1`改为`1 ^ 3 = 2`。在查找表中，`2`代表地雷标记，因此该格子会显示为地雷标志。由于`2`属于真值，`b`会直接跳过后续操作，不会打开该格子。- 若右键点击的是地雷标记，其值会从`2`改为`2 ^ 3 = 1`，从而将该格子恢复为未打开状态。由于`1`属于真值，`b`仍会直接跳过后续操作。这种方式还能防止用户尝试打开已经打开的格子或地雷标记，不过有个副作用是`b\[i\]`的值会发生变化，看起来像是格子的值在不断增减。不过这种代价是值得的，因为问题仅体现在视觉上，用户只需再次点击即可修复。当`b`函数递归调用自身时，它会使用参数`b\[j\] ^ 1 \| e`。只有当目标相邻格子未打开（即`b\[j\] ^ 1 == 0`）且当前格子周围没有地雷（即`e == 0`）时，该表达式的结果才会为`0`。通过这种方式，既能避免无限递归，又能防止访问无效索引，同时还能处理地雷标记的放置问题，而这一切都仅需一个变量和异或运算即可实现。更令人惊叹的是，由于`b`的格子打开逻辑只有在`e=0`时才会执行，因此我们还有一个额外的变量可以用作累加器，用来统计每个格子周围的地雷数量！**小贴士：**在处理整数或布尔值时，如果不需要短路逻辑，可以使用位运算`\|`和`&`代替`\|\|`和`&&`，这样每个字符就能节省下来！比如：`` - b[j]^1 || e + b[j]^1 | e `` ## 一维思维 我们有两个独立的二维状态，但都存储在一个一维数组中。要计算相邻地雷数量并递归打开空白格子，就需要采用一维思维方式。在常规的扫雷实现中，通常会使用双重`for`循环来实现这些功能：`` for (let dy = y - 1; dy <= y + 1; dy++) { for (let dx = x - 1; dx <= x + 1; dx++) { // 检查(dx, dy)是否在棋盘范围内，// 如果是地雷则增加相邻地雷计数器，// 等等 } } ``不过也可以直接硬编码偏移量，创建一个包含八个差值的数组：`` [ [-1, -1], [0, -1] [1, -1], [1, 0], //... ] ``然后再遍历这个数组……这正是我在本次代码高尔夫挑战中采用的方法。对于二维实现来说，硬编码偏移量可能显得有些多余，但在一维场景下，只要棋盘大小是固定的，这种方式就非常简单。**JavaScript**允许我们在数组中使用无效索引——这样只会返回`undefined`。而更便利的是，我们已经在棋盘的右侧设置了一列隐藏列，这足以解决所有与无效索引相关的问题！**以下是4×4棋盘上的实现示例：**该图展示了四种不同的5×4棋盘，每种棋盘都有不同的蓝色高亮格子，直观显示了通过对索引应用偏移量后相邻格子的位置。（https://yui.dev/static/blog/minisweeper/offsets.png）如果我们检查边缘或角落的格子，应用这些偏移量后，无效的相邻格子要么会落在隐藏列中（显示为洋红色），要么会完全超出数组范围（显示为红色）。在检查某个偏移量位置的格子是否为地雷时，只需判断该值是否为真值即可。隐藏列中没有地雷，而`undefined`属于假值。这样就已经形成了一个非常简洁的循环结构，但我们还可以通过使用**增量值**来进一步优化。无需存储完整的偏移量，也不用为多个负号浪费字节，只需不断修改`i`的值即可：`` [-10, 1, 1, 7, 2, 7, 1, 1, -10].map( j => m[i -= j]? e++ : i ) ``这种方式会从`i\+10`开始，不断从`i`中减去较小的1位数增量值，最终再将`i`恢复到初始状态。对于每个找到的地雷，都会增加累加器`e`的值（即之前提到的那个备用变量）。如果未找到地雷，最终会得到一个索引数组，我们可以利用这个数组递归打开所有相邻格子。如果至少发现了一个地雷，那么就不需要继续递归了，因此也就无需保留有效的索引列表。虽然这种方式会让原始格子被计算两次，但在这里并无影响——如果点击的格子是地雷，最终会显示为`\*`符号；如果不是地雷，重复计算也不会产生任何变化。最后，我们还可以通过一些技巧让数组更加紧凑：`` [~9,..."1172711", ~9].map( j => m[i -= j]? ++e : i ) ``在JavaScript中，展开运算符是将字符串拆分为单个字符的最简方式。在我们的例子中，它会生成一个由数字字符串组成的数组。之所以要减去`i`而不是加上，是因为类型转换的规则所致：- 将字符串加到数字上时，数字会被转换为字符串：`3\+"1"`的结果是`"31"`。- 而将字符串从数字中减去时，字符串会被转换为数字：`3\-"1"`的结果是`2`。此外，我们还会使用`~9`（位取反运算）代替`\-10`，以此节省2字节。 ## 更新格子并递归 在生成数组之后，我们会使用`.map`方法来更新已打开格子的显示状态，并继续递归处理。这里同样运用了我之前提到的带有额外参数的技巧：``.map( j => b(...), // 这部分会在.map调用之前先执行 b[i] =!m[C--, i] * ~e ) ``首先会递减`C`的值，然后通过`\!m\[C\-\-,i\]`判断当前格子是否不是地雷。该索引表达式的计算结果为`i`，但同时会以副作用的形式悄悄递减`C`的值。之后将该值与地雷计数器的位取反结果相乘：`\!m\[C\-\-,i\] \* ~e`。由于布尔值会转换为整数，因此`false \* x`的结果为`0`，而`true \* x`的结果则为`x`。我们将这个结果存储到`b\[i\]`中。如果当前格子是地雷，存储的结果为`0`；如果该格子周围没有地雷，结果为`\-1`；如果周围有1个地雷，结果为`\-2`，以此类推。之后，`.map`方法会针对数组中的每个索引调用这个函数：`` j => b(b[i = j] ^ 1 | e) ``这一步会将全局变量`i`的值设置为`j`，同时如前所述，构建传递给`b`的参数，确保只有当目标格子未打开（即`b\[j\]^1 == 0`）且周围没有地雷（即`e == 0`）时，`b`才会执行其核心逻辑。完成所有这些操作后，最终会调用`m`函数，将其结果赋值给页面的`innerHTML`，从而向玩家展示包含新打开格子的更新后的棋盘。 ## 接下来怎么办？就这些了。仅靠这些代码就能运行扫雷游戏。当然，这还不是目前存在的最小版本的扫雷游戏。如果去掉大部分功能，使用`prompt`函数来显示棋盘并获取玩家输入，还可以进一步缩小代码大小。我曾想过利用`prompt`函数会暂停程序执行直到用户输入内容这一特性——这样我们就可以通过`Date`对象在初始化阶段生成随机数（不过这意味着玩家需要按上百次回车键才能开始游戏）：`` - Math.random()<.1 + new Date%7<1 ``不过我是从这套特定的功能集开始优化的，最终在**没有删除任何核心功能**的情况下，就将代码大小从658字节缩减到了247字节。这个版本很可能已经非常接近理论上的最小尺寸了，但由于柯尔莫哥洛夫复杂度（https://en.wikipedia.org/wiki/Kolmogorov_complexity）是不可计算的，我们永远无法确定这是否就是真正的最小值。也许还有其他完全不同的方法能在更少的字节数下实现相同的效果，但除非有人想出这些方法，否则我们永远无法知晓。 ## 总结 这个项目的实现经历了无数次尝试与调试。我和**DNEK（https://dnek.net/）**尝试了各种不同的思路和方法——有时会对代码进行重大修改，有时又会回到旧有的方案，有时会对某个潜在的优化方案充满期待，结果却发现它并不可行。每一个字节都是经过精心设计与权衡的。虽然在我发布这篇博客之后，也许还会有人找到更小的实现方式，但我个人对目前的成果已经非常满意。从宏观角度来看，这可能没什么意义，但这正是娱乐性编程的魅力所在。从小我就将代码视为一种艺术形式，我很高兴即便在如今这个时代，仍能从单纯为了创造而创造一些有趣的东西中获得乐趣。> 如果您喜欢我的作品，欢迎考虑支持我（https://yui.dev/donate）！如果您希望与我合作，也可以联系我（https://yui.dev/contact），我目前正在寻找远程工作机会！3,120字 • 100段