每日算法 — 使用java实现小蜜蜂：遗传算法进化搜索与最优弹幕躲避路径规划

引言

小蜜蜂（Galaga/Space Invaders风格）是街机黄金时代最具代表性的射击游戏之一。玩家操控飞船在屏幕底部移动，躲避从天而降的敌人子弹并反击。本文将敌人的弹幕躲避问题抽象为路径规划问题，并使用遗传算法（Genetic Algorithm, GA）在解空间中进行进化搜索，让AI自主学会最优的躲避与反击策略。

问题建模

游戏状态空间

小蜜蜂的核心决策包含两个层面：

1. 躲避层：根据当前弹幕分布，选择飞船的水平移动方向（左/右/停）和是否使用护盾
2. 攻击层：根据敌人阵型的暴露程度，选择射击时机与瞄准目标

我们将每一帧的决策编码为一个基因序列：在连续N帧内，每帧的行动组合（移动方向 × 射击决策）构成一个染色体。

适应度函数设计

遗传算法的核心在于适应度函数。我们采用多目标加权策略：

• 生存奖励：+1 每存活一帧
• 距离惩罚：-dist(飞船, 最近子弹) 的倒数（鼓励远离子弹）
• 射击奖励：+10 每次命中敌人
• 中心偏离惩罚：-|x – 屏幕中点|（鼓励保持在可机动区域）
• 死亡惩罚：-1000 被击中

遗传算法流程

1. 初始化：随机生成M条染色体（每条代表N帧的行动序列）
2. 评估：在模拟环境中执行每条染色体，计算适应度
3. 选择：使用锦标赛选择或轮盘赌选出父代
4. 交叉：单点交叉或均匀交叉产生子代
5. 变异：以概率p对基因位进行随机翻转
6. 精英保留：将最优个体直接带入下一代
7. 迭代：重复2-6步直到收敛或达到最大代数

Java实现

核心数据结构

import java.util.*;

/**
 * 小蜜蜂遗传算法求解器
 * 进化搜索最优弹幕躲避与反击策略
 */
public class GalagaGeneticSolver {

    static final int SCREEN_WIDTH = 800;
    static final int SCREEN_HEIGHT = 600;
    static final int SHIP_Y = 550;        // 飞船Y坐标（固定）
    static final int SHIP_SPEED = 5;      // 飞船水平速度
    static final int BULLET_SPEED = 4;    // 子弹下落速度
    static final int HORIZON = 30;        // 预测帧数（染色体长度）
    static final int POP_SIZE = 100;      // 种群大小
    static final int MAX_GEN = 50;        // 最大迭代代数
    static final double MUT_RATE = 0.15;  // 变异率
    static final double CROSS_RATE = 0.8; // 交叉率

    // 行动编码：0=左移, 1=右移, 2=停留, 3=左移+射击, 4=右移+射击, 5=停留+射击
    static final int ACTION_LEFT = 0;
    static final int ACTION_RIGHT = 1;
    static final int ACTION_STAY = 2;
    static final int ACTION_LEFT_SHOOT = 3;
    static final int ACTION_RIGHT_SHOOT = 4;
    static final int ACTION_STAY_SHOOT = 5;

    static class Vector2 {
        double x, y;
        Vector2(double x, double y) { this.x = x; this.y = y; }
        double distanceTo(Vector2 other) {
            return Math.sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
        }
    }

    static class Bullet {
        Vector2 pos;
        Vector2 vel;  // 速度向量（允许斜向子弹）
        Bullet(double x, double y, double vx, double vy) {
            this.pos = new Vector2(x, y);
            this.vel = new Vector2(vx, vy);
        }
        void update() {
            pos.x += vel.x;
            pos.y += vel.y;
        }
    }

    static class Enemy {
        Vector2 pos;
        int hp;
        Enemy(double x, double y) {
            this.pos = new Vector2(x, y);
            this.hp = 1;
        }
    }

    // 染色体：连续HORIZON帧的行动序列
    static class Chromosome {
        int[] genes;  // 长度 = HORIZON
        double fitness;

        Chromosome() {
            genes = new int[HORIZON];
            for (int i = 0; i < HORIZON; i++) {
                genes[i] = (int)(Math.random() * 6);
            }
        }

        Chromosome(int[] genes) {
            this.genes = genes.clone();
        }

        Chromosome copy() {
            return new Chromosome(this.genes);
        }
    }

    static class GameSnapshot {
        double shipX;
        List<Bullet> bullets;
        List<Enemy> enemies;
        int score;

        GameSnapshot(double shipX, List<Bullet> bullets, List<Enemy> enemies, int score) {
            this.shipX = shipX;
            this.bullets = deepCopyBullets(bullets);
            this.enemies = deepCopyEnemies(enemies);
            this.score = score;
        }

        List<Bullet> deepCopyBullets(List<Bullet> src) {
            List<Bullet> dst = new ArrayList<>();
            for (Bullet b : src) dst.add(new Bullet(b.pos.x, b.pos.y, b.vel.x, b.vel.y));
            return dst;
        }

