每日算法 — 使用java实现水果忍者：滑动切割检测与贪心连击策略

引言

水果忍者（Fruit Ninja）是风靡全球的休闲游戏：屏幕上不断抛出水果，玩家通过滑动屏幕进行切割，切中水果得分，切中炸弹则游戏结束。本文将用 Java 完整实现水果忍者的核心算法系统，重点讲解滑动轨迹与水果的线段-圆碰撞检测以及贪心连击策略下的最优切割序列规划。

几何基础：线段与圆的碰撞检测

核心问题

玩家的一次滑动对应平面上的一条线段（从触摸开始到释放），水果是一个圆形。需要判断线段是否与圆相交，即是否存在线段上的点到圆心的距离小于等于半径。

最近点投影法

设线段端点为 P1(x1,y1)、P2(x2,y2)，圆心为 C(cx,cy)，半径为 r。计算 C 在线段所在直线上的投影点 Q：

线段方向向量:  d = P2 - P1
参数 t = dot(C - P1, d) / dot(d, d)
若 0 ≤ t ≤ 1，投影点在线段上，Q = P1 + t * d
若 t < 0，最近点为 P1
若 t > 1，最近点为 P2

碰撞判定：distance(C, Q) ≤ r

/**
 * 二维向量工具类
 */
public class Vec2 {
    public final double x, y;

    public Vec2(double x, double y) { this.x = x; this.y = y; }
    public Vec2 add(Vec2 v) { return new Vec2(x + v.x, y + v.y); }
    public Vec2 sub(Vec2 v) { return new Vec2(x - v.x, y - v.y); }
    public Vec2 mul(double s) { return new Vec2(x * s, y * s); }
    public double dot(Vec2 v) { return x * v.x + y * v.y; }
    public double length() { return Math.hypot(x, y); }
    public double distTo(Vec2 v) { return sub(v).length(); }
}

/**
 * 几何碰撞检测工具
 */
public class GeometryUtils {

    /**
     * 线段与圆的碰撞检测（最近点投影法）
     * @param p1 线段起点
     * @param p2 线段终点
     * @param center 圆心
     * @param radius 半径
     * @return 是否相交，相交时返回true并填充outClosest
     */
    public static boolean segmentCircleIntersect(Vec2 p1, Vec2 p2, 
                                                  Vec2 center, double radius,
                                                  Vec2[] outClosest) {
        Vec2 d = p2.sub(p1); // 线段方向向量
        Vec2 f = p1.sub(center);

        double a = d.dot(d);
        double b = 2 * f.dot(d);
        double c = f.dot(f) - radius * radius;

        double discriminant = b * b - 4 * a * c;
        if (discriminant < 0) return false; // 无交点

        // 计算投影参数t
        discriminant = Math.sqrt(discriminant);
        double t1 = (-b - discriminant) / (2 * a);
        double t2 = (-b + discriminant) / (2 * a);

        // 检查是否有交点落在线段范围内 [0, 1]
        if ((t1 >= 0 && t1 <= 1) || (t2 >= 0 && t2 <= 1)) {
            // 计算最近点用于切点效果
            double t = Math.max(0, Math.min(1, -b / (2 * a)));
            if (outClosest != null) {
                outClosest[0] = p1.add(d.mul(t));
            }
            return true;
        }

        return false;
    }

    /**
     * 简化版：仅判断线段与圆是否相交
     */
    public static boolean segmentHitsCircle(Vec2 p1, Vec2 p2, Vec2 c, double r) {
        Vec2 d = p2.sub(p1);
        Vec2 f = p1.sub(c);
        double a = d.dot(d);
        double b = 2 * f.dot(d);
        double cc = f.dot(f) - r * r;
        double disc = b * b - 4 * a * cc;
        if (disc < 0) return false;
        disc = Math.sqrt(disc);
        double t1 = (-b - disc) / (2 * a);
        double t2 = (-b + disc) / (2 * a);
        return (t1 >= 0 && t1 <= 1) || (t2 >= 0 && t2 <= 1);
    }
}

游戏实体系统

import java.util.*;

/**
 * 水果实体
 */
public class Fruit {
    public enum Type { APPLE, BANANA, WATERMELON, BOMB }

    private Vec2 pos;       // 位置
    private Vec2 vel;       // 速度
    private double radius;  // 半径
    private Type type;
    private boolean sliced; // 是否已被切
    private double gravity; // 重力加速度

