每日算法 — 使用java实现Flappy Bird：物理引擎与Q-Learning强化学习

引言

Flappy Bird 是一款曾风靡全球的休闲小游戏，玩家通过点击屏幕控制小鸟向上跳跃，穿越不断出现的管道间隙。看似简单，但其背后蕴含着丰富的算法知识。本文将用 Java 从零实现一个带 AI 的 Flappy Bird，重点讲解物理引擎的数值模拟、AABB 碰撞检测、管道生成的随机算法，以及让小鸟自主飞行的 Q-Learning 强化学习决策机制。

一、物理引擎设计：重力与跳跃

Flappy Bird 的核心物理模型非常简单：小鸟在竖直方向上受重力影响持续下坠，每次点击时获得一个向上的瞬时速度。我们用经典的欧拉积分来更新状态。

设小鸟的竖直位置为 y，竖直速度为 vy，重力加速度为 g，跳跃初速度为 jumpVelocity，时间步长为 dt。每帧更新逻辑如下：

vy = vy + g * dt
y = y + vy * dt

当玩家点击时：vy = -jumpVelocity（向上为负方向）。

二、管道生成算法：可控随机性

游戏中的管道成对出现，上下各一根，中间留有间隙。为了游戏体验，管道生成需要满足：

1. 间隙高度固定：保证小鸟能够穿过。
2. 管道位置随机：间隙中心点在屏幕范围内随机分布。
3. 水平间隔可控：相邻两组管道的水平距离保持恒定或在小范围内波动。

生成公式：设屏幕高度为 H，间隙高度为 gap，则间隙中心 centerY 在 [gap/2, H - gap/2] 之间均匀随机取值。上管道底部 = centerY - gap/2，下管道顶部 = centerY + gap/2。

三、碰撞检测：AABB 矩形包围盒

小鸟和管道均可抽象为矩形。我们使用 AABB（Axis-Aligned Bounding Box）碰撞检测判断小鸟是否撞到管道或地面。

两个矩形相交的判定条件：在 x 轴和 y 轴上的投影区间均有重叠。

相交条件：
rect1.x < rect2.x + rect2.width  &&
rect1.x + rect1.width > rect2.x  &&
rect1.y < rect2.y + rect2.height &&
rect1.y + rect1.height > rect2.y

四、Q-Learning 强化学习：让小鸟学会飞行

为了让小鸟能够自主决策何时跳跃，我们引入 Q-Learning 算法。核心思想是小鸟通过与环境交互，学习在每个状态下采取哪个动作能获得最大长期奖励。

4.1 状态设计（State）

状态空间需要足够简洁以降低学习难度，同时包含足够的信息做决策。我们定义状态为四元组：

• dx：小鸟到下一组管道入口的水平距离（离散化为远/中/近）
• dy：小鸟到下一组管道间隙中心的竖直偏差（离散化为上/中/下）
• vy：小鸟当前竖直速度（离散化为上升/下降快/下降慢）
• pipe_gap_y：间隙中心位置（离散化为高/中/低）

4.2 动作设计（Action）

只有两个动作：

• 0：不跳跃（自由落体）
• 1：跳跃（给予向上速度）

4.3 奖励函数（Reward）

奖励设计直接影响学习效果：

• 成功穿过一组管道：+10
• 碰撞死亡：-100
• 每存活一帧：+0.1（鼓励持续飞行）
• 距离间隙中心越近，额外奖励越高

4.4 Q 表更新

Q-Learning 的核心更新公式：

Q(s, a) = Q(s, a) + α * [r + γ * max(Q(s', a')) - Q(s, a)]

其中 α 为学习率，γ 为折扣因子，s' 为下一状态。

4.5 ε-贪心探索策略

训练时以 ε 的概率随机选择动作（探索），以 1-ε 的概率选择当前 Q 值最大的动作（利用）。随着训练进行，ε 逐渐衰减。

五、完整 Java 实现

