每日算法 — 使用java实现飞机大战：AABB碰撞检测与敌人波次生成算法

飞机大战是街机时代最具代表性的射击游戏之一，玩家操控战机在屏幕底部移动，躲避并击毁从上方不断涌现的敌机。看似简单的玩法背后，蕴含着碰撞检测、状态机驱动、波次生成等多项经典算法。本文将用Java完整实现核心逻辑，重点讲解AABB轴对齐包围盒碰撞检测的高效判定，以及基于有限状态机的敌人波次生成与行为控制策略。

游戏规则与状态设计

游戏核心状态包含玩家战机、敌机群、子弹集合、道具掉落和爆炸特效五类实体。每帧更新时，系统依次执行：生成新敌机 → 更新所有实体位置 → 检测碰撞 → 处理销毁与得分 → 渲染画面。

关键约束条件：
– 玩家战机位于屏幕底部，通过键盘或触摸控制水平移动
– 敌机从屏幕顶部以不同轨迹入场，部分敌机具备射击能力
– 碰撞触发条件：玩家子弹命中敌机、敌机撞击玩家、敌机子弹命中玩家
– 波次难度随时间递增：敌机速度加快、射击频率提升、出现新型敌机

核心数据结构

实体基类与AABB包围盒

所有游戏实体共享位置、尺寸和存活状态。AABB（Axis-Aligned Bounding Box）碰撞检测要求包围盒边与坐标轴平行，仅需比较最小/最大坐标即可判定相交，计算复杂度为 $O(1)$。

/**
 * 游戏实体基类，所有可碰撞对象继承此类
 */
abstract class Entity {
    protected double x, y;          // 中心坐标
    protected double width, height; // 尺寸
    protected boolean alive = true; // 存活标记

    public Entity(double x, double y, double width, double height) {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
    }

    /**
     * AABB轴对齐包围盒碰撞检测
     * 两个矩形相交的充要条件：在X轴和Y轴上的投影区间均重叠
     *
     * @param other 另一个实体
     * @return 是否发生碰撞
     */
    public boolean collidesWith(Entity other) {
        // 计算本实体在X轴和Y轴上的投影区间 [min, max]
        double thisMinX = this.x - this.width / 2;
        double thisMaxX = this.x + this.width / 2;
        double thisMinY = this.y - this.height / 2;
        double thisMaxY = this.y + this.height / 2;

        double otherMinX = other.x - other.width / 2;
        double otherMaxX = other.x + other.width / 2;
        double otherMinY = other.y - other.height / 2;
        double otherMaxY = other.y + other.height / 2;

        // 在X轴和Y轴上均重叠即发生碰撞
        boolean overlapX = thisMinX < otherMaxX && thisMaxX > otherMinX;
        boolean overlapY = thisMinY < otherMaxY && thisMaxY > otherMinY;

        return overlapX && overlapY;
    }

    /**
     * 获取圆形近似半径，用于优化：先进行粗略距离筛选，再执行精确AABB检测
     */
    public double getApproximateRadius() {
        return Math.max(width, height) / 2;
    }

    public abstract void update(double deltaTime);
}

/**
 * 玩家战机
 */
class Player extends Entity {
    private double speed = 300;      // 像素/秒
    private int health = 3;
    private double shootCooldown = 0;
    private static final double SHOOT_INTERVAL = 0.25; // 射击间隔

    public Player(double x, double y) {
        super(x, y, 48, 48);
    }

    public void move(double dx, double deltaTime) {
        this.x += dx * speed * deltaTime;
        // 限制在屏幕边界内
        this.x = Math.max(width / 2, Math.min(800 - width / 2, this.x));
    }

    public Bullet tryShoot(double currentTime) {
        if (currentTime - shootCooldown >= SHOOT_INTERVAL) {
            shootCooldown = currentTime;
            // 从战机顶部发射子弹
            return new Bullet(x, y - height / 2 - 10, -400, true);
        }
        return null;
    }

    @Override
    public void update(double deltaTime) {
        // 玩家位置由外部输入控制，此处无需自动更新
    }

    public void takeDamage() { health--; if (health <= 0) alive = false; }
    public int getHealth() { return health; }
}

/**
 * 子弹实体
 */
class Bullet extends Entity {
    private double vy;      // 垂直速度，负值向上，正值向下
    private boolean fromPlayer; // 是否来自玩家

