每日算法 — 使用java实现太空侵略者：队列调度与弹幕轨迹预测算法

引言

太空侵略者是街机射击游戏鼻祖，核心机制为玩家操控飞船射击从上方阵列降落的入侵者。本文用Java实现太空侵略者的核心AI，重点讲解队列调度算法管理敌机编队阵型，以及弹幕轨迹预测算法让敌机子弹更具威胁性。

核心算法概览

1. 敌机编队队列调度：入侵者按行列组成编队，以整体阵型左右平移并逐行下降
2. 射击决策算法：计算与玩家的夹角，预测子弹飞行轨迹
3. 动态难度调整：随敌机数量减少加快移动速度，维持游戏紧张感

敌机编队队列模型

将入侵者抽象为二维队列，每行同类型敌机，整体按队形规则移动。

import java.util.*;

public class InvaderFormation {

    // 单个入侵者
    static class Invader {
        int row, col;      // 编队中的行列位置
        double x, y;       // 屏幕实际坐标
        int type;          // 敌机类型（1=小型，2=中型，3=大型）
        boolean alive;
        long lastShotTime; // 上次射击时间

        Invader(int row, int col, double x, double y, int type) {
            this.row = row; this.col = col;
            this.x = x; this.y = y;
            this.type = type;
            this.alive = true;
            this.lastShotTime = 0;
        }
    }

    private List<Invader> invaders;
    private int rows = 5, cols = 11;      // 标准5行11列编队
    private double spacingX = 48, spacingY = 36; // 敌机间距
    private double startX = 60, startY = 50;     // 编队起始位置
    private int direction = 1;            // 1=右移，-1=左移
    private double speed = 0.5;           // 基础移动速度
    private double dropDistance = 20;     // 触边后下降距离

    public InvaderFormation() {
        invaders = new ArrayList<>();
        initFormation();
    }

    /**
     * 初始化标准编队阵型
     * 第0行：大型敌机（3分）
     * 第1-2行：中型敌机（2分）
     * 第3-4行：小型敌机（1分）
     */
    private void initFormation() {
        for (int r = 0; r < rows; r++) {
            int type = (r == 0) ? 3 : (r <= 2) ? 2 : 1;
            for (int c = 0; c < cols; c++) {
                double x = startX + c * spacingX;
                double y = startY + r * spacingY;
                invaders.add(new Invader(r, c, x, y, type));
            }
        }
    }

    /**
     * 队列调度更新：整队左右平移，触边后下降换向
     */
    public void updateFormation() {
        boolean hitEdge = false;

        // 先检测是否有存活敌机触边
        for (Invader inv : invaders) {
            if (!inv.alive) continue;
            if ((direction == 1 && inv.x >= 750) || 
                (direction == -1 && inv.x <= 10)) {
                hitEdge = true;
                break;
            }
        }

        // 触边：全队下降并换向
        if (hitEdge) {
            direction *= -1;
            for (Invader inv : invaders) {
                if (inv.alive) inv.y += dropDistance;
            }
        } else {
            // 正常平移：按存活数量动态加速
            double currentSpeed = speed * speedMultiplier();
            for (Invader inv : invaders) {
                if (inv.alive) inv.x += direction * currentSpeed;
            }
        }
    }

    /**
     * 动态速度倍率：存活越少，速度越快
     * 公式：speedMult = 1 + (1 - aliveRatio) * 2
     * 满编时1.0倍，剩1只时约3.0倍
     */
    private double speedMultiplier() {
        int aliveCount = 0;
        for (Invader inv : invaders) if (inv.alive) aliveCount++;
        double ratio = (double) aliveCount / invaders.size();
        return 1.0 + (1.0 - ratio) * 2.0;
    }

    public List<Invader> getInvaders() { return invaders; }
}

弹幕轨迹预测算法

敌机发射的子弹需要预判玩家位置，使用简单的线性插值预测。

public class BulletTrajectory {

    private double x, y;      // 子弹当前位置
    private double vx, vy;    // 速度向量
    private double speed = 3.0; // 子弹基础速度

    /**
     * 创建指向玩家当前位置的子弹（简单追踪）
     * @param startX, startY 子弹起始坐标
     * @param targetX, targetY 玩家当前坐标
     */
    public BulletTrajectory(double startX, double startY, 
                            double targetX, double targetY) {
        this.x = startX;
        this.y = startY;

        double dx = targetX - startX;
        double dy = targetY - startY;
        double dist = Math.sqrt(dx * dx + dy * dy);

        // 归一化方向向量并乘以速度
        if (dist > 0) {
            this.vx = (dx / dist) * speed;
            this.vy = (dy / dist) * speed;
        } else {
            this.vx = 0; this.vy = speed;
        }
    }

    /**
     * 每帧更新子弹位置
     */
    public void update() {
        x += vx;
        y += vy;
    }

    /**
     * 预测N帧后的位置（用于碰撞预检和玩家预警）
     */
    public double[] predictPosition(int frames) {
        return new double[]{ x + vx * frames, y + vy * frames };
    }

    public boolean isOutOfScreen(double height) {
        return y > height || y < 0 || x < 0 || x > 800;
    }

    public double getX() { return x; }
    public double getY() { return y; }
}

射击决策系统

使用概率加权选择发射敌机，最下方的敌机有更高射击权重，避免被上方敌机遮挡。

import java.util.*;

public class ShootingSystem {

    private Random random = new Random();
    private long lastGlobalShot = 0;
    private long minShotInterval = 800; // 全局最小射击间隔(ms)

