每日算法 — 使用java实现俄罗斯方块：T-Spin判定与SRS踢墙位移表

可莉爸爸 AI算法

大多数俄罗斯方块 AI 的评估函数都能算得很准，却常常算不对一件事：T-Spin。这个现代规则里的高分技巧要求”用旋转而非平移把方块塞进一个原本进不去的缝里”，而方块之所以能进去，靠的是 SRS（Super Rotation System，超级旋转系统）定义的那份踢墙位移表。也就是说，AI 如果只按”左移/右移/下落”三种动作枚举，就永远发现不了 T-Spin；必须先实现旋转状态机 + 踢墙表，才能让搜索空间里出现这种着法。本文就从位掩码棋盘出发，把 SRS 的旋转与踢墙逻辑、T-Spin 的三点判定、以及带旋转动作的落点枚举全部写成可运行的 Java 代码。

一、方块的四种旋转态：不用矩阵旋转，用坐标表

教科书式的方块旋转是”绕中心点旋转 90°”，但 SRS 的旋转并不是几何旋转——它是四个预定义形状之间的状态切换，且每个形状的踢墙偏移由外部表格给出。因此正确做法是把每种方块的四个状态直接写成坐标表，而不是运行时算三角函数或做矩阵乘法：

/** 7 种方块的 4 个旋转态, 每态用 4 个格子坐标 (行,列) 表示, 以 3x3 或 4x4 包围盒为参考 */
static final int[][][][] SHAPES = {
    // I 型: 使用 4x4 包围盒
    { { {1,0},{1,1},{1,2},{1,3} }, { {0,2},{1,2},{2,2},{3,2} },
      { {2,0},{2,1},{2,2},{2,3} }, { {0,1},{1,1},{2,1},{3,1} } },
    // O 型: 旋转不变
    { { {0,0},{0,1},{1,0},{1,1} }, { {0,0},{0,1},{1,0},{1,1} },
      { {0,0},{0,1},{1,0},{1,1} }, { {0,0},{0,1},{1,0},{1,1} } },
    // T 型: 3x3 包围盒, 中心固定 (1,1)
    { { {0,1},{1,0},{1,1},{1,2} }, { {0,1},{1,1},{1,2},{2,1} },
      { {1,0},{1,1},{1,2},{2,1} }, { {0,1},{1,0},{1,1},{2,1} } },
    // S / Z / J / L 同理, 略去展开以节省篇幅, 结构与上面一致
};

用坐标表的好处有两条：一是旋转是 O(1) 查表，不涉及任何浮点或取整，不会出现”旋转后位置漂移半格”的经典 bug；二是踢墙表的偏移可以直接叠加在坐标上，因为 SRS 的偏移量本来就是以格子为单位定义的。

状态用 0..3 表示，顺时针旋转就是 (state + 1) % 4，逆时针是 (state + 3) % 4。这一点必须写死，因为踢墙表的索引依赖它。

二、SRS 踢墙：五组候选偏移的尝试顺序

当一个方块旋转后与已有堆叠或墙壁重叠时，SRS 允许它平移若干格后再落位，这就是”踢墙”。每个旋转方向对应恰好 5 组候选偏移，按表格顺序逐个尝试，第一个不冲突的就采纳；全部冲突则旋转失败（保持原状态）。T 型方块的表长这样：

/** T 型: 顺时针旋转的 5 组候选偏移 (dx=列, dy=行, 行向下为正) */
static final int[][] T_CW = {
    {0, 0}, {-1, 0}, {-1, -1}, {0, +2}, {-1, +2}
};
/** T 型: 逆时针旋转的 5 组候选偏移 */
static final int[][] T_CCW = {
    {0, 0}, {+1, 0}, {+1, +1}, {0, -2}, {+1, -2}
};

I 型方块用的是另一套更”暴力”的表，因为它旋转后包围盒跨 4 行，需要的位移更大：

static final int[][] I_CW  = { {0,0}, {-2,0}, {+1,0}, {-2,+1}, {+1,-2} };
static final int[][] I_CCW = { {0,0}, {+2,0}, {-1,0}, {+2,-1}, {-1,+2} };

O 型方块旋转后形状完全不变，所以只需要 {0,0} 一个候选（多给候选也不会错，但会浪费检测）。

