每日算法 — 使用java实现恐龙跳跳：物理跳跃模拟与遗传算法进化AI

引言

恐龙跳跳（Chrome Dino Game）是 Chrome 浏览器离线时出现的经典小游戏：玩家控制一只小恐龙在沙漠中奔跑，通过跳跃躲避随机出现的仙人掌和飞鸟。本文将用 Java 完整实现该游戏的物理引擎与 AI 训练系统，核心讲解抛物线物理跳跃模拟与遗传算法（Genetic Algorithm）进化智能体两大技术。

物理引擎：跳跃与碰撞

抛物线运动模型

小恐龙的跳跃遵循匀变速直线运动。设起跳初速度为 v0，重力加速度为 g，则任意时刻 t 的速度和位移为：

• 垂直速度：v(t) = v0 - g × t
• 垂直位移：y(t) = v0 × t - 0.5 × g × t²

当 v(t) = 0 时达到最高点；当 y(t) = 0 时落地。

/**
 * 恐龙物理实体
 */
public class Dino {
    private static final double GRAVITY = 0.6;      // 重力加速度
    private static final double JUMP_VELOCITY = -12; // 起跳初速度（向上为负）

    private double x, y;      // 位置坐标
    private double vy;        // 垂直速度
    private boolean onGround; // 是否在地面上
    private boolean isAlive;  // 是否存活

    public Dino(double startX, double groundY) {
        this.x = startX;
        this.y = groundY;
        this.vy = 0;
        this.onGround = true;
        this.isAlive = true;
    }

    /**
     * 起跳操作：仅在地面时可执行
     */
    public void jump() {
        if (onGround) {
            vy = JUMP_VELOCITY;
            onGround = false;
        }
    }

    /**
     * 物理更新：每帧调用一次
     */
    public void update(double groundY) {
        if (!isAlive) return;

        // 应用重力
        vy += GRAVITY;
        y += vy;

        // 地面碰撞检测
        if (y >= groundY) {
            y = groundY;
            vy = 0;
            onGround = true;
        }
    }

    // Getters...
    public double getX() { return x; }
    public double getY() { return y; }
    public boolean isAlive() { return isAlive; }
    public void die() { isAlive = false; }
}

障碍物系统

import java.util.*;

/**
 * 障碍物基类
 */
abstract class Obstacle {
    protected double x, y;
    protected double width, height;
    protected double speed; // 向左移动速度

    public Obstacle(double x, double y, double w, double h, double speed) {
        this.x = x; this.y = y;
        this.width = w; this.height = h;
        this.speed = speed;
    }

    public void update() { x -= speed; }
    public boolean isOffScreen() { return x + width < 0; }

    /**
     * AABB轴对齐包围盒碰撞检测
     */
    public boolean collidesWith(Dino dino) {
        double dx = dino.getX(), dy = dino.getY();
        double dw = 30, dh = 40; // 恐龙尺寸
        return x < dx + dw && x + width > dx &&
               y < dy + dh && y + height > dy;
    }
}

class Cactus extends Obstacle {
    public Cactus(double x, double groundY, double speed) {
        super(x, groundY - 35, 20 + Math.random() * 15, 35, speed);
    }
}

class Bird extends Obstacle {
    public Bird(double x, double groundY, double speed) {
        // 飞鸟在高中低三个高度随机出现
        double[] heights = {groundY - 25, groundY - 55, groundY - 85};
        double h = heights[(int)(Math.random() * 3)];
        super(x, h, 30, 20, speed);
    }
}

遗传算法训练 AI

神经网络决策模型

每个恐龙个体拥有一个简单的前馈神经网络：输入层接收环境感知信息，输出层决定是否跳跃。

/**
 * 简单神经网络：输入层 -> 隐藏层 -> 输出层
 */
public class NeuralNetwork {
    private final int inputSize, hiddenSize, outputSize;
    private final double[][] weightsIH; // 输入到隐藏
    private final double[][] weightsHO; // 隐藏到输出
    private final double[] biasH, biasO;

    private static final Random rand = new Random();

