每日算法 — 使用java实现斯诺克：多球碰撞链式反应与最优击球路径规划

引言

斯诺克是极具策略性的台球运动，选手需要精确计算母球撞击目标球后的分离角度、力度控制，以及多球碰撞的链式反应。本文用Java实现斯诺克台面的物理引擎，核心算法包括弹性碰撞的动量守恒求解、碰撞链式反应检测，以及基于射线投射的最优击球路径搜索。

核心算法原理

1. 弹性碰撞模型

两球碰撞时动量守恒且动能守恒（理想弹性碰撞）。设两球质量相等，碰撞后速度分解为沿碰撞法线方向和切线方向：

[ \vec{v}1′ = \vec{v}{1t} + \vec{v}{2n} ]
[ \vec{v}_2′ = \vec{v}{2t} + \vec{v}_{1n} ]

法线方向速度交换，切线方向速度不变。

2. 碰撞链式反应

一次击球可能引发多球连续碰撞。采用事件驱动模拟，按时间顺序处理碰撞事件，直到系统静止或达到最大步数。

3. 最优击球路径规划

通过射线投射（Ray Casting）从母球出发，检测与目标球的碰撞路径，评估角度和力度，选择最优击球方案。

Java完整实现

import java.util.*;

/**
 * 斯诺克物理引擎与最优击球路径规划
 * 核心算法：弹性碰撞动量守恒 + 事件驱动模拟 + 射线投射路径搜索
 */
public class SnookerEngine {

    private static final double BALL_RADIUS = 0.02625; // 斯诺克球半径(m)
    private static final double BALL_MASS = 0.145; // kg
    private static final double TABLE_WIDTH = 3.569;
    private static final double TABLE_LENGTH = 1.778;
    private static final double FRICTION_COEFF = 0.2;
    private static final double GRAVITY = 9.81;
    private static final double RESTITUTION = 0.98; // 恢复系数

    static class Ball {
        int id;
        double x, y;
        double vx, vy;
        boolean pocketed;

        Ball(int id, double x, double y) {
            this.id = id;
            this.x = x;
            this.y = y;
            this.vx = 0;
            this.vy = 0;
            this.pocketed = false;
        }

        double speed() { return Math.sqrt(vx * vx + vy * vy); }

        void move(double dt) {
            if (pocketed) return;
            x += vx * dt;
            y += vy * dt;

            // 摩擦力减速
            double frictionDecel = FRICTION_COEFF * GRAVITY * dt;
            double s = speed();
            if (s > 0) {
                double ratio = Math.max(0, (s - frictionDecel) / s);
                vx *= ratio;
                vy *= ratio;
                if (s < 0.01) { vx = 0; vy = 0; }
            }
        }

        Ball copy() {
            Ball b = new Ball(id, x, y);
            b.vx = vx; b.vy = vy; b.pocketed = pocketed;
            return b;
        }
    }

    static class CollisionEvent implements Comparable<CollisionEvent> {
        double time;
        int ballA, ballB; // ballB = -1 表示与桌边碰撞

        CollisionEvent(double time, int a, int b) {
            this.time = time; this.ballA = a; this.ballB = b;
        }

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

    /**
     * 计算两球碰撞后的新速度（理想弹性碰撞）
     */
    private void resolveBallCollision(Ball a, Ball b) {
        double dx = b.x - a.x;
        double dy = b.y - a.y;
        double dist = Math.sqrt(dx * dx + dy * dy);
        if (dist == 0) return;

        // 碰撞法线方向
        double nx = dx / dist;
        double ny = dy / dist;

        // 相对速度在法线方向的分量
        double dvx = a.vx - b.vx;
        double dvy = a.vy - b.vy;
        double velAlongNormal = dvx * nx + dvy * ny;

        if (velAlongNormal > 0) return; // 球正在分离

        // 冲量
        double j = -(1 + RESTITUTION) * velAlongNormal;
        j /= (1.0 / BALL_MASS + 1.0 / BALL_MASS);

        double impulseX = j * nx;
        double impulseY = j * ny;

        a.vx += impulseX / BALL_MASS;
        a.vy += impulseY / BALL_MASS;
        b.vx -= impulseX / BALL_MASS;
        b.vy -= impulseY / BALL_MASS;

        // 分离重叠
        double overlap = 2 * BALL_RADIUS - dist;
        if (overlap > 0) {
            a.x -= nx * overlap * 0.5;
            a.y -= ny * overlap * 0.5;
            b.x += nx * overlap * 0.5;
            b.y += ny * overlap * 0.5;
        }
    }

