每日算法 — 使用java实现台球：圆形碰撞检测与多步反弹路径规划

引言

台球（Billiards）是一项经典的双人对抗游戏，玩家通过球杆击打白球，利用碰撞和反弹将目标球击入袋中。在台球游戏中，精准的碰撞检测和路径预判是AI实现自动瞄准的核心挑战。与矩形包围盒（AABB）碰撞不同，台球涉及的是圆形物体之间的碰撞检测，需要计算圆心距离和碰撞法向量。更进一步，优秀的台球AI需要能够”预判”球在多面边界上的多次反弹路径，从而找到最佳击球角度。

本文将用Java实现一个简化的台球物理引擎，重点讲解圆形碰撞检测算法和基于射线追踪的多步反弹路径搜索，帮助读者理解几何计算在游戏开发中的实际应用。

核心问题分析

台球游戏的算法核心可以拆解为三个子问题：

1. 圆形碰撞检测：判断两个台球是否接触，计算碰撞点和法向量
2. 反弹向量计算：根据入射方向和碰撞法线，计算反射后的运动方向
3. 多步路径搜索：从白球出发，模拟在桌边反弹后的路径，找到能够击中目标球并最终落入球袋的击球路线

这三个问题层层递进，构成了台球AI的完整决策链路。

圆形碰撞检测算法

台球可以抽象为二维平面上的圆，每个球具有圆心坐标 (x, y) 和半径 r。两个球发生碰撞的充要条件是圆心距离小于等于两球半径之和。

距离检测与碰撞响应

/**
 * 台球球体类
 */
class Ball {
    double x, y;      // 圆心坐标
    double vx, vy;    // 速度向量
    double radius;    // 半径
    int type;         // 0=白球, 1=目标球, 2=球袋

    public Ball(double x, double y, double radius, int type) {
        this.x = x;
        this.y = y;
        this.radius = radius;
        this.vx = 0;
        this.vy = 0;
        this.type = type;
    }

    /**
     * 计算与另一球的距离
     */
    double distanceTo(Ball other) {
        double dx = this.x - other.x;
        double dy = this.y - other.y;
        return Math.sqrt(dx * dx + dy * dy);
    }
}

/**
 * 圆形碰撞检测与响应
 * 当两球圆心距离 <= 半径之和时发生碰撞
 */
class CircleCollision {

    /**
     * 检测两个台球是否发生碰撞
     * @return true if collision detected
     */
    static boolean checkCollision(Ball a, Ball b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        double distanceSq = dx * dx + dy * dy;
        double radiusSum = a.radius + b.radius;
        // 使用平方比较避免开方运算，提升性能
        return distanceSq <= radiusSum * radiusSum;
    }

    /**
     * 弹性碰撞响应：动量守恒与能量守恒
     * 简化模型：两球质量相等
     */
    static void resolveCollision(Ball a, Ball b) {
        // 碰撞法向量（从a指向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;

        // 弹性碰撞，恢复系数 e = 1（完全弹性）
        double e = 1.0;
        double j = -(1 + e) * velAlongNormal;
        j /= (1.0 / 1.0 + 1.0 / 1.0); // 质量倒数之和，假设质量均为1

        //  impulse 向量
        double impulseX = j * nx;
        double impulseY = j * ny;

        // 更新速度
        a.vx -= impulseX / 1.0;
        a.vy -= impulseY / 1.0;
        b.vx += impulseX / 1.0;
        b.vy += impulseY / 1.0;

        // 防止球体重叠：将球体沿法线方向分离
        double overlap = (a.radius + b.radius - dist) / 2.0;
        a.x -= overlap * nx;
        a.y -= overlap * ny;
        b.x += overlap * nx;
        b.y += overlap * ny;
    }
}

算法关键点