    public Bullet(double x, double y, double vy, boolean fromPlayer) {
        super(x, y, 6, 14);
        this.vy = vy;
        this.fromPlayer = fromPlayer;
    }

    @Override
    public void update(double deltaTime) {
        y += vy * deltaTime;
        // 飞出屏幕则标记销毁
        if (y < -20 || y > 620) alive = false;
    }

    public boolean isFromPlayer() { return fromPlayer; }
}

/**
 * 敌机实体，内置有限状态机控制移动行为
 */
class Enemy extends Entity {
    // 敌机类型枚举，决定血量、速度和射击能力
    enum Type { NORMAL, FAST, SHOOTER, BOSS }

    private Type type;
    private double baseSpeed;
    private double vx, vy;          // 当前速度分量
    private int health;
    private double shootTimer = 0;
    private double shootInterval;
    private int scoreValue;

    // 状态机相关字段
    private MoveState currentState;
    private double stateTimer = 0;
    private double amplitude;       // 正弦波动的振幅
    private double frequency;       // 正弦波动的频率
    private double entryX;          // 入场时的基准X坐标

    /**
     * 敌机移动状态机：直线、正弦波、悬停射击、快速俯冲
     */
    enum MoveState {
        STRAIGHT,    // 垂直下落
        SINE_WAVE,   // 正弦波轨迹
        HOVER_SHOOT, // 悬停并射击
        DIVE_BOMB    // 快速俯冲向玩家
    }

    public Enemy(double x, double y, Type type, double difficultyMultiplier) {
        super(x, y, 40, 40);
        this.type = type;
        this.entryX = x;

        // 根据类型和难度倍率初始化属性
        switch (type) {
            case NORMAL:
                baseSpeed = 80 * difficultyMultiplier;
                health = 1;
                shootInterval = Double.MAX_VALUE; // 不射击
                scoreValue = 10;
                width = 40; height = 40;
                currentState = MoveState.STRAIGHT;
                break;
            case FAST:
                baseSpeed = 180 * difficultyMultiplier;
                health = 1;
                shootInterval = Double.MAX_VALUE;
                scoreValue = 20;
                width = 32; height = 32;
                currentState = MoveState.STRAIGHT;
                break;
            case SHOOTER:
                baseSpeed = 60 * difficultyMultiplier;
                health = 2;
                shootInterval = 1.5 / difficultyMultiplier;
                scoreValue = 30;
                width = 44; height = 44;
                currentState = MoveState.SINE_WAVE;
                amplitude = 60 + Math.random() * 40;
                frequency = 2 + Math.random() * 2;
                break;
            case BOSS:
                baseSpeed = 40 * difficultyMultiplier;
                health = 20;
                shootInterval = 0.8 / difficultyMultiplier;
                scoreValue = 200;
                width = 80; height = 60;
                currentState = MoveState.HOVER_SHOOT;
                break;
        }

        this.vy = baseSpeed;
        this.vx = 0;
    }

    /**
     * 状态机驱动的位置更新
     */
    @Override
    public void update(double deltaTime) {
        stateTimer += deltaTime;

        switch (currentState) {
            case STRAIGHT:
                y += vy * deltaTime;
                break;

            case SINE_WAVE:
                y += vy * deltaTime;
                // 正弦波水平偏移：x = entryX + amplitude * sin(frequency * time)
                x = entryX + amplitude * Math.sin(frequency * stateTimer);
                // 确保不越界
                x = Math.max(width / 2, Math.min(800 - width / 2, x));
                break;

            case HOVER_SHOOT:
                // 缓慢下落，到达屏幕中上部后改为左右移动
                if (y < 150) {
                    y += vy * deltaTime;
                } else {
                    // 悬停阶段：水平往复运动
                    x = entryX + 100 * Math.sin(stateTimer);
                    x = Math.max(width / 2, Math.min(800 - width / 2, x));
                }
                break;

            case DIVE_BOMB:
                // 快速俯冲，速度逐渐加快
                vy += 100 * deltaTime;
                y += vy * deltaTime;
                x += vx * deltaTime;
                break;
        }

        // 飞出底部屏幕标记销毁
        if (y > 650) alive = false;
    }

