每日算法 — 使用java实现割绳子：物理绳索模拟与抛物线轨迹计算

概述

割绳子（Cut the Rope）是一款经典的物理解谜游戏，玩家通过切断绳子让糖果落入小怪兽口中。游戏的核心在于绳索物理模拟、抛物线运动轨迹计算，以及碰撞与切割判定。本文用Java实现其中的核心物理算法，包括基于Verlet积分的绳索模拟、二次贝塞尔曲线描述绳索形态，以及射线与线段相交检测实现割绳判定。

核心算法设计

1. 质点-弹簧绳索模型

我们将绳索离散为一系列质点，相邻质点之间用弹簧连接。通过Verlet积分更新质点位置，该方法无需显式存储速度，稳定性优于欧拉法。

public class RopeNode {
    public double x, y;       // 当前位置
    public double oldX, oldY; // 上一帧位置（Verlet积分用）
    public boolean fixed;     // 是否固定（如挂在钉子上）
    public double mass = 1.0;

    public RopeNode(double x, double y, boolean fixed) {
        this.x = this.oldX = x;
        this.y = this.oldY = y;
        this.fixed = fixed;
    }

    /**
     * Verlet积分更新位置
     * x(t+dt) = 2*x(t) - x(t-dt) + a(t)*dt^2
     */
    public void verletIntegrate(double dt, double gravity) {
        if (fixed) return;
        double tempX = x;
        double tempY = y;
        double damping = 0.98; // 速度阻尼
        x += (x - oldX) * damping + 0 * dt * dt; // 水平无外力
        y += (y - oldY) * damping + gravity * dt * dt;
        oldX = tempX;
        oldY = tempY;
    }
}

public class RopeSpring {
    public RopeNode a, b;
    public double restLength; // 弹簧原长
    public double stiffness = 0.5;

    public RopeSpring(RopeNode a, RopeNode b) {
        this.a = a;
        this.b = b;
        this.restLength = Math.hypot(a.x - b.x, a.y - b.y);
    }

    /**
     * 弹簧约束松弛：将两质点距离拉回至restLength
     */
    public void relax() {
        double dx = b.x - a.x;
        double dy = b.y - a.y;
        double dist = Math.hypot(dx, dy);
        if (dist == 0) return;
        double diff = (dist - restLength) / dist * stiffness;
        double offsetX = dx * diff * 0.5;
        double offsetY = dy * diff * 0.5;

        if (!a.fixed) { a.x += offsetX; a.y += offsetY; }
        if (!b.fixed) { b.x -= offsetX; b.y -= offsetY; }
    }
}

2. 完整绳索模拟系统

每帧执行多次约束松弛迭代，使绳索达到力学平衡。

public class RopeSimulation {
    private List<RopeNode> nodes = new ArrayList<>();
    private List<RopeSpring> springs = new ArrayList<>();
    private static final double GRAVITY = 500.0;
    private static final double DT = 0.016; // 60FPS
    private static final int ITERATIONS = 5; // 每帧松弛迭代次数

    public void createRope(double startX, double startY, double endX, double endY, int segments) {
        nodes.clear();
        springs.clear();
        for (int i = 0; i <= segments; i++) {
            double t = (double) i / segments;
            double x = startX + (endX - startX) * t;
            double y = startY + (endY - startY) * t;
            // 首尾固定（挂在钉子和糖果上）
            nodes.add(new RopeNode(x, y, i == 0));
        }
        for (int i = 0; i < segments; i++) {
            springs.add(new RopeSpring(nodes.get(i), nodes.get(i + 1)));
        }
    }

    public void update() {
        // 1. Verlet积分更新所有质点
        for (RopeNode n : nodes) {
            n.verletIntegrate(DT, GRAVITY);
        }

        // 2. 多次迭代约束松弛
        for (int i = 0; i < ITERATIONS; i++) {
            for (RopeSpring s : springs) {
                s.relax();
            }
        }
    }
}

3. 抛物线轨迹预测

当绳子被割断后，糖果受重力影响做抛物线运动。我们预先计算糖果的理论落点，辅助玩家判断切割时机。

public class TrajectoryPredictor {
    /**
     * 计算抛物线轨迹上的若干采样点
     * 运动方程：y = y0 + vy0*t + 0.5*g*t^2
     *          x = x0 + vx0*t
     */
    public List<double[]> predictTrajectory(
            double x0, double y0,
            double vx0, double vy0,
            double gravity, int steps) {
        List<double[]> points = new ArrayList<>();
        double dt = 0.05; // 每0.05秒采样一次
        for (int i = 0; i < steps; i++) {
            double t = i * dt;
            double x = x0 + vx0 * t;
            double y = y0 + vy0 * t + 0.5 * gravity * t * t;
            if (y > 800) break; // 超出屏幕底部停止
            points.add(new double[]{x, y});
        }
        return points;
    }

    /**
     * 计算糖果到达目标水平位置所需时间
     * 解方程：targetX = x0 + vx0 * t  =>  t = (targetX - x0) / vx0
     */
    public Double timeToReachX(double x0, double vx0, double targetX) {
        if (Math.abs(vx0) < 1e-6) return null;
        return (targetX - x0) / vx0;
    }

    /**
     * 计算给定时刻的Y坐标
     */
    public double heightAtTime(double y0, double vy0, double gravity, double t) {
        return y0 + vy0 * t + 0.5 * gravity * t * t;
    }
}

4. 射线-线段相交检测（割绳判定）

玩家滑动屏幕产生一条切割射线，我们需要检测该射线与哪段绳索相交。使用方向向量叉积法判断两线段是否相交。