• 平方距离优化：在碰撞检测阶段使用 distance² <= radiusSum² 避免昂贵的 sqrt 运算
• 分离向量：碰撞后通过 overlap 将两球沿法线方向推开，防止下一帧仍然重叠导致抖动
• 动量守恒：弹性碰撞中，速度在法线方向上交换，切线方向保持不变

边界反弹与反射向量

台球桌具有矩形边界，球撞击桌边后会发生反弹。边界反弹可以视为球与质量无限大的静止墙面的碰撞。

/**
 * 台球桌边界定义
 */
class Table {
    double left, right, top, bottom;

    public Table(double left, double top, double right, double bottom) {
        this.left = left;
        this.top = top;
        this.right = right;
        this.bottom = bottom;
    }

    /**
     * 处理球与边界的碰撞反弹
     * 边界法向量：左右边为(±1,0)，上下边为(0,±1)
     */
    void resolveBoundaryCollision(Ball ball) {
        // 左边界
        if (ball.x - ball.radius < left) {
            ball.x = left + ball.radius;
            ball.vx = -ball.vx; // x方向速度反向
        }
        // 右边界
        if (ball.x + ball.radius > right) {
            ball.x = right - ball.radius;
            ball.vx = -ball.vx;
        }
        // 上边界
        if (ball.y - ball.radius < top) {
            ball.y = top + ball.radius;
            ball.vy = -ball.vy; // y方向速度反向
        }
        // 下边界
        if (ball.y + ball.radius > bottom) {
            ball.y = bottom - ball.radius;
            ball.vy = -ball.vy;
        }
    }
}

反射的数学本质：入射向量在法线方向的分量取反，切线方向分量不变。对于垂直边界（法向量 n = (1, 0)），只有 vx 反向；对于水平边界（法向量 n = (0, 1)），只有 vy 反向。

多步反弹路径搜索

这是台球AI的核心：给定白球位置和目标球位置，找到一个击球方向，使得白球经过若干次桌边反弹后能够击中目标球，或者目标球被击中后能够落入某个球袋。

镜像法原理

直接模拟反弹路径较为复杂，因为每次反弹都需要改变速度方向。一个优雅的替代方案是镜像法（Mirror/Reflection Method）：将台球桌沿边界进行镜像反射，把折线路径转化为直线路径。

import java.util.*;

/**
 * 使用镜像法计算多步反弹路径
 * 将台球桌沿边界镜像展开，折线路径变为直线
 */
class PathFinder {

    /**
     * 镜像点：将点关于垂直线x=axisX镜像
     */
    static double[] mirrorVertical(double x, double y, double axisX) {
        return new double[]{2 * axisX - x, y};
    }

    /**
     * 镜像点：将点关于水平线y=axisY镜像
     */
    static double[] mirrorHorizontal(double x, double y, double axisY) {
        return new double[]{x, 2 * axisY - y};
    }

    /**
     * 生成目标球在镜像空间中的所有"虚像"
     * 限制最大反弹次数maxBounces
     */
    static List<VirtualBall> generateMirrorImages(
            double targetX, double targetY,
            double left, double top, double right, double bottom,
            int maxBounces) {

        List<VirtualBall> images = new ArrayList<>();
        double width = right - left;
        double height = bottom - top;

        // 在x方向和y方向分别进行镜像展开
        // 水平反弹次数: -maxBounces 到 +maxBounces
        for (int mx = -maxBounces; mx <= maxBounces; mx++) {
            for (int my = -maxBounces; my <= maxBounces; my++) {
                if (Math.abs(mx) + Math.abs(my) > maxBounces) continue;

                double vx = targetX;
                double vy = targetY;

                // x方向镜像
                if (mx % 2 == 0) {
                    vx += mx * width;
                } else {
                    vx = (mx + 1) * width - (vx - left) + left;
                }

                // y方向镜像
                if (my % 2 == 0) {
                    vy += my * height;
                } else {
                    vy = (my + 1) * height - (vy - top) + top;
                }

                images.add(new VirtualBall(vx, vy, Math.abs(mx) + Math.abs(my)));
            }
        }
        return images;
    }

