引言
切水果是一款风靡全球的休闲游戏，玩家需要在屏幕上滑动手指，将抛出的水果切成两半。游戏的核心挑战在于准确判断水果的运动轨迹，并在最佳时机完成切割。本文将用Java实现一个切水果模拟系统，重点讲解抛物线运动学建模、线段与圆的碰撞检测，以及基于多目标覆盖的贪心切割策略算法。
核心算法原理
1. 抛物线运动学建模
水果被抛出后，在空中仅受重力作用，其运动轨迹为抛物线。设初始位置为 $(x_0, y_0)$，初始速度为 $(vx_0, vy_0)$，则 $t$ 时刻的位置为：
x(t) = x0 + vx0 * t
y(t) = y0 + vy0 * t - 0.5 * g * t^2
其中 $g$ 为重力加速度。通过求解 $y(t) = 0$ 可以得到水果落地时间。
2. 线段与圆的碰撞检测
切割轨迹可抽象为一条线段，水果可抽象为一个圆。判断线段是否与圆相交的算法：
- 计算圆心到线段所在直线的最短距离
- 如果距离小于圆半径，则存在交点
- 进一步判断垂足是否在线段范围内
3. 贪心多目标切割策略
当屏幕上有多个水果时，AI需要规划一条切割路径，使单次滑动切割尽可能多的水果。贪心策略：
- 枚举所有可能的切割直线（通过每两个水果的圆心确定一条直线）
- 计算每条直线能同时切割的水果数量
- 选择能切割最多水果的路径
- 若存在多条最优路径，优先选择切割高价值水果的路径
Java完整实现
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.util.*;
import java.util.List;
/**
* 切水果模拟 - 抛物线运动检测与贪心切割策略
*
* 核心算法：
* 1. 抛物线运动学建模（重力加速度）
* 2. 线段与圆的碰撞检测
* 3. 贪心多目标切割路径选择
* 4. 粒子爆炸效果系统
*/
public class FruitNinjaGame extends JPanel implements Runnable {
// 物理常量
private static final double GRAVITY = 0.25; // 重力加速度（像素/帧²）
private static final double SPAWN_INTERVAL = 60; // 生成间隔（帧）
private static final int MAX_FRUITS = 8; // 最大同时存在水果数
private static final double SLICE_TOLERANCE = 5.0; // 切割容差（像素）
// 游戏状态
private final List<Fruit> fruits = new ArrayList<>();
private final List<SliceTrail> trails = new ArrayList<>();
private final List<Particle> particles = new ArrayList<>();
private volatile boolean running = true;
private volatile int score = 0;
private volatile int lives = 3;
private volatile boolean gameOver = false;
private int frameCount = 0;
private boolean aiMode = true;
// 切割状态
private Point2D lastMousePos = null;
private Point2D currentMousePos = null;
private List<Point2D> currentTrail = new ArrayList<>();
/**
* 水果类
*/
static class Fruit {
Point2D position;
Point2D velocity;
double radius;
Color color;
int value; // 分值
boolean sliced; // 是否已被切
double rotation; // 旋转角度
double rotationSpeed;
String type; // 水果类型
Fruit(double x, double y, double vx, double vy,
double radius, Color color, int value, String type) {
this.position = new Point2D.Double(x, y);
this.velocity = new Point2D.Double(vx, vy);
this.radius = radius;
this.color = color;
this.value = value;
this.type = type;
this.sliced = false;
this.rotation = 0;
this.rotationSpeed = (Math.random() - 0.5) * 0.15;
}
double getX() { return position.getX(); }
double getY() { return position.getY(); }
double getVX() { return velocity.getX(); }
double getVY() { return velocity.getY(); }
}
/**
* 切割轨迹段
*/
static class SliceTrail {
Point2D start, end;
int life;
SliceTrail(Point2D s, Point2D e) {
this.start = s;
this.end = e;
this.life = 10;
}
}
/**
* 粒子效果（果汁飞溅）
*/
static class Particle {
Point2D position;
Point2D velocity;
Color color;
int life;
int maxLife;
double size;
Particle(double x, double y, double vx, double vy,
Color color, int life, double size) {
this.position = new Point2D.Double(x, y);
this.velocity = new Point2D.Double(vx, vy);
this.color = color;
this.life = life;
this.maxLife = life;
this.size = size;
}
}
/**
* 贪心切割路径候选
*/
static class SliceCandidate {
Point2D start, end;
List<Fruit> targets;
double totalValue;
double efficiency; // 价值/路径长度
SliceCandidate(Point2D s, Point2D e, List<Fruit> t, double v, double eff) {
this.start = s;
this.end = e;
this.targets = t;
this.totalValue = v;
this.efficiency = eff;
}
}
public FruitNinjaGame() {
setPreferredSize(new Dimension(800, 600));
setBackground(new Color(20, 20, 40));
// 鼠标/触摸监听
addMouseListener(new MouseAdapter() {
@Override
public void mousePressed(MouseEvent e) {
if (!aiMode && !gameOver) {
lastMousePos = new Point2D.Double(e.getX(), e.getY());
currentTrail.clear();
currentTrail.add(lastMousePos);
}
}
@Override
public void mouseReleased(MouseEvent e) {
if (!aiMode && lastMousePos != null) {
performSlice();
lastMousePos = null;
currentTrail.clear();
}
}
});
addMouseMotionListener(new MouseMotionAdapter() {
@Override
public void mouseDragged(MouseEvent e) {
if (!aiMode && lastMousePos != null) {
currentMousePos = new Point2D.Double(e.getX(), e.getY());
currentTrail.add(currentMousePos);
if (currentTrail.size() > 2) {
performSlice();
}
}
}
});
}
/**
* 生成新水果
*
* 算法：
* 1. 从屏幕底部两侧随机生成
* 2. 初速度向上偏中间方向
* 3. 随机选择水果类型和大小
*/
private void spawnFruit() {
if (fruits.size() >= MAX_FRUITS) return;
String[] types = {"苹果", "香蕉", "西瓜", "橙子", "炸弹"};
Color[] colors = {Color.RED, Color.YELLOW, Color.GREEN, Color.ORANGE, Color.BLACK};
int[] values = {10, 15, 20, 12, -50};
double[] radii = {25, 30, 40, 22, 28};
int idx = (int) (Math.random() * types.length);
// 从底部两侧生成，向中间抛出
double startX = Math.random() < 0.5 ? 50 + Math.random() * 100
: getWidth() - 150 + Math.random() * 100;
double startY = getHeight() + 20;
// 初速度：向上且偏向屏幕中心
double targetX = getWidth() / 2 + (Math.random() - 0.5) * 200;
double vx = (targetX - startX) / 80;
double vy = -(8 + Math.random() * 5); // 向上速度
fruits.add(new Fruit(startX, startY, vx, vy,
radii[idx], colors[idx], values[idx], types[idx]));
}
/**
* 更新物理状态
*
* 每帧执行：
* 1. 应用重力
* 2. 更新位置
* 3. 更新旋转
* 4. 移除掉出屏幕的水果
*/
private void updatePhysics() {
Iterator<Fruit> it = fruits.iterator();
while (it.hasNext()) {
Fruit fruit = it.next();
// 应用重力
double newVY = fruit.getVY() + GRAVITY;
double newVX = fruit.getVX() * 0.999; // 微小空气阻力
fruit.velocity.setLocation(newVX, newVY);
// 更新位置
double newX = fruit.getX() + newVX;
double newY = fruit.getY() + newVY;
fruit.position.setLocation(newX, newY);
// 更新旋转
fruit.rotation += fruit.rotationSpeed;
// 移除掉出屏幕且未切的水果（扣生命）
if (fruit.getY() > getHeight() + 50 && !fruit.sliced) {
if (!fruit.type.equals("炸弹")) {
lives--;
if (lives <= 0) gameOver = true;
}
it.remove();
}
}
// 更新粒子
Iterator<Particle> pit = particles.iterator();
while (pit.hasNext()) {
Particle p = pit.next();
p.velocity.setLocation(p.velocity.getX(), p.velocity.getY() + GRAVITY * 0.5);
p.position.setLocation(p.getX() + p.velocity.getX(),
p.getY() + p.velocity.getY());
p.life--;
if (p.life <= 0) pit.remove();
}
// 更新轨迹
trails.removeIf(t -> --t.life <= 0);
}
/**
* 执行切割检测
*
* 算法步骤：
* 1. 取切割轨迹的最后两个点形成线段
* 2. 遍历所有未切水果
* 3. 计算圆心到线段的最短距离
* 4. 若距离小于半径+容差，判定为切割成功
*/
private void performSlice() {
if (currentTrail.size() < 2) return;
Point2D p1 = currentTrail.get(currentTrail.size() - 2);
Point2D p2 = currentTrail.get(currentTrail.size() - 1);
// 添加视觉轨迹
trails.add(new SliceTrail(p1, p2));
for (Fruit fruit : fruits) {
if (fruit.sliced) continue;
// 线段与圆的碰撞检测
if (lineIntersectsCircle(p1, p2, fruit.position, fruit.radius + SLICE_TOLERANCE)) {
fruit.sliced = true;
if (fruit.type.equals("炸弹")) {
// 炸弹：扣除生命并产生爆炸效果
lives--;
if (lives <= 0) gameOver = true;
createExplosion(fruit.getX(), fruit.getY(), Color.RED);
} else {
// 正常水果：加分并产生果汁效果
score += fruit.value;
createJuiceEffect(fruit.getX(), fruit.getY(), fruit.color);
}
// 水果被切后分成两半飞出
fruit.velocity.setLocation(
fruit.getVX() + (Math.random() - 0.5) * 3,
fruit.getVY() - 2
);
}
}
}
/**
* 线段与圆的碰撞检测算法
*
* 数学推导：
* 1. 线段参数方程：P = P1 + t*(P2-P1), t∈[0,1]
* 2. 圆心到线段上最近点的参数：t = ((C-P1)·(P2-P1)) / |P2-P1|²
* 3. 将t限制在[0,1]范围内
* 4. 计算最近点到圆心的距离
*
* @param p1 线段起点
* @param p2 线段终点
* @param center 圆心
* @param radius 圆半径
* @return 是否相交
*/
private boolean lineIntersectsCircle(Point2D p1, Point2D p2,
Point2D center, double radius) {
double dx = p2.getX() - p1.getX();
double dy = p2.getY() - p1.getY();
double lenSq = dx * dx + dy * dy;
if (lenSq < 0.0001) {
// 线段近似一个点
return center.distance(p1) <= radius;
}
// 计算投影参数t
double t = ((center.getX() - p1.getX()) * dx +
(center.getY() - p1.getY()) * dy) / lenSq;
// 限制t在[0,1]内
t = Math.max(0, Math.min(1, t));
// 最近点坐标
double closestX = p1.getX() + t * dx;
double closestY = p1.getY() + t * dy;
// 距离
double distSq = (center.getX() - closestX) * (center.getX() - closestX) +
(center.getY() - closestY) * (center.getY() - closestY);
return distSq <= radius * radius;
}
/**
* AI贪心切割策略
*
* 核心算法：
* 1. 收集所有未切水果的位置
* 2. 枚举通过每两个水果圆心的直线作为候选切割路径
* 3. 对每条候选路径，计算能同时切割的所有水果
* 4. 按切割数量优先、总价值次之排序
* 5. 选择最优路径执行切割
*/
private void aiSliceDecision() {
if (gameOver) return;
List<Fruit> targets = new ArrayList<>();
for (Fruit f : fruits) {
if (!f.sliced && !f.type.equals("炸弹")) {
targets.add(f);
}
}
if (targets.isEmpty()) return;
List<SliceCandidate> candidates = new ArrayList<>();
// 策略1：尝试通过两个水果的直线切割
for (int i = 0; i < targets.size(); i++) {
for (int j = i + 1; j < targets.size(); j++) {
Fruit f1 = targets.get(i);
Fruit f2 = targets.get(j);
// 计算通过两圆心的直线，向外延伸
double dx = f2.getX() - f1.getX();
double dy = f2.getY() - f1.getY();
double dist = Math.hypot(dx, dy);
if (dist < 0.001) continue;
double nx = dx / dist;
double ny = dy / dist;
// 向外延伸形成切割线段
double extend = 100;
Point2D start = new Point2D.Double(
f1.getX() - nx * extend, f1.getY() - ny * extend);
Point2D end = new Point2D.Double(
f2.getX() + nx * extend, f2.getY() + ny * extend);
// 评估这条路径能切多少水果
evaluateCandidate(start, end, candidates);
}
}
// 策略2：单水果垂直切割（当没有好的多目标路径时）
for (Fruit f : targets) {
Point2D start = new Point2D.Double(f.getX() - 100, f.getY());
Point2D end = new Point2D.Double(f.getX() + 100, f.getY());
evaluateCandidate(start, end, candidates);
start = new Point2D.Double(f.getX(), f.getY() - 100);
end = new Point2D.Double(f.getX(), f.getY() + 100);
evaluateCandidate(start, end, candidates);
}
if (candidates.isEmpty()) return;
// 贪心选择：优先切最多水果，其次总价值最高
candidates.sort((a, b) -> {
if (b.targets.size() != a.targets.size()) {
return b.targets.size() - a.targets.size();
}
return Double.compare(b.totalValue, a.totalValue);
});
SliceCandidate best = candidates.get(0);
if (best.targets.size() >= 2 ||
(best.targets.size() == 1 && best.targets.get(0).getY() < getHeight() * 0.7)) {
// 执行切割：模拟鼠标轨迹
currentTrail.clear();
currentTrail.add(best.start);
currentTrail.add(best.end);
performSlice();
}
}
/**
* 评估候选切割路径
*/
private void evaluateCandidate(Point2D start, Point2D end,
List<SliceCandidate> candidates) {
List<Fruit> hit = new ArrayList<>();
double totalValue = 0;
for (Fruit f : fruits) {
if (f.sliced || f.type.equals("炸弹")) continue;
if (lineIntersectsCircle(start, end, f.position, f.radius)) {
hit.add(f);
totalValue += f.value;
}
}
if (!hit.isEmpty()) {
double dist = start.distance(end);
double efficiency = totalValue / Math.max(1, dist);
candidates.add(new SliceCandidate(start, end, hit, totalValue, efficiency));
}
}
/**
* 创建果汁粒子效果
*/
private void createJuiceEffect(double x, double y, Color color) {
int count = 15 + (int) (Math.random() * 10);
for (int i = 0; i < count; i++) {
double angle = Math.random() * Math.PI * 2;
double speed = 1 + Math.random() * 4;
double vx = Math.cos(angle) * speed;
double vy = Math.sin(angle) * speed - 3;
int life = 20 + (int) (Math.random() * 20);
particles.add(new Particle(x, y, vx, vy, color, life, 3 + Math.random() * 4));
}
}
/**
* 创建爆炸效果
*/
private void createExplosion(double x, double y, Color color) {
for (int i = 0; i < 30; i++) {
double angle = Math.random() * Math.PI * 2;
double speed = 2 + Math.random() * 6;
double vx = Math.cos(angle) * speed;
double vy = Math.sin(angle) * speed;
particles.add(new Particle(x, y, vx, vy, color, 40, 5 + Math.random() * 6));
}
}
/**
* 游戏主循环
*/
@Override
public void run() {
while (running) {
frameCount++;
// 生成新水果
if (frameCount % (int) SPAWN_INTERVAL == 0 && !gameOver) {
spawnFruit();
}
// AI决策
if (aiMode && frameCount % 5 == 0 && !gameOver) {
aiSliceDecision();
}
// 更新物理
updatePhysics();
// 重绘
repaint();
// 帧率控制
try {
Thread.sleep(16);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
break;
}
}
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2d = (Graphics2D) g;
g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
// 绘制背景网格（装饰）
g2d.setColor(new Color(30, 30, 50));
for (int i = 0; i < getWidth(); i += 50) {
g2d.drawLine(i, 0, i, getHeight());
}
for (int i = 0; i < getHeight(); i += 50) {
g2d.drawLine(0, i, getWidth(), i);
}
// 绘制切割轨迹
g2d.setStroke(new BasicStroke(3, BasicStroke.CAP_ROUND,
BasicStroke.JOIN_ROUND));
for (SliceTrail trail : trails) {
float alpha = trail.life / 10.0f;
g2d.setColor(new Color(0.8f, 0.9f, 1.0f, alpha));
g2d.drawLine((int) trail.start.getX(), (int) trail.start.getY(),
(int) trail.end.getX(), (int) trail.end.getY());
}
// 绘制当前切割轨迹
if (currentTrail.size() >= 2) {
g2d.setColor(new Color(150, 220, 255));
g2d.setStroke(new BasicStroke(4));
for (int i = 1; i < currentTrail.size(); i++) {
Point2D a = currentTrail.get(i - 1);
Point2D b = currentTrail.get(i);
g2d.drawLine((int) a.getX(), (int) a.getY(),
(int) b.getX(), (int) b.getY());
}
}
// 绘制水果
for (Fruit fruit : fruits) {
if (fruit.sliced && fruit.getY() > getHeight() + 100) continue;
Graphics2D fruitG = (Graphics2D) g2d.create();
fruitG.translate(fruit.getX(), fruit.getY());
fruitG.rotate(fruit.rotation);
if (fruit.sliced) {
// 被切后的两半效果
fruitG.setColor(fruit.color.darker());
fruitG.fillArc((int) (-fruit.radius), (int) (-fruit.radius),
(int) (fruit.radius * 2), (int) (fruit.radius * 2),
0, 180);
fruitG.setColor(Color.WHITE);
fruitG.fillArc((int) (-fruit.radius), (int) (-fruit.radius),
(int) (fruit.radius * 2), (int) (fruit.radius * 2),
180, 180);
} else {
// 完整水果
fruitG.setColor(fruit.color);
fruitG.fillOval((int) (-fruit.radius), (int) (-fruit.radius),
(int) (fruit.radius * 2), (int) (fruit.radius * 2));
// 高光
fruitG.setColor(fruit.color.brighter());
fruitG.fillOval((int) (-fruit.radius * 0.4),
(int) (-fruit.radius * 0.6),
(int) (fruit.radius * 0.5),
(int) (fruit.radius * 0.4));
}
// 炸弹绘制特殊标记
if (fruit.type.equals("炸弹") && !fruit.sliced) {
fruitG.setColor(Color.YELLOW);
fruitG.setFont(new Font("Arial", Font.BOLD, 16));
fruitG.drawString("X", -6, 6);
}
fruitG.dispose();
}
// 绘制粒子
for (Particle p : particles) {
float alpha = p.life / (float) p.maxLife;
g2d.setColor(new Color(
p.color.getRed() / 255.0f,
p.color.getGreen() / 255.0f,
p.color.getBlue() / 255.0f,
alpha));
int s = (int) (p.size * alpha);
g2d.fillOval((int) (p.getX() - s / 2), (int) (p.getY() - s / 2), s, s);
}
// 绘制UI
g2d.setColor(Color.WHITE);
g2d.setFont(new Font("微软雅黑", Font.BOLD, 24));
g2d.drawString("分数: " + score, 20, 40);
// 生命数
g2d.setColor(Color.RED);
for (int i = 0; i < lives; i++) {
g2d.fillOval(getWidth() - 40 - i * 35, 20, 25, 25);
}
// AI模式标识
if (aiMode) {
g2d.setColor(Color.CYAN);
g2d.drawString("AI 模式", 20, 70);
}
// 游戏结束
if (gameOver) {
g2d.setColor(new Color(0, 0, 0, 180));
g2d.fillRect(0, 0, getWidth(), getHeight());
g2d.setColor(Color.WHITE);
g2d.setFont(new Font("微软雅黑", Font.BOLD, 48));
String msg = "游戏结束 - 得分: " + score;
FontMetrics fm = g2d.getFontMetrics();
g2d.drawString(msg, (getWidth() - fm.stringWidth(msg)) / 2,
getHeight() / 2);
}
}
public static void main(String[] args) {
SwingUtilities.invokeLater(() -> {
JFrame frame = new JFrame("切水果 - 抛物线运动检测与贪心切割策略");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
FruitNinjaGame game = new FruitNinjaGame();
frame.add(game);
frame.pack();
frame.setLocationRelativeTo(null);
frame.setVisible(true);
new Thread(game).start();
});
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 抛物线位置更新 | O(N) | O(1) | N为水果数 |
| 切割检测 | O(N) | O(1) | 每条轨迹检测一次 |
| 线段与圆碰撞 | O(1) | O(1) | 纯数学计算 |
| AI贪心路径枚举 | O(N³) | O(N²) | 枚举所有两两组合 |
| 粒子更新 | O(P) | O(1) | P为粒子数 |
核心算法优化点
- 投影法碰撞检测：将圆心投影到线段上，避免了复杂的联立方程求解，仅需O(1)计算。
- 贪心多目标策略：通过枚举所有两水果连线，优先选择切割数量最多的路径，提高AI得分效率。
- 分层粒子系统：果汁飞溅和爆炸效果使用独立的粒子池管理，避免频繁创建销毁对象。
- 轨迹插值：切割轨迹使用连续线段而非离散点，提升碰撞检测精度。
扩展思考
- 贝塞尔曲线切割：将直线切割扩展为曲线切割，通过二次贝塞尔曲线模拟挥刀弧度，增加游戏真实感。
- 预测切割：根据水果抛物线轨迹，预测未来位置并提前规划切割路径，实现”预判切”。
- 神经网络策略：使用强化学习训练AI，让模型自主学习何时切、如何避开炸弹的最优策略。
总结
本文通过Java实现了一个完整的切水果游戏模拟，涵盖抛物线运动学建模、线段与圆碰撞检测、贪心多目标切割策略三大核心算法。该实现不仅展示了物理模拟与几何碰撞检测的结合，也演示了如何用贪心思想解决实时多目标决策问题。