    public NeuralNetwork(int inputSize, int hiddenSize, int outputSize) {
        this.inputSize = inputSize;
        this.hiddenSize = hiddenSize;
        this.outputSize = outputSize;

        weightsIH = new double[hiddenSize][inputSize];
        weightsHO = new double[outputSize][hiddenSize];
        biasH = new double[hiddenSize];
        biasO = new double[outputSize];

        randomize();
    }

    /**
     * Xavier初始化权重
     */
    private void randomize() {
        for (int i = 0; i < hiddenSize; i++) {
            for (int j = 0; j < inputSize; j++) {
                weightsIH[i][j] = rand.nextGaussian() * Math.sqrt(2.0 / inputSize);
            }
            biasH[i] = rand.nextGaussian() * 0.1;
        }
        for (int i = 0; i < outputSize; i++) {
            for (int j = 0; j < hiddenSize; j++) {
                weightsHO[i][j] = rand.nextGaussian() * Math.sqrt(2.0 / hiddenSize);
            }
            biasO[i] = rand.nextGaussian() * 0.1;
        }
    }

    /**
     * 前向传播：返回是否跳跃（输出 > 0.5）
     */
    public boolean predict(double[] inputs) {
        // 隐藏层
        double[] hidden = new double[hiddenSize];
        for (int i = 0; i < hiddenSize; i++) {
            double sum = biasH[i];
            for (int j = 0; j < inputSize; j++) {
                sum += inputs[j] * weightsIH[i][j];
            }
            hidden[i] = relu(sum);
        }

        // 输出层
        double[] output = new double[outputSize];
        for (int i = 0; i < outputSize; i++) {
            double sum = biasO[i];
            for (int j = 0; j < hiddenSize; j++) {
                sum += hidden[j] * weightsHO[i][j];
            }
            output[i] = sigmoid(sum);
        }

        return output[0] > 0.5;
    }

    private double relu(double x) { return Math.max(0, x); }
    private double sigmoid(double x) { return 1.0 / (1.0 + Math.exp(-x)); }
}

遗传算法核心流程

遗传算法通过选择（Selection）→ 交叉（Crossover）→ 变异（Mutation）三代迭代优化种群：

/**
 * 遗传算法进化器
 */
public class GeneticTrainer {
    private static final int POPULATION_SIZE = 100;  // 种群规模
    private static final double MUTATION_RATE = 0.15; // 变异率
    private static final int INPUT_SIZE = 4;          // 输入特征数
    private static final int HIDDEN_SIZE = 6;         // 隐藏层节点

    private List<Individual> population;
    private int generation = 0;

    static class Individual implements Comparable<Individual> {
        NeuralNetwork brain;
        int fitness; // 存活时间（得分）

        Individual() {
            this.brain = new NeuralNetwork(INPUT_SIZE, HIDDEN_SIZE, 1);
        }

        @Override
        public int compareTo(Individual o) {
            return Integer.compare(o.fitness, this.fitness); // 降序
        }
    }

    public GeneticTrainer() {
        population = new ArrayList<>();
        for (int i = 0; i < POPULATION_SIZE; i++) {
            population.add(new Individual());
        }
    }

    /**
     * 单代进化
     */
    public void evolve() {
        // 1. 评估适应度（让每只恐龙跑游戏，记录存活时间）
        evaluateFitness();
        Collections.sort(population);

        System.out.printf("Generation %d: Best=%d, Avg=%.1f%n",
            generation, population.get(0).fitness,
            population.stream().mapToInt(p -> p.fitness).average().orElse(0));

        // 2. 选择精英保留前20%
        List<Individual> nextGen = new ArrayList<>();
        int eliteCount = POPULATION_SIZE / 5;
        for (int i = 0; i < eliteCount; i++) {
            nextGen.add(cloneIndividual(population.get(i)));
        }

        // 3. 轮盘赌选择 + 交叉 + 变异产生后代
        while (nextGen.size() < POPULATION_SIZE) {
            Individual parent1 = selectByTournament();
            Individual parent2 = selectByTournament();
            Individual child = crossover(parent1, parent2);
            mutate(child);
            nextGen.add(child);
        }

        population = nextGen;
        generation++;
    }