以下代码提供了完整的项目结构，包含物理引擎、管道生成、碰撞检测和 Q-Learning AI 四个核心模块。

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

/**
 * Flappy Bird 完整实现，包含物理引擎、管道生成、碰撞检测与 Q-Learning AI
 */
public class FlappyBirdGame extends JPanel implements ActionListener, KeyListener {

    // ==================== 游戏常量 ====================
    private static final int WIDTH = 800;
    private static final int HEIGHT = 600;
    private static final int BIRD_SIZE = 30;
    private static final int PIPE_WIDTH = 80;
    private static final int PIPE_GAP = 150;
    private static final int PIPE_SPEED = 3;
    private static final int PIPE_SPAWN_INTERVAL = 300; // 像素间隔
    private static final double GRAVITY = 0.5;
    private static final double JUMP_VELOCITY = 8.0;
    private static final double MAX_FALL_SPEED = 10.0;

    // ==================== 物理状态 ====================
    private double birdX = 100;
    private double birdY = HEIGHT / 2.0;
    private double birdVy = 0;

    // ==================== 管道管理 ====================
    private java.util.List<Pipe> pipes = new ArrayList<>();
    private int nextPipeX = WIDTH;
    private int score = 0;
    private boolean gameOver = false;

    // ==================== Q-Learning AI ====================
    private QLearningAI ai;
    private boolean useAI = true; // 设为 false 可手动游玩
    private Timer timer;
    private int frameCount = 0;

    public FlappyBirdGame() {
        setPreferredSize(new Dimension(WIDTH, HEIGHT));
        setBackground(new Color(135, 206, 235)); // 天空蓝
        setFocusable(true);
        addKeyListener(this);

        ai = new QLearningAI();
        // 尝试加载预训练的 Q 表（如果有）
        ai.loadQTable();

        timer = new Timer(16, this); // 约 60 FPS
        timer.start();
        spawnPipe();
    }

    /**
     * 管道数据结构
     */
    static class Pipe {
        int x;
        int topHeight;    // 上管道高度
        int bottomY;      // 下管道顶部 y 坐标
        boolean passed;   // 是否已计分

        Pipe(int x, int topHeight, int bottomY) {
            this.x = x;
            this.topHeight = topHeight;
            this.bottomY = bottomY;
            this.passed = false;
        }
    }

    /**
     * 生成新管道，使用可控随机算法确保间隙在屏幕范围内
     */
    private void spawnPipe() {
        // 间隙中心在 [PIPE_GAP/2 + 50, HEIGHT - PIPE_GAP/2 - 50] 范围内随机
        int minCenter = PIPE_GAP / 2 + 50;
        int maxCenter = HEIGHT - PIPE_GAP / 2 - 50;
        int centerY = minCenter + (int)(Math.random() * (maxCenter - minCenter));

        int topHeight = centerY - PIPE_GAP / 2;
        int bottomY = centerY + PIPE_GAP / 2;

        pipes.add(new Pipe(nextPipeX, topHeight, bottomY));
        nextPipeX += PIPE_SPAWN_INTERVAL;
    }