    /**
     * 选择射击敌机并生成子弹
     * 策略：仅最下方存活敌机可射击，按列随机选择
     * @param formation 敌机编队
     * @param playerX, playerY 玩家位置
     * @param currentTime 当前时间戳
     * @return 新生成的子弹，若无则返回null
     */
    public EnemyBullet selectShooterAndFire(List<InvaderFormation.Invader> invaders,
                                            double playerX, double playerY,
                                            long currentTime) {
        if (currentTime - lastGlobalShot < minShotInterval) return null;

        // 找出每列最下方的存活敌机
        Map<Integer, InvaderFormation.Invader> bottomInvaders = new HashMap<>();
        for (InvaderFormation.Invader inv : invaders) {
            if (!inv.alive) continue;
            InvaderFormation.Invader existing = bottomInvaders.get(inv.col);
            if (existing == null || inv.row > existing.row) {
                bottomInvaders.put(inv.col, inv);
            }
        }

        if (bottomInvaders.isEmpty()) return null;

        // 随机选择一列进行射击
        List<InvaderFormation.Invader> shooters = new ArrayList<>(bottomInvaders.values());
        InvaderFormation.Invader shooter = shooters.get(random.nextInt(shooters.size()));

        lastGlobalShot = currentTime;

        // 生成带轨迹预测的子弹
        return new EnemyBullet(shooter.x + 16, shooter.y + 16, playerX, playerY);
    }

    // 内部类：敌方子弹
    static class EnemyBullet {
        BulletTrajectory trajectory;

        EnemyBullet(double startX, double startY, double targetX, double targetY) {
            this.trajectory = new BulletTrajectory(startX, startY, targetX, targetY);
        }
    }
}

玩家飞船与碰撞检测

public class PlayerShip {
    private double x, y;       // 位置
    private double speed = 5;  // 移动速度
    private int lives = 3;     // 生命数
    private double width = 32, height = 24; // 碰撞体积

    public PlayerShip(double startX, double startY) {
        this.x = startX; this.y = startY;
    }

    public void moveLeft() { x -= speed; clamp(); }
    public void moveRight() { x += speed; clamp(); }

    private void clamp() {
        if (x < 0) x = 0;
        if (x > 800 - width) x = 800 - width;
    }

    /**
     * 圆形-矩形碰撞检测（子弹击中玩家）
     */
    public boolean checkHit(double bulletX, double bulletY, double bulletRadius) {
        // 找到矩形上离圆心最近的点
        double closestX = Math.max(x, Math.min(bulletX, x + width));
        double closestY = Math.max(y, Math.min(bulletY, y + height));
        double dx = bulletX - closestX;
        double dy = bulletY - closestY;
        return (dx * dx + dy * dy) < (bulletRadius * bulletRadius);
    }

    public void loseLife() { lives--; }
    public boolean isAlive() { return lives > 0; }
    public double getX() { return x; }
    public double getY() { return y; }
}

游戏主循环

public class SpaceInvadersGame {

    private InvaderFormation formation;
    private PlayerShip player;
    private ShootingSystem shootingSystem;
    private List<BulletTrajectory> enemyBullets;
    private List<BulletTrajectory> playerBullets;

    public SpaceInvadersGame() {
        formation = new InvaderFormation();
        player = new PlayerShip(400, 550);
        shootingSystem = new ShootingSystem();
        enemyBullets = new ArrayList<>();
        playerBullets = new ArrayList<>();
    }

    /**
     * 游戏主循环，每帧调用
     */
    public void gameLoop(long currentTime) {
        // 1. 更新敌机编队位置（队列调度）
        formation.updateFormation();

        // 2. 敌机射击决策
        ShootingSystem.EnemyBullet newBullet = shootingSystem.selectShooterAndFire(
            formation.getInvaders(), player.getX(), player.getY(), currentTime);
        if (newBullet != null) {
            enemyBullets.add(newBullet.trajectory);
        }

        // 3. 更新所有子弹位置
        for (BulletTrajectory bt : enemyBullets) bt.update();
        for (BulletTrajectory bt : playerBullets) bt.update();

        // 4. 碰撞检测
        checkCollisions();

        // 5. 清理越界子弹
        enemyBullets.removeIf(b -> b.isOutOfScreen(600));
        playerBullets.removeIf(b -> b.isOutOfScreen(600));
    }

    private void checkCollisions() {
        // 检测敌方子弹是否击中玩家
        for (BulletTrajectory bt : enemyBullets) {
            if (player.checkHit(bt.getX(), bt.getY(), 3)) {
                player.loseLife();
            }
        }

        // 检测玩家子弹是否击中敌机
        for (BulletTrajectory pb : playerBullets) {
            for (InvaderFormation.Invader inv : formation.getInvaders()) {
                if (!inv.alive) continue;
                if (pb.getX() >= inv.x && pb.getX() <= inv.x + 32 &&
                    pb.getY() >= inv.y && pb.getY() <= inv.y + 24) {
                    inv.alive = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        SpaceInvadersGame game = new SpaceInvadersGame();
        long startTime = System.currentTimeMillis();

        // 模拟运行100帧
        for (int i = 0; i < 100; i++) {
            game.gameLoop(startTime + i * 16); // 假设60FPS，每帧16ms
        }

        System.out.println("Game simulation completed.");
    }
}

复杂度分析

总结

本文以太空侵略者为场景，讲解了队列调度管理敌机编队阵型、以及基于方向向量的弹幕轨迹预测。读者可扩展：
– 实现更智能的射击预测（考虑玩家移动速度，进行提前量计算）
– 加入敌机俯冲攻击模式，突破队列编队限制
– 使用对象池管理子弹，避免频繁创建销毁对象