每日算法 — 使用java实现切水果：抛物线轨迹检测与最优切割策略

切水果是一款经典的休闲游戏，玩家需要在屏幕上滑动手指，将不断抛出的水果切成两半。看似简单的操作背后，蕴含着丰富的物理与算法知识。本文将从算法角度深入剖析切水果游戏的核心机制，用Java实现抛物线运动模拟、碰撞检测与最优切割路径计算。

一、游戏机制与物理建模

在切水果游戏中，水果从屏幕底部以随机角度和速度抛出，沿抛物线轨迹飞行。玩家划出的切割线需要与水果的圆形碰撞盒相交，才能完成切割判定。

1.1 抛物线运动模型

水果的运动可简化为二维平面上的抛体运动，忽略空气阻力时，位置随时间变化的公式为：

• 水平位移：x = x0 + vx * t
• 垂直位移：y = y0 + vy * t - 0.5 * g * t^2

其中 vx = v * cos(θ)，vy = v * sin(θ)，g 为重力加速度。

1.2 圆形碰撞盒

每个水果用一个圆形表示，包含圆心坐标 (cx, cy) 和半径 r。切割线可用两点式直线方程表示。切割判定转化为判断直线与圆是否相交的问题。

二、核心算法设计

2.1 直线与圆的相交检测

给定直线经过点 p1(x1,y1) 和 p2(x2,y2)，圆的圆心 c(cx,cy)，半径 r。相交判定步骤如下：

1. 计算圆心到直线的垂直距离 d
2. 若 d <= r，则直线与圆相交（相切或相割）

点到直线的距离公式：

d = |(y2-y1)*cx - (x2-x1)*cy + x2*y1 - y2*x1| / sqrt((y2-y1)^2 + (x2-x1)^2)

2.2 最优切割策略

当多个水果同时出现在屏幕上时，一次切割能切到的水果越多，得分越高。最优切割问题可抽象为：寻找一条直线，使其与尽可能多的圆相交。

该问题是NP-hard的几何覆盖问题。本文采用贪心启发式策略：

1. 枚举所有水果圆两两之间的公切线方向
2. 对每个方向，计算该直线能切割的水果数量
3. 选择切割数量最多的方向作为最优切割线

三、Java完整实现

import java.util.ArrayList;
import java.util.List;

/**
 * 切水果游戏核心算法实现
 * 包含抛物线运动模拟、碰撞检测与最优切割策略
 */
public class FruitNinja {

    // 重力加速度 (像素/秒^2)
    private static final double GRAVITY = 500.0;

    /**
     * 水果类，表示一个圆形碰撞盒
     */
    static class Fruit {
        double x, y;      // 圆心坐标
        double vx, vy;    // 速度分量
        double radius;    // 半径
        boolean sliced;   // 是否已被切

        Fruit(double x, double y, double vx, double vy, double radius) {
            this.x = x;
            this.y = y;
            this.vx = vx;
            this.vy = vy;
            this.radius = radius;
            this.sliced = false;
        }

        /**
         * 更新水果位置，模拟抛物线运动
         * @param dt 时间步长（秒）
         */
        void update(double dt) {
            x += vx * dt;
            y += vy * dt;
            vy -= GRAVITY * dt;  // 重力影响垂直速度
        }
    }

    /**
     * 切割线，由起点和终点确定
     */
    static class CutLine {
        double x1, y1, x2, y2;