        List<Enemy> deepCopyEnemies(List<Enemy> src) {
            List<Enemy> dst = new ArrayList<>();
            for (Enemy e : src) dst.add(new Enemy(e.pos.x, e.pos.y));
            return dst;
        }
    }

适应度评估（模拟器）

    /**
     * 在模拟环境中执行染色体，计算适应度
     */
    double evaluate(Chromosome chrom, GameSnapshot snapshot) {
        double shipX = snapshot.shipX;
        List<Bullet> bullets = snapshot.deepCopyBullets(snapshot.bullets);
        List<Enemy> enemies = snapshot.deepCopyEnemies(snapshot.enemies);
        double fitness = 0;
        boolean alive = true;

        for (int t = 0; t < HORIZON && alive; t++) {
            int action = chrom.genes[t];

            // 执行移动
            switch (action) {
                case ACTION_LEFT:
                case ACTION_LEFT_SHOOT:
                    shipX -= SHIP_SPEED;
                    break;
                case ACTION_RIGHT:
                case ACTION_RIGHT_SHOOT:
                    shipX += SHIP_SPEED;
                    break;
                default:
                    break;
            }
            // 边界限制
            shipX = Math.max(20, Math.min(SCREEN_WIDTH - 20, shipX));

            // 处理射击
            if (action >= ACTION_LEFT_SHOOT) {
                // 发射子弹向上
                bullets.add(new Bullet(shipX, SHIP_Y - 10, 0, -6));
            }

            // 更新所有子弹位置
            Iterator<Bullet> bit = bullets.iterator();
            while (bit.hasNext()) {
                Bullet b = bit.next();
                b.update();
                // 移除超出屏幕的子弹
                if (b.pos.y < 0 || b.pos.y > SCREEN_HEIGHT || b.pos.x < 0 || b.pos.x > SCREEN_WIDTH) {
                    bit.remove();
                }
            }

            // 碰撞检测：敌人子弹 vs 飞船
            for (Bullet b : bullets) {
                if (b.vel.y > 0) {  // 向下飞的子弹才是敌人的
                    if (b.pos.distanceTo(new Vector2(shipX, SHIP_Y)) < 15) {
                        alive = false;
                        fitness -= 1000;
                        break;
                    }
                }
            }

            // 碰撞检测：我方子弹 vs 敌人
            Iterator<Bullet> myBit = bullets.iterator();
            while (myBit.hasNext()) {
                Bullet b = myBit.next();
                if (b.vel.y < 0) {  // 向上飞的子弹
                    Iterator<Enemy> eit = enemies.iterator();
                    while (eit.hasNext()) {
                        Enemy e = eit.next();
                        if (b.pos.distanceTo(e.pos) < 20) {
                            eit.remove();
                            myBit.remove();
                            fitness += 10;
                            break;
                        }
                    }
                }
            }

            if (!alive) break;

            // 每帧生存奖励
            fitness += 1;

            // 距离最近子弹的惩罚（鼓励远离威胁）
            double minDist = Double.MAX_VALUE;
            for (Bullet b : bullets) {
                if (b.vel.y > 0) {
                    double d = b.pos.distanceTo(new Vector2(shipX, SHIP_Y));
                    if (d < minDist) minDist = d;
                }
            }
            if (minDist < Double.MAX_VALUE) {
                fitness -= 50.0 / (minDist + 1);
            }

            // 中心偏离惩罚（鼓励留在中间区域以便机动）
            double centerDist = Math.abs(shipX - SCREEN_WIDTH / 2.0);
            fitness -= centerDist * 0.01;
        }

        return fitness;
    }

遗传算子

    /**
     * 锦标赛选择
     */
    Chromosome tournamentSelect(Chromosome[] pop, GameSnapshot snapshot, int tournamentSize) {
        Chromosome best = null;
        double bestFit = Double.NEGATIVE_INFINITY;

        for (int i = 0; i < tournamentSize; i++) {
            int idx = (int)(Math.random() * pop.length);
            Chromosome cand = pop[idx];
            double fit = evaluate(cand, snapshot);
            if (fit > bestFit) {
                bestFit = fit;
                best = cand;
            }
        }
        return best.copy();
    }

    /**
     * 单点交叉
     */
    Chromosome[] crossover(Chromosome p1, Chromosome p2) {
        if (Math.random() > CROSS_RATE) {
            return new Chromosome[]{p1.copy(), p2.copy()};
        }
        int point = (int)(Math.random() * (HORIZON - 1)) + 1;
        int[] c1 = new int[HORIZON];
        int[] c2 = new int[HORIZON];

        System.arraycopy(p1.genes, 0, c1, 0, point);
        System.arraycopy(p2.genes, point, c1, point, HORIZON - point);
        System.arraycopy(p2.genes, 0, c2, 0, point);
        System.arraycopy(p1.genes, point, c2, point, HORIZON - point);

        return new Chromosome[]{new Chromosome(c1), new Chromosome(c2)};
    }