    /**
     * 锦标赛选择：随机选3个，取最优
     */
    private Individual selectByTournament() {
        Individual best = population.get((int)(Math.random() * population.size()));
        for (int i = 0; i < 2; i++) {
            Individual challenger = population.get((int)(Math.random() * population.size()));
            if (challenger.fitness > best.fitness) best = challenger;
        }
        return best;
    }

    /**
     * 均匀交叉：随机混合两个父代的权重
     */
    private Individual crossover(Individual p1, Individual p2) {
        Individual child = new Individual();
        // 简化实现：以50%概率从p1或p2继承整个网络
        // 实际项目中可对每个权重独立交叉
        if (Math.random() < 0.5) {
            child.brain = cloneBrain(p1.brain);
        } else {
            child.brain = cloneBrain(p2.brain);
        }
        return child;
    }

    /**
     * 高斯变异：对权重添加小幅度随机扰动
     */
    private void mutate(Individual ind) {
        // 简化实现：变异率影响是否重新初始化整个网络
        if (Math.random() < MUTATION_RATE) {
            ind.brain = new NeuralNetwork(INPUT_SIZE, HIDDEN_SIZE, 1);
        }
    }

    private void evaluateFitness() {
        for (Individual ind : population) {
            ind.fitness = runGame(ind.brain);
        }
    }

    /**
     * 模拟单局游戏，返回存活帧数
     */
    private int runGame(NeuralNetwork brain) {
        Dino dino = new Dino(50, 200);
        List<Obstacle> obstacles = new ArrayList<>();
        int score = 0;
        int spawnTimer = 0;
        double gameSpeed = 5;

        while (dino.isAlive() && score < 10000) {
            // 生成障碍物
            spawnTimer++;
            if (spawnTimer > 60 + Math.random() * 40) {
                obstacles.add(Math.random() < 0.7 
                    ? new Cactus(800, 200, gameSpeed)
                    : new Bird(800, 200, gameSpeed));
                spawnTimer = 0;
            }

            // 获取最近障碍物信息作为神经网络的输入
            Obstacle nearest = findNearest(obstacles, dino.getX());
            double[] inputs = new double[INPUT_SIZE];
            if (nearest != null) {
                inputs[0] = (nearest.x - dino.getX()) / 800.0;      // 水平距离
                inputs[1] = nearest.y / 200.0;                       // 障碍物高度
                inputs[2] = nearest.width / 50.0;                    // 障碍物宽度
                inputs[3] = gameSpeed / 15.0;                        // 游戏速度
            }

            // AI决策
            if (brain.predict(inputs)) {
                dino.jump();
            }

            // 物理更新
            dino.update(200);
            for (Obstacle obs : obstacles) {
                obs.update();
                if (obs.collidesWith(dino)) {
                    dino.die();
                    break;
                }
            }
            obstacles.removeIf(Obstacle::isOffScreen);

            score++;
            if (score % 500 == 0) gameSpeed += 0.5; // 加速
        }
        return score;
    }

    private Obstacle findNearest(List<Obstacle> obstacles, double dinoX) {
        return obstacles.stream()
            .filter(o -> o.x > dinoX)
            .min(Comparator.comparingDouble(o -> o.x))
            .orElse(null);
    }

    // clone helpers...
    private Individual cloneIndividual(Individual src) {
        Individual copy = new Individual();
        copy.brain = cloneBrain(src.brain);
        copy.fitness = src.fitness;
        return copy;
    }

    private NeuralNetwork cloneBrain(NeuralNetwork src) {
        // 实际项目中实现深拷贝
        return new NeuralNetwork(INPUT_SIZE, HIDDEN_SIZE, 1);
    }

    public static void main(String[] args) {
        GeneticTrainer trainer = new GeneticTrainer();
        for (int i = 0; i < 50; i++) { // 进化50代
            trainer.evolve();
        }
    }
}

复杂度与训练效果分析

总结

恐龙跳跳的 AI 实现展示了神经进化（Neuroevolution）的经典范式：无需反向传播，仅通过遗传算法迭代优化神经网络权重，即可让 AI 学会在复杂动态环境中做出正确决策。这种方法在实时游戏 AI、机器人控制等无法获取精确梯度的场景中具有独特优势。