每日算法 — 使用java实现叠叠高：物理稳定性模拟与贪心抽取策略

引言

叠叠高（Jenga）是一款经典的物理益智游戏，玩家从由多层木块交错堆叠而成的高塔中，逐块抽取木块并将其放置于塔顶，目标是使塔尽可能高而不倒塌。本文将用Java实现叠叠高的核心物理稳定性模拟与贪心抽取策略，帮助读者理解刚体物理模拟、重心计算与贪心决策算法。

游戏物理模型

叠叠高的核心物理原理是重心稳定性。当塔的重心投影超出底座支撑面时，塔就会倾倒。每根木块的抽取都会改变整体的质量分布，从而影响系统的重心位置。

核心物理量

• 木块尺寸：长 3 单位、宽 1 单位、高 0.5 单位
• 每层木块数：3 根，交错方向堆叠
• 重心投影：整体重心在水平面上的投影必须落在当前最底层木块组的支撑面内
• 倾倒条件：重心投影超出支撑面边界

核心算法设计

1. 木块与塔的数据结构

import java.util.*;

/**
 * 叠叠高木块类
 * 表示单根木块的物理属性和状态
 */
class Block {
    // 木块在局部坐标系中的位置（层内索引 0,1,2）
    int index;
    // 是否已被抽取
    boolean removed;
    // 木块质量（统一为单位质量）
    double mass = 1.0;

    public Block(int index) {
        this.index = index;
        this.removed = false;
    }
}

/**
 * 叠叠高塔层类
 * 每层包含3根木块，方向交替变化
 */
class Layer {
    // 层号，0为最底层
    int level;
    // 方向：true为X方向，false为Z方向
    boolean xDirection;
    // 该层的3根木块
    Block[] blocks;

    public Layer(int level) {
        this.level = level;
        // 偶数层沿X方向，奇数层沿Z方向
        this.xDirection = (level % 2 == 0);
        this.blocks = new Block[3];
        for (int i = 0; i < 3; i++) {
            blocks[i] = new Block(i);
        }
    }

    /**
     * 获取该层剩余（未抽取）的木块数量
     */
    public int remainingCount() {
        int count = 0;
        for (Block b : blocks) {
            if (!b.removed) count++;
        }
        return count;
    }

    /**
     * 获取该层剩余木块的索引列表
     */
    public List<Integer> remainingIndices() {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            if (!blocks[i].removed) list.add(i);
        }
        return list;
    }
}

2. 塔的物理稳定性计算

/**
 * 叠叠高塔类
 * 管理整个塔的状态并提供稳定性分析
 */
class JengaTower {
    // 木块尺寸常量
    static final double BLOCK_LENGTH = 3.0;  // 长
    static final double BLOCK_WIDTH = 1.0;   // 宽
    static final double BLOCK_HEIGHT = 0.5;  // 高

    // 塔的层列表
    List<Layer> layers;
    // 当前总层数
    int totalLayers;

    public JengaTower(int initialLayers) {
        this.totalLayers = initialLayers;
        this.layers = new ArrayList<>();
        for (int i = 0; i < initialLayers; i++) {
            layers.add(new Layer(i));
        }
    }

    /**
     * 计算塔在当前状态下的整体重心位置
     * 每层未抽取木块的质量均匀分布，逐层累加计算加权平均重心
     * 
     * @return double[]{centerX, centerZ} 重心在水平面上的坐标
     */
    public double[] calculateCenterOfMass() {
        double totalMass = 0;
        double weightedX = 0;
        double weightedZ = 0;

        for (Layer layer : layers) {
            // 该层的物理高度（Y坐标）
            double layerY = layer.level * BLOCK_HEIGHT + BLOCK_HEIGHT / 2;

            for (int i = 0; i < 3; i++) {
                Block block = layer.blocks[i];
                if (block.removed) continue;

                // 计算该木块在其层内的局部重心位置
                double[] localCenter = getBlockLocalCenter(layer, i);

                weightedX += localCenter[0] * block.mass;
                weightedZ += localCenter[1] * block.mass;
                totalMass += block.mass;
            }
        }

        if (totalMass == 0) return new double[]{0, 0};
        return new double[]{weightedX / totalMass, weightedZ / totalMass};
    }

    /**
     * 获取指定木块在水平面上的局部重心坐标
     * 根据层的方向，木块交错排列
     * 
     * @param layer 所在层
     * @param blockIndex 木块在层内的索引 0,1,2
     * @return double[]{x, z} 木块中心坐标
     */
    private double[] getBlockLocalCenter(Layer layer, int blockIndex) {
        // 偏移量：-1, 0, 1 对应三个木块位置
        double offset = blockIndex - 1;

        if (layer.xDirection) {
            // X方向层：木块沿X轴排列，长度方向为X
            // 每根木块占据宽度为 BLOCK_WIDTH 的空间
            double x = offset * BLOCK_WIDTH;
            double z = 0;
            return new double[]{x, z};
        } else {
            // Z方向层：木块沿Z轴排列
            double x = 0;
            double z = offset * BLOCK_WIDTH;
            return new double[]{x, z};
        }
    }

