每日算法 — 使用java实现Minecraft：Perlin噪声地形生成与洞穴细胞自动机

一、程序化地形生成的算法核心

Minecraft的世界并非预先设计，而是由算法实时生成。其核心是伪随机噪声函数：给定相同的种子，任何玩家都能重建完全一致的地形。本文聚焦两大算法：

• Perlin噪声：生成自然起伏的地形高度图
• 细胞自动机：模拟侵蚀作用生成洞穴与峡谷网络

二、Perlin噪声原理与实现

Perlin噪声通过梯度向量的平滑插值，生成连续可导的伪随机信号。相比纯随机，它保证了空间连续性——相邻采样点的值高度相关。

/**
 * 二维Perlin噪声实现
 * 核心：梯度网格 + 平滑插值（fade函数）
 */
public class PerlinNoise {
    private final int[] permutation;
    private final int[] p; // 扩展后的排列表（512长度，避免越界）

    public PerlinNoise(int seed) {
        // 基于种子初始化256个梯度索引的伪随机排列
        permutation = new int[256];
        for (int i = 0; i < 256; i++) permutation[i] = i;

        // Fisher-Yates洗牌，使用线性同余作为PRNG
        long state = seed;
        for (int i = 255; i > 0; i--) {
            state = (state * 1103515245L + 12345) & 0x7FFFFFFF;
            int j = (int)(state % (i + 1));
            int tmp = permutation[i];
            permutation[i] = permutation[j];
            permutation[j] = tmp;
        }

        // 扩展为512长度，避免边界检查
        p = new int[512];
        for (int i = 0; i < 512; i++) {
            p[i] = permutation[i & 255];
        }
    }

    /**
     * 核心噪声采样函数
     * @param x 世界坐标X
     * @param y 世界坐标Y（在Minecraft中通常对应高度或Z坐标）
     * @return [-1, 1] 范围内的平滑噪声值
     */
    public double noise(double x, double y) {
        // 1. 找到所在网格单元
        int X = (int)Math.floor(x) & 255;
        int Y = (int)Math.floor(y) & 255;

        // 2. 计算单元内局部坐标
        double xf = x - Math.floor(x);
        double yf = y - Math.floor(y);

        // 3. 应用fade曲线：6t^5 - 15t^4 + 10t^3
        // 保证二阶导数连续，消除网格视觉痕迹
        double u = fade(xf);
        double v = fade(yf);

        // 4. 四个角点的梯度哈希值
        int aa = p[p[X] + Y];
        int ab = p[p[X] + Y + 1];
        int ba = p[p[X + 1] + Y];
        int bb = p[p[X + 1] + Y + 1];

        // 5. 计算四个角点的梯度影响值
        double x1 = grad(aa, xf, yf);
        double x2 = grad(ba, xf - 1, yf);
        double y1 = lerp(u, x1, x2);

        double x3 = grad(ab, xf, yf - 1);
        double x4 = grad(bb, xf - 1, yf - 1);
        double y2 = lerp(u, x3, x4);

        // 6. 双线性插值得到最终值
        return lerp(v, y1, y2);
    }

    /** Ken Perlin的fade函数：S型平滑曲线 */
    private double fade(double t) {
        return t * t * t * (t * (t * 6 - 15) + 10);
    }

    /** 线性插值 */
    private double lerp(double t, double a, double b) {
        return a + t * (b - a);
    }

    /**
     * 梯度点积计算
     * 使用预定义的12个梯度方向（简化自经典Perlin）
     */
    private double grad(int hash, double x, double y) {
        int h = hash & 15;
        double u = h < 8 ? x : y;
        double v = h < 4 ? y : (h == 12 || h == 14 ? x : 0);
        return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
    }

    /**
     * 倍频叠加（Fractal Brownian Motion）
     * 叠加多个频率的Perlin噪声，模拟自然地貌的多尺度特征
     * @param octaves 倍频数（通常4~8）
     * @param lacunarity 频率倍增因子（通常2.0）
     * @param gain 振幅衰减因子（通常0.5）
     */
    public double fbm(double x, double y, int octaves, double lacunarity, double gain) {
        double total = 0;
        double frequency = 1;
        double amplitude = 1;
        double maxValue = 0; // 归一化用

        for (int i = 0; i < octaves; i++) {
            total += noise(x * frequency, y * frequency) * amplitude;
            maxValue += amplitude;
            amplitude *= gain;
            frequency *= lacunarity;
        }

        return total / maxValue; // 归一化到[-1, 1]
    }
}

三、地形高度图生成