    /**
     * 尝试射击，返回子弹对象或null
     */
    public Bullet tryShoot(double currentTime, double playerX) {
        if (shootInterval >= Double.MAX_VALUE) return null;

        shootTimer += currentTime - shootTimer > shootInterval ? shootInterval + 0.001 : 0;
        // 简化：基于时间间隔判定
        if (Math.random() < 0.02 * (1 / shootInterval)) {
            return new Bullet(x, y + height / 2 + 10, 250, false);
        }
        return null;
    }

    public void takeDamage() {
        health--;
        if (health <= 0) alive = false;
    }

    public int getScoreValue() { return scoreValue; }
    public Type getType() { return type; }

    /**
     * 切换到俯冲状态，朝向玩家位置
     */
    public void startDiveBomb(double playerX) {
        currentState = MoveState.DIVE_BOMB;
        double dx = playerX - this.x;
        double dy = 600 - this.y; // 屏幕底部
        double dist = Math.sqrt(dx * dx + dy * dy);
        vx = (dx / dist) * 200;
        vy = (dy / dist) * 200;
    }
}

碰撞检测系统

游戏中每帧可能涉及数十个实体，暴力两两检测的时间复杂度为 $O(n^2)$。本实现采用空间划分优化：先将实体按类型分组，仅检测可能产生交互的组别（玩家子弹 vs 敌机、敌机 vs 玩家、敌机子弹 vs 玩家），避免无意义的配对比较。

/**
 * 碰撞检测管理器
 */
class CollisionManager {

    /**
     * 执行全量碰撞检测
     * 优化策略：按实体类型分组，只检测存在交互逻辑的组别
     */
    public static CollisionResult detectCollisions(
            Player player,
            List<Enemy> enemies,
            List<Bullet> bullets) {

        CollisionResult result = new CollisionResult();

        // 分离玩家子弹和敌机子弹
        List<Bullet> playerBullets = new ArrayList<>();
        List<Bullet> enemyBullets = new ArrayList<>();
        for (Bullet b : bullets) {
            if (b.isFromPlayer()) playerBullets.add(b);
            else enemyBullets.add(b);
        }

        // 1. 玩家子弹 vs 敌机：O(m * n)，m为玩家子弹数，n为敌机数
        for (Bullet bullet : playerBullets) {
            if (!bullet.alive) continue;
            for (Enemy enemy : enemies) {
                if (!enemy.alive) continue;
                if (bullet.collidesWith(enemy)) {
                    bullet.alive = false;
                    enemy.takeDamage();
                    if (!enemy.alive) {
                        result.scoreGained += enemy.getScoreValue();
                        result.enemiesDestroyed++;
                    }
                    break; // 一颗子弹只命中一个目标
                }
            }
        }

        // 2. 敌机 vs 玩家
        for (Enemy enemy : enemies) {
            if (!enemy.alive) continue;
            if (enemy.collidesWith(player)) {
                enemy.alive = false;
                player.takeDamage();
                result.playerDamaged = true;
                result.scoreGained += enemy.getScoreValue();
            }
        }

        // 3. 敌机子弹 vs 玩家
        for (Bullet bullet : enemyBullets) {
            if (!bullet.alive) continue;
            if (bullet.collidesWith(player)) {
                bullet.alive = false;
                player.takeDamage();
                result.playerDamaged = true;
            }
        }

        return result;
    }

    /**
     * 基于距离的快速排除：当两实体中心距离大于半径之和时，不可能碰撞
     * 可作为AABB检测的前置过滤层
     */
    public static boolean quickReject(Entity a, Entity b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        double radiusSum = a.getApproximateRadius() + b.getApproximateRadius();
        return (dx * dx + dy * dy) > (radiusSum * radiusSum);
    }
}

/**
 * 碰撞检测结果
 */
class CollisionResult {
    int scoreGained = 0;
    int enemiesDestroyed = 0;
    boolean playerDamaged = false;
}

波次生成算法

敌机波次生成是维持游戏节奏的核心算法。本实现采用基于时间线的加权随机生成策略：难度随游戏时间指数增长，同时通过权重池控制各类型敌机的出现比例。

/**
 * 波次生成器，基于难度曲线和加权随机策略生成敌机
 */
class WaveGenerator {
    private double elapsedTime = 0;       // 游戏已进行时间
    private double spawnTimer = 0;        // 生成计时器
    private double baseSpawnInterval = 1.5; // 基础生成间隔
    private Random random = new Random();

