每日算法 — 使用java实现滚方块Bloxorz：三维滚动状态编码与A*搜索

滚方块（Bloxorz）是很多玩家童年记忆里那个”一根 1×1×2 的方木在悬浮地板上翻滚”的谜题：你要让方木最终竖直落进终点洞，中途不能从地板上掉下去，也不能让方木平躺压在由两个方格拼成的”弱格”上——弱格承受不住平躺的重量。

它看起来像个几何游戏，本质却是一道非常纯粹的图搜索题：状态空间很小、每步动作固定、有无解判定明确。这篇文章用 Java 从零实现一个完整的 Bloxorz 求解器，重点讲清三件事：状态怎么编码、滚动怎么用查表实现、A* 的启发式怎么设计才不会破坏最优性。

一、先把”游戏”翻译成”图”

任何搜索算法的第一步都是回答：节点是什么，边是什么。

在 Bloxorz 里，玩家唯一能做的就是朝上、下、左、右四个方向”翻滚”一次。方木始终是 1×1×2 的长方体，因此它在任意时刻只有三种朝向：

朝向	占用的格子	说明
STAND（竖立）	1 格 `(r,c)`	只有这种姿态能落进终点洞
HORIZONTAL（横躺）	2 格 `(r,c)`、`(r,c+1)`	沿列方向延伸
VERTICAL（竖躺）	2 格 `(r,c)`、`(r+1,c)`	沿行方向延伸

于是”节点”就是 (r, c, orientation) 三元组，其中 (r,c) 是占位左上角的格子坐标。这个建模非常关键：很多人会下意识把”方木占据的所有格子”当作状态，那会导致同一姿态被重复表示，状态数膨胀数倍。

边则是”一次翻滚”，代价恒为 1。由于代价相同，BFS 就能求出最少步数；但为了在更大的地图上也能快速收敛，我们会用 A*。

一个 30×30 的地图，状态总数上界是 30 × 30 × 3 = 2700。这个规模小到可以用一个三维数组做 dist 表，也小到可以放心地用优先队列跑 A——真正的难点从来不是性能，而是合法性判定*。

二、滚动变换表：把物理规则变成常量数组

翻滚的位移是完全确定的，可以预先枚举。设当前占位左上角为 (r,c)：

从 STAND 出发（方木倒下）：

向上 → 变成 VERTICAL，占据 (r-2,c)、(r-1,c)
向下 → 变成 VERTICAL，占据 (r+1,c)、(r+2,c)
向左 → 变成 HORIZONTAL，占据 (r,c-2)、(r,c-1)
向右 → 变成 HORIZONTAL，占据 (r,c+1)、(r,c+2)

从 HORIZONTAL 出发（沿自身长轴滚 / 侧向滚）：

向上、向下 → 仍是 HORIZONTAL，整体平移一格：(r±1, c)
向左 → 变成 STAND，落在 (r,c-1)（右端翘起）
向右 → 变成 STAND，落在 (r,c+2)（左端翘起）

从 VERTICAL 出发：与 HORIZONTAL 完全对称，横向平移保持 VERTICAL，纵向滚动压成 STAND。

把这 12 条规则写成三张 static final int[][] 表，每张表 4 行（四个方向）、3 列（dr, dc, newOrientation），运行时只做整数加法，没有任何分支判断。这是消除”物理逻辑散落在各处”的最有效手段：

// 方向索引：0=上 1=下 2=左 3=右
private static final int[] DR = {-1, 1, 0, 0};
private static final int[] DC = {0, 0, -1, 1};

// TRANS[ori][dir] = {dr, dc, newOri}
// dr/dc 表示新姿态左上角相对于旧左上角的偏移
private static final int[][][] TRANS = {
    // STAND
    { {-2, 0, VERTICAL}, {1, 0, VERTICAL}, {0, -2, HORIZONTAL}, {0, 1, HORIZONTAL} },
    // HORIZONTAL
    { {-1, 0, HORIZONTAL}, {1, 0, HORIZONTAL}, {0, -1, STAND}, {0, 2, STAND} },
    // VERTICAL
    { {-1, 0, STAND}, {2, 0, STAND}, {0, -1, VERTICAL}, {0, 1, VERTICAL} }
};

三、合法性判定：三种格子，三类约束

地图用字符表示，一共四种语义：

# / .：普通地板，任何姿态都能压
O：弱格（fragile）。只有方木以 STAND 姿态、且恰好只有这一格承重时才能停留；一旦有两格重量压上去（HORIZONTAL 或 VERTICAL 覆盖到它），立刻塌陷
X：目标洞。只有 STAND 且恰好落在这一格才算通关；平躺压上去视为掉下去
空格：虚空，任何姿态都不能覆盖