    /**
     * 处理球与桌边碰撞
     */
    private void resolveWallCollision(Ball ball) {
        if (ball.x - BALL_RADIUS < 0) { ball.x = BALL_RADIUS; ball.vx = -ball.vx * RESTITUTION; }
        if (ball.x + BALL_RADIUS > TABLE_WIDTH) { ball.x = TABLE_WIDTH - BALL_RADIUS; ball.vx = -ball.vx * RESTITUTION; }
        if (ball.y - BALL_RADIUS < 0) { ball.y = BALL_RADIUS; ball.vy = -ball.vy * RESTITUTION; }
        if (ball.y + BALL_RADIUS > TABLE_LENGTH) { ball.y = TABLE_LENGTH - BALL_RADIUS; ball.vy = -ball.vy * RESTITUTION; }
    }

    /**
     * 检测是否进袋
     */
    private boolean checkPocketed(Ball ball) {
        double[][] pockets = {
            {0, 0}, {TABLE_WIDTH / 2, 0}, {TABLE_WIDTH, 0},
            {0, TABLE_LENGTH}, {TABLE_WIDTH / 2, TABLE_LENGTH}, {TABLE_WIDTH, TABLE_LENGTH}
        };
        for (double[] p : pockets) {
            double dist = Math.sqrt(Math.pow(ball.x - p[0], 2) + Math.pow(ball.y - p[1], 2));
            if (dist < 0.05) return true;
        }
        return false;
    }

    /**
     * 模拟一次击球的完整物理过程（含多球链式碰撞）
     * @param balls 所有球状态
     * @param cueBallId 母球ID
     * @param cueVx 母球初始x速度
     * @param cueVy 母球初始y速度
     * @param dt 时间步长
     * @param maxSteps 最大步数
     * @return 最终球状态
     */
    public List<Ball> simulateShot(List<Ball> balls, int cueBallId, double cueVx, double cueVy, double dt, int maxSteps) {
        List<Ball> state = new ArrayList<>();
        for (Ball b : balls) state.add(b.copy());

        // 设置母球初速度
        for (Ball b : state) {
            if (b.id == cueBallId) { b.vx = cueVx; b.vy = cueVy; }
        }

        for (int step = 0; step < maxSteps; step++) {
            boolean allStopped = true;

            // 移动所有球
            for (Ball b : state) {
                if (!b.pocketed) {
                    b.move(dt);
                    if (b.speed() > 0.01) allStopped = false;
                }
            }

            // 检测并处理球-球碰撞
            for (int i = 0; i < state.size(); i++) {
                for (int j = i + 1; j < state.size(); j++) {
                    Ball a = state.get(i), b = state.get(j);
                    if (a.pocketed || b.pocketed) continue;
                    double dx = b.x - a.x, dy = b.y - a.y;
                    double dist = Math.sqrt(dx * dx + dy * dy);
                    if (dist < 2 * BALL_RADIUS) {
                        resolveBallCollision(a, b);
                    }
                }
            }

            // 处理桌边碰撞和进袋
            for (Ball b : state) {
                if (b.pocketed) continue;
                resolveWallCollision(b);
                if (checkPocketed(b)) b.pocketed = true;
            }

            if (allStopped) break;
        }

        return state;
    }

    /**
     * 射线投射：从母球出发检测能否直接击中目标球
     * @param cueBall 母球
     * @param targetBall 目标球
     * @param otherBalls 其他球（障碍物）
     * @return 可行击球方向列表
     */
    public List<double[]> rayCastHitDirections(Ball cueBall, Ball targetBall, List<Ball> otherBalls) {
        List<double[]> directions = new ArrayList<>();

        // 目标球中心方向
        double dx = targetBall.x - cueBall.x;
        double dy = targetBall.y - cueBall.y;
        double baseAngle = Math.atan2(dy, dx);

        // 在目标球周围搜索可以撞击的角度范围（考虑球半径）
        for (double offset = -BALL_RADIUS; offset <= BALL_RADIUS; offset += 0.002) {
            double angle = baseAngle + Math.asin(offset / Math.sqrt(dx * dx + dy * dy));
            double dirX = Math.cos(angle);
            double dirY = Math.sin(angle);

            // 检测路径上是否有其他球阻挡
            boolean blocked = false;
            for (Ball obstacle : otherBalls) {
                if (obstacle.id == cueBall.id || obstacle.id == targetBall.id) continue;
                double cross = Math.abs((obstacle.x - cueBall.x) * dirY - (obstacle.y - cueBall.y) * dirX);
                double dot = (obstacle.x - cueBall.x) * dirX + (obstacle.y - cueBall.y) * dirY;
                if (cross < 2 * BALL_RADIUS && dot > 0 && dot < Math.sqrt(dx * dx + dy * dy)) {
                    blocked = true;
                    break;
                }
            }

            if (!blocked) {
                directions.add(new double[]{dirX, dirY, offset});
            }
        }

        return directions;
    }