    static class VirtualBall {
        double x, y;
        int bounceCount;

        VirtualBall(double x, double y, int bounceCount) {
            this.x = x;
            this.y = y;
            this.bounceCount = bounceCount;
        }
    }

    /**
     * 找到最佳击球方向
     * 返回：角度（弧度）和对应的反弹次数
     */
    static ShotSolution findBestShot(
            double cueX, double cueY,
            double targetX, double targetY,
            Table table, int maxBounces) {

        List<VirtualBall> images = generateMirrorImages(
            targetX, targetY,
            table.left, table.top, table.right, table.bottom,
            maxBounces
        );

        double bestAngle = 0;
        int bestBounces = Integer.MAX_VALUE;
        double minDist = Double.MAX_VALUE;

        for (VirtualBall vb : images) {
            double dx = vb.x - cueX;
            double dy = vb.y - cueY;
            double dist = Math.sqrt(dx * dx + dy * dy);
            double angle = Math.atan2(dy, dx);

            // 优先选择反弹次数少的方案，其次选择距离短的
            if (vb.bounceCount < bestBounces ||
                (vb.bounceCount == bestBounces && dist < minDist)) {
                bestBounces = vb.bounceCount;
                bestAngle = angle;
                minDist = dist;
            }
        }

        return new ShotSolution(bestAngle, bestBounces);
    }

    static class ShotSolution {
        double angle;
        int bounceCount;

        ShotSolution(double angle, int bounceCount) {
            this.angle = angle;
            this.bounceCount = bounceCount;
        }
    }
}

镜像法的核心思想

1. 展开空间：将台球桌沿上下左右边界无限镜像展开，形成一个由多个”虚桌”拼接而成的平面
2. 直线替代折线：在展开空间中，白球到目标球虚像的直线，对应原空间中的折线反弹路径
3. 反弹次数：虚像所在的位置决定了反弹次数——跨越几个”虚桌”边界，就对应几次反弹

完整可运行代码

以下是一个完整的台球模拟程序，包含碰撞检测、反弹物理和AI瞄准：

import java.util.*;

/**
 * 台球物理引擎与AI瞄准系统
 * 核心算法：圆形碰撞检测 + 镜像法路径搜索
 */
public class BilliardsSimulator {

    static final double BALL_RADIUS = 10.0;
    static final double TABLE_LEFT = 0;
    static final double TABLE_TOP = 0;
    static final double TABLE_RIGHT = 600;
    static final double TABLE_BOTTOM = 300;

    public static void main(String[] args) {
        // 初始化台球桌
        Table table = new Table(TABLE_LEFT, TABLE_TOP, TABLE_RIGHT, TABLE_BOTTOM);

        // 初始化球：白球 + 目标球 + 球袋
        Ball cueBall = new Ball(150, 150, BALL_RADIUS, 0);
        Ball targetBall = new Ball(450, 150, BALL_RADIUS, 1);

        // 球袋位置（6个角袋）
        List<Ball> pockets = Arrays.asList(
            new Ball(0, 0, 15, 2),
            new Ball(TABLE_RIGHT / 2, 0, 15, 2),
            new Ball(TABLE_RIGHT, 0, 15, 2),
            new Ball(0, TABLE_BOTTOM, 15, 2),
            new Ball(TABLE_RIGHT / 2, TABLE_BOTTOM, 15, 2),
            new Ball(TABLE_RIGHT, TABLE_BOTTOM, 15, 2)
        );

        System.out.println("=== 台球AI瞄准系统 ===");
        System.out.printf("白球位置: (%.1f, %.1f)%n", cueBall.x, cueBall.y);
        System.out.printf("目标球位置: (%.1f, %.1f)%n", targetBall.x, targetBall.y);

        // 步骤1：找到白球直接击中目标球的方向
        PathFinder.ShotSolution directShot = PathFinder.findBestShot(
            cueBall.x, cueBall.y,
            targetBall.x, targetBall.y,
            table, 0  // 0次反弹 = 直接击打
        );
        System.out.printf("%n直接击打方案：角度=%.2f°, 反弹次数=%d%n",
            Math.toDegrees(directShot.angle), directShot.bounceCount);

        // 步骤2：寻找带反弹的最佳击球路线（最多3次反弹）
        PathFinder.ShotSolution bankShot = PathFinder.findBestShot(
            cueBall.x, cueBall.y,
            targetBall.x, targetBall.y,
            table, 3
        );
        System.out.printf("最佳反弹方案：角度=%.2f°, 反弹次数=%d%n",
            Math.toDegrees(bankShot.angle), bankShot.bounceCount);

        // 步骤3：模拟击球过程
        System.out.println("\n=== 物理模拟 ===");
        simulateShot(cueBall, targetBall, table, bankShot.angle, 15.0);
    }