这套表的意义在于：它把”能不能转进去”从几何推理问题变成了”按顺序试 5 个偏移”的枚举问题。这是实现难度的断崖式下降——不需要判断”旋转中心到墙角的角度”，只需要 for 循环加碰撞检测。

/** 尝试旋转: 返回新位置, 失败返回 null */
static int[] tryRotate(Board b, int type, int state, int row, int col, boolean cw) {
    int ns = cw ? (state + 1) % 4 : (state + 3) % 4;
    int[][] kicks = kickTable(type, cw);
    for (int[] k : kicks) {
        int nr = row + k[1], nc = col + k[0];
        if (!collides(b, type, ns, nr, nc)) return new int[]{ns, nr, nc};
    }
    return null;   // 五组全冲突: 旋转失败, 方块原地不动
}

三、T-Spin 的三点判定

T-Spin 的规则定义（现代 Guideline）是：用旋转动作锁定 T 型方块，且它的四个斜角中至少有三个被占据。”占据”包括墙壁、地板和已堆叠的方块。所以判定逻辑是纯几何的：

/** T 型方块锁定后是否构成 T-Spin: 四个斜角至少三个被占据 */
static boolean isTSpin(Board b, int state, int row, int col) {
    // T 型的中心格固定在包围盒的 (1,1)
    int cr = row + 1, cc = col + 1;
    int filled = 0;
    if (b.solid(cr - 1, cc - 1)) filled++;
    if (b.solid(cr - 1, cc + 1)) filled++;
    if (b.solid(cr + 1, cc - 1)) filled++;
    if (b.solid(cr + 1, cc + 1)) filled++;
    return filled >= 3;
}

Board.solid(r,c) 对越界坐标返回 true——墙壁和地板算作”占据”，这一条是 T-Spin 在贴墙时成立的关键。

一个容易被忽略的细节：T-Spin 判定的是”最后一步是旋转”。如果玩家先用旋转把 T 塞进缝里，然后又按了一次左移才锁定，那就不算 T-Spin（某些规则变体叫 Mini T-Spin 或干脆不算）。所以搜索里必须记录”上一个动作类型”，才能正确判定。这也是为什么带旋转的落点枚举不能简单地”枚举所有 (state, row, col) 组合”——同一个落位，从”平移过去”和”旋转过去”两种路径到达，得分完全不同。

四、带旋转的落点枚举：动作路径而非终态

正确做法是按动作序列枚举：从当前方块位姿出发，做一次”左移/右移/旋转/下落”的动作，检查合法性，把这个动作的终态作为一个候选；对每个候选再记录”最后一次动作是不是旋转”，从而得到 T-Spin 标记。

/** 枚举当前方块的所有可锁定终态: (state, row, col, lastActionWasSpin) */
static List<int[]> enumeratePlacements(Board b, int type, int state, int row, int col) {
    List<int[]> out = new ArrayList<>();
    // 水平平移的各个列
    for (int c = 0; c < b.cols; c++) {
        if (!fitsHorizontally(b, type, state, row, c)) continue;
        int drop = dropRow(b, type, state, c);            // 硬降落点
        out.add(new int[]{state, drop, c, 0});
    }
    // 旋转后落位(可能触发踢墙, 也可能触发 T-Spin)
    for (boolean cw : new boolean[]{true, false}) {
        int[] r = tryRotate(b, type, state, row, col, cw);
        if (r == null) continue;
        for (int c = 0; c < b.cols; c++) {
            if (!fitsHorizontally(b, type, r[0], r[1], c)) continue;
            int drop = dropRow(b, type, r[0], c);
            // 旋转后直接落地且无水平动作 -> 标记为 spin 路径
            out.add(new int[]{r[0], drop, c, 1});
        }
    }
    return out;
}

dropRow 就是标准的”从当前行一直下落到不能下为止”，等价于硬降（hard drop）。真实游戏里落地后还有锁定延迟，可以用水平移动微调；枚举时用硬降近似，对评估精度影响很小。

五、位掩码棋盘：一次 long 存 10 列

俄罗斯方块的棋盘通常是 10×20，用 long[20] 每行 10 位即可，或者干脆用两个 long 拼成 64 位以上——但更实用的做法是每行一个 int 掩码，因为它让”整行检测”和”消行”变成位运算：

