每日算法 — 使用java实现太空侵略者：阵型波浪移动与子弹碰撞检测

引言

太空侵略者（Space Invaders）是1978年推出的街机射击游戏，被誉为电子游戏史上的里程碑。玩家控制飞船在屏幕底部移动，射击从上方阵型中逐渐下降的敌人。本文将用Java实现太空侵略者的核心算法，重点讲解敌人阵型的波浪移动模式、AABB碰撞检测系统，以及敌方射击AI的概率触发策略。

问题建模

太空侵略者可抽象为以下算法组件：

1. 敌人阵型：M行N列的敌人矩阵，每个敌人有固定间距
2. 波浪移动：阵型整体左右移动，触边后下降一层并反向
3. 碰撞检测：玩家子弹与敌人、敌人子弹与玩家的命中判定
4. 射击AI：敌人何时射击、由哪个敌人射击
5. 难度曲线：随着敌人数量减少，移动速度加快

核心算法设计

1. 阵型波浪移动

敌人以矩阵形式排列，整体移动逻辑：
– 所有敌人共享一个基础位置偏移量（formation offset）
– 每帧更新偏移量，使阵型左右移动
– 当最左/最右敌人触边时，偏移量下移并水平反向
– 移动速度 = 基础速度 × 存活敌人数量倒数（越少越快）

2. AABB碰撞检测

所有游戏对象使用轴对齐包围盒（AABB）表示：
– 碰撞判定：两个AABB在X轴和Y轴上的投影均重叠
– 公式：(a.x < b.x + b.w) && (a.x + a.w > b.x) && (a.y < b.y + b.h) && (a.y + a.h > b.y)

3. 射击AI

敌人射击策略：
– 概率触发：每帧每个底部敌人有概率发射子弹
– 底部优先：只有最底部的敌人才有射击权限（避免自伤）
– 难度调整：存活敌人越少，射击频率越高

Java完整实现

import java.util.*;

/**
 * 太空侵略者：阵型波浪移动与AABB碰撞检测
 */
public class SpaceInvadersAI {

    // 游戏参数
    private static final int SCREEN_WIDTH = 800;
    private static final int SCREEN_HEIGHT = 600;
    private static final int ENEMY_ROWS = 5;
    private static final int ENEMY_COLS = 11;
    private static final int ENEMY_WIDTH = 40;
    private static final int ENEMY_HEIGHT = 30;
    private static final int ENEMY_SPACING_X = 50;
    private static final int ENEMY_SPACING_Y = 40;
    private static final int PLAYER_WIDTH = 50;
    private static final int PLAYER_HEIGHT = 30;
    private static final int BULLET_WIDTH = 4;
    private static final int BULLET_HEIGHT = 10;
    private static final int BUNKER_WIDTH = 60;
    private static final int BUNKER_HEIGHT = 40;
    private static final int BASE_SPEED = 2;
    private static final int DROP_DISTANCE = 20;

    private Random random;
    private int score;
    private int lives;
    private boolean gameOver;

    // 阵型状态
    private double formationX;      // 阵型左上角X
    private double formationY;      // 阵型左上角Y
    private int direction;          // 1=右, -1=左

    public SpaceInvadersAI() {
        this.random = new Random();
        this.score = 0;
        this.lives = 3;
        this.gameOver = false;
        this.formationX = 50;
        this.formationY = 50;
        this.direction = 1;
        initializeGame();
    }

    /**
     * AABB包围盒
     */
    static class AABB {
        double x, y, w, h;

        AABB(double x, double y, double w, double h) {
            this.x = x; this.y = y; this.w = w; this.h = h;
        }

        /**
         * AABB碰撞检测核心算法
         */
        boolean intersects(AABB other) {
            return this.x < other.x + other.w &&
                   this.x + this.w > other.x &&
                   this.y < other.y + other.h &&
                   this.y + this.h > other.y;
        }

        boolean isOffScreen() {
            return y + h < 0 || y > SCREEN_HEIGHT || x + w < 0 || x > SCREEN_WIDTH;
        }
    }

    /**
     * 敌人
     */
    static class Enemy {
        int row, col;           // 在阵型中的行列位置
        boolean alive;          // 是否存活
        int type;               // 敌人类型（不同分数）
        AABB bbox;            // 包围盒

        Enemy(int row, int col, int type) {
            this.row = row;
            this.col = col;
            this.alive = true;
            this.type = type;
            this.bbox = new AABB(0, 0, ENEMY_WIDTH, ENEMY_HEIGHT);
        }

        void updatePosition(double formX, double formY) {
            bbox.x = formX + col * ENEMY_SPACING_X;
            bbox.y = formY + row * ENEMY_SPACING_Y;
        }
    }

    /**
     * 子弹
     */
    static class Bullet {
        double x, y;
        double speedY;
        boolean fromPlayer;     // true=玩家子弹, false=敌人子弹
        AABB bbox;
        boolean active;

        Bullet(double x, double y, double speedY, boolean fromPlayer) {
            this.x = x; this.y = y;
            this.speedY = speedY;
            this.fromPlayer = fromPlayer;
            this.bbox = new AABB(x, y, BULLET_WIDTH, BULLET_HEIGHT);
            this.active = true;
        }