于是 isValid(state) 要检查两件事：覆盖的每一格都在地图内且不是虚空；以及弱格/洞的承重约束。

private boolean isValid(int r, int c, int ori) {
    if (ori == STAND) {
        if (!inside(r, c)) return false;
        Cell cell = grid[r][c];
        // 竖立只有一格承重，弱格可以承受；洞是终点
        return cell == Cell.FLOOR || cell == Cell.WEAK || cell == Cell.GOAL;
    }
    // 平躺两格承重：不能碰弱格，不能碰洞
    int r2 = r + (ori == VERTICAL ? 1 : 0);
    int c2 = c + (ori == HORIZONTAL ? 1 : 0);
    if (!inside(r, c) || !inside(r2, c2)) return false;
    return isPlainFloor(r, c) && isPlainFloor(r2, c2);
}

private boolean isPlainFloor(int r, int c) {
    Cell cell = grid[r][c];
    return cell == Cell.FLOOR;   // 弱格与洞都不能被平躺压住
}

这里有一个容易被忽略的细节：通关判定必须是 STAND 且 (r,c) 是 GOAL，而不是”覆盖到 GOAL 就行”。如果只判断”任一格是 GOAL”，平躺压过洞口会被误判成胜利，实际游戏里那是直接掉下去。

四、A* 的启发式：别让”乐观”变成”不合法”

A 的正确性依赖启发式函数的可采纳性*（admissible）：h(n) ≤ 真实剩余代价。一旦高估，就可能返回非最优解。

在 Bloxorz 里，一个状态到目标的”距离”取决于什么？取决于方木中心点到洞口的曼哈顿距离。

三种姿态的中心点分别是：

STAND：(r, c)
HORIZONTAL：(r, c + 0.5)
VERTICAL：(r + 0.5, c)

一次翻滚让中心点最多移动 1.5 格（从 STAND 向左滚一步，中心从 (r,c) 变到 (r,c-1.5)，位移 1.5）。所以：

h = L1_distance(center, goal) / 1.5

为了避免浮点误差破坏可采纳性，用整数算术向下取整：

private int heuristic(int r, int c, int ori) {
    // 用 2 倍坐标做整数运算，避免浮点
    double cr = r + (ori == VERTICAL ? 0.5 : 0);
    double cc = c + (ori == HORIZONTAL ? 0.5 : 0);
    double d = Math.abs(cr - goalR) + Math.abs(cc - goalC);
    return (int) Math.floor(d / 1.5);
}

这个启发式在地图空旷时能大幅剪枝，但它不是一致的（consistent）——某些边的代价会让 h 下降超过 1。这不影响正确性（只要求可采纳），代价是优先队列中可能出现同一节点的多份拷贝，需要用”跳过已出队的更优节点”来防御。

想进一步加速，可以叠加一个弱格约束惩罚，但那会破坏可采纳性。工程上的折中做法是：把惩罚项乘以一个很小的系数（如 0.1）并单独记作 tie-breaker，而不是并入 f——这样只影响同分状态的出队顺序，不影响最优性。

五、完整实现

下面是可直接运行的完整 Java 实现，包含地图解析、状态枚举、A* 求解与路径回放。

5.1 单文件版本（`Main.java`）

import java.util.*;

public class Main {

    // ---------------- 常量与方向表 ----------------
    static final int STAND = 0, HORIZONTAL = 1, VERTICAL = 2;
    static final int[] DR = {-1, 1, 0, 0};
    static final int[] DC = {0, 0, -1, 1};
    static final String[] DIR_NAME = {"上", "下", "左", "右"};

    // TRANS[ori][dir] = {dr, dc, newOri}
    static final int[][][] TRANS = {
        { {-2, 0, VERTICAL}, { 1, 0, VERTICAL}, {0, -2, HORIZONTAL}, {0, 1, HORIZONTAL} },
        { {-1, 0, HORIZONTAL}, { 1, 0, HORIZONTAL}, {0, -1, STAND},   {0, 2, STAND} },
        { {-1, 0, STAND},      { 2, 0, STAND},      {0, -1, VERTICAL}, {0, 1, VERTICAL} }
    };

    enum Cell { VOID, FLOOR, WEAK, GOAL }

    // ---------------- 地图 ----------------
    final Cell[][] grid;
    final int rows, cols;
    final int goalR, goalC;
    final int startR, startC, startOri;