    /**
     * 每帧更新游戏状态
     */
    @Override
    public void actionPerformed(ActionEvent e) {
        if (gameOver) return;

        frameCount++;

        // --- 物理更新：重力作用 ---
        birdVy += GRAVITY;
        if (birdVy > MAX_FALL_SPEED) birdVy = MAX_FALL_SPEED;
        birdY += birdVy;

        // 地面碰撞检测
        if (birdY + BIRD_SIZE >= HEIGHT - 30) {
            birdY = HEIGHT - 30 - BIRD_SIZE;
            handleDeath();
            return;
        }
        if (birdY <= 0) {
            birdY = 0;
            birdVy = 0;
        }

        // --- AI 决策 ---
        if (useAI && !gameOver) {
            int action = ai.decideAction(getState());
            if (action == 1) {
                birdVy = -JUMP_VELOCITY;
            }
        }

        // --- 管道更新与生成 ---
        for (Pipe pipe : pipes) {
            pipe.x -= PIPE_SPEED;

            // 计分：小鸟通过管道右边界
            if (!pipe.passed && pipe.x + PIPE_WIDTH < birdX) {
                pipe.passed = true;
                score++;
                ai.updateReward(10.0); // 穿过管道获得奖励
            }
        }

        // 移除屏幕外管道
        pipes.removeIf(p -> p.x + PIPE_WIDTH < 0);

        // 生成新管道
        if (pipes.isEmpty() || pipes.get(pipes.size() - 1).x < WIDTH - PIPE_SPAWN_INTERVAL) {
            spawnPipe();
        }

        // --- 碰撞检测：AABB ---
        Rectangle birdRect = new Rectangle((int)birdX, (int)birdY, BIRD_SIZE, BIRD_SIZE);
        for (Pipe pipe : pipes) {
            // 上管道矩形
            Rectangle topPipe = new Rectangle(pipe.x, 0, PIPE_WIDTH, pipe.topHeight);
            // 下管道矩形
            Rectangle bottomPipe = new Rectangle(pipe.x, pipe.bottomY, PIPE_WIDTH, HEIGHT - pipe.bottomY);

            if (birdRect.intersects(topPipe) || birdRect.intersects(bottomPipe)) {
                handleDeath();
                return;
            }
        }

        // 存活奖励
        ai.updateReward(0.1);
        ai.learn(getState());

        repaint();
    }

    /**
     * 获取当前离散化状态，供 Q-Learning 使用
     */
    private int[] getState() {
        // 找到最近的未通过管道
        Pipe target = null;
        for (Pipe p : pipes) {
            if (!p.passed || p.x + PIPE_WIDTH >= birdX) {
                target = p;
                break;
            }
        }

        int dx = 2; // 默认远
        int dy = 1; // 默认中
        int gapY = 1; // 默认中

        if (target != null) {
            int dist = target.x - (int)birdX;
            dx = dist < 80 ? 0 : (dist < 200 ? 1 : 2); // 近/中/远

            int centerY = target.topHeight + PIPE_GAP / 2;
            int diff = (int)birdY - centerY;
            dy = diff < -30 ? 0 : (diff > 30 ? 2 : 1); // 上/中/下

            gapY = centerY < HEIGHT / 3 ? 0 : (centerY > 2 * HEIGHT / 3 ? 2 : 1); // 高/中/低
        }

        int vyState = birdVy < -2 ? 0 : (birdVy > 2 ? 2 : 1); // 上升/平缓/下降

        return new int[]{dx, dy, vyState, gapY};
    }

    private void handleDeath() {
        gameOver = true;
        ai.updateReward(-100.0);
        ai.learn(getState());
        ai.saveQTable();
        System.out.println("Game Over! Score: " + score);
    }

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

        // 绘制地面
        g.setColor(new Color(34, 139, 34));
        g.fillRect(0, HEIGHT - 30, WIDTH, 30);

        // 绘制管道
        g.setColor(new Color(0, 128, 0));
        for (Pipe pipe : pipes) {
            g.fillRect(pipe.x, 0, PIPE_WIDTH, pipe.topHeight);
            g.fillRect(pipe.x, pipe.bottomY, PIPE_WIDTH, HEIGHT - pipe.bottomY);
            // 管道边缘高光
            g.setColor(new Color(0, 100, 0));
            g.drawRect(pipe.x, 0, PIPE_WIDTH, pipe.topHeight);
            g.drawRect(pipe.x, pipe.bottomY, PIPE_WIDTH, HEIGHT - pipe.bottomY);
            g.setColor(new Color(0, 128, 0));
        }