        void update() {
            y += speedY;
            bbox.x = x;
            bbox.y = y;
            if (bbox.isOffScreen()) active = false;
        }
    }

    /**
     * 玩家飞船
     */
    static class Player {
        double x, y;
        double speed;
        AABB bbox;
        int cooldown;           // 射击冷却

        Player() {
            this.x = SCREEN_WIDTH / 2.0;
            this.y = SCREEN_HEIGHT - 50;
            this.speed = 5;
            this.bbox = new AABB(x, y, PLAYER_WIDTH, PLAYER_HEIGHT);
            this.cooldown = 0;
        }

        void moveLeft() { x = Math.max(0, x - speed); }
        void moveRight() { x = Math.min(SCREEN_WIDTH - PLAYER_WIDTH, x + speed); }

        void update() {
            bbox.x = x;
            bbox.y = y;
            if (cooldown > 0) cooldown--;
        }

        Bullet shoot() {
            if (cooldown > 0) return null;
            cooldown = 15;
            return new Bullet(x + PLAYER_WIDTH/2, y, -8, true);
        }
    }

    /**
     * 掩体（防御工事）
     */
    static class Bunker {
        AABB bbox;
        int health;

        Bunker(double x, double y) {
            this.bbox = new AABB(x, y, BUNKER_WIDTH, BUNKER_HEIGHT);
            this.health = 4;
        }
    }

    // 游戏对象集合
    private Enemy[][] enemies;
    private List<Bullet> bullets;
    private Player player;
    private List<Bunker> bunkers;