    Main(String[] raw) {
        rows = raw.length;
        cols = raw[0].length();
        grid = new Cell[rows][cols];
        int gr = -1, gc = -1, sr = -1, sc = -1;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char ch = j < raw[i].length() ? raw[i].charAt(j) : ' ';
                switch (ch) {
                    case '#': grid[i][j] = Cell.FLOOR; break;
                    case 'O': grid[i][j] = Cell.WEAK;  break;
                    case 'X': grid[i][j] = Cell.GOAL;  gr = i; gc = j; break;
                    case 'S': grid[i][j] = Cell.FLOOR; sr = i; sc = j; break;
                    default : grid[i][j] = Cell.VOID;  break;
                }
            }
        }
        goalR = gr; goalC = gc; startR = sr; startC = sc; startOri = STAND;
    }

    boolean inside(int r, int c) {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }

    boolean isPlainFloor(int r, int c) {
        return inside(r, c) && grid[r][c] == Cell.FLOOR;
    }

    boolean isValid(int r, int c, int ori) {
        if (!inside(r, c)) return false;
        if (ori == STAND) {
            Cell cell = grid[r][c];
            return cell == Cell.FLOOR || cell == Cell.WEAK || cell == Cell.GOAL;
        }
        int r2 = r + (ori == VERTICAL ? 1 : 0);
        int c2 = c + (ori == HORIZONTAL ? 1 : 0);
        // 平躺由两格承重：必须都是普通地板
        return isPlainFloor(r, c) && isPlainFloor(r2, c2);
    }

    int heuristic(int r, int c, int ori) {
        // 中心点坐标（用 double 表达 0.5 偏移）
        double cr = r + (ori == VERTICAL ? 0.5 : 0.0);
        double cc = c + (ori == HORIZONTAL ? 0.5 : 0.0);
        double d = Math.abs(cr - goalR) + Math.abs(cc - goalC);
        // 单步中心位移上界 1.5 格 => 可采纳
        return (int) Math.floor(d / 1.5);
    }

    // ---------------- 状态封装 ----------------
    static final class State {
        final int r, c, ori, g, h, f;
        final long key;
        State parent;
        int parentDir;

        State(int r, int c, int ori, int g, int h, State parent, int parentDir) {
            this.r = r; this.c = c; this.ori = ori;
            this.g = g; this.h = h; this.f = g + h;
            this.parent = parent; this.parentDir = parentDir;
            this.key = encode(r, c, ori);
        }

        static long encode(int r, int c, int ori) {
            return (((long) r) << 20) | (((long) c) << 4) | ori;
        }
    }

    // ---------------- A* 求解 ----------------
    static final class Result {
        final int steps;
        final List<String> moves;
        final List<int[]> path;
        final int expanded;
        Result(int steps, List<String> moves, List<int[]> path, int expanded) {
            this.steps = steps; this.moves = moves; this.path = path; this.expanded = expanded;
        }
    }

    Result solve() {
        int n = rows * cols * 3;
        int[] best = new int[n];
        Arrays.fill(best, Integer.MAX_VALUE);

        PriorityQueue<State> open = new PriorityQueue<>(
            Comparator.comparingInt((State s) -> s.f)
                      .thenComparingInt(s -> s.h)   // 同分时优先更接近目标的节点
        );

        State start = new State(startR, startC, startOri, 0,
                                heuristic(startR, startC, startOri), null, -1);
        best[flat(startR, startC, startOri)] = 0;
        open.add(start);
        int expanded = 0;

        while (!open.isEmpty()) {
            State cur = open.poll();
            // 防御式剪枝：同一状态可能被多次入队，只处理第一次（g 最小）出队
            if (cur.g > best[flat(cur.r, cur.c, cur.ori)]) continue;
            expanded++;

            // 通关条件：竖立且正好落在洞上
            if (cur.ori == STAND && cur.r == goalR && cur.c == goalC) {
                return buildResult(cur, expanded);
            }

            for (int dir = 0; dir < 4; dir++) {
                int[] t = TRANS[cur.ori][dir];
                int nr = cur.r + t[0], nc = cur.c + t[1], nori = t[2];
                if (!isValid(nr, nc, nori)) continue;

                int ng = cur.g + 1;
                int idx = flat(nr, nc, nori);
                if (ng >= best[idx]) continue;
                best[idx] = ng;
                open.add(new State(nr, nc, nori, ng,
                                   heuristic(nr, nc, nori), cur, dir));
            }
        }
        return null;   // 无解
    }

    int flat(int r, int c, int ori) {
        return (r * cols + c) * 3 + ori;
    }

    Result buildResult(State end, int expanded) {
        LinkedList<String> moves = new LinkedList<>();
        LinkedList<int[]> path = new LinkedList<>();
        for (State s = end; s != null; s = s.parent) {
            path.addFirst(new int[]{s.r, s.c, s.ori});
            if (s.parent != null) moves.addFirst(DIR_NAME[s.parentDir]);
        }
        return new Result(end.g, moves, path, expanded);
    }

    // ---------------- 棋盘打印 ----------------
    void printPath(Result res) {
        for (int[] st : res.path) {
            char[][] canvas = new char[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++) canvas[i][j] = symbol(grid[i][j]);
            int r = st[0], c = st[1], ori = st[2];
            if (ori == STAND) {
                canvas[r][c] = 'B';
            } else {
                int r2 = r + (ori == VERTICAL ? 1 : 0);
                int c2 = c + (ori == HORIZONTAL ? 1 : 0);
                canvas[r][c] = 'B'; canvas[r2][c2] = 'B';
            }
            for (char[] row : canvas) System.out.println(new String(row));
            System.out.println("----------");
        }
    }

    static char symbol(Cell c) {
        switch (c) {
            case FLOOR: return '.';
            case WEAK:  return 'O';
            case GOAL:  return 'X';
            default:    return ' ';
        }
    }

    // ---------------- 入口 ----------------
    public static void main(String[] args) {
        String[] raw = {
            "  #####  ",
            "  #...#  ",
            "###O#O###",
            "#S.....X#",
            "###...# #",
            "  #####  "
        };
        Main game = new Main(raw);
        long t0 = System.nanoTime();
        Result res = game.solve();
        long ms = (System.nanoTime() - t0) / 1_000_000;

        if (res == null) {
            System.out.println("无解");
            return;
        }
        System.out.println("最少步数: " + res.steps);
        System.out.println("扩展节点: " + res.expanded + "，耗时 " + ms + "ms");
        System.out.println("动作序列: " + String.join(" → ", res.moves));
        game.printPath(res);
    }
}