    /**
     * 变异操作
     */
    void mutate(Chromosome chrom) {
        for (int i = 0; i < HORIZON; i++) {
            if (Math.random() < MUT_RATE) {
                chrom.genes[i] = (int)(Math.random() * 6);
            }
        }
    }

主进化循环

    /**
     * 遗传算法主循环
     */
    int[] evolve(GameSnapshot snapshot) {
        Chromosome[] population = new Chromosome[POP_SIZE];
        for (int i = 0; i < POP_SIZE; i++) {
            population[i] = new Chromosome();
        }

        Chromosome bestEver = null;
        double bestFitness = Double.NEGATIVE_INFINITY;

        for (int gen = 0; gen < MAX_GEN; gen++) {
            // 评估并找出当代最优
            Chromosome[] newPop = new Chromosome[POP_SIZE];
            double genBest = Double.NEGATIVE_INFINITY;
            Chromosome genBestChrom = null;

            for (Chromosome c : population) {
                double fit = evaluate(c, snapshot);
                c.fitness = fit;
                if (fit > genBest) {
                    genBest = fit;
                    genBestChrom = c;
                }
            }

            if (genBest > bestFitness) {
                bestFitness = genBest;
                bestEver = genBestChrom.copy();
            }

            // 精英保留
            newPop[0] = bestEver.copy();

            // 生成新一代
            for (int i = 1; i < POP_SIZE; i += 2) {
                Chromosome p1 = tournamentSelect(population, snapshot, 5);
                Chromosome p2 = tournamentSelect(population, snapshot, 5);
                Chromosome[] children = crossover(p1, p2);
                mutate(children[0]);
                mutate(children[1]);
                newPop[i] = children[0];
                if (i + 1 < POP_SIZE) newPop[i + 1] = children[1];
            }

            population = newPop;
        }

        return bestEver != null ? bestEver.genes : new int[HORIZON];
    }

实时决策接口

    /**
     * 每帧调用，返回当前最优行动
     */
    int decideAction(double shipX, List<Bullet> bullets, List<Enemy> enemies, int score) {
        GameSnapshot snapshot = new GameSnapshot(shipX, bullets, enemies, score);
        int[] plan = evolve(snapshot);
        return plan[0];  // 执行规划的第一步
    }

    public static void main(String[] args) {
        GalagaGeneticSolver solver = new GalagaGeneticSolver();

        // 模拟测试场景
        double shipX = 400;
        List<Bullet> bullets = new ArrayList<>();
        List<Enemy> enemies = new ArrayList<>();

        // 生成一些测试子弹
        for (int i = 0; i < 5; i++) {
            bullets.add(new Bullet(200 + i * 100, 100 + i * 50, 0, BULLET_SPEED));
        }
        // 生成测试敌人
        for (int i = 0; i < 3; i++) {
            enemies.add(new Enemy(300 + i * 100, 80));
        }

        int action = solver.decideAction(shipX, bullets, enemies, 0);
        String[] actionNames = {"左移", "右移", "停留", "左移+射击", "右移+射击", "停留+射击"};
        System.out.println("最优决策: " + actionNames[action]);

        // 运行完整模拟
        int totalScore = 0;
        for (int frame = 0; frame < 300; frame++) {
            action = solver.decideAction(shipX, bullets, enemies, totalScore);
            // 更新shipX...
            if (action % 3 == 0) shipX -= SHIP_SPEED;
            else if (action % 3 == 1) shipX += SHIP_SPEED;
            shipX = Math.max(20, Math.min(SCREEN_WIDTH - 20, shipX));

            // 简化：每50帧添加新子弹
            if (frame % 50 == 0) {
                bullets.add(new Bullet(shipX, 50, 0, BULLET_SPEED));
            }

            if (frame % 10 == 0) {
                System.out.println("Frame " + frame + ": shipX=" + (int)shipX + 
                                 ", bullets=" + bullets.size() + ", action=" + actionNames[action]);
            }
        }
    }
}

算法分析

遗传算法不需要计算梯度，对非连续、不可导的适应度 landscape 非常鲁棒。通过种群多样性维持和精英保留策略，能在数十毫秒内找到近似最优的躲避路径。

扩展方向

1. 多目标进化：使用NSGA-II同时优化生存率、击杀数和操作平滑度
2. 协方差矩阵自适应（CMA-ES）：用连续空间优化替代离散基因编码
3. 神经网络策略：将遗传算法搜索到的优质轨迹作为训练数据，监督学习一个实时前馈网络

总结

本文将小蜜蜂的弹幕躲避问题建模为序列决策问题，设计了包含移动和射击联合编码的染色体结构，并通过生存奖励、距离惩罚、射击收益等多目标适应度函数引导遗传算法进化。读者可以调整HORIZON长度平衡前瞻深度与计算开销，也可以将本框架迁移到其他实时策略游戏AI中。