    // 难度参数
    private double getDifficultyMultiplier() {
        // 难度随时间缓慢增长，采用平方根函数避免后期过难
        return 1.0 + Math.sqrt(elapsedTime) * 0.15;
    }

    /**
     * 计算当前生成间隔，随难度提升而缩短
     */
    private double getCurrentSpawnInterval() {
        double diff = getDifficultyMultiplier();
        return baseSpawnInterval / Math.min(diff, 4.0); // 最短间隔限制为原来的1/4
    }

    /**
     * 根据难度计算各类型敌机的出现权重
     * 后期高难度时，SHOOTER和BOSS的权重显著提升
     */
    private Map<Enemy.Type, Double> getSpawnWeights() {
        double diff = getDifficultyMultiplier();
        Map<Enemy.Type, Double> weights = new EnumMap<>(Enemy.Type.class);

        weights.put(Enemy.Type.NORMAL, Math.max(0.4, 1.0 - diff * 0.15));
        weights.put(Enemy.Type.FAST, Math.min(0.35, 0.1 + diff * 0.05));
        weights.put(Enemy.Type.SHOOTER, Math.min(0.35, 0.05 + diff * 0.08));
        weights.put(Enemy.Type.BOSS, diff > 3.0 ? 0.08 : 0.0); // 3分钟后才可能出现BOSS

        return weights;
    }

    /**
     * 加权随机选择敌机类型
     */
    private Enemy.Type randomTypeByWeight(Map<Enemy.Type, Double> weights) {
        double total = weights.values().stream().mapToDouble(Double::doubleValue).sum();
        double r = random.nextDouble() * total;
        double cumulative = 0;
        for (Map.Entry<Enemy.Type, Double> entry : weights.entrySet()) {
            cumulative += entry.getValue();
            if (r <= cumulative) return entry.getKey();
        }
        return Enemy.Type.NORMAL;
    }

    /**
     * 每帧调用，生成新的敌机
     * @param deltaTime 距上一帧的秒数
     * @param playerX 玩家当前X坐标，用于部分敌机的瞄准生成
     * @return 新生成的敌机列表
     */
    public List<Enemy> update(double deltaTime, double playerX) {
        elapsedTime += deltaTime;
        spawnTimer += deltaTime;

        List<Enemy> spawned = new ArrayList<>();
        double interval = getCurrentSpawnInterval();

        while (spawnTimer >= interval) {
            spawnTimer -= interval;

            Map<Enemy.Type, Double> weights = getSpawnWeights();
            Enemy.Type type = randomTypeByWeight(weights);

            // 随机生成X坐标，BOSS生成在屏幕中央附近
            double spawnX;
            if (type == Enemy.Type.BOSS) {
                spawnX = 400 + (random.nextDouble() - 0.5) * 100;
            } else {
                spawnX = 40 + random.nextDouble() * 720;
            }

            Enemy enemy = new Enemy(spawnX, -30, type, getDifficultyMultiplier());

            // 部分敌机直接以俯冲状态入场
            if (type == Enemy.Type.FAST && random.nextDouble() < 0.3) {
                enemy.startDiveBomb(playerX);
            }

            spawned.add(enemy);

            // 高难度时可能一次生成多架敌机
            if (getDifficultyMultiplier() > 2.5 && random.nextDouble() < 0.2) {
                double extraX = 40 + random.nextDouble() * 720;
                spawned.add(new Enemy(extraX, -30, Enemy.Type.NORMAL, getDifficultyMultiplier()));
            }
        }

        return spawned;
    }

    public double getElapsedTime() { return elapsedTime; }
    public double getDifficultyMultiplier() { return getDifficultyMultiplier(); }
}

游戏主循环架构

/**
 * 游戏主控制器，整合所有子系统
 */
public class AirplaneBattle {
    private Player player;
    private List<Enemy> enemies = new ArrayList<>();
    private List<Bullet> bullets = new ArrayList<>();
    private WaveGenerator waveGen = new WaveGenerator();
    private int score = 0;
    private boolean gameOver = false;
    private double gameTime = 0;

    // 屏幕常量
    public static final int SCREEN_WIDTH = 800;
    public static final int SCREEN_HEIGHT = 600;

    public AirplaneBattle() {
        player = new Player(SCREEN_WIDTH / 2.0, SCREEN_HEIGHT - 60);
    }