    /**
     * 寻找最优击球方案
     * @param balls 当前球布局
     * @param cueBallId 母球ID
     * @param targetBallId 目标球ID
     * @return 最优击球速度和角度
     */
    public double[] findOptimalShot(List<Ball> balls, int cueBallId, int targetBallId) {
        Ball cueBall = null, targetBall = null;
        List<Ball> others = new ArrayList<>();
        for (Ball b : balls) {
            if (b.id == cueBallId) cueBall = b;
            else if (b.id == targetBallId) targetBall = b;
            else others.add(b);
        }
        if (cueBall == null || targetBall == null) return null;

        List<double[]> dirs = rayCastHitDirections(cueBall, targetBall, others);
        if (dirs.isEmpty()) return null;

        double bestScore = -1;
        double[] bestShot = null;

        for (double[] dir : dirs) {
            for (double speed = 1; speed <= 10; speed += 0.5) {
                List<Ball> result = simulateShot(balls, cueBallId, dir[0] * speed, dir[1] * speed, 0.001, 10000);

                // 评分：目标球进袋 + 母球安全位置
                double score = 0;
                for (Ball b : result) {
                    if (b.id == targetBallId && b.pocketed) score += 100;
                    if (b.id == cueBallId && !b.pocketed) {
                        // 母球离袋口越远越好
                        double minDistToPocket = Double.MAX_VALUE;
                        double[][] pockets = {
                            {0, 0}, {TABLE_WIDTH / 2, 0}, {TABLE_WIDTH, 0},
                            {0, TABLE_LENGTH}, {TABLE_WIDTH / 2, TABLE_LENGTH}, {TABLE_WIDTH, TABLE_LENGTH}
                        };
                        for (double[] p : pockets) {
                            double d = Math.sqrt(Math.pow(b.x - p[0], 2) + Math.pow(b.y - p[1], 2));
                            minDistToPocket = Math.min(minDistToPocket, d);
                        }
                        score += minDistToPocket * 5;
                    }
                }

                if (score > bestScore) {
                    bestScore = score;
                    bestShot = new double[]{dir[0] * speed, dir[1] * speed};
                }
            }
        }

        return bestShot;
    }

    public static void main(String[] args) {
        SnookerEngine engine = new SnookerEngine();

        List<Ball> balls = new ArrayList<>();
        balls.add(new Ball(0, 0.5, TABLE_LENGTH / 2)); // 母球
        balls.add(new Ball(1, 2.0, TABLE_LENGTH / 2)); // 红球
        balls.add(new Ball(2, 2.5, TABLE_LENGTH / 2 + 0.1)); // 障碍球
        balls.add(new Ball(3, 3.0, TABLE_LENGTH / 2 - 0.15)); // 另一个红球

        System.out.println("=== 斯诺克最优击球路径规划 ===\n");

        double[] optimal = engine.findOptimalShot(balls, 0, 1);
        if (optimal != null) {
            System.out.printf("最优击球速度: (%.3f, %.3f) m/s%n", optimal[0], optimal[1]);
            System.out.printf("速度大小: %.3f m/s%n", Math.sqrt(optimal[0] * optimal[0] + optimal[1] * optimal[1]));

            List<Ball> result = engine.simulateShot(balls, 0, optimal[0], optimal[1], 0.001, 10000);
            System.out.println("\n击球后球状态:");
            for (Ball b : result) {
                System.out.printf("球 %d: (%.3f, %.3f) %s%n", b.id, b.x, b.y, b.pocketed ? "[进袋]" : "");
            }
        } else {
            System.out.println("未找到可行击球路径");
        }
    }
}

复杂度分析

总结

本文构建了完整的斯诺克物理引擎，核心亮点包括：
1. 精确碰撞模型：基于动量守恒和恢复系数的弹性碰撞求解
2. 链式反应模拟：通过时间步进迭代处理多球连续碰撞
3. 射线投射路径搜索：从母球出发检测无障碍的击球路径
4. 评分优化：综合目标球进袋概率与母球安全性评估最优方案

该系统可进一步扩展加入旋转（侧旋、拉杆）对碰撞后轨迹的影响。