引言
台球是一项讲究角度与力度的经典桌上运动。高手不仅能准确计算击球角度，更能预判球在台边的多次反射轨迹。本文用 Java 实现一个台球路径规划系统，核心解决几何反射定律计算、多次反弹路径预测以及最优击球角度搜索三个算法问题。读者将学会如何用向量几何模拟台球运动，并通过组合搜索找到一杆进球或多杆连续得分的最优解。
核心算法设计
1. 镜面反射定律
台球撞击台边时遵循镜面反射定律：入射角等于反射角。在向量表示中，若台边法向量为 $n$，入射速度为 $v$，则反射速度 $v’$ 为：
$$v’ = v – 2(v \cdot n)n$$
该公式将速度向量沿法线方向反转，切线方向分量保持不变，精确描述了弹性碰撞后的运动方向。
2. 镜像法求反弹路径
追踪多次反弹轨迹的经典方法是镜像法：将台球桌沿撞击边做镜像反射，原问题中的折线路径在新坐标系中变为直线路径。
设台球桌尺寸为 $W \times H$，目标球位置 $T$，白球位置 $C$。若要计算经底边反弹后击中 $T$ 的入射方向：
1. 将 $T$ 关于底边做镜像，得到 $T’ = (T_x, -T_y)$
2. 连接 $C$ 与 $T’$ 的直线方向即为所需入射方向
3. 直线与底边的交点即为反弹点
对于多次反弹，可连续镜像扩展坐标系，在展开的无限网格中搜索直达目标的路径。
3. 最短路径与最优击球搜索
将台球桌在四个方向无限镜像展开，形成网格 $T_{m,n}$，其中 $m,n \in \mathbb{Z}$ 表示横纵镜像次数。白球到每个镜像目标的直线距离构成候选路径集合。通过以下约束筛选可行解：
- 路径不穿越其他球：检查直线段上是否有其他球阻挡
- 反弹点在台边范围内：交点坐标必须在 $[0, W]$ 或 $[0, H]$ 区间内
- 力度可行：路径长度对应初始速度，需在合理范围内
采用优先队列按路径长度排序，BFS 式搜索最多 $k$ 次反弹的最优解。
Java 实现
import java.util.*;
/**
* 台球几何反射与最短路径规划系统
*/
public class BilliardsPathFinder {
// 台球桌尺寸 (标准美式台球桌: 2.54m x 1.27m)
private static final double TABLE_WIDTH = 2.54;
private static final double TABLE_HEIGHT = 1.27;
private static final double BALL_RADIUS = 0.028575; // 标准球半径(m)
/**
* 二维点/向量
*/
static class Point {
double x, y;
Point(double x, double y) { this.x = x; this.y = y; }
Point sub(Point p) { return new Point(x - p.x, y - p.y); }
Point add(Point p) { return new Point(x + p.x, y + p.y); }
Point mul(double s) { return new Point(x * s, y * s); }
double dot(Point p) { return x * p.x + y * p.y; }
double length() { return Math.sqrt(x * x + y * y); }
Point normalize() {
double len = length();
return len < 1e-12 ? new Point(0, 0) : new Point(x / len, y / len);
}
}
/**
* 台球球体
*/
static class Ball {
Point pos;
int id; // 球编号 (0=白球, 1-7=单色, 9-15=双色, 8=黑8)
boolean active; // 是否仍在桌上
Ball(Point pos, int id) {
this.pos = pos;
this.id = id;
this.active = true;
}
}
/**
* 路径节点：记录一次反弹或进球事件
*/
static class PathNode {
Point position; // 事件发生位置
boolean isPocket; // 是否为进球
int edge; // 撞击边 (0=左,1=右,2=上,3=下, -1=无)
PathNode(Point p, boolean pocket, int edge) {
this.position = p;
this.isPocket = pocket;
this.edge = edge;
}
}
/**
* 候选路径
*/
static class Candidate implements Comparable<Candidate> {
Point target; // 镜像目标位置
int mx, my; // 镜像次数
double distance; // 路径长度
List<PathNode> path; // 详细路径点
Candidate(Point target, int mx, int my, double dist, List<PathNode> path) {
this.target = target;
this.mx = mx;
this.my = my;
this.distance = dist;
this.path = path;
}
@Override
public int compareTo(Candidate other) {
return Double.compare(this.distance, other.distance);
}
}
private List<Ball> balls;
public BilliardsPathFinder(List<Ball> balls) {
this.balls = balls;
}
/**
* 使用镜像法计算白球到目标球的所有可行路径
* @param cueBallIdx 白球索引
* @param targetIdx 目标球索引
* @param maxBounces 最大反弹次数
* @return 按路径长度排序的候选路径列表
*/
public List<Candidate> findPaths(int cueBallIdx, int targetIdx, int maxBounces) {
Ball cue = balls.get(cueBallIdx);
Ball target = balls.get(targetIdx);
List<Candidate> candidates = new ArrayList<>();
// 直接击打（无反弹）
Candidate direct = checkDirectPath(cue.pos, target.pos);
if (direct != null) candidates.add(direct);
// 镜像法搜索带反弹的路径
for (int mx = -maxBounces; mx <= maxBounces; mx++) {
for (int my = -maxBounces; my <= maxBounces; my++) {
if (mx == 0 && my == 0) continue;
Candidate c = checkMirroredPath(cue.pos, target.pos, mx, my);
if (c != null) candidates.add(c);
}
}
Collections.sort(candidates);
return candidates;
}
/**
* 检查直接击打路径（无台边反弹）
*/
private Candidate checkDirectPath(Point cuePos, Point targetPos) {
// 目标球实际被击中的位置：需要偏移一个球半径
Point direction = targetPos.sub(cuePos).normalize();
Point hitPoint = targetPos.sub(direction.mul(2 * BALL_RADIUS));
// 检查路径上是否有其他球阻挡
if (hasObstruction(cuePos, hitPoint, -1)) return null;
double dist = cuePos.sub(hitPoint).length();
List<PathNode> path = new ArrayList<>();
path.add(new PathNode(cuePos, false, -1));
path.add(new PathNode(hitPoint, false, -1));
return new Candidate(targetPos, 0, 0, dist, path);
}
/**
* 检查经镜像反射后的路径可行性
* @param mx 水平镜像次数 (正值=右侧镜像, 负值=左侧镜像)
* @param my 垂直镜像次数 (正值=上方镜像, 负值=下方镜像)
*/
private Candidate checkMirroredPath(Point cuePos, Point targetPos, int mx, int my) {
// 计算镜像目标位置
double mirrorX = (mx % 2 == 0) ? targetPos.x : TABLE_WIDTH - targetPos.x;
double mirrorY = (my % 2 == 0) ? targetPos.y : TABLE_HEIGHT - targetPos.y;
mirrorX += mx * TABLE_WIDTH;
mirrorY += my * TABLE_HEIGHT;
Point mirrorTarget = new Point(mirrorX, mirrorY);
// 白球到镜像目标的直线方向
Point dir = mirrorTarget.sub(cuePos);
if (dir.length() < 1e-9) return null;
dir = dir.normalize();
// 需要击中的目标球位置（考虑碰撞偏移）
Point hitPoint = mirrorTarget.sub(dir.mul(2 * BALL_RADIUS));
// 还原实际路径中的反弹点
List<PathNode> path = reconstructPath(cuePos, hitPoint, mx, my);
if (path == null) return null;
// 检查路径是否有阻挡
for (int i = 0; i < path.size() - 1; i++) {
if (hasObstruction(path.get(i).position, path.get(i + 1).position, -1))
return null;
}
double dist = cuePos.sub(hitPoint).length();
return new Candidate(mirrorTarget, mx, my, dist, path);
}
/**
* 根据镜像参数还原实际反弹路径点
*/
private List<PathNode> reconstructPath(Point start, Point end, int mx, int my) {
List<PathNode> path = new ArrayList<>();
path.add(new PathNode(start, false, -1));
// 计算直线与台边的交点序列
Point dir = end.sub(start);
double tMax = 1.0;
Point current = new Point(start.x, start.y);
int steps = Math.abs(mx) + Math.abs(my);
for (int s = 0; s < steps && tMax > 1e-9; s++) {
double tX = Double.POSITIVE_INFINITY;
double tY = Double.POSITIVE_INFINITY;
// 计算到左右边的参数t
if (Math.abs(dir.x) > 1e-12) {
if (dir.x > 0) {
tX = (TABLE_WIDTH - current.x) / dir.x;
} else {
tX = (0 - current.x) / dir.x;
}
}
// 计算到上下边的参数t
if (Math.abs(dir.y) > 1e-12) {
if (dir.y > 0) {
tY = (TABLE_HEIGHT - current.y) / dir.y;
} else {
tY = (0 - current.y) / dir.y;
}
}
double t = Math.min(tX, tY);
if (t < 0 || t > tMax) return null;
current = current.add(dir.mul(t));
// 修正浮点误差，确保点在边界上
if (t == tX) {
current.x = (dir.x > 0) ? TABLE_WIDTH : 0;
dir.x = -dir.x; // 水平方向反转
} else {
current.y = (dir.y > 0) ? TABLE_HEIGHT : 0;
dir.y = -dir.y; // 垂直方向反转
}
int edge = (t == tX) ? ((dir.x > 0) ? 1 : 0) : ((dir.y > 0) ? 3 : 2);
path.add(new PathNode(new Point(current.x, current.y), false, edge));
tMax -= t;
}
// 最终到达目标点
path.add(new PathNode(end, false, -1));
return path;
}
/**
* 检查两点之间是否有其他球阻挡
* @param excludeId 排除检查的球ID
*/
private boolean hasObstruction(Point a, Point b, int excludeId) {
Point dir = b.sub(a);
double len = dir.length();
if (len < 1e-12) return false;
dir = dir.normalize();
for (Ball ball : balls) {
if (!ball.active || ball.id == excludeId) continue;
Point ap = ball.pos.sub(a);
double proj = ap.dot(dir);
if (proj < 0 || proj > len) continue; // 投影不在线段上
Point closest = a.add(dir.mul(proj));
double dist = ball.pos.sub(closest).length();
if (dist < 2 * BALL_RADIUS - 1e-6) {
return true; // 有阻挡
}
}
return false;
}
/**
* 计算一杆进球路径：白球先击中目标球，目标球进入袋口
* @param pocketIdx 袋口索引 (0=左上,1=右上,2=左中,3=右中,4=左下,5=右下)
*/
public Candidate findPocketPath(int cueBallIdx, int targetIdx, int pocketIdx) {
Point[] pockets = {
new Point(0, 0), new Point(TABLE_WIDTH, 0),
new Point(0, TABLE_HEIGHT / 2), new Point(TABLE_WIDTH, TABLE_HEIGHT / 2),
new Point(0, TABLE_HEIGHT), new Point(TABLE_WIDTH, TABLE_HEIGHT)
};
Point pocket = pockets[pocketIdx];
Ball target = balls.get(targetIdx);
// 目标球到袋口的向量
Point toPocket = pocket.sub(target.pos);
double dist = toPocket.length();
if (dist < 2 * BALL_RADIUS) return null;
toPocket = toPocket.normalize();
// 白球需要击中目标球的位置（使目标球向袋口运动）
Point hitPoint = target.pos.sub(toPocket.mul(2 * BALL_RADIUS));
// 检查白球到hitPoint的路径
if (hasObstruction(balls.get(cueBallIdx).pos, hitPoint, cueBallIdx)) return null;
// 检查目标球到袋口的路径
if (hasObstruction(target.pos, pocket, targetIdx)) return null;
List<PathNode> path = new ArrayList<>();
path.add(new PathNode(balls.get(cueBallIdx).pos, false, -1));
path.add(new PathNode(hitPoint, false, -1));
path.add(new PathNode(pocket, true, -1));
double totalDist = balls.get(cueBallIdx).pos.sub(hitPoint).length() + dist;
return new Candidate(pocket, 0, 0, totalDist, path);
}
public static void main(String[] args) {
// 初始化一局台球
List<Ball> balls = new ArrayList<>();
balls.add(new Ball(new Point(0.635, 0.3175), 0)); // 白球
balls.add(new Ball(new Point(1.27, 0.635), 1)); // 1号球
balls.add(new Ball(new Point(1.905, 0.3175), 8)); // 黑8
BilliardsPathFinder finder = new BilliardsPathFinder(balls);
System.out.println("=== 台球路径规划系统 ===\n");
// 搜索白球到1号球的路径
System.out.println("1. 白球到1号球的路径搜索:");
List<Candidate> paths = finder.findPaths(0, 1, 2);
for (int i = 0; i < Math.min(3, paths.size()); i++) {
Candidate c = paths.get(i);
System.out.printf(" 方案%d: 距离=%.3fm, 反弹=%d次%n",
i + 1, c.distance, Math.abs(c.mx) + Math.abs(c.my));
}
// 搜索进球路径
System.out.println("\n2. 一杆进球路径搜索 (白球->1号球->袋口):");
Candidate pocketPath = finder.findPocketPath(0, 1, 5);
if (pocketPath != null) {
System.out.printf(" 可行! 总路径长度=%.3fm%n", pocketPath.distance);
System.out.print(" 路径点: ");
for (PathNode node : pocketPath.path) {
System.out.printf("(%.2f,%.2f) ", node.position.x, node.position.y);
}
System.out.println();
} else {
System.out.println(" 当前布局下无可行进球路径");
}
}
}
复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 镜像路径枚举 | $O(k^2)$ | $O(k^2)$ | $k$ 为最大反弹次数，枚举 $(2k+1)^2$ 个镜像位置 |
| 单条路径重建 | $O(b)$ | $O(b)$ | $b$ 为反弹次数，逐次计算交点 |
| 碰撞检测 | $O(n)$ | $O(1)$ | 检查路径上 $n$ 个其他球是否阻挡 |
| 全局搜索 | $O(k^2 \cdot b \cdot n)$ | $O(k^2)$ | 综合复杂度，实际 $k \leq 3, n \leq 16$ |
镜像法的核心优势在于将折线路径转化为直线路径，避免了对反射轨迹的逐步迭代模拟，将多次反弹的复杂几何问题降维为简单的直线交点计算。
总结
本文通过镜像法巧妙地将台球多次反弹的路径规划问题转化为镜像空间中的直线搜索问题。系统支持直接击打、多反弹路径以及一杆进球三种模式，通过向量几何精确计算反射轨迹，并实时检测路径上的障碍物。该算法框架可进一步扩展：引入旋转（塞球）效果、考虑摩擦力导致的轨迹偏移、或使用 A* 算法在状态空间中寻找多杆连续得分的最优序列。