final class Board {
    static final int COLS = 10, ROWS = 20;
    final int[] rows = new int[ROWS];   // 第 i 位为 1 表示该列被占

    boolean solid(int r, int c) {
        if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return true;  // 墙与地板算占据
        return ((rows[r] >>> c) & 1) != 0;
    }

    /** 落子并把满行清零; 返回消除的行数 */
    int lockAndClear(int[] cells) {
        for (int[] p : cells) rows[p[0]] |= 1 << p[1];
        int cleared = 0;
        for (int r = ROWS - 1; r >= 0; r--) {
            if (rows[r] == (1 << COLS) - 1) {       // 整行全 1
                System.arraycopy(rows, 0, rows, 1, r);  // 上方整体下移一行
                rows[0] = 0;
                cleared++;
                r++;                                 // 复查当前行(已换成上一行内容)
            }
        }
        return cleared;
    }
}

rows[r] == (1 << COLS) - 1 这个判断是 O(1)，而 System.arraycopy 一次性下移整块内存——比逐格搬迁快得多，也让”消行”成为评估里最便宜的部分。

六、完整可运行骨架

tetris-srs/
└── src/main/java/tetris/
    ├── Board.java       # 位掩码棋盘
    ├── Piece.java       # 形状表 + SRS 踢墙表 + 旋转
    ├── SpinDetector.java# T-Spin 判定
    └── Demo.java        # main: 枚举落点并标注 T-Spin

package tetris;

import java.util.*;

final class Board {
    static final int COLS = 10, ROWS = 20;
    final int[] rows = new int[ROWS];

    boolean solid(int r, int c) {
        if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return true;
        return ((rows[r] >>> c) & 1) != 0;
    }

    /** 把方块的 4 个绝对坐标写入棋盘, 返回消除行数 */
    int lockAndClear(int[][] cells) {
        for (int[] p : cells) rows[p[0]] |= 1 << p[1];
        int cleared = 0;
        for (int r = ROWS - 1; r >= 0; r--) {
            if (rows[r] == (1 << COLS) - 1) {
                System.arraycopy(rows, 0, rows, 1, r + 1);
                rows[0] = 0;
                cleared++;
                r++;
            }
        }
        return cleared;
    }
}

final class Piece {
    /** 形状表: [方块类型][旋转态][4 个格子的 (行,列)] —— 仅展示 I/T/O 三种, 其余按同构补全 */
    static final int[][][][] SHAPES = {
        // I
        { { {1,0},{1,1},{1,2},{1,3} }, { {0,2},{1,2},{2,2},{3,2} },
          { {2,0},{2,1},{2,2},{2,3} }, { {0,1},{1,1},{2,1},{3,1} } },
        // O
        { { {0,0},{0,1},{1,0},{1,1} }, { {0,0},{0,1},{1,0},{1,1} },
          { {0,0},{0,1},{1,0},{1,1} }, { {0,0},{0,1},{1,0},{1,1} } },
        // T
        { { {0,1},{1,0},{1,1},{1,2} }, { {0,1},{1,1},{1,2},{2,1} },
          { {1,0},{1,1},{1,2},{2,1} }, { {0,1},{1,0},{1,1},{2,1} } },
    };

    static final int[][] T_CW  = { {0,0}, {-1,0}, {-1,-1}, {0,+2}, {-1,+2} };
    static final int[][] T_CCW = { {0,0}, {+1,0}, {+1,+1}, {0,-2}, {+1,-2} };
    static final int[][] I_CW  = { {0,0}, {-2,0}, {+1,0}, {-2,+1}, {+1,-2} };
    static final int[][] I_CCW = { {0,0}, {+2,0}, {-1,0}, {+2,-1}, {-1,+2} };
    static final int[][] NONE  = { {0,0} };

    /** 取踢墙表: 注意行偏移符号, 工程中统一把 dy 定义为"向下为正" */
    static int[][] kickTable(int type, boolean cw) {
        if (type == 0) return cw ? I_CW : I_CCW;   // I
        if (type == 1) return NONE;                // O 不需要踢墙
        return cw ? T_CW : T_CCW;                  // T/S/Z/J/L 共用一套
    }