5.2 多文件工程结构

上面是便于单测阅读的单文件版。实际工程里建议拆成包，逻辑边界更清晰：

bloxorz/
├── build.gradle
└── src/main/java/com/example/bloxorz/
    ├── Cell.java            // 枚举：VOID / FLOOR / WEAK / GOAL
    ├── Orientation.java     // 枚举：STAND / HORIZONTAL / VERTICAL
    ├── BlockState.java      // (r, c, orientation) 不可变值对象 + encode/decode
    ├── Board.java           // 地图解析、isValid、neighbor() 迭代
    ├── Heuristic.java       // 可采纳启发式
    ├── AStarSolver.java     // 搜索主循环 + 路径重建
    └── Main.java            // 命令行入口

关键设计点：Board.neighbor(state, dir) 把”查表 + 判定”封装成单一方法，A* 完全不关心游戏规则；BlockState 做成不可变对象，hashCode 用 (r << 20) | (c << 4) | ori 预先算好，可以直接进 HashSet 做图去重。

六、复杂度与工程要点

状态空间规模：O(R × C × 3)。求解器的时间复杂度是 O(V log V + E)，其中 E ≤ 4V，所以整体是 O(RC log(RC))。对 30×30 的地图，约 2700 个节点，耗时在毫秒级。

三条实战经验：

优先队列的去重要靠 best[]，不能靠 visited。A* 的非一致启发式会让同一状态以不同 g 多次入队，用布尔 visited 会漏掉更优路径；用”出队时比对 g“才是正确做法。
变换表里的 dr/dc 必须是”新左上角偏移”，不是”每格偏移”。这是实现中最容易算错的地方——STAND 向下滚一步，新占位是 (r+1,c) 到 (r+2,c)，左上角偏移是 +1，而不是 +2。
弱格判定要放在 isValid 里，而不是放在 neighbor 里。因为弱格约束依赖”当前占用格数”，而 neighbor 只知道目标状态——把判定下沉到目标状态判定，逻辑才不会分叉。

七、还能怎么扩展

双向 BFS：滚方块的可逆性极好（每个动作都有唯一的逆），从起终点同时 BFS 能把搜索半径减半，在这类小图上往往比 A* 更快。
预处理全图最短路：把所有”可站立的格子”建成一张辅助图，预先算忽略朝向的最短距离，作为 A* 的加权启发式（需注意保持可采纳）。
关卡生成：反过来做——随机撒弱格和目标，用 BFS 检测”是否存在一条 STAND 落到目标的路径”，同时要求路径长度超过阈值，就能自动生成难度递增的关卡。

滚方块教会我们的是：当一个游戏的规则足够离散时，把它 Compile 成”状态 + 转移表”就是最好的算法设计。规则里那些”弱格塌陷””必须竖立”的细节，最终都会沉淀成 isValid 里的几行 return——而搜索算法本身，反而成了最不需要动脑的部分。

Tagged with: Bloxorz 启发式搜索图搜索滚方块状态编码