Minecraft将世界切分为16×16的Chunk。每个Chunk生成时，基于世界坐标计算高度图，再填充方块。

/**
 * Minecraft风格地形生成器
 */
public class TerrainGenerator {
    private final PerlinNoise heightNoise;    // 主地形起伏
    private final PerlinNoise detailNoise;    // 细节噪声
    private final PerlinNoise caveNoise;      // 洞穴三维噪声
    private final int seaLevel = 64;          // 海平面高度
    private final int worldHeight = 128;      // 世界最大高度

    public TerrainGenerator(int seed) {
        // 使用不同种子派生多个独立噪声源
        heightNoise = new PerlinNoise(seed);
        detailNoise = new PerlinNoise(seed + 1);
        caveNoise = new PerlinNoise(seed + 2);
    }

    /**
     * 生成单个Chunk的地形高度图
     * @param chunkX Chunk的X坐标
     * @param chunkZ Chunk的Z坐标
     * @return 16×16的高度图数组
     */
    public int[][] generateHeightMap(int chunkX, int chunkZ) {
        int[][] heights = new int[16][16];
        double scale = 0.01; // 世界缩放因子：小值=平缓丘陵，大值=陡峭山峰

        for (int localX = 0; localX < 16; localX++) {
            for (int localZ = 0; localZ < 16; localZ++) {
                double worldX = (chunkX * 16 + localX) * scale;
                double worldZ = (chunkZ * 16 + localZ) * scale;

                // 主地形：低频大尺度起伏
                double baseHeight = heightNoise.fbm(worldX, worldZ, 6, 2.0, 0.5);

                // 细节：高频小尺度扰动
                double detail = detailNoise.fbm(worldX * 2, worldZ * 2, 4, 2.0, 0.5) * 0.1;

                // 归一化到实际高度范围 [seaLevel-20, seaLevel+40]
                double normalized = (baseHeight + detail + 1) / 2.0; // [0, 1]
                heights[localX][localZ] = (int)(normalized * 60) + (seaLevel - 20);

                //  clamp到有效范围
                heights[localX][localZ] = Math.max(1, Math.min(worldHeight - 1, heights[localX][localZ]));
            }
        }
        return heights;
    }

    /**
     * 生成Chunk的三维方块数据
     * 方块类型：0=空气, 1=石头, 2=泥土, 3=草方块, 4=沙子, 5=水
     */
    public byte[][][] generateChunkBlocks(int chunkX, chunkZ) {
        int[][] heightMap = generateHeightMap(chunkX, chunkZ);
        byte[][][] blocks = new byte[16][worldHeight][16];

        for (int x = 0; x < 16; x++) {
            for (int z = 0; z < 16; z++) {
                int surface = heightMap[x][z];

                for (int y = 0; y < worldHeight; y++) {
                    if (y > surface && y <= seaLevel) {
                        blocks[x][y][z] = 5; // 水
                    } else if (y == surface && y > seaLevel) {
                        blocks[x][y][z] = 3; // 草方块
                    } else if (y < surface && y >= surface - 3) {
                        blocks[x][y][z] = 2; // 泥土层
                    } else if (y < surface - 3) {
                        blocks[x][y][z] = 1; // 石头
                    } else {
                        blocks[x][y][z] = 0; // 空气
                    }
                }
            }
        }

        // 第二步：应用洞穴侵蚀
        applyCaves(blocks, chunkX, chunkZ);

        return blocks;
    }
}

四、细胞自动机洞穴生成

单纯噪声生成的洞穴过于”圆润”。Minecraft采用3D Perlin噪声 + 细胞自动机平滑两步法：先用噪声划定大致空腔区域，再用细胞自动机迭代平滑边界，产生自然的粗糙岩壁。

public class TerrainGenerator {