    void initializeGame() {
        enemies = new Enemy[ENEMY_ROWS][ENEMY_COLS];
        for (int r = 0; r < ENEMY_ROWS; r++) {
            for (int c = 0; c < ENEMY_COLS; c++) {
                int type = (r == 0) ? 3 : (r <= 2) ? 2 : 1; // 越上面分数越高
                enemies[r][c] = new Enemy(r, c, type);
            }
        }

        bullets = new ArrayList<>();
        player = new Player();

        bunkers = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            bunkers.add(new Bunker(100 + i * 200, SCREEN_HEIGHT - 120));
        }
    }

    /**
     * 获取存活敌人数量
     */
    int getAliveCount() {
        int count = 0;
        for (int r = 0; r < ENEMY_ROWS; r++) {
            for (int c = 0; c < ENEMY_COLS; c++) {
                if (enemies[r][c].alive) count++;
            }
        }
        return count;
    }

    /**
     * 获取阵型边界
     */
    int getLeftmostCol() {
        for (int c = 0; c < ENEMY_COLS; c++) {
            for (int r = 0; r < ENEMY_ROWS; r++) {
                if (enemies[r][c].alive) return c;
            }
        }
        return 0;
    }

    int getRightmostCol() {
        for (int c = ENEMY_COLS - 1; c >= 0; c--) {
            for (int r = 0; r < ENEMY_ROWS; r++) {
                if (enemies[r][c].alive) return c;
            }
        }
        return ENEMY_COLS - 1;
    }

    int getBottommostRow(int col) {
        for (int r = ENEMY_ROWS - 1; r >= 0; r--) {
            if (enemies[r][col].alive) return r;
        }
        return -1;
    }

    /**
     * 更新阵型位置（波浪移动核心算法）
     */
    void updateFormation() {
        int alive = getAliveCount();
        if (alive == 0) {
            gameOver = true;
            return;
        }

        // 速度随敌人减少而增加
        double speed = BASE_SPEED + (ENEMY_ROWS * ENEMY_COLS - alive) * 0.3;

        // 水平移动
        formationX += direction * speed;

        // 检测是否触边
        int leftCol = getLeftmostCol();
        int rightCol = getRightmostCol();
        double leftEdge = formationX + leftCol * ENEMY_SPACING_X;
        double rightEdge = formationX + rightCol * ENEMY_SPACING_X + ENEMY_WIDTH;

        if (direction > 0 && rightEdge >= SCREEN_WIDTH - 20) {
            direction = -1;
            formationY += DROP_DISTANCE;
        } else if (direction < 0 && leftEdge <= 20) {
            direction = 1;
            formationY += DROP_DISTANCE;
        }

        // 更新所有敌人位置
        for (int r = 0; r < ENEMY_ROWS; r++) {
            for (int c = 0; c < ENEMY_COLS; c++) {
                enemies[r][c].updatePosition(formationX, formationY);
            }
        }

        // 检查是否到达底部（游戏结束）
        for (int r = 0; r < ENEMY_ROWS; r++) {
            for (int c = 0; c < ENEMY_COLS; c++) {
                if (enemies[r][c].alive && enemies[r][c].bbox.y + ENEMY_HEIGHT >= player.bbox.y) {
                    gameOver = true;
                    return;
                }
            }
        }
    }

    /**
     * 敌人射击AI：概率触发，底部敌人优先
     */
    void enemyShoot() {
        int alive = getAliveCount();
        double shootProb = 0.005 + (55 - alive) * 0.0002; // 基础概率+难度加成

        for (int c = 0; c < ENEMY_COLS; c++) {
            int bottomRow = getBottommostRow(c);
            if (bottomRow >= 0 && enemies[bottomRow][c].alive) {
                if (random.nextDouble() < shootProb) {
                    Enemy e = enemies[bottomRow][c];
                    bullets.add(new Bullet(e.bbox.x + ENEMY_WIDTH/2, e.bbox.y + ENEMY_HEIGHT, 3, false));
                }
            }
        }
    }

    /**
     * 碰撞检测与处理
     */
    void handleCollisions() {
        Iterator<Bullet> it = bullets.iterator();
        while (it.hasNext()) {
            Bullet b = it.next();
            if (!b.active) continue;

            if (b.fromPlayer) {
                // 玩家子弹打敌人
                for (int r = 0; r < ENEMY_ROWS; r++) {
                    for (int c = 0; c < ENEMY_COLS; c++) {
                        Enemy e = enemies[r][c];
                        if (e.alive && b.bbox.intersects(e.bbox)) {
                            e.alive = false;
                            b.active = false;
                            score += e.type * 10;
                            break;
                        }
                    }
                    if (!b.active) break;
                }

                // 玩家子弹打掩体
                if (b.active) {
                    for (Bunker bunker : bunkers) {
                        if (bunker.health > 0 && b.bbox.intersects(bunker.bbox)) {
                            bunker.health--;
                            b.active = false;
                            break;
                        }
                    }
                }
            } else {
                // 敌人子弹打玩家
                if (b.bbox.intersects(player.bbox)) {
                    b.active = false;
                    lives--;
                    if (lives <= 0) gameOver = true;
                }

                // 敌人子弹打掩体
                if (b.active) {
                    for (Bunker bunker : bunkers) {
                        if (bunker.health > 0 && b.bbox.intersects(bunker.bbox)) {
                            bunker.health--;
                            b.active = false;
                            break;
                        }
                    }
                }
            }
        }

        bullets.removeIf(b -> !b.active);
    }

    /**
     * AI玩家策略：左右移动瞄准最近敌人，适时射击
     */
    void updatePlayerAI() {
        // 找到最近的存活敌人
        Enemy nearest = null;
        double minDist = Double.MAX_VALUE;

        for (int r = 0; r < ENEMY_ROWS; r++) {
            for (int c = 0; c < ENEMY_COLS; c++) {
                Enemy e = enemies[r][c];
                if (e.alive) {
                    double dx = e.bbox.x - player.x;
                    double dy = e.bbox.y - player.y;
                    double dist = dx * dx + dy * dy;
                    if (dist < minDist) {
                        minDist = dist;
                        nearest = e;
                    }
                }
            }
        }

        if (nearest != null) {
            double targetX = nearest.bbox.x;
            // 向目标移动
            if (Math.abs(player.x - targetX) > 5) {
                if (player.x < targetX) player.moveRight();
                else player.moveLeft();
            }
        }

        // 射击
        Bullet b = player.shoot();
        if (b != null) bullets.add(b);
    }

    /**
     * 主游戏循环
     */
    void gameLoop(int maxFrames) {
        System.out.println("=== 太空侵略者模拟开始 ===");

        for (int frame = 0; frame < maxFrames && !gameOver; frame++) {
            // 更新阵型
            updateFormation();

            // 敌人射击
            enemyShoot();

            // AI玩家操作
            updatePlayerAI();

            // 更新子弹
            for (Bullet b : bullets) b.update();
            bullets.removeIf(b -> !b.active);

            // 碰撞检测
            handleCollisions();

            // 更新玩家
            player.update();

            // 每30帧输出状态
            if (frame % 30 == 0) {
                System.out.printf("Frame %d: Score=%d, Lives=%d, Enemies=%d%n",
                    frame, score, lives, getAliveCount());
            }
        }

        System.out.println("=== 模拟结束 ===");
        System.out.println("最终得分: " + score);
        System.out.println("剩余生命: " + lives);
        System.out.println("存活敌人: " + getAliveCount());
    }

    public static void main(String[] args) {
        SpaceInvadersAI game = new SpaceInvadersAI();
        game.gameLoop(5000);
    }
}

复杂度分析

对于标准55个敌人的阵型，每帧处理在可接受范围内。

算法优化方向

1. 空间哈希：将屏幕划分为网格，加速碰撞检测从O(n²)降到O(n)
2. 预测射击：AI预判敌人移动轨迹，提前射击
3. 群体行为：敌人添加蜂拥、散开等群体AI行为
4. Boss模式：大型敌人的多部位AABB检测与弱点系统

总结

太空侵略者是学习游戏AI与碰撞检测的经典案例。波浪移动算法展示了如何用简单的偏移量控制群体行为，AABB碰撞检测是2D游戏开发的基础技能，而概率射击AI则提供了入门级的行为决策模型。通过Java实现，我们掌握了从游戏循环设计到空间碰撞检测的完整开发流程。