        // 绘制小鸟
        g.setColor(Color.YELLOW);
        g.fillOval((int)birdX, (int)birdY, BIRD_SIZE, BIRD_SIZE);
        g.setColor(Color.BLACK);
        g.drawOval((int)birdX, (int)birdY, BIRD_SIZE, BIRD_SIZE);
        // 小鸟眼睛
        g.fillOval((int)birdX + 20, (int)birdY + 8, 6, 6);
        // 小鸟嘴巴
        g.setColor(Color.ORANGE);
        int[] beakX = {(int)birdX + 28, (int)birdX + 38, (int)birdX + 28};
        int[] beakY = {(int)birdY + 14, (int)birdY + 17, (int)birdY + 20};
        g.fillPolygon(beakX, beakY, 3);

        // 绘制分数
        g.setColor(Color.WHITE);
        g.setFont(new Font("Arial", Font.BOLD, 36));
        g.drawString("Score: " + score, 20, 50);

        // 绘制 AI 状态
        if (useAI) {
            g.setFont(new Font("Arial", Font.PLAIN, 14));
            g.drawString("AI Mode | Frame: " + frameCount, 20, 80);
        }

        if (gameOver) {
            g.setColor(new Color(0, 0, 0, 180));
            g.fillRect(0, 0, WIDTH, HEIGHT);
            g.setColor(Color.WHITE);
            g.setFont(new Font("Arial", Font.BOLD, 48));
            String msg = "Game Over";
            int msgWidth = g.getFontMetrics().stringWidth(msg);
            g.drawString(msg, (WIDTH - msgWidth) / 2, HEIGHT / 2);
            g.setFont(new Font("Arial", Font.PLAIN, 24));
            String scoreMsg = "Final Score: " + score;
            int sw = g.getFontMetrics().stringWidth(scoreMsg);
            g.drawString(scoreMsg, (WIDTH - sw) / 2, HEIGHT / 2 + 40);
        }
    }

    // 手动控制
    @Override
    public void keyPressed(KeyEvent e) {
        if (e.getKeyCode() == KeyEvent.VK_SPACE && !useAI) {
            if (gameOver) {
                restart();
            } else {
                birdVy = -JUMP_VELOCITY;
            }
        }
    }
    @Override public void keyReleased(KeyEvent e) {}
    @Override public void keyTyped(KeyEvent e) {}

    private void restart() {
        birdY = HEIGHT / 2.0;
        birdVy = 0;
        pipes.clear();
        nextPipeX = WIDTH;
        score = 0;
        gameOver = false;
        frameCount = 0;
        spawnPipe();
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame("Flappy Bird - Q-Learning AI");
        FlappyBirdGame game = new FlappyBirdGame();
        frame.add(game);
        frame.pack();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }
}

/**
 * Q-Learning 强化学习模块
 * 负责状态管理、Q 表维护、动作决策与学习更新
 */
class QLearningAI {
    // Q 表：state -> action -> value
    private Map<String, double[]> qTable = new HashMap<>();

    // 超参数
    private static final double ALPHA = 0.1;   // 学习率
    private static final double GAMMA = 0.95;  // 折扣因子
    private static final double EPSILON_START = 0.3; // 初始探索率
    private static final double EPSILON_MIN = 0.01;
    private static final double EPSILON_DECAY = 0.9995;

    private double epsilon = EPSILON_START;
    private int[] lastState = null;
    private int lastAction = 0;
    private double accumulatedReward = 0;
    private int totalSteps = 0;

    /**
     * 根据当前状态选择动作（ε-贪心策略）
     */
    public int decideAction(int[] state) {
        String stateKey = stateToKey(state);
        qTable.putIfAbsent(stateKey, new double[]{0.0, 0.0});
        double[] values = qTable.get(stateKey);

        int action;
        if (Math.random() < epsilon) {
            // 探索：随机选择
            action = Math.random() < 0.5 ? 0 : 1;
        } else {
            // 利用：选择 Q 值最大的动作
            action = values[0] >= values[1] ? 0 : 1;
        }

        lastState = state.clone();
        lastAction = action;
        return action;
    }