    /**
     * 判断塔是否稳定
     * 核心算法：整体重心投影必须落在最底层的支撑面内
     * 最底层支撑面是一个矩形，边界由最底层剩余木块决定
     * 
     * @return true if 塔稳定，false if 塔会倾倒
     */
    public boolean isStable() {
        double[] com = calculateCenterOfMass();
        double comX = com[0];
        double comZ = com[1];

        // 获取最底层的支撑边界
        double[] bounds = getBaseSupportBounds();
        double minX = bounds[0], maxX = bounds[1];
        double minZ = bounds[2], maxZ = bounds[3];

        // 重心投影必须严格在支撑面内（含边界）
        return comX >= minX && comX <= maxX && comZ >= minZ && comZ <= maxZ;
    }

    /**
     * 计算最底层的支撑边界
     * 最底层剩余木块构成的外接矩形即为支撑面
     * 
     * @return double[]{minX, maxX, minZ, maxZ}
     */
    private double[] getBaseSupportBounds() {
        Layer base = layers.get(0);
        List<Integer> remaining = base.remainingIndices();

        if (remaining.isEmpty()) {
            // 如果最底层全被抽走，向上一层寻找支撑
            return getLayerSupportBounds(1);
        }

        return getLayerSupportBounds(0);
    }

    /**
     * 计算指定层的支撑边界
     */
    private double[] getLayerSupportBounds(int level) {
        if (level >= layers.size()) {
            return new double[]{-0.5, 0.5, -0.5, 0.5};
        }

        Layer layer = layers.get(level);
        List<Integer> remaining = layer.remainingIndices();

        if (remaining.isEmpty()) {
            return getLayerSupportBounds(level + 1);
        }

        double minX = Double.MAX_VALUE, maxX = -Double.MAX_VALUE;
        double minZ = Double.MAX_VALUE, maxZ = -Double.MAX_VALUE;

        for (int idx : remaining) {
            double[] center = getBlockLocalCenter(layer, idx);
            // 木块在垂直于排列方向上的半长
            double halfLen = layer.xDirection ? BLOCK_LENGTH / 2 : BLOCK_WIDTH / 2;
            double halfWid = layer.xDirection ? BLOCK_WIDTH / 2 : BLOCK_LENGTH / 2;

            minX = Math.min(minX, center[0] - halfWid);
            maxX = Math.max(maxX, center[0] + halfWid);
            minZ = Math.min(minZ, center[1] - halfLen);
            maxZ = Math.max(maxZ, center[1] + halfLen);
        }

        return new double[]{minX, maxX, minZ, maxZ};
    }
}

3. 贪心抽取策略

/**
 * 叠叠高AI决策类
 * 使用贪心策略选择最优抽取木块
 */
class JengaAI {
    JengaTower tower;
    Random random = new Random();

    public JengaAI(JengaTower tower) {
        this.tower = tower;
    }

    /**
     * 贪心策略：选择使塔保持最稳定的木块进行抽取
     * 评估每个可抽取木块的"安全分数"，选择分数最高的
     * 
     * 安全分数 = 抽取后塔的稳定性度量
     * 稳定性度量 = 重心到支撑面边界的最近距离（越大越稳定）
     * 
     * @return Move对象，包含抽取位置和放置位置
     */
    public Move findBestMove() {
        List<MoveCandidate> candidates = new ArrayList<>();

        // 遍历所有可抽取的木块（非顶层且未抽取）
        for (int level = 0; level < tower.layers.size() - 1; level++) {
            Layer layer = tower.layers.get(level);
            for (int idx = 0; idx < 3; idx++) {
                if (layer.blocks[idx].removed) continue;

                // 模拟抽取该木块
                double safetyScore = evaluateRemoval(level, idx);
                candidates.add(new MoveCandidate(level, idx, safetyScore));
            }
        }

        if (candidates.isEmpty()) return null;

        // 贪心：选择安全分数最高的
        candidates.sort((a, b) -> Double.compare(b.safetyScore, a.safetyScore));
        MoveCandidate best = candidates.get(0);

        // 放置在塔顶（新的一层）
        int newLevel = tower.totalLayers;

        return new Move(best.level, best.blockIndex, newLevel);
    }

    /**
     * 评估抽取指定木块后的稳定性
     * 使用"重心偏移量"作为稳定性度量
     * 
     * @param level 木块所在层
     * @param blockIndex 木块索引
     * @return 安全分数（正值表示稳定，越大越稳定；负值表示会倾倒）
     */
    private double evaluateRemoval(int level, int blockIndex) {
        // 保存原始状态
        Block block = tower.layers.get(level).blocks[blockIndex];
        boolean originalState = block.removed;

        // 模拟抽取
        block.removed = true;

        // 计算抽取后的重心
        double[] com = tower.calculateCenterOfMass();
        double comX = com[0];
        double comZ = com[1];

        // 计算支撑边界
        double[] bounds = tower.getBaseSupportBounds();
        double minX = bounds[0], maxX = bounds[1];
        double minZ = bounds[2], maxZ = bounds[3];

        // 计算重心到四个边界的距离
        double distLeft = comX - minX;
        double distRight = maxX - comX;
        double distBottom = comZ - minZ;
        double distTop = maxZ - comZ;

        // 安全分数取最小边界距离（瓶颈决定稳定性）
        double safetyScore = Math.min(Math.min(distLeft, distRight), 
                                       Math.min(distBottom, distTop));

        // 恢复原始状态
        block.removed = originalState;

        return safetyScore;
    }

