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

一、游戏简介与算法目标

叠叠乐（Jenga）是一款经典的物理益智游戏，玩家轮流从由多层木块堆叠而成的塔中抽取一块，并将其放置到塔顶。塔体在失去支撑后会发生倾斜，当重心超出底面支撑范围时塔倒塌，游戏结束。

本文的核心算法目标包括三个层面：
1. 物理稳定性判定：计算塔体在当前结构下的重心位置，判断是否超出底面支撑多边形
2. 最优抽取策略：为AI玩家选择使塔体稳定性下降最小的木块进行抽取
3. 塔顶放置优化：选择最优放置位置使塔体重心尽量居中

二、核心算法原理

2.1 重心计算模型

将塔体抽象为若干长方体木块的组合。每个木块的重心位于其几何中心，塔体整体重心为各木块重心的加权平均（假设质量均匀分布）：

Cx = Σ(mi * xi) / Σmi
Cy = Σ(mi * yi) / Σmi

对于标准叠叠乐塔，所有木块质量相同，公式简化为算术平均。

2.2 稳定性判定

塔体稳定的充要条件：整体重心在水平面上的投影必须落在最底层木块的支撑范围内。对于矩形底面，支撑范围是一个矩形区域；当底层有多块木块时，支撑范围是这些木块底面的凸包。

2.3 贪心抽取策略

AI选择抽取木块的策略：
1. 模拟抽取每块可抽取的木块
2. 计算抽取后塔体的稳定性指标（重心偏移量）
3. 选择使稳定性指标最优（重心偏移最小）的木块
4. 若有多块等价，优先选择中层木块（降低后续抽取难度）

三、Java完整实现

import java.util.*;

/**
 * 叠叠乐（Jenga）物理稳定性模拟与贪心策略AI
 * 核心算法：重心计算、稳定性判定、贪心最优抽取
 */
public class JengaGame {

    // 塔体参数
    private static final int BLOCKS_PER_LAYER = 3;  // 每层木块数
    private static final double BLOCK_WIDTH = 25.0;  // 木块宽度(mm)
    private static final double BLOCK_LENGTH = 75.0; // 木块长度(mm)
    private static final double BLOCK_HEIGHT = 15.0; // 木块高度(mm)
    private static final double GAP = 1.0;           // 木块间隙(mm)

    // 木块状态
    static class Block {
        int layer;          // 所在层数(0为底层)
        int index;          // 层内索引(0,1,2)
        double centerX, centerY; // 重心坐标
        boolean removed;    // 是否已被抽取
        boolean placed;     // 是否已放置到塔顶

        Block(int layer, int index) {
            this.layer = layer;
            this.index = index;
            this.removed = false;
            this.placed = false;
            // 初始化位置：奇偶层交替方向
            if (layer % 2 == 0) {
                // 水平层：木块沿X轴排列
                this.centerX = (index - 1) * (BLOCK_WIDTH + GAP);
                this.centerY = 0;
            } else {
                // 垂直层：木块沿Y轴排列
                this.centerX = 0;
                this.centerY = (index - 1) * (BLOCK_WIDTH + GAP);
            }
        }

        // 获取木块在当前层的水平跨度
        double getMinX() {
            if (layer % 2 == 0) return centerX - BLOCK_WIDTH / 2;
            return centerX - BLOCK_LENGTH / 2;
        }
        double getMaxX() {
            if (layer % 2 == 0) return centerX + BLOCK_WIDTH / 2;
            return centerX + BLOCK_LENGTH / 2;
        }
        double getMinY() {
            if (layer % 2 == 0) return centerY - BLOCK_LENGTH / 2;
            return centerY - BLOCK_WIDTH / 2;
        }
        double getMaxY() {
            if (layer % 2 == 0) return centerY + BLOCK_LENGTH / 2;
            return centerY + BLOCK_WIDTH / 2;
        }
    }

    private List<Block> blocks;      // 所有木块
    private int totalLayers;         // 当前总层数
    private Random random;

    public JengaGame(int initialLayers) {
        this.blocks = new ArrayList<>();
        this.totalLayers = initialLayers;
        this.random = new Random();
        initializeTower(initialLayers);
    }