    /** 绝对坐标 */
    static int[][] cells(int type, int state, int row, int col) {
        int[][] s = SHAPES[type][state];
        int[][] out = new int[4][2];
        for (int i = 0; i < 4; i++) {
            out[i][0] = row + s[i][0];
            out[i][1] = col + s[i][1];
        }
        return out;
    }

    static boolean collides(Board b, int type, int state, int row, int col) {
        for (int[] p : cells(type, state, row, col)) if (b.solid(p[0], p[1])) return true;
        return false;
    }

    /** 旋转 + 踢墙: 成功返回 {state,row,col}, 失败返回 null */
    static int[] rotate(Board b, int type, int state, int row, int col, boolean cw) {
        int ns = cw ? (state + 1) % 4 : (state + 3) % 4;
        for (int[] k : kickTable(type, cw)) {
            int nr = row + k[1], nc = col + k[0];
            if (!collides(b, type, ns, nr, nc)) return new int[]{ns, nr, nc};
        }
        return null;
    }

    /** 硬降落点 */
    static int dropRow(Board b, int type, int state, int row, int col) {
        while (!collides(b, type, state, row + 1, col)) row++;
        return row;
    }
}

final class SpinDetector {
    /** T-Spin: T 型中心 (row+1,col+1) 的四个斜角至少 3 个被占据 */
    static boolean tSpin(Board b, int row, int col) {
        int cr = row + 1, cc = col + 1, filled = 0;
        if (b.solid(cr - 1, cc - 1)) filled++;
        if (b.solid(cr - 1, cc + 1)) filled++;
        if (b.solid(cr + 1, cc - 1)) filled++;
        if (b.solid(cr + 1, cc + 1)) filled++;
        return filled >= 3;
    }
}

final class Demo {
    public static void main(String[] args) {
        Board b = new Board();
        // 造一个 T-Spin 的经典槽位: 左右各留一列空隙, 顶部有盖子
        b.rows[18] = 0b0111111110;   // 中间 8 列被填, 两侧留空
        b.rows[19] = 0b0111111110;
        b.rows[17] = 0b0110000110;   // 中间开一个 2 格宽的缝

        int[] r = Piece.rotate(b, 2, 0, 15, 3, true);   // T 型顺时针
        if (r != null) {
            int drop = Piece.dropRow(b, 2, r[0], r[1], r[2]);
            boolean spin = SpinDetector.tSpin(b, drop, r[2]);
            System.out.printf("旋转成功 state=%d row=%d col=%d 落点行=%d T-Spin=%s%n",
                    r[0], r[1], r[2], drop, spin);
        } else {
            System.out.println("旋转失败(五组踢墙全部冲突)");
        }

        int cleared = b.lockAndClear(Piece.cells(2, r[0], Piece.dropRow(b, 2, r[0], r[1]), r[2]));
        System.out.println("消除行数 = " + cleared);
    }
}

七、复杂度与实现要点

  • 旋转 + 踢墙：O(5 × 4)，五次偏移、每次检查 4 格，常数极小。
  • 落点枚举：O(COLS × 动作数) ≈ 20×4 个候选，全部做一遍不到百次碰撞检测。
  • 消行：检测 O(ROWS)，下移 O(ROWS)，位掩码让整行判定只花一次比较。

三个容易踩的坑：

  1. 踢墙表方向符号。SRS 官方表用”y 向上为正”，而屏幕坐标向下为正，直接抄表会得到上下镜像的错误位移。本文统一改成向下为正后重新排列，抄表时务必确认符号。
  2. T 型中心格的位置随旋转态变化。本文给出的是 T 中心固定在包围盒 (1,1) 的坐标表，这样 tSpin 才能统一用 row+1, col+1；如果坐标表换了一种约定，判定代码必须同步改。
  3. O 型不该有踢墙。O 型旋转后形状不变，给它五组偏移只会制造”转一下就莫名位移一格”的诡异 bug。

八、小结

T-Spin 的本质不是”旋转技巧”，而是把旋转动作和踢墙偏移纳入搜索空间之后自然涌现的策略。三块基础设施缺一不可：坐标表让旋转 O(1)、踢墙表把”能否转进去”变成五次尝试、三点判定把”这是不是 T-Spin”变成四格检查。有了这三块，评估函数才第一次能”看见”高价值着法——否则再精确的启发式也只能在平移的落点里打转。

Tagged with: