每日算法 — 使用java实现消灭病毒：弹幕轨迹预测与扫描线碰撞检测

引言

消灭病毒是一款休闲射击游戏，玩家控制飞机发射子弹消灭从上方不断袭来的病毒。本文用Java实现消灭病毒的核心AI系统，重点讲解弹幕轨迹的线性预测算法、扫描线碰撞检测以及最优射击策略，包含完整的代码实现。

游戏机制建模

战场坐标系

• 玩家飞机位于屏幕底部，可左右移动
• 病毒从屏幕顶部以不同速度向下移动
• 子弹从飞机向上直线飞行
• 碰撞检测在二维平面进行

病毒运动模型

病毒的运动轨迹可简化为线性或轻微正弦波动：

virus_x(t) = x0 + vx * t + A * sin(w * t)
virus_y(t) = y0 + vy * t

其中 A 为振幅，w 为角频率，控制左右摇摆幅度。

弹幕轨迹预测算法

为了提前规划射击位置，需要预测病毒未来的运动轨迹：

public class TrajectoryPredictor {
    /**
     * 预测病毒在t时刻后的位置（线性+正弦模型）
     */
    public Point2D predictPosition(Virus virus, double t) {
        double x = virus.getX() + virus.getVx() * t 
                   + virus.getAmplitude() * Math.sin(virus.getOmega() * t);
        double y = virus.getY() + virus.getVy() * t;
        return new Point2D.Double(x, y);
    }

    /**
     * 计算子弹命中病毒所需的提前量
     * @param bulletSpeed 子弹速度
     * @return 预计命中时间，无解返回-1
     */
    public double calculateLeadTime(Player player, Virus virus, double bulletSpeed) {
        double dx = virus.getX() - player.getX();
        double dy = virus.getY() - player.getY();
        double vx = virus.getVx();
        double vy = virus.getVy();

        // 简化模型：忽略正弦扰动，用相对运动求解
        // 子弹方向固定向上，相对速度 = (virus_vx, virus_vy - bulletSpeed)
        double relVy = vy - bulletSpeed;

        // 需要子弹到达病毒y坐标的时间
        if (relVy >= 0) return -1; // 病毒下落速度比子弹快，无法命中

        double t = dy / (-relVy); // 相对运动到达y坐标的时间
        double hitX = virus.getX() + vx * t;

        // 检查x坐标是否在射程内（玩家可左右移动补偿）
        if (Math.abs(hitX - player.getX()) > player.getMaxMoveSpeed() * t + 50) {
            return -1; // 即使最大速度移动也无法到达射击位置
        }

        return t;
    }
}

扫描线碰撞检测

游戏中子弹和病毒数量众多，需要高效碰撞检测。扫描线算法（Sweep Line）可以将二维碰撞检测优化到接近线性：

public class SweepLineCollision {

    static class Event implements Comparable<Event> {
        double x;
        boolean isStart;
        Entity entity;

        Event(double x, boolean isStart, Entity entity) {
            this.x = x;
            this.isStart = isStart;
            this.entity = entity;
        }

        @Override
        public int compareTo(Event other) {
            return Double.compare(this.x, other.x);
        }
    }

    /**
     * 扫描线检测所有碰撞对
     * 时间复杂度: O((N+M) log(N+M))，N=子弹数, M=病毒数
     */
    public List<CollisionPair> detectCollisions(List<Bullet> bullets, List<Virus> viruses) {
        List<Event> events = new ArrayList<>();

        // 为每个实体生成x轴区间事件
        for (Bullet b : bullets) {
            double r = b.getRadius();
            events.add(new Event(b.getX() - r, true, b));
            events.add(new Event(b.getX() + r, false, b));
        }
        for (Virus v : viruses) {
            double r = v.getRadius();
            events.add(new Event(v.getX() - r, true, v));
            events.add(new Event(v.getX() + r, false, v));
        }

        Collections.sort(events);

        List<CollisionPair> collisions = new ArrayList<>();
        Set<Entity> active = new HashSet<>();

        for (Event e : events) {
            if (e.isStart) {
                // 新实体进入扫描范围，与当前活跃实体检测碰撞
                for (Entity other : active) {
                    if (checkCollision(e.entity, other)) {
                        collisions.add(new CollisionPair(e.entity, other));
                    }
                }
                active.add(e.entity);
            } else {
                active.remove(e.entity);
            }
        }

        return collisions;
    }

    private boolean checkCollision(Entity a, Entity b) {
        double dx = a.getX() - b.getX();
        double dy = a.getY() - b.getY();
        double dist = Math.sqrt(dx * dx + dy * dy);
        return dist < (a.getRadius() + b.getRadius());
    }
}

最优射击策略

面对屏幕上大量病毒，AI需要决定射击目标和移动位置：

public class ShootingStrategy {
    private TrajectoryPredictor predictor = new TrajectoryPredictor();

    /**
     * 动态规划/贪心混合策略：优先消灭威胁最大的病毒
     * 威胁评估 = 病毒价值 / (距离 * 移动所需时间)
     */
    public Decision makeDecision(Player player, List<Virus> viruses, double bulletSpeed) {
        Virus bestTarget = null;
        double bestPriority = Double.NEGATIVE_INFINITY;
        double bestMoveX = player.getX();

        for (Virus v : viruses) {
            double leadTime = predictor.calculateLeadTime(player, v, bulletSpeed);
            if (leadTime < 0) continue; // 无法命中

            Point2D futurePos = predictor.predictPosition(v, leadTime);
            double moveDist = Math.abs(futurePos.getX() - player.getX());
            double moveTime = moveDist / player.getMaxMoveSpeed();

            if (moveTime > leadTime) continue; // 来不及移动到射击位置

            // 威胁优先级 = 价值 / (距离 * 总响应时间)
            double distToPlayer = Math.sqrt(
                Math.pow(v.getX() - player.getX(), 2) +
                Math.pow(v.getY() - player.getY(), 2)
            );
            double priority = v.getValue() / (distToPlayer * (leadTime + moveTime));

            if (priority > bestPriority) {
                bestPriority = priority;
                bestTarget = v;
                bestMoveX = futurePos.getX();
            }
        }

        return new Decision(bestTarget, bestMoveX, bestTarget != null);
    }
}

完整项目结构

virus-shooter/
├── src/
│   ├── model/
│   │   ├── Player.java          # 玩家飞机
│   │   ├── Virus.java           # 病毒实体
│   │   ├── Bullet.java          # 子弹实体
│   │   └── Decision.java        # AI决策封装
│   ├── physics/
│   │   ├── TrajectoryPredictor.java # 轨迹预测
│   │   └── SweepLineCollision.java  # 扫描线碰撞检测
│   ├── strategy/
│   │   └── ShootingStrategy.java    # 射击策略
│   └── game/
│       └── VirusGame.java       # 游戏主循环
└── Main.java

复杂度分析

总结

本文通过Java实现了消灭病毒射击游戏的核心AI系统。轨迹预测利用线性运动模型计算提前量，扫描线算法将碰撞检测从O(N×M)优化到O((N+M)log(N+M))，射击策略基于威胁优先级进行贪心决策。三者协同构成了高效的弹幕射击AI。