    public Fruit(double x, double y, double vx, double vy, 
                 double radius, Type type) {
        this.pos = new Vec2(x, y);
        this.vel = new Vec2(vx, vy);
        this.radius = radius;
        this.type = type;
        this.sliced = false;
        this.gravity = 0.5;
    }

    /**
     * 物理更新
     */
    public void update() {
        if (sliced) return;
        pos = pos.add(vel);
        vel = new Vec2(vel.x, vel.y + gravity);
    }

    /**
     * 尝试切割
     * @param swipe 滑动线段
     * @return 是否切中
     */
    public boolean trySlice(Swipe swipe) {
        if (sliced) return false;
        if (GeometryUtils.segmentHitsCircle(swipe.start, swipe.end, pos, radius)) {
            sliced = true;
            return true;
        }
        return false;
    }

    public boolean isOffScreen(double width, double height) {
        return pos.y > height + radius || pos.x < -radius || pos.x > width + radius;
    }

    public boolean isBomb() { return type == Type.BOMB; }
    public boolean isSliced() { return sliced; }
    public Vec2 getPos() { return pos; }
    public double getRadius() { return radius; }
    public Type getType() { return type; }
    public int getScore() {
        return switch(type) {
            case APPLE -> 1;
            case BANANA -> 2;
            case WATERMELON -> 3;
            default -> 0;
        };
    }
}

/**
 * 滑动轨迹
 */
public class Swipe {
    public final Vec2 start;
    public final Vec2 end;
    public final long timestamp;

    public Swipe(Vec2 start, Vec2 end) {
        this.start = start;
        this.end = end;
        this.timestamp = System.currentTimeMillis();
    }
}

贪心连击策略

问题定义

一次滑动可能同时切中多个水果。若一次切中 n 个水果，得分为 n × (n + 1) / 2（连击加成）。给定一组水果和滑动能力，如何规划滑动轨迹使总得分最大化？

贪心策略：最大覆盖直线

由于滑动极快，可假设一次滑动是一条直线段。问题转化为：找一条线段，使其穿过的水果圆数量最多。

/**
 * 贪心连击策略：寻找最优切割直线
 */
public class ComboStrategy {

    /**
     * 贪心算法：枚举所有水果对的连线作为候选切割方向
     * 选择能穿过最多水果（且不切中炸弹）的方向
     */
    public static Swipe findBestSwipe(List<Fruit> fruits, double screenWidth, 
                                       double screenHeight) {
        List<Fruit> aliveFruits = fruits.stream()
            .filter(f -> !f.isSliced() && !f.isOffScreen(screenWidth, screenHeight))
            .toList();

        if (aliveFruits.isEmpty()) return null;

        Swipe bestSwipe = null;
        int bestScore = 0;

        // 策略1：枚举每对水果，以它们连线方向作为候选
        for (int i = 0; i < aliveFruits.size(); i++) {
            for (int j = i + 1; j < aliveFruits.size(); j++) {
                Fruit f1 = aliveFruits.get(i);
                Fruit f2 = aliveFruits.get(j);

                Swipe candidate = createSwipeThrough(f1.getPos(), f2.getPos(), 
                                                      screenWidth, screenHeight);
                int score = evaluateSwipe(candidate, aliveFruits);

                if (score > bestScore) {
                    bestScore = score;
                    bestSwipe = candidate;
                }
            }
        }

        // 策略2：如果无有效连线，切最近的一个水果
        if (bestSwipe == null || bestScore == 0) {
            Fruit nearest = aliveFruits.stream()
                .filter(f -> !f.isBomb())
                .min(Comparator.comparingDouble(f -> f.getPos().y))
                .orElse(null);
            if (nearest != null) {
                bestSwipe = createSwipeThrough(nearest.getPos(), 
                    new Vec2(nearest.getPos().x + 100, nearest.getPos().y),
                    screenWidth, screenHeight);
            }
        }

        return bestSwipe;
    }

    /**
     * 评估一次滑动能获得的得分（考虑炸弹惩罚）
     */
    private static int evaluateSwipe(Swipe swipe, List<Fruit> fruits) {
        if (swipe == null) return 0;

        int fruitCount = 0;
        boolean hitsBomb = false;

        for (Fruit f : fruits) {
            if (GeometryUtils.segmentHitsCircle(swipe.start, swipe.end, 
                                                 f.getPos(), f.getRadius())) {
                if (f.isBomb()) {
                    hitsBomb = true;
                    break;
                }
                fruitCount++;
            }
        }

        if (hitsBomb) return -1000; // 切中炸弹，极大惩罚
        return fruitCount * (fruitCount + 1) / 2; // 连击加成
    }