    /**
     * 单帧更新，由外部渲染循环以固定频率调用（如60FPS）
     * @param deltaTime 距上一帧秒数，通常为 1/60 ≈ 0.0167
     */
    public void update(double deltaTime, double playerMoveInput) {
        if (gameOver) return;
        gameTime += deltaTime;

        // 1. 更新玩家
        player.move(playerMoveInput, deltaTime);
        Bullet pb = player.tryShoot(gameTime);
        if (pb != null) bullets.add(pb);

        // 2. 生成新敌机
        List<Enemy> newEnemies = waveGen.update(deltaTime, player.x);
        enemies.addAll(newEnemies);

        // 3. 敌机更新与射击
        for (Enemy e : enemies) {
            e.update(deltaTime);
            Bullet eb = e.tryShoot(gameTime, player.x);
            if (eb != null) bullets.add(eb);
        }

        // 4. 更新子弹
        for (Bullet b : bullets) {
            b.update(deltaTime);
        }

        // 5. 碰撞检测
        CollisionResult result = CollisionManager.detectCollisions(player, enemies, bullets);
        score += result.scoreGained;
        if (result.playerDamaged && !player.alive) {
            gameOver = true;
        }

        // 6. 清理已销毁实体
        enemies.removeIf(e -> !e.alive);
        bullets.removeIf(b -> !b.alive);
    }

    public int getScore() { return score; }
    public boolean isGameOver() { return gameOver; }
    public Player getPlayer() { return player; }
    public List<Enemy> getEnemies() { return enemies; }
    public List<Bullet> getBullets() { return bullets; }
    public double getGameTime() { return gameTime; }

    /**
     * 带简单文本渲染的演示主方法
     */
    public static void main(String[] args) throws InterruptedException {
        AirplaneBattle game = new AirplaneBattle();
        double deltaTime = 1.0 / 60;

        System.out.println("=== 飞机大战算法演示 ===");
        System.out.println("每帧输出: 时间 | 得分 | 敌机数 | 子弹数 | 玩家血量");
        System.out.println("-".repeat(60));

        int frames = 0;
        while (!game.isGameOver() && frames < 3600) { // 模拟最多60秒
            // 模拟玩家左右移动：正弦波输入
            double input = Math.sin(frames * 0.02);
            game.update(deltaTime, input);

            frames++;
            if (frames % 60 == 0) { // 每秒输出一次状态
                System.out.printf("t=%.1fs | 得分=%d | 敌机=%d | 子弹=%d | 血量=%d%n",
                    game.getGameTime(),
                    game.getScore(),
                    game.getEnemies().size(),
                    game.getBullets().size(),
                    game.getPlayer().getHealth()
                );
            }

            Thread.sleep(16); // 模拟60FPS
        }

        System.out.println("-".repeat(60));
        System.out.println("游戏结束！最终得分: " + game.getScore());
        System.out.println("存活时间: " + String.format("%.1f", game.getGameTime()) + " 秒");
    }
}

算法复杂度分析

碰撞检测是每帧计算开销最大的环节。当玩家子弹和敌机数量均达到20时，每帧需要进行约400次AABB检测。若未来实体数量进一步增长，可引入均匀网格（Uniform Grid）或四叉树（Quadtree）空间索引，将碰撞检测复杂度降至 $O(n)$ 级别。

扩展方向

1. 空间索引优化：当同屏实体超过50个时，使用四叉树划分屏幕空间，仅检测同网格内实体对，可将 $O(n^2)$ 降为 $O(n \log n)$。
2. 行为树替代状态机：为BOSS敌机引入行为树（Behavior Tree），实现更复杂的阶段转换和技能组合。
3. 对象池模式：敌机和子弹频繁创建销毁，使用对象池复用实例，避免GC抖动。
4. 预测射击算法：敌机子弹可加入简单的线性预测，向玩家未来位置发射，提升AI挑战性。

小结

飞机大战虽小，却完整覆盖了游戏开发中的多项核心算法：AABB碰撞检测提供了实体交互的数学基础，有限状态机赋予敌机多样化的行为模式，而基于难度曲线的加权波次生成则确保了游戏节奏的张弛有度。将这三者有机整合，即可在数百行Java代码内构建出一个可玩性十足的射击游戏原型。