引言
滚弹珠是广受喜爱的经典物理益智游戏：玩家弹射一颗弹珠，利用墙壁和其他弹珠的反弹与碰撞，击中场景中的目标物体。游戏的精髓在于预测多体碰撞的链式反应与寻找最优弹射路径。本文用Java实现滚弹珠物理引擎，核心涉及三大算法：弹性碰撞动量守恒求解、碰撞检测几何算法、以及将反射路径建模为图后的Dijkstra最短路径规划。
核心算法思路
1. 弹性碰撞模型
两弹珠发生弹性碰撞时，动量守恒且动能守恒。设两弹珠质量分别为 m1、m2，速度向量为 v1、v2，碰撞法线方向为 n。碰撞后的速度可通过以下公式计算：
v1' = v1 - (2*m2/(m1+m2)) * dot(v1-v2, n) * n
v2' = v2 + (2*m1/(m1+m2)) * dot(v1-v2, n) * n
2. 碰撞检测
弹珠与墙壁的碰撞：检测圆形与线段的相交。弹珠与弹珠的碰撞：检测两圆心距离是否小于半径之和。
3. 反射路径图与Dijkstra
将场景中的墙壁、弹珠位置离散化为图的节点，反射路径作为边。通过镜像法展开反射路径，将”反射到达目标”转化为”直线穿过镜像空间到达镜像目标”，然后使用Dijkstra算法求解最短射击路径。
Java实现
import java.util.*;
/**
* 滚弹珠物理引擎与最短路径规划器
* 核心算法：弹性碰撞、几何碰撞检测、Dijkstra最短路径
*/
public class MarblePhysicsEngine {
static final double EPS = 1e-9;
// 二维向量
static class Vec2 {
double x, y;
Vec2(double x, double y) { this.x = x; this.y = y; }
Vec2 add(Vec2 v) { return new Vec2(x + v.x, y + v.y); }
Vec2 sub(Vec2 v) { return new Vec2(x - v.x, y - v.y); }
Vec2 mul(double s) { return new Vec2(x * s, y * s); }
double dot(Vec2 v) { return x * v.x + y * v.y; }
double len() { return Math.sqrt(x * x + y * y); }
Vec2 normalize() {
double l = len();
if (l < EPS) return new Vec2(0, 0);
return new Vec2(x / l, y / l);
}
}
// 弹珠
static class Marble {
Vec2 pos; // 位置
Vec2 vel; // 速度
double radius; // 半径
double mass; // 质量
boolean isStatic; // 是否固定（如障碍物弹珠）
Marble(Vec2 pos, Vec2 vel, double r, double m, boolean stat) {
this.pos = pos; this.vel = vel;
this.radius = r; this.mass = m;
this.isStatic = stat;
}
}
// 墙壁线段
static class Wall {
Vec2 p1, p2;
Wall(Vec2 a, Vec2 b) { p1 = a; p2 = b; }
}
/**
* 核心算法1：弹性碰撞动量守恒求解
* 输入：两弹珠对象
* 效果：更新两弹珠的速度向量
*/
public static void resolveElasticCollision(Marble a, Marble b) {
Vec2 normal = b.pos.sub(a.pos).normalize();
if (normal.len() < EPS) return; // 重合，无法确定法线
Vec2 relativeVel = b.vel.sub(a.vel);
double velAlongNormal = relativeVel.dot(normal);
// 如果已经分离，不处理
if (velAlongNormal > 0) return;
double e = 1.0; // 弹性系数，1为完全弹性
double j = -(1 + e) * velAlongNormal;
j /= (1.0 / a.mass + 1.0 / b.mass);
Vec2 impulse = normal.mul(j);
a.vel = a.vel.sub(impulse.mul(1.0 / a.mass));
b.vel = b.vel.add(impulse.mul(1.0 / b.mass));
}
/**
* 核心算法2：弹珠与墙壁的碰撞检测与反射
* 返回反射后的速度向量，若未碰撞返回null
*/
public static Vec2 resolveWallCollision(Marble m, Wall w) {
Vec2 wallDir = w.p2.sub(w.p1);
Vec2 wallNormal = new Vec2(-wallDir.y, wallDir.x).normalize();
// 计算弹珠到墙壁线段的最近距离
Vec2 toMarble = m.pos.sub(w.p1);
double proj = toMarble.dot(wallDir) / wallDir.dot(wallDir);
proj = Math.max(0, Math.min(1, proj));
Vec2 closest = w.p1.add(wallDir.mul(proj));
Vec2 distVec = m.pos.sub(closest);
double dist = distVec.len();
if (dist > m.radius + EPS) return null; // 未碰撞
// 计算反射速度：v' = v - 2(v·n)n
double vn = m.vel.dot(wallNormal);
if (vn > 0) return null; // 正在远离墙壁
Vec2 reflected = m.vel.sub(wallNormal.mul(2 * vn));
return reflected;
}
/**
* 核心算法3：两弹珠碰撞检测
* 返回碰撞发生的时间比例 t ∈ [0,1]，若无碰撞返回 -1
*/
public static double circleCollisionTime(Marble a, Marble b, double dt) {
Vec2 relPos = b.pos.sub(a.pos);
Vec2 relVel = b.vel.sub(a.vel);
double rSum = a.radius + b.radius;
double A = relVel.dot(relVel);
double B = 2 * relPos.dot(relVel);
double C = relPos.dot(relPos) - rSum * rSum;
double discriminant = B * B - 4 * A * C;
if (discriminant < 0 || Math.abs(A) < EPS) return -1;
double sqrtD = Math.sqrt(discriminant);
double t1 = (-B - sqrtD) / (2 * A);
double t2 = (-B + sqrtD) / (2 * A);
if (t1 >= 0 && t1 <= dt) return t1;
if (t2 >= 0 && t2 <= dt) return t2;
return -1;
}
/**
* 核心算法4：模拟单步物理更新
* 检测并处理所有碰撞，时间复杂度 O(n² + n*m)
* n为弹珠数，m为墙壁数
*/
public static void stepSimulation(List<Marble> marbles, List<Wall> walls, double dt) {
// 检测弹珠-弹珠碰撞
int n = marbles.size();
boolean[] collided = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Marble a = marbles.get(i);
Marble b = marbles.get(j);
if (a.isStatic && b.isStatic) continue;
double t = circleCollisionTime(a, b, dt);
if (t >= 0) {
// 将弹珠移动到碰撞时刻
a.pos = a.pos.add(a.vel.mul(t));
b.pos = b.pos.add(b.vel.mul(t));
resolveElasticCollision(a, b);
collided[i] = collided[j] = true;
}
}
}
// 检测弹珠-墙壁碰撞
for (int i = 0; i < n; i++) {
Marble m = marbles.get(i);
if (m.isStatic) continue;
for (Wall w : walls) {
Vec2 newVel = resolveWallCollision(m, w);
if (newVel != null) {
m.vel = newVel;
}
}
}
// 更新位置
for (Marble m : marbles) {
if (!m.isStatic) {
m.pos = m.pos.add(m.vel.mul(dt));
}
}
}
// ============ 最短路径规划模块 ============
// 路径节点：代表一次反射点或发射点/目标点
static class PathNode {
int id;
Vec2 pos;
boolean isMirror; // 是否为镜像点
PathNode(int id, Vec2 pos, boolean mirror) {
this.id = id; this.pos = pos; this.isMirror = mirror;
}
}
/**
* 核心算法5：使用镜像法构建反射路径图 + Dijkstra最短路径
* 思路：将墙壁反射展开为镜像空间，在镜像空间中直线即对应原空间的反射路径
*/
public static List<Vec2> findShortestReflectionPath(
Vec2 start, Vec2 target, List<Wall> walls, int maxReflections) {
// 生成镜像点（仅考虑目标点关于各墙壁的镜像）
List<PathNode> nodes = new ArrayList<>();
nodes.add(new PathNode(0, start, false)); // 起点
nodes.add(new PathNode(1, target, false)); // 原始目标
int nextId = 2;
Queue<PathNode> queue = new LinkedList<>();
queue.add(new PathNode(1, target, false));
// BFS生成镜像点（限制深度）
Map<Integer, Integer> mirrorDepth = new HashMap<>();
mirrorDepth.put(1, 0);
while (!queue.isEmpty() && Collections.max(mirrorDepth.values()) < maxReflections) {
PathNode cur = queue.poll();
int depth = mirrorDepth.get(cur.id);
if (depth >= maxReflections) continue;
for (Wall w : walls) {
Vec2 mirrored = mirrorPoint(cur.pos, w);
PathNode mn = new PathNode(nextId++, mirrored, true);
nodes.add(mn);
mirrorDepth.put(mn.id, depth + 1);
queue.add(mn);
}
}
// 构建图：若两点连线不与墙壁相交（除端点所在墙），则建立边
int N = nodes.size();
List<double[]>[] graph = new ArrayList[N];
for (int i = 0; i < N; i++) graph[i] = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (hasClearPath(nodes.get(i).pos, nodes.get(j).pos, walls)) {
double dist = nodes.get(i).pos.sub(nodes.get(j).pos).len();
graph[i].add(new double[]{j, dist});
graph[j].add(new double[]{i, dist});
}
}
}
// Dijkstra求最短路径
return dijkstra(graph, nodes, 0, 1);
}
// 计算点关于墙壁的镜像
private static Vec2 mirrorPoint(Vec2 p, Wall w) {
Vec2 wallDir = w.p2.sub(w.p1);
Vec2 wallNormal = new Vec2(-wallDir.y, wallDir.x).normalize();
Vec2 toP = p.sub(w.p1);
double dist = toP.dot(wallNormal);
return p.sub(wallNormal.mul(2 * dist));
}
// 判断两点间是否有直达路径（不被墙壁阻挡）
private static boolean hasClearPath(Vec2 a, Vec2 b, List<Wall> walls) {
for (Wall w : walls) {
if (segmentsIntersect(a, b, w.p1, w.p2)) {
return false;
}
}
return true;
}
// 判断两线段是否相交
private static boolean segmentsIntersect(Vec2 p1, Vec2 p2, Vec2 p3, Vec2 p4) {
double d1 = direction(p3, p4, p1);
double d2 = direction(p3, p4, p2);
double d3 = direction(p1, p2, p3);
double d4 = direction(p1, p2, p4);
if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
return true;
}
return false;
}
private static double direction(Vec2 pi, Vec2 pj, Vec2 pk) {
return (pk.x - pi.x) * (pj.y - pi.y) - (pj.x - pi.x) * (pk.y - pi.y);
}
// Dijkstra算法
private static List<Vec2> dijkstra(List<double[]>[] graph, List<PathNode> nodes,
int src, int dst) {
int N = graph.length;
double[] dist = new double[N];
int[] parent = new int[N];
Arrays.fill(dist, Double.POSITIVE_INFINITY);
Arrays.fill(parent, -1);
dist[src] = 0;
PriorityQueue<double[]> pq = new PriorityQueue<>(Comparator.comparingDouble(a -> a[0]));
pq.add(new double[]{0, src});
while (!pq.isEmpty()) {
double[] cur = pq.poll();
double d = cur[0];
int u = (int) cur[1];
if (d > dist[u] + EPS) continue;
if (u == dst) break;
for (double[] edge : graph[u]) {
int v = (int) edge[0];
double w = edge[1];
if (dist[u] + w < dist[v] - EPS) {
dist[v] = dist[u] + w;
parent[v] = u;
pq.add(new double[]{dist[v], v});
}
}
}
// 回溯路径
List<Vec2> path = new ArrayList<>();
if (dist[dst] == Double.POSITIVE_INFINITY) return path; // 无路径
int cur = dst;
while (cur != -1) {
path.add(nodes.get(cur).pos);
cur = parent[cur];
}
Collections.reverse(path);
return path;
}
// 主程序演示
public static void main(String[] args) {
System.out.println("=== 滚弹珠物理引擎演示 ===");
// 创建弹珠
List<Marble> marbles = new ArrayList<>();
marbles.add(new Marble(new Vec2(1, 1), new Vec2(3, 2), 0.15, 1.0, false)); // 发射弹珠
marbles.add(new Marble(new Vec2(5, 3), new Vec2(0, 0), 0.15, 1.0, true)); // 障碍物
marbles.add(new Marble(new Vec2(8, 2), new Vec2(0, 0), 0.15, 1.0, true)); // 目标
// 创建墙壁
List<Wall> walls = new ArrayList<>();
walls.add(new Wall(new Vec2(0, 0), new Vec2(10, 0)));
walls.add(new Wall(new Vec2(10, 0), new Vec2(10, 5)));
walls.add(new Wall(new Vec2(10, 5), new Vec2(0, 5)));
walls.add(new Wall(new Vec2(0, 5), new Vec2(0, 0)));
walls.add(new Wall(new Vec2(3, 0), new Vec2(3, 3))); // 中间隔墙
// 模拟10步
System.out.println("\n物理模拟：");
for (int step = 0; step < 10; step++) {
Marble shooter = marbles.get(0);
System.out.printf("Step %d: shooter pos=(%.2f, %.2f), vel=(%.2f, %.2f)%n",
step, shooter.pos.x, shooter.pos.y, shooter.vel.x, shooter.vel.y);
stepSimulation(marbles, walls, 0.1);
}
// 最短路径规划演示
System.out.println("\n最短反射路径规划：");
List<Vec2> path = findShortestReflectionPath(
new Vec2(1, 1), new Vec2(8, 2), walls, 2);
System.out.println("路径点数：" + path.size());
for (int i = 0; i < path.size(); i++) {
Vec2 p = path.get(i);
System.out.printf(" 点%d: (%.2f, %.2f)%n", i, p.x, p.y);
}
}
}
复杂度分析
| 算法模块 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 弹性碰撞求解 | O(1) | O(1) |
| 全弹珠碰撞检测 | O(n²) | O(n) |
| 镜像点生成 | O(k^m) | O(k^m) |
| Dijkstra最短路径 | O(V² log V) | O(V) |
总结
本文实现了滚弹珠游戏的完整物理引擎与路径规划系统。弹性碰撞模块基于动量守恒精确计算反弹速度；碰撞检测模块处理圆形与线段的相交判定；最短路径模块通过镜像法将反射问题转化为图上的Dijkstra求解。该框架可扩展到台球、弹珠台等更复杂的物理益智游戏中。