    /**
     * 模拟击球过程
     * @param power 击球力度（初始速度大小）
     */
    static void simulateShot(Ball cue, Ball target, Table table,
                             double angle, double power) {
        cue.vx = power * Math.cos(angle);
        cue.vy = power * Math.sin(angle);

        int steps = 0;
        final int MAX_STEPS = 1000;
        final double FRICTION = 0.995; // 摩擦力衰减

        while (steps < MAX_STEPS && (Math.abs(cue.vx) > 0.1 || Math.abs(cue.vy) > 0.1)) {
            // 更新位置
            cue.x += cue.vx;
            cue.y += cue.vy;

            // 边界反弹
            table.resolveBoundaryCollision(cue);

            // 检测与目标球碰撞
            if (CircleCollision.checkCollision(cue, target)) {
                CircleCollision.resolveCollision(cue, target);
                System.out.printf("碰撞发生！步骤=%d, 白球位置=(%.1f, %.1f)%n",
                    steps, cue.x, cue.y);
            }

            // 摩擦力减速
            cue.vx *= FRICTION;
            cue.vy *= FRICTION;

            steps++;
        }

        System.out.printf("模拟结束，总步数=%d%n", steps);
        System.out.printf("白球最终位置: (%.1f, %.1f)%n", cue.x, cue.y);
        System.out.printf("目标球最终位置: (%.1f, %.1f)%n", target.x, target.y);
    }
}

复杂度分析

在实际游戏中，maxBounces 通常不超过3，因此镜像法的搜索开销非常小。相比逐帧模拟反弹路径的O(步数)方法，镜像法将路径规划问题转化为几何查询问题，大幅提升了AI决策效率。

扩展与优化方向

1. 球袋瞄准：将目标点从”目标球位置”替换为”目标球被击中后能滚入球袋的接触点”，这需要考虑二次碰撞（目标球与球袋）
2. 力度控制：当前模型使用固定力度，实际游戏中需要根据距离和反弹次数调整力度
3. 旋转效应（English）：引入 topspin/backspin 的物理模型，使球在碰撞后产生曲线运动
4. 多球碰撞：当有多个目标球时，可以使用A*或Dijkstra算法在”球-袋”图上寻找最优击球顺序

总结

本文通过台球游戏的场景，讲解了两个核心算法：

• 圆形碰撞检测：利用圆心距离与半径之和的关系快速判断碰撞，并通过动量守恒计算碰撞后的速度变化
• 镜像法路径搜索：通过空间镜像展开，将复杂的折线反弹路径转化为直线距离问题，优雅地解决了多步反弹路径规划

台球游戏的算法设计展示了几何计算在物理引擎中的核心地位。镜像法的思想不仅适用于台球，在光线追踪、声波传播、无线信号反射等领域也有广泛应用。掌握这类空间变换技巧，能够帮助开发者在面对复杂路径问题时找到简洁优雅的解决方案。