    /**
     * 累积环境奖励
     */
    public void updateReward(double reward) {
        accumulatedReward += reward;
    }

    /**
     * 执行 Q 表更新（TD 学习）
     */
    public void learn(int[] newState) {
        if (lastState == null) return;

        String lastKey = stateToKey(lastState);
        String newKey = stateToKey(newState);
        qTable.putIfAbsent(newKey, new double[]{0.0, 0.0});

        double[] oldValues = qTable.get(lastKey);
        double[] newValues = qTable.get(newKey);

        double maxNextQ = Math.max(newValues[0], newValues[1]);
        double oldQ = oldValues[lastAction];
        double reward = accumulatedReward;

        // Q-Learning 核心更新公式
        double newQ = oldQ + ALPHA * (reward + GAMMA * maxNextQ - oldQ);
        oldValues[lastAction] = newQ;

        // 重置累积奖励并衰减探索率
        accumulatedReward = 0;
        totalSteps++;
        epsilon = Math.max(EPSILON_MIN, epsilon * EPSILON_DECAY);
    }

    private String stateToKey(int[] state) {
        return state[0] + "," + state[1] + "," + state[2] + "," + state[3];
    }

    /**
     * 将 Q 表序列化保存到文件
     */
    public void saveQTable() {
        try (java.io.PrintWriter out = new java.io.PrintWriter("qtable.txt")) {
            for (Map.Entry<String, double[]> entry : qTable.entrySet()) {
                out.println(entry.getKey() + "=" + entry.getValue()[0] + "," + entry.getValue()[1]);
            }
            System.out.println("Q-Table saved. Size: " + qTable.size() + ", Epsilon: " + String.format("%.4f", epsilon));
        } catch (Exception e) {
            System.err.println("Failed to save Q-Table: " + e.getMessage());
        }
    }

    /**
     * 从文件加载 Q 表
     */
    public void loadQTable() {
        try (java.io.BufferedReader reader = new java.io.BufferedReader(new java.io.FileReader("qtable.txt"))) {
            String line;
            while ((line = reader.readLine()) != null) {
                String[] parts = line.split("=");
                if (parts.length == 2) {
                    String[] vals = parts[1].split(",");
                    qTable.put(parts[0], new double[]{
                        Double.parseDouble(vals[0]),
                        Double.parseDouble(vals[1])
                    });
                }
            }
            System.out.println("Q-Table loaded. Size: " + qTable.size());
        } catch (Exception e) {
            System.out.println("No existing Q-Table found. Starting fresh.");
        }
    }
}

六、算法复杂度分析

整体来看，游戏主循环的每帧时间复杂度为 O(P)，其中 P 为当前屏幕上的管道数量，性能表现非常优异。

七、运行与训练建议

1. 手动模式：将 useAI 设为 false，按空格键控制小鸟，体验物理手感。
2. AI 训练模式：保持 useAI = true，让 AI 自动运行数千局。初期小鸟会频繁撞墙（探索阶段），随着 Q 表收敛，飞行策略会显著改善。
3. 加载预训练模型：若目录下存在 qtable.txt，程序启动时会自动加载，可在已有基础上继续训练。

八、总结

本文通过 Java 实现了一个完整的 Flappy Bird 游戏，涵盖了四大核心算法模块：

• 物理引擎：欧拉积分模拟重力与跳跃，代码简洁且数值稳定。
• 管道生成：均匀随机与边界约束结合，确保游戏既公平又有挑战性。
• 碰撞检测：AABB 矩形包围盒判断，高效且直观。
• Q-Learning：通过状态离散化、奖励塑造和 ε-贪心策略，让 AI 在数千局游戏中自主学习最优飞行策略。

读者可以在此基础上继续扩展：尝试使用神经网络替代 Q 表（DQN）、增加更多状态维度、或引入更复杂的奖励函数，进一步探索强化学习的魅力。