每日算法 — 使用java实现太空侵略者：波次生成与网格碰撞检测

概述

太空侵略者（Space Invaders）是1978年推出的经典街机射击游戏。玩家操控飞船击落从屏幕上方逐步逼近的外星入侵者。本文将用Java实现该游戏的核心算法，重点讲解外星敌人的波次生成算法、基于网格系统的移动策略，以及AABB碰撞检测在子弹与敌人之间的应用。

核心算法设计

1. 外星入侵者网格布局

游戏中的敌人按行列排成整齐的网格，每波敌人有固定的行列数。我们使用二维数组存储敌人状态，并通过统一的步长控制整体移动。

public class InvaderGrid {
    private Invader[][] grid;
    private int rows, cols;
    private float x, y;           // 网格左上角坐标
    private float stepX = 15f;    // 水平步长
    private float stepY = 20f;    // 垂直步长（碰到边界后下沉）
    private int direction = 1;    // 1=右移, -1=左移
    private float speed = 1.0f;   // 速度倍率（随数量减少而加快）

    public InvaderGrid(int rows, int cols, float startX, float startY) {
        this.rows = rows;
        this.cols = cols;
        this.x = startX;
        this.y = startY;
        grid = new Invader[rows][cols];
        initGrid();
    }

    private void initGrid() {
        float spacingX = 40f;
        float spacingY = 30f;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                // 不同行敌人分值不同（越靠上分值越高）
                int type = (r < 1) ? 3 : (r < 3) ? 2 : 1;
                grid[r][c] = new Invader(
                    x + c * spacingX,
                    y + r * spacingY,
                    type
                );
            }
        }
    }
}

2. 波次移动与边界检测

所有存活的外星人同步移动，当任意一列触及屏幕边界时，整批敌人下移并反向。速度随存活数量减少而递增，制造逐渐紧张的游戏节奏。

public void update(float screenWidth, float screenHeight) {
    boolean hitEdge = false;
    float spacingX = 40f;
    float rightmost = 0, leftmost = screenWidth;

    // 计算存活敌人的最左和最右位置
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            Invader inv = grid[r][c];
            if (inv != null && inv.isAlive()) {
                float ex = inv.getX();
                if (ex < leftmost) leftmost = ex;
                if (ex > rightmost) rightmost = ex;
            }
        }
    }

    // 检测是否触及边界
    if (rightmost >= screenWidth - 30 || leftmost <= 10) {
        hitEdge = true;
    }

    if (hitEdge) {
        direction *= -1;           // 反向
        y += stepY;                // 整体下移
        // 速度递增：存活越少越快
        speed = 1.0f + (1.0f - getAliveRatio()) * 2.5f;
    }

    // 统一更新所有存活敌人位置
    float dx = direction * stepX * speed;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            Invader inv = grid[r][c];
            if (inv != null && inv.isAlive()) {
                inv.move(dx, hitEdge ? stepY : 0);
            }
        }
    }
}

private float getAliveRatio() {
    int alive = 0, total = rows * cols;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != null && grid[r][c].isAlive()) alive++;
        }
    }
    return (float) alive / total;
}

3. AABB碰撞检测

子弹与敌人、敌人子弹与玩家飞船之间均使用轴对齐包围盒（AABB）碰撞检测。该方法仅需比较四个边界值，计算复杂度为O(1)。

public class AABB {
    public float x, y, width, height;

    public AABB(float x, float y, float width, float height) {
        this.x = x; this.y = y;
        this.width = width; this.height = height;
    }

    /**
     * AABB碰撞检测核心算法
     * 两个矩形相交当且仅当在X轴和Y轴上的投影均重叠
     */
    public boolean intersects(AABB other) {
        return this.x < other.x + other.width &&
               this.x + this.width > other.x &&
               this.y < other.y + other.height &&
               this.y + this.height > other.y;
    }
}

4. 敌人随机射击算法

存活敌人中随机选择若干名进行射击，射击概率与波次进度和存活数量相关。

public List<Bullet> tryFire(Random rand) {
    List<Bullet> bullets = new ArrayList<>();
    List<Invader> alive = new ArrayList<>();

    // 收集所有存活敌人
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != null && grid[r][c].isAlive()) {
                alive.add(grid[r][c]);
            }
        }
    }

    // 射击概率：基础概率 + 波次加成
    double baseChance = 0.02;
    double waveBonus = waveNumber * 0.005;
    double chance = Math.min(baseChance + waveBonus, 0.08);

    for (Invader inv : alive) {
        if (rand.nextDouble() < chance) {
            // 只有底部敌人才射击（避免子弹穿过上方敌人）
            if (isBottommost(inv)) {
                bullets.add(new Bullet(inv.getX() + 15, inv.getY() + 20, 3f));
            }
        }
    }
    return bullets;
}

private boolean isBottommost(Invader target) {
    int col = target.getCol();
    for (int r = rows - 1; r >= 0; r--) {
        if (grid[r][col] != null && grid[r][col].isAlive()) {
            return grid[r][col] == target;
        }
    }
    return false;
}

5. 完整运行示例

public class SpaceInvadersGame {
    private InvaderGrid grid;
    private PlayerShip player;
    private List<Bullet> playerBullets = new ArrayList<>();
    private List<Bullet> enemyBullets = new ArrayList<>();
    private Random rand = new Random();
    private int score = 0;
    private int waveNumber = 1;

    public SpaceInvadersGame() {
        grid = new InvaderGrid(5, 11, 50, 50);
        player = new PlayerShip(400, 550);
    }

    public void update(float screenWidth, float screenHeight) {
        // 更新敌人网格
        grid.update(screenWidth, screenHeight);

        // 敌人随机射击
        enemyBullets.addAll(grid.tryFire(rand));

        // 更新子弹位置
        for (Bullet b : playerBullets) b.move(0, -6f);
        for (Bullet b : enemyBullets) b.move(0, 4f);

        // 碰撞检测：玩家子弹 vs 敌人
        Iterator<Bullet> pit = playerBullets.iterator();
        while (pit.hasNext()) {
            Bullet pb = pit.next();
            Invader hit = grid.findCollision(pb.getBounds());
            if (hit != null) {
                hit.setAlive(false);
                score += hit.getScore();
                pit.remove();
            }
        }

        // 碰撞检测：敌人子弹 vs 玩家
        for (Bullet eb : enemyBullets) {
            if (eb.getBounds().intersects(player.getBounds())) {
                player.hit();
            }
        }

        // 清理越界子弹
        playerBullets.removeIf(b -> b.getY() < 0);
        enemyBullets.removeIf(b -> b.getY() > screenHeight);

        // 检查波次结束
        if (grid.allDestroyed()) {
            waveNumber++;
            grid = new InvaderGrid(5, 11, 50, 50 - waveNumber * 5);
        }
    }

    public void playerShoot() {
        playerBullets.add(new Bullet(player.getX() + 18, player.getY(), -8f));
    }
}

复杂度分析

总结

太空侵略者的核心算法围绕网格同步移动、边界触发反向和AABB碰撞检测三大机制展开。速度随存活数量递减而递增的设计，是典型的难度曲线控制策略。将敌人按行列组织成二维网格，不仅便于统一管理移动，也为后续的波次生成和阵型变化提供了良好的数据结构基础。