    /**
     * 构造穿过两点的屏幕宽度滑动线段
     */
    private static Swipe createSwipeThrough(Vec2 p1, Vec2 p2, 
                                             double w, double h) {
        Vec2 dir = p2.sub(p1);
        if (dir.length() < 0.001) return null;
        dir = new Vec2(dir.x / dir.length(), dir.y / dir.length());

        // 将线段延伸到屏幕边界
        Vec2 start = new Vec2(p1.x - dir.x * w, p1.y - dir.y * h);
        Vec2 end = new Vec2(p2.x + dir.x * w, p2.y + dir.y * h);

        return new Swipe(start, end);
    }
}

完整游戏引擎

/**
 * 水果忍者游戏主引擎
 */
public class FruitNinjaGame {
    private static final double SCREEN_W = 800;
    private static final double SCREEN_H = 600;
    private static final int MAX_FRUITS = 8;

    private List<Fruit> fruits;
    private int score;
    private int lives;
    private int combo;
    private Random random;
    private int frameCount;

    public FruitNinjaGame() {
        this.fruits = new ArrayList<>();
        this.score = 0;
        this.lives = 3;
        this.combo = 0;
        this.random = new Random();
        this.frameCount = 0;
    }

    /**
     * 生成新水果
     */
    private void spawnFruit() {
        if (fruits.size() >= MAX_FRUITS) return;

        double x = 100 + random.nextDouble() * 600;
        double y = SCREEN_H + 20;
        double vx = (random.nextDouble() - 0.5) * 8;
        double vy = -(12 + random.nextDouble() * 6); // 向上抛
        double radius = 20 + random.nextDouble() * 15;

        Fruit.Type type;
        double r = random.nextDouble();
        if (r < 0.15) type = Fruit.Type.BOMB;
        else if (r < 0.5) type = Fruit.Type.APPLE;
        else if (r < 0.8) type = Fruit.Type.BANANA;
        else type = Fruit.Type.WATERMELON;

        fruits.add(new Fruit(x, y, vx, vy, radius, type));
    }

    /**
     * AI自动切割
     */
    public void aiSlice() {
        Swipe swipe = ComboStrategy.findBestSwipe(fruits, SCREEN_W, SCREEN_H);
        if (swipe == null) return;

        int slicedCount = 0;
        boolean hitBomb = false;

        for (Fruit f : fruits) {
            if (f.trySlice(swipe)) {
                if (f.isBomb()) {
                    hitBomb = true;
                } else {
                    slicedCount++;
                }
            }
        }

        if (hitBomb) {
            lives--;
            combo = 0;
            System.out.println("BOOM! 切中炸弹，剩余生命: " + lives);
        } else if (slicedCount > 0) {
            combo += slicedCount;
            int points = slicedCount * (slicedCount + 1) / 2;
            score += points;
            System.out.printf("切中 %d 个水果！+%d分 (连击x%d), 总分: %d%n",
                slicedCount, points, combo, score);
        }
    }

    /**
     * 游戏主循环
     */
    public void update() {
        frameCount++;

        // 每30帧生成一波水果
        if (frameCount % 30 == 0) {
            int count = 1 + random.nextInt(3);
            for (int i = 0; i < count; i++) spawnFruit();
        }

        // AI切割
        aiSlice();

        // 物理更新
        for (Fruit f : fruits) f.update();

        // 清理掉出屏幕的水果（未切中的扣生命）
        Iterator<Fruit> it = fruits.iterator();
        while (it.hasNext()) {
            Fruit f = it.next();
            if (f.isOffScreen(SCREEN_W, SCREEN_H)) {
                if (!f.isSliced() && !f.isBomb()) {
                    lives--;
                    combo = 0;
                    System.out.println("水果掉落！剩余生命: " + lives);
                }
                it.remove();
            }
        }
    }

    public boolean isGameOver() { return lives <= 0; }
    public int getScore() { return score; }

    public static void main(String[] args) {
        FruitNinjaGame game = new FruitNinjaGame();

        while (!game.isGameOver() && game.frameCount < 1000) {
            game.update();
        }

        System.out.println("\n游戏结束！最终得分: " + game.getScore());
    }
}

复杂度分析

总结

水果忍者的核心算法将计算几何与贪心策略完美结合：线段-圆碰撞检测用投影法实现 O(1) 判定，贪心连击策略通过枚举水果对连线寻找最大覆盖方向。这种”几何检测 + 组合优化”的架构广泛应用于物理引擎、图形编辑器和自动驾驶感知系统中。