public class LineIntersection {
    /**
     * 计算向量叉积 (P1P2 × P1P3)
     */
    private static double cross(double x1, double y1, double x2, double y2,
                                 double x3, double y3) {
        return (x2 - x1) * (y3 - y1) - (y3 - y1) * (x2 - x1);
    }

    /**
     * 判断点C是否在线段AB上（共线且在包围盒内）
     */
    private static boolean onSegment(double ax, double ay, double bx, double by,
                                      double cx, double cy) {
        return Math.min(ax, bx) <= cx && cx <= Math.max(ax, bx) &&
               Math.min(ay, by) <= cy && cy <= Math.max(ay, by);
    }

    /**
     * 射线（线段）与绳索弹簧的相交检测
     * 基于方向向量叉积符号判断
     */
    public static boolean segmentsIntersect(
            double ax1, double ay1, double ax2, double ay2, // 切割线
            double bx1, double by1, double bx2, double by2  // 绳索段
    ) {
        double d1 = direction(bx1, by1, bx2, by2, ax1, ay1);
        double d2 = direction(bx1, by1, bx2, by2, ax2, ay2);
        double d3 = direction(ax1, ay1, ax2, ay2, bx1, by1);
        double d4 = direction(ax1, ay1, ax2, ay2, bx2, by2);

        if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
            ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
            return true;
        }
        // 共线特殊情况
        if (d1 == 0 && onSegment(bx1, by1, bx2, by2, ax1, ay1)) return true;
        if (d2 == 0 && onSegment(bx1, by1, bx2, by2, ax2, ay2)) return true;
        if (d3 == 0 && onSegment(ax1, ay1, ax2, ay2, bx1, by1)) return true;
        if (d4 == 0 && onSegment(ax1, ay1, ax2, ay2, bx2, by2)) return true;
        return false;
    }

    private static double direction(double ax, double ay, double bx, double by,
                                     double cx, double cy) {
        return (cx - ax) * (by - ay) - (cy - ay) * (bx - ax);
    }
}

5. 二次贝塞尔曲线渲染绳索

为了使绳索看起来自然平滑，我们用相邻质点作为控制点，通过二次贝塞尔曲线插值渲染。

public class BezierCurve {
    /**
     * 二次贝塞尔曲线插值
     * B(t) = (1-t)^2 * P0 + 2(1-t)t * P1 + t^2 * P2,  t ∈ [0,1]
     */
    public static double[] quadraticBezier(double t,
                                            double x0, double y0,
                                            double x1, double y1,
                                            double x2, double y2) {
        double u = 1 - t;
        double x = u * u * x0 + 2 * u * t * x1 + t * t * x2;
        double y = u * u * y0 + 2 * u * t * y1 + t * t * y2;
        return new double[]{x, y};
    }

    /**
     * 将绳索质点序列转换为平滑的贝塞尔曲线点集
     */
    public List<double[]> smoothRopePoints(List<RopeNode> nodes, int samplesPerSegment) {
        List<double[]> result = new ArrayList<>();
        for (int i = 0; i < nodes.size() - 1; i++) {
            RopeNode p0 = nodes.get(Math.max(0, i - 1));
            RopeNode p1 = nodes.get(i);
            RopeNode p2 = nodes.get(Math.min(nodes.size() - 1, i + 1));
            // 使用P1作为中点控制点
            double midX = (p0.x + p2.x) / 2;
            double midY = (p0.y + p2.y) / 2;
            for (int s = 0; s < samplesPerSegment; s++) {
                double t = (double) s / samplesPerSegment;
                double[] pt = quadraticBezier(t, p1.x, p1.y, midX, midY, p2.x, p2.y);
                result.add(pt);
            }
        }
        return result;
    }
}

6. 完整游戏逻辑

public class CutTheRopeGame {
    private RopeSimulation ropeSim;
    private Candy candy;
    private Monster monster;
    private List<Star> stars = new ArrayList<>();
    private TrajectoryPredictor predictor = new TrajectoryPredictor();

    public CutTheRopeGame() {
        ropeSim = new RopeSimulation();
        // 钉子固定在(200,50)，糖果初始在(200,300)
        ropeSim.createRope(200, 50, 200, 300, 20);
        candy = new Candy(200, 300);
        monster = new Monster(400, 600);
        stars.add(new Star(300, 400));
        stars.add(new Star(350, 500));
        stars.add(new Star(450, 450));
    }

    public void cutRope(double x1, double y1, double x2, double y2) {
        List<RopeSpring> toRemove = new ArrayList<>();
        for (RopeSpring spring : ropeSim.getSprings()) {
            if (LineIntersection.segmentsIntersect(
                    x1, y1, x2, y2,
                    spring.a.x, spring.a.y, spring.b.x, spring.b.y)) {
                toRemove.add(spring);
            }
        }
        // 移除被切断的弹簧
        for (RopeSpring s : toRemove) {
            ropeSim.removeSpring(s);
        }
    }

    public void update(double dt) {
        ropeSim.update();
        // 更新糖果（如果与绳索断开，受重力下落）
        if (!candy.isAttached()) {
            candy.applyGravity(500, dt);
        }
        // 检测糖果是否吃到星星
        for (Star star : stars) {
            if (!star.collected && candy.collidesWith(star)) {
                star.collected = true;
            }
        }
        // 检测糖果是否落入怪兽口中
        if (candy.collidesWith(monster)) {
            levelComplete();
        }
    }
}

复杂度分析

总结

割绳子游戏的物理核心在于质点-弹簧模型与Verlet积分的结合，该方法以较低的计算成本实现了稳定的绳索摆动效果。射线-线段相交检测为切割交互提供了精确判定，而抛物线轨迹预测则是连接玩家操作与物理解谜的关键桥梁。二次贝塞尔曲线渲染将离散的质点转化为视觉流畅的绳索形态，体现了算法与表现层分离的经典设计思想。