    /**
     * 初始化标准塔体
     */
    private void initializeTower(int layers) {
        for (int l = 0; l < layers; l++) {
            for (int i = 0; i < BLOCKS_PER_LAYER; i++) {
                Block b = new Block(l, i);
                blocks.add(b);
            }
        }
    }

    /**
     * 计算塔体整体重心
     * 算法：遍历所有未移除的木块，求算术平均重心
     * 时间复杂度：O(n)，n为木块总数
     */
    public double[] calculateCenterOfGravity() {
        double sumX = 0, sumY = 0, sumZ = 0;
        int count = 0;

        for (Block b : blocks) {
            if (!b.removed || b.placed) {
                sumX += b.centerX;
                sumY += b.centerY;
                // Z坐标由层数决定，底层为0，向上递增
                sumZ += b.layer * BLOCK_HEIGHT + BLOCK_HEIGHT / 2;
                count++;
            }
        }

        if (count == 0) return new double[]{0, 0, 0};
        return new double[]{sumX / count, sumY / count, sumZ / count};
    }

    /**
     * 计算最底层支撑区域（凸包近似为矩形并集）
     * 返回支撑区域的边界框
     */
    public double[] getSupportBounds() {
        double minX = Double.POSITIVE_INFINITY, maxX = Double.NEGATIVE_INFINITY;
        double minY = Double.POSITIVE_INFINITY, maxY = Double.NEGATIVE_INFINITY;

        for (Block b : blocks) {
            if (b.layer == 0 && !b.removed) {
                minX = Math.min(minX, b.getMinX());
                maxX = Math.max(maxX, b.getMaxX());
                minY = Math.min(minY, b.getMinY());
                maxY = Math.max(maxY, b.getMaxY());
            }
        }

        return new double[]{minX, maxX, minY, maxY};
    }

    /**
     * 稳定性判定核心算法
     * 判断重心投影是否在支撑范围内
     * 返回：true-稳定，false-倒塌
     */
    public boolean isStable() {
        double[] cog = calculateCenterOfGravity();
        double[] bounds = getSupportBounds();

        // 重心投影必须在支撑矩形内（含边界）
        double margin = 0.5; // 安全裕度(mm)
        boolean stable = cog[0] >= bounds[0] + margin && cog[0] <= bounds[1] - margin
                      && cog[1] >= bounds[2] + margin && cog[1] <= bounds[3] - margin;

        return stable;
    }

    /**
     * 计算稳定性指标：重心到支撑边界的最小距离
     * 值越大越稳定，值<=0表示即将倒塌
     */
    public double stabilityMetric() {
        double[] cog = calculateCenterOfGravity();
        double[] bounds = getSupportBounds();

        double distLeft = cog[0] - bounds[0];
        double distRight = bounds[1] - cog[0];
        double distBottom = cog[1] - bounds[2];
        double distTop = bounds[3] - cog[1];

        return Math.min(Math.min(distLeft, distRight), Math.min(distBottom, distTop));
    }

    /**
     * 获取所有可抽取的木块（非顶层且未被移除）
     */
    public List<Block> getRemovableBlocks() {
        List<Block> removable = new ArrayList<>();
        for (Block b : blocks) {
            if (!b.removed && b.layer < totalLayers - 1) {
                removable.add(b);
            }
        }
        return removable;
    }

    /**
     * 模拟抽取某块后的稳定性（不改变实际状态）
     */
    public double simulateRemoval(Block target) {
        boolean originalRemoved = target.removed;
        target.removed = true;
        double metric = stabilityMetric();
        target.removed = originalRemoved;
        return metric;
    }

    /**
     * 贪心最优抽取策略
     * 算法：遍历所有可抽取木块，选择使稳定性下降最小的块
     * 时间复杂度：O(k * n)，k为可抽取数，n为总木块数
     */
    public Block greedyBestRemoval() {
        List<Block> candidates = getRemovableBlocks();
        if (candidates.isEmpty()) return null;

        Block bestBlock = null;
        double bestMetric = Double.NEGATIVE_INFINITY;

        for (Block b : candidates) {
            double metric = simulateRemoval(b);
            // 优先选择抽取后稳定性最高的
            if (metric > bestMetric) {
                bestMetric = metric;
                bestBlock = b;
            } else if (metric == bestMetric && bestBlock != null) {
                // 稳定性相同时，优先选择中层木块（减少上层压力）
                int midLayer = totalLayers / 2;
                if (Math.abs(b.layer - midLayer) < Math.abs(bestBlock.layer - midLayer)) {
                    bestBlock = b;
                }
            }
        }

        return bestBlock;
    }