    /**
     * 另一种贪心策略：优先抽取中间木块
     * 因为中间木块对重心影响最小
     */
    public Move findCenterFirstMove() {
        // 优先抽取每层的中间木块（index=1）
        for (int level = 0; level < tower.layers.size() - 1; level++) {
            if (!tower.layers.get(level).blocks[1].removed) {
                return new Move(level, 1, tower.totalLayers);
            }
        }
        // 中间木块抽完后再抽两边
        return findBestMove();
    }
}

/**
 * 移动候选类
 */
class MoveCandidate {
    int level;
    int blockIndex;
    double safetyScore;

    public MoveCandidate(int level, int blockIndex, double safetyScore) {
        this.level = level;
        this.blockIndex = blockIndex;
        this.safetyScore = safetyScore;
    }
}

/**
 * 移动操作类
 */
class Move {
    int fromLevel;    // 从哪层抽取
    int fromIndex;    // 抽取哪根木块
    int toLevel;      // 放置到哪层

    public Move(int fromLevel, int fromIndex, int toLevel) {
        this.fromLevel = fromLevel;
        this.fromIndex = fromIndex;
        this.toLevel = toLevel;
    }

    @Override
    public String toString() {
        return String.format("抽取第%d层第%d号木块 -> 放置到第%d层", 
                            fromLevel + 1, fromIndex + 1, toLevel + 1);
    }
}

4. 完整游戏模拟器

/**
 * 叠叠高完整游戏模拟器
 */
public class JengaGame {

    public static void main(String[] args) {
        // 初始化16层标准叠叠高塔
        JengaTower tower = new JengaTower(16);
        JengaAI ai = new JengaAI(tower);

        System.out.println("=== 叠叠高游戏模拟开始 ===");
        System.out.println("初始塔高: " + tower.totalLayers + " 层");
        System.out.println("初始稳定性: " + (tower.isStable() ? "稳定" : "不稳定"));

        int moveCount = 0;
        final int MAX_MOVES = 100;

        while (moveCount < MAX_MOVES) {
            // AI寻找最佳移动
            Move move = ai.findBestMove();

            if (move == null) {
                System.out.println("没有可抽取的木块了！");
                break;
            }

            // 执行移动：抽取木块
            Block block = tower.layers.get(move.fromLevel).blocks[move.fromIndex];
            block.removed = true;

            // 在塔顶添加新层（放置木块）
            if (move.toLevel >= tower.layers.size()) {
                tower.layers.add(new Layer(move.toLevel));
                tower.totalLayers++;
            }
            // 将木块放置到新层
            Layer newLayer = tower.layers.get(move.toLevel);
            for (int i = 0; i < 3; i++) {
                if (newLayer.blocks[i] == null || newLayer.blocks[i].removed) {
                    // 简化处理：新放置的木块填充到新层
                    newLayer.blocks[i] = new Block(i);
                    break;
                }
            }

            moveCount++;

            // 检查稳定性
            boolean stable = tower.isStable();
            double[] com = tower.calculateCenterOfMass();

            System.out.printf("第%3d步: %s | 重心(%.3f, %.3f) | %s%n", 
                moveCount, move, com[0], com[1],
                stable ? "稳定" : "*** 倾倒！***");

            if (!stable) {
                System.out.println("\n塔在抽取后倾倒！游戏结束。");
                System.out.println("总步数: " + moveCount);
                break;
            }
        }

        if (moveCount == MAX_MOVES) {
            System.out.println("\n达到最大步数限制，模拟结束。");
        }

        System.out.println("最终塔高: " + tower.totalLayers + " 层");
        System.out.println("=== 叠叠高游戏模拟结束 ===");
    }
}

算法复杂度分析

策略优化方向

1. 蒙特卡洛模拟：对每种抽取方案进行多次随机后续模拟，统计倒塌概率
2. Minimax博弈：在双人叠叠高中，考虑对手的最优反制策略
3. 物理引擎集成：使用更精确的刚体物理（如Box2D）模拟木块间的接触力和摩擦力
4. 神经网络估值：训练深度网络预测塔的稳定性，替代显式重心计算

总结

本文通过Java实现了叠叠高游戏的核心物理稳定性模拟与贪心抽取策略。关键算法包括：
– 重心计算：加权平均法计算多层系统的整体重心
– 稳定性判定：重心投影法判断结构是否倾倒
– 贪心策略：评估每个可行动作对稳定性的影响，选择最优方案

叠叠高是理解刚体物理与结构力学的绝佳案例，其算法思想也可应用于建筑结构分析、机器人平衡控制等领域。