    /**
     * 基于3D噪声 + 细胞自动机的洞穴系统
     * 
     * 算法流程：
     * 1. 用3D Perlin噪声生成初始洞穴掩码
     * 2. 用Moore邻域细胞自动机迭代平滑边界
     * 3. 仅对y<50的地下区域应用（地表保持完整）
     */
    void applyCaves(byte[][][] blocks, int chunkX, int chunkZ) {
        double caveScale = 0.03;
        double threshold = 0.15; // 噪声值低于此阈值生成洞穴

        // 第一步：3D噪声初始化洞穴掩码
        boolean[][][] caveMask = new boolean[16][worldHeight][16];
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < worldHeight; y++) {
                for (int z = 0; z < 16; z++) {
                    if (y > 50) continue; // 洞穴只出现在地下

                    double wx = (chunkX * 16 + x) * caveScale;
                    double wy = y * caveScale;
                    double wz = (chunkZ * 16 + z) * caveScale;

                    // 3D噪声：叠加两个不同频率的噪声
                    double n1 = caveNoise.noise(wx, wy, wz);
                    double n2 = caveNoise.noise(wx * 2 + 100, wy * 2 + 100, wz * 2 + 100) * 0.5;
                    double combined = (n1 + n2) / 1.5;

                    // 越深越容易产生洞穴（指数衰减）
                    double depthFactor = Math.exp(-y / 30.0);
                    caveMask[x][y][z] = combined < threshold * depthFactor;
                }
            }
        }

        // 第二步：细胞自动机平滑（5轮迭代）
        for (int iteration = 0; iteration < 5; iteration++) {
            boolean[][][] next = new boolean[16][worldHeight][16];

            for (int x = 1; x < 15; x++) {
                for (int y = 1; y < worldHeight - 1; y++) {
                    for (int z = 1; z < 15; z++) {
                        int neighbors = countCaveNeighbors(caveMask, x, y, z);

                        // 规则：
                        // - 如果当前是洞穴且邻居<4，则填回（消除孤岛空腔）
                        // - 如果当前是石头且邻居>5，则挖空（扩大主洞穴）
                        if (caveMask[x][y][z]) {
                            next[x][y][z] = neighbors >= 4;
                        } else {
                            next[x][y][z] = neighbors > 5;
                        }
                    }
                }
            }
            caveMask = next;
        }

        // 第三步：应用洞穴掩码到方块数据
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < worldHeight; y++) {
                for (int z = 0; z < 16; z++) {
                    if (caveMask[x][y][z] && blocks[x][y][z] != 0) {
                        blocks[x][y][z] = 0; // 挖空
                    }
                }
            }
        }
    }

    /**
     * 统计3D Moore邻域中的洞穴邻居数（26邻域）
     */
    int countCaveNeighbors(boolean[][][] mask, int cx, int cy, int cz) {
        int count = 0;
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                for (int dz = -1; dz <= 1; dz++) {
                    if (dx == 0 && dy == 0 && dz == 0) continue;
                    int nx = cx + dx, ny = cy + dy, nz = cz + dz;
                    if (nx >= 0 && nx < 16 && ny >= 0 && ny < worldHeight && nz >= 0 && nz < 16) {
                        if (mask[nx][ny][nz]) count++;
                    }
                }
            }
        }
        return count;
    }
}

五、可视化渲染与种子一致性验证

import javax.swing.*;
import java.awt.*;
import java.awt.image.BufferedImage;

/**
 * 地形可视化器：将高度图渲染为俯视图和截面图
 */
public class TerrainVisualizer extends JPanel {
    private final TerrainGenerator generator;
    private final int viewRadius = 4; // 渲染半径（Chunk数）

    public TerrainVisualizer(int seed) {
        this.generator = new TerrainGenerator(seed);
        setPreferredSize(new Dimension(800, 600));
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);

        // 俯视图：每个像素代表一个方块列的最高非空气方块
        int imgSize = viewRadius * 2 * 16;
        BufferedImage topDown = new BufferedImage(imgSize, imgSize, BufferedImage.TYPE_INT_RGB);

        for (int cx = -viewRadius; cx < viewRadius; cx++) {
            for (int cz = -viewRadius; cz < viewRadius; cz++) {
                byte[][][] blocks = generator.generateChunkBlocks(cx, cz);

                for (int x = 0; x < 16; x++) {
                    for (int z = 0; z < 16; z++) {
                        // 找到最高非空气方块
                        int topY = 0;
                        for (int y = generator.worldHeight - 1; y >= 0; y--) {
                            if (blocks[x][y][z] != 0) {
                                topY = y;
                                break;
                            }
                        }

                        // 颜色映射
                        Color c = getBlockColor(blocks[x][topY][z], topY);
                        int px = (cx + viewRadius) * 16 + x;
                        int pz = (cz + viewRadius) * 16 + z;
                        topDown.setRGB(px, pz, c.getRGB());
                    }
                }
            }
        }