        CutLine(double x1, double y1, double x2, double y2) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }
    }

    /**
     * 计算点到直线的距离
     * 使用叉积公式：d = |cross(p2-p1, p1-p0)| / |p2-p1|
     */
    static double pointToLineDistance(double px, double py,
                                       double x1, double y1, double x2, double y2) {
        double cross = Math.abs((x2 - x1) * (y1 - py) - (x1 - px) * (y2 - y1));
        double lineLen = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
        if (lineLen < 1e-9) return Double.MAX_VALUE;
        return cross / lineLen;
    }

    /**
     * 检测切割线是否与水果相交
     */
    static boolean intersects(CutLine line, Fruit fruit) {
        double dist = pointToLineDistance(fruit.x, fruit.y,
                                          line.x1, line.y1, line.x2, line.y2);
        return dist <= fruit.radius;
    }

    /**
     * 贪心最优切割策略
     * 枚举候选切割方向，选择能切割最多水果的直线
     */
    static CutLine findOptimalCut(List<Fruit> fruits, double screenWidth, double screenHeight) {
        int n = fruits.size();
        if (n == 0) return null;

        CutLine bestCut = null;
        int maxSliced = 0;

        // 候选方向1：穿过每两个水果圆心的方向
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Fruit a = fruits.get(i);
                Fruit b = fruits.get(j);
                double dx = b.x - a.x;
                double dy = b.y - a.y;

                // 构建穿过两圆心并延伸至屏幕边界的直线
                double len = Math.sqrt(dx * dx + dy * dy);
                if (len < 1e-9) continue;

                double ux = dx / len;
                double uy = dy / len;

                // 向两端延伸
                double sx = a.x - ux * screenWidth;
                double sy = a.y - uy * screenWidth;
                double ex = b.x + ux * screenWidth;
                double ey = b.y + uy * screenWidth;

                CutLine candidate = new CutLine(sx, sy, ex, ey);
                int count = countIntersections(candidate, fruits);
                if (count > maxSliced) {
                    maxSliced = count;
                    bestCut = candidate;
                }
            }
        }

        // 候选方向2：水平线和垂直线
        double[][] directions = {{1, 0}, {0, 1}, {1, 1}, {1, -1}};
        for (double[] dir : directions) {
            double ux = dir[0] / Math.sqrt(dir[0]*dir[0] + dir[1]*dir[1]);
            double uy = dir[1] / Math.sqrt(dir[0]*dir[0] + dir[1]*dir[1]);

            for (Fruit f : fruits) {
                double sx = f.x - ux * screenWidth;
                double sy = f.y - uy * screenWidth;
                double ex = f.x + ux * screenWidth;
                double ey = f.y + uy * screenWidth;

                CutLine candidate = new CutLine(sx, sy, ex, ey);
                int count = countIntersections(candidate, fruits);
                if (count > maxSliced) {
                    maxSliced = count;
                    bestCut = candidate;
                }
            }
        }

        return bestCut;
    }

    /**
     * 计算一条切割线能切到的水果数量
     */
    static int countIntersections(CutLine line, List<Fruit> fruits) {
        int count = 0;
        for (Fruit f : fruits) {
            if (!f.sliced && intersects(line, f)) {
                count++;
            }
        }
        return count;
    }

    /**
     * 执行切割，标记被切中的水果
     */
    static int executeCut(CutLine line, List<Fruit> fruits) {
        int slicedCount = 0;
        for (Fruit f : fruits) {
            if (!f.sliced && intersects(line, f)) {
                f.sliced = true;
                slicedCount++;
            }
        }
        return slicedCount;
    }

    /**
     * 生成随机抛出的水果
     */
    static List<Fruit> generateFruits(int count, double screenWidth, double screenHeight) {
        List<Fruit> fruits = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            double x = screenWidth * 0.2 + Math.random() * screenWidth * 0.6;
            double y = screenHeight;
            double speed = 300 + Math.random() * 200;
            double angle = Math.PI / 4 + Math.random() * Math.PI / 4; // 45°~90°
            double vx = speed * Math.cos(angle) * (Math.random() > 0.5 ? 1 : -1);
            double vy = speed * Math.sin(angle);
            double radius = 20 + Math.random() * 15;
            fruits.add(new Fruit(x, y, vx, vy, radius));
        }
        return fruits;
    }

    public static void main(String[] args) {
        double screenWidth = 800;
        double screenHeight = 600;

        // 生成10个随机水果
        List<Fruit> fruits = generateFruits(10, screenWidth, screenHeight);

        System.out.println("=== 切水果游戏模拟 ===");
        System.out.println("初始水果数量: " + fruits.size());

        // 模拟3轮切割
        for (int round = 1; round <= 3; round++) {
            // 更新水果位置（模拟0.5秒飞行）
            for (Fruit f : fruits) {
                if (!f.sliced) f.update(0.5);
            }

            // 寻找最优切割线
            CutLine bestCut = findOptimalCut(fruits, screenWidth, screenHeight);
            if (bestCut == null) break;

            int sliced = executeCut(bestCut, fruits);
            System.out.println("第" + round + "轮切割: 切中 " + sliced + " 个水果");
        }

        long remaining = fruits.stream().filter(f -> !f.sliced).count();
        System.out.println("剩余未切水果: " + remaining);
    }
}

四、算法复杂度分析

实际游戏中，水果数量 n 通常不超过20，O(n³) 的精确搜索完全可以接受。若追求更高性能，可将候选方向限制为固定数量，降为 O(n) 级别。

五、扩展与优化方向

1. 多刀连切：记录切割轨迹的多个线段，支持连续滑动切割
2. 炸弹检测：将炸弹建模为负分圆形区域，切割时排除含炸弹的最优解
3. 预测拦截：基于当前速度和加速度，预测水果未来位置，提前规划切割时机
4. 视觉反馈：通过向量反射计算水果被切后的两半飞行方向

六、总结

本文从物理建模出发，将切水果游戏抽象为抛体运动与几何相交问题。核心算法包括：

• 抛物线运动方程 模拟水果飞行轨迹
• 点到直线距离公式 实现精确的圆形碰撞检测
• 贪心启发式搜索 在多项式时间内找到近似最优切割线

通过Java完整实现，读者可以深入理解休闲游戏背后的算法原理，并将这些技术迁移到其他需要物理模拟与几何计算的场景。