    /**
     * 塔顶放置策略：选择使新层重心最居中的放置位置
     */
    public void placeOnTop(Block removedBlock) {
        // 新增一层
        int newLayer = totalLayers;
        totalLayers++;

        // 根据奇偶层决定方向
        double bestX = 0, bestY = 0;
        double minOffset = Double.POSITIVE_INFINITY;

        // 尝试三种标准位置
        int[][] positions = {{-1, 0}, {0, 0}, {1, 0}};
        for (int[] pos : positions) {
            double testX, testY;
            if (newLayer % 2 == 0) {
                testX = pos[0] * (BLOCK_WIDTH + GAP);
                testY = 0;
            } else {
                testX = 0;
                testY = pos[0] * (BLOCK_WIDTH + GAP);
            }

            // 临时设置位置计算重心偏移
            removedBlock.centerX = testX;
            removedBlock.centerY = testY;
            removedBlock.layer = newLayer;
            removedBlock.placed = true;

            double[] cog = calculateCenterOfGravity();
            double offset = Math.abs(cog[0]) + Math.abs(cog[1]);

            if (offset < minOffset) {
                minOffset = offset;
                bestX = testX;
                bestY = testY;
            }
        }

        // 应用最优位置
        removedBlock.centerX = bestX;
        removedBlock.centerY = bestY;
        removedBlock.layer = newLayer;
        removedBlock.placed = true;
    }

    /**
     * 执行一次完整回合：抽取+放置
     */
    public boolean playTurn() {
        if (!isStable()) {
            System.out.println("塔已倒塌！游戏结束。");
            return false;
        }

        Block toRemove = greedyBestRemoval();
        if (toRemove == null) {
            System.out.println("没有可抽取的木块！");
            return false;
        }

        System.out.printf("AI抽取第%d层第%d块木块，当前稳定性指标: %.2fmm%n",
            toRemove.layer + 1, toRemove.index + 1, stabilityMetric());

        toRemove.removed = true;

        if (!isStable()) {
            System.out.println("抽取后塔倒塌！游戏结束。");
            return false;
        }

        placeOnTop(toRemove);
        System.out.printf("放置到第%d层，新稳定性指标: %.2fmm%n%n",
            totalLayers, stabilityMetric());

        return true;
    }

    /**
     * 运行完整模拟
     */
    public void simulateGame() {
        System.out.println("=== 叠叠乐（Jenga）物理稳定性模拟 ===");
        System.out.printf("初始层数: %d，总木块数: %d%n", totalLayers, blocks.size());
        System.out.printf("初始稳定性指标: %.2fmm%n%n", stabilityMetric());

        int turn = 1;
        while (playTurn()) {
            turn++;
            if (turn > 100) {
                System.out.println("达到最大回合数限制。");
                break;
            }
        }

        System.out.printf("游戏进行了%d回合后结束。%n", turn - 1);
    }

    public static void main(String[] args) {
        JengaGame game = new JengaGame(16); // 标准16层叠叠乐
        game.simulateGame();
    }
}

四、算法复杂度分析

五、扩展思考

1. 三维倾斜模型：实际塔体可能发生三维倾斜，可引入四元数或旋转矩阵描述姿态，通过力矩平衡方程判定稳定性。
2. 随机扰动因子：真实游戏中存在手抖和放置误差，可在模型中加入高斯噪声模拟不确定性。
3. 对抗策略：在双人游戏中，玩家可选择使对手下回合最困难的抽取方式，这转化为一个minimax博弈问题。
4. 机器学习增强：可用神经网络拟合复杂稳定性边界，替代简化的重心判定模型。

六、总结

本文通过叠叠乐游戏讲解了物理重心计算、稳定性判定和贪心策略三个核心算法。Java实现从基础的重心加权平均出发，构建了完整的塔体稳定性评估框架，并基于贪心思想设计了AI抽取策略。该框架可扩展至更复杂的物理模拟和博弈分析场景。