        g.drawImage(topDown, 10, 10, null);
        g.setColor(Color.WHITE);
        g.drawString("Seed: " + generator.hashCode(), 10, imgSize + 30);
    }

    Color getBlockColor(byte block, int height) {
        switch (block) {
            case 1: return new Color(128, 128, 128); // 石头
            case 2: return new Color(139, 119, 101); // 泥土
            case 3: return new Color(34, 139, 34);   // 草
            case 4: return new Color(238, 214, 175); // 沙子
            case 5: return new Color(64, 164, 223);  // 水
            default: return new Color(135, 206, 235); // 天空
        }
    }

    public static void main(String[] args) {
        // 验证种子一致性：相同种子必须生成相同地形
        int seed = 12345;

        TerrainGenerator g1 = new TerrainGenerator(seed);
        TerrainGenerator g2 = new TerrainGenerator(seed);

        int[][] h1 = g1.generateHeightMap(0, 0);
        int[][] h2 = g2.generateHeightMap(0, 0);

        boolean match = true;
        for (int i = 0; i < 16; i++) {
            for (int j = 0; j < 16; j++) {
                if (h1[i][j] != h2[i][j]) match = false;
            }
        }
        System.out.println("Seed consistency test: " + (match ? "PASS" : "FAIL"));

        // 可视化窗口
        JFrame frame = new JFrame("Minecraft Terrain Generator");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(new TerrainVisualizer(seed));
        frame.pack();
        frame.setVisible(true);
    }
}

六、Simplex噪声优化（进阶）

Perlin噪声在高维时有O(2^n)的梯度查找开销。Simplex噪声将其优化到O(n^2)，且视觉质量更优。

/**
 * Simplex噪声核心改进：
 * 1. 使用单形网格（Simplex Grid）替代立方体网格
 * 2. n维空间只需访问n+1个角点（Perlin需要2^n个）
 * 3. 梯度分布更均匀，避免方向性伪影
 */
public class SimplexNoise {
    private final int[] perm = new int[512];
    private static final double F2 = 0.5 * (Math.sqrt(3.0) - 1.0);
    private static final double G2 = (3.0 - Math.sqrt(3.0)) / 6.0;

    public SimplexNoise(int seed) {
        int[] p = new int[256];
        for (int i = 0; i < 256; i++) p[i] = i;
        java.util.Random rnd = new java.util.Random(seed);
        for (int i = 255; i > 0; i--) {
            int j = rnd.nextInt(i + 1);
            int tmp = p[i]; p[i] = p[j]; p[j] = tmp;
        }
        for (int i = 0; i < 512; i++) perm[i] = p[i & 255];
    }

    public double noise(double xin, double yin) {
        double s = (xin + yin) * F2;
        int i = (int)Math.floor(xin + s);
        int j = (int)Math.floor(yin + s);
        double t = (i + j) * G2;
        double X0 = i - t, Y0 = j - t;
        double x0 = xin - X0, y0 = yin - Y0;

        int i1, j1;
        if (x0 > y0) { i1 = 1; j1 = 0; }
        else { i1 = 0; j1 = 1; }

        double x1 = x0 - i1 + G2, y1 = y0 - j1 + G2;
        double x2 = x0 - 1.0 + 2.0 * G2, y2 = y0 - 1.0 + 2.0 * G2;

        int ii = i & 255, jj = j & 255;
        double n0 = 0, n1 = 0, n2 = 0;

        double t0 = 0.5 - x0 * x0 - y0 * y0;
        if (t0 >= 0) { t0 *= t0; n0 = t0 * t0 * grad(perm[ii + perm[jj]], x0, y0); }

        double t1 = 0.5 - x1 * x1 - y1 * y1;
        if (t1 >= 0) { t1 *= t1; n1 = t1 * t1 * grad(perm[ii + i1 + perm[jj + j1]], x1, y1); }

        double t2 = 0.5 - x2 * x2 - y2 * y2;
        if (t2 >= 0) { t2 *= t2; n2 = t2 * t2 * grad(perm[ii + 1 + perm[jj + 1]], x2, y2); }

        return 70.0 * (n0 + n1 + n2);
    }

    private double grad(int hash, double x, double y) {
        int h = hash & 7;
        double u = h < 4 ? x : y;
        double v = h < 4 ? y : x;
        return ((h & 1) != 0 ? -u : u) + ((h & 2) != 0 ? -2 * v : 2 * v);
    }
}

七、复杂度分析与总结

核心收获：
1. Perlin噪声通过梯度插值实现自然连续随机，是程序化生成的基石
2. FBM倍频叠加模拟自然的多尺度特征（山脉有山峰，山峰有岩石）
3. 细胞自动机将”光滑”的噪声边界转化为自然的粗糙侵蚀效果
4. 种子一致性保证可重现性，是多人协作世界的核心设计

Minecraft证明了：仅用几十行噪声代码，就能创造出人类探索数年仍不觉重复的虚拟世界。