位运算在游戏状态压缩与碰撞检测中的应用

一、为什么位运算适合俄罗斯方块

俄罗斯方块的逻辑看似简单，但真正实现时会同时遇到两类问题：内存占用和运行效率。如果采用常见的二维数组表示法，例如用 char ball[23][10] 表示容器、用 char fall[4][4] 表示当前方块，虽然直观，但内存占用大，碰撞判断也要逐格遍历，运行速度很容易下降。这在内存仅有十几 KB 的设备上尤其明显。

进一步观察可以发现，俄罗斯方块中的每个格子只有两种状态：显示与不显示。这种“二值状态”天然适合用二进制位表示。一个位表示一个格点，1 表示占用，0 表示空白。这样不仅可以大幅压缩内存，还能把整行、整列的判断转化为按位与、按位或、移位等操作。

位运算的优势主要有三点：

1. 内存占用显著降低，单行容器用一个整数即可表示。
2. 碰撞判断可以从多次坐标比较变为一次按位与。
3. 左右边界可以用预设掩码处理，减少分支判断。

二、容器建模：用 short 表示一行

俄罗斯方块标准容器通常有 10 列。如果每个格点占用一位，那么一行需要至少 10 位。char 通常只有 8 位，不够用；short 通常有 16 位，可以覆盖 10 列，并且多出 6 位。

这 6 位不一定要浪费，可以放在显示区域两侧，作为隐藏边界。例如：

• 左侧放 3 位，置为 1；
• 右侧放 3 位，置为 1；
• 中间 10 位表示实际可见区域。

这样一行数据可以写成：

1110000000000111

从二进制角度理解，左边的 111 是左边界，右边的 111 是右边界，中间 10 个 0 表示初始空白区域。这样，当方块移动到边缘时，只要与边界位发生重叠，按位与就会得到非零结果，无需再写额外的左右边界判断。

采用这种方案后，容器可以用一个包含 24 个 short 的数组来表示。为什么是 24 行？因为除了可见区域外，顶部通常还需要预留几行，用于方块从屏幕顶端逐渐出现；底部还需要一行全 1 掩码，表示容器底。

例如，容器底部可以直接设置：

short bottom = 0xFFFF;

这一行所有位都是 1，方块一旦与它发生按位与，就说明已经触底。

三、方块建模：四个 short 表示一个形状

每个标准方块由四个格点组成。若使用二维数组表示，每个方块需要 4×4 的数组；使用位表示后，一个方块可以由 4 个 short 组成，每个 short 表示一行。

例如，一个常见的方块形状可以表示为：

short shape[4] = {
    0b0100,
    0b0100,
    0b0100,
    0b0100
};

这表示一个竖条形状。由于每种方块有四个旋转方向，因此可以使用三维数组预置所有数据：

short data[7][4][4];

其中：

• 第一维表示 7 种方块；
• 第二维表示 4 个旋转方向；
• 第三维表示该方向下的 4 行数据。

这种设计有两个明显好处：

1. 所有形状和旋转体都在初始化阶段准备好，运行期不需要再构造。
2. 每种方向的数据固定，逻辑中只需要根据当前方向和位置进行移位。

四、预置数据与运行时移位

预置数据通常以 short 的第 0 位对齐，即方块最左侧紧贴低位。实际落到容器中时，需要把方块数据左移到目标列位置。

例如，如果方块要落到容器可显示区域的第 3 列，可以这样计算：

int offset = 3;
short shifted[4];
for (int i = 0; i < 4; i++) {
    shifted[i] = shape[i] << offset;
}

这样得到的新数据可以直接与容器行进行按位操作。容器中的左侧隐藏边界恰好可以通过偏移量自然避开。

五、碰撞检测：一次按位与即可完成

传统二维数组方案中，判断方块是否能继续下移，需要遍历 4×4 区域，逐格检查是否与已有格子重叠，代码中通常包含多轮循环和边界判断。

使用位表示后，检测过程可以简化为按位与。假设容器用一个 short 数组 board[24] 表示，当前方块用 short current[4] 表示，当前所在行号为 row，则下移前可以先检查：

int canMoveDown = 1;
for (int i = 0; i < 4; i++) {
    if (board[row + i + 1] & current[i]) {
        canMoveDown = 0;
        break;
    }
}

这里的核心操作就是一次按位与。只要结果非零，说明目标位置已被占用，方块不能继续下移。该判断不需要再比较横纵坐标，也不需要对容器边界单独判断，因为底部全 1 行已经起到天然阻挡作用。

左右移动的判断类似。假设向左移动时，可以先检查方块与左侧边界是否冲突：

int canMoveLeft = 1;
for (int i = 0; i < 4; i++) {
    if ((current[i] << 1) & board[row + i]) {
        canMoveLeft = 0;
        break;
    }
}

如果容器左侧预置了 3 位边界，那么方块一旦贴近左边缘，左移后的位就会与边界位重叠，按位与返回非零，移动自然被禁止。

六、方块固定与行消除

当方块无法继续下移时，需要将它固定到容器中。这个过程也可以使用按位或完成：

for (int i = 0; i < 4; i++) {
    board[row + i] |= current[i];
}

固定之后，可以检查是否存在满行。传统做法是逐格判断该行是否全部为 1；而使用位表示后，可以提前准备一个全 1 的显示区掩码：

short fullMask = 0x0FFC; // 假如中间 10 位为 1

判断某一行是否已满：

if ((board[r] & fullMask) == fullMask) {
    // 该行已满，需要消除
}

消除行时，可以将该行以上的数据逐行下移。由于每一行只是一个 short，下移操作本质上是数组元素的搬移，比二维数组的整行赋值更快。

七、旋转处理：预先制作方向数据

旋转是俄罗斯方块中比较复杂的一环。如果使用二维数组动态旋转，需要逐点计算坐标变换，容易出现越界或形状不一致的问题。

使用预置三维数组后，旋转逻辑可以简化为切换方向索引。例如：

int newDir = (currentDir + 1) % 4;
short *nextShape = data[currentType][newDir];

然后对 nextShape 做同样的碰撞检测。如果不发生冲突，就更新当前方块数据和方向；如果发生冲突，则保持原状。

这种方式将复杂的旋转计算从运行期转移到初始化阶段，不仅减少运行期开销，也降低了逻辑出错的可能性。

八、性能与可读性的平衡

位运算方案并非在所有场景下都优于二维数组。对于现代 PC 或高性能移动设备，内存和算力通常足够，二维数组实现可能更直观、更容易维护。但在以下场景中，位运算优势明显：

• 内存非常有限的嵌入式设备；
• 需要同时处理大量对象的游戏状态；
• 对碰撞检测频率要求极高的实时系统；
• 需要批量判断整行或整列状态的数据结构设计。

即便不在极端受限环境下，理解位运算建模思路也能帮助开发者写出更紧凑的代码。将状态从“对象属性”抽象为“位集合”，在很多工程中都能带来性能提升。

九、总结

俄罗斯方块的位运算实现展示了一种重要的程序设计思路：当问题可以被拆解为大量二值状态时，位掩码往往比对象数组更高效。通过 short 表示一行、预设边界位、预置旋转数据以及使用按位与进行碰撞检测，可以同时降低内存占用和减少运行期判断。

这种方法的本质，是利用整数的二进制特性，把原本分散的格点状态集中到少数几个变量中，再用处理器非常擅长的位操作完成业务逻辑。对于资源受限、性能敏感或状态空间较大的系统，这是一种值得掌握的工程实践。