引言
保龄球是一项经典的室内运动，玩家通过投掷一个重球击倒排列成三角形的十个球瓶。看似简单的游戏规则背后，隐藏着丰富的物理碰撞与策略决策问题。本文将用 Java 实现一个带 AI 决策的保龄球模拟系统，核心聚焦在碰撞物理计算、球瓶连锁倒下判定以及贪心最优投球策略三大算法模块。
核心算法设计
1. 碰撞物理模型
保龄球与球瓶的碰撞可简化为二维弹性碰撞问题。设球的质量为 $M$，球瓶质量为 $m$，碰撞前后动量守恒、动能守恒。对于非对心碰撞，采用向量分解法：将速度分解为沿碰撞法线方向和切线方向，法线方向按一维弹性碰撞处理，切线方向速度不变。
碰撞响应公式：
– 法线方向相对速度：$v_{rel} = (v_1 – v_2) \cdot n$
– 冲量大小：$J = \frac{-(1+e) \cdot v_{rel}}{\frac{1}{M} + \frac{1}{m}}$
– 其中 $e$ 为恢复系数（保龄球约 0.3）
2. 球瓶连锁倒下判定
球瓶被击倒后可能撞击相邻球瓶，形成连锁反应。采用事件驱动模拟：维护一个按碰撞时间排序的优先队列，每次取出最早发生的碰撞事件进行处理，更新物体状态后重新计算可能的新碰撞。
倒下判定条件：球瓶质心水平位移超过底座半径，或倾斜角度超过阈值（约 15 度）。
3. 贪心最优投球策略
AI 投球决策的核心是选择最佳投球角度和力度，以最大化期望击倒球瓶数。采用贪心策略：
- 目标选择：计算球瓶三角形的几何中心（1号瓶与3号瓶之间偏右位置为最优入射点）
- 角度枚举：在 $[-5°, 5°]$ 范围内以 $0.5°$ 为步长枚举投球角度
- 模拟评估：对每个角度进行快速物理模拟，统计击倒球瓶数
- 选择最优：取击倒数最多的角度，若相同则选接近中心的角度
Java 实现
import java.util.*;
/**
* 保龄球碰撞物理与贪心策略模拟系统
*/
public class BowlingGame {
// 物理常量
private static final double BALL_MASS = 7.26; // 球质量(kg)
private static final double PIN_MASS = 1.586; // 球瓶质量(kg)
private static final double BALL_RADIUS = 0.108; // 球半径(m)
private static final double PIN_RADIUS = 0.057; // 球瓶底部半径(m)
private static final double PIN_HEIGHT = 0.381; // 球瓶高度(m)
private static final double RESTITUTION = 0.3; // 恢复系数
private static final double FRICTION = 0.12; // 球道摩擦系数
private static final double GRAVITY = 9.8; // 重力加速度
/**
* 二维向量类
*/
static class Vector2D {
double x, y;
Vector2D(double x, double y) { this.x = x; this.y = y; }
Vector2D add(Vector2D v) { return new Vector2D(x + v.x, y + v.y); }
Vector2D sub(Vector2D v) { return new Vector2D(x - v.x, y - v.y); }
Vector2D mul(double s) { return new Vector2D(x * s, y * s); }
double dot(Vector2D v) { return x * v.x + y * v.y; }
double length() { return Math.sqrt(x * x + y * y); }
Vector2D normalize() {
double len = length();
return len < 1e-9 ? new Vector2D(0, 0) : new Vector2D(x / len, y / len);
}
}
/**
* 物理物体基类
*/
static class Body {
Vector2D position; // 位置
Vector2D velocity; // 速度
double mass; // 质量
double radius; // 碰撞半径
boolean active; // 是否仍在运动
Body(Vector2D pos, Vector2D vel, double mass, double radius) {
this.position = pos;
this.velocity = vel;
this.mass = mass;
this.radius = radius;
this.active = true;
}
}
/**
* 保龄球
*/
static class Ball extends Body {
Ball(Vector2D pos, Vector2D vel) {
super(pos, vel, BALL_MASS, BALL_RADIUS);
}
}
/**
* 球瓶
*/
static class Pin extends Body {
boolean standing; // 是否站立
double tiltAngle; // 倾斜角度
Pin(Vector2D pos) {
super(pos, new Vector2D(0, 0), PIN_MASS, PIN_RADIUS);
this.standing = true;
this.tiltAngle = 0;
}
}
/**
* 碰撞事件
*/
static class Collision implements Comparable<Collision> {
double time; // 碰撞发生时间
Body a, b; // 碰撞双方
Collision(double time, Body a, Body b) {
this.time = time;
this.a = a;
this.b = b;
}
@Override
public int compareTo(Collision other) {
return Double.compare(this.time, other.time);
}
}
private Ball ball;
private List<Pin> pins;
private static final double LANE_LENGTH = 18.29; // 球道长度(m)
private static final double LANE_WIDTH = 1.07; // 球道宽度(m)
public BowlingGame() {
this.pins = new ArrayList<>();
initPins();
}
/**
* 初始化球瓶三角形排列
* 标准排列：第1排1个，第2排2个...第4排4个，共10个
*/
private void initPins() {
double pinSpacing = 0.305; // 球瓶间距(m)
double startY = LANE_LENGTH - 0.152; // 球瓶区起始Y坐标
double centerX = LANE_WIDTH / 2;
int pinCount = 0;
for (int row = 0; row < 4; row++) {
for (int col = 0; col <= row; col++) {
double x = centerX + (col - row / 2.0) * pinSpacing;
double y = startY - row * pinSpacing * Math.sqrt(3) / 2;
pins.add(new Pin(new Vector2D(x, y)));
pinCount++;
}
}
}
/**
* 设置投球参数
* @param startX 起始X位置(球道宽度比例，0.0-1.0)
* @param angle 投球角度(度，0为正前方，正值偏右)
* @param speed 初速度(m/s)
*/
public void throwBall(double startX, double angle, double speed) {
double rad = Math.toRadians(angle);
Vector2D pos = new Vector2D(startX * LANE_WIDTH, 0);
Vector2D vel = new Vector2D(speed * Math.sin(rad), speed * Math.cos(rad));
this.ball = new Ball(pos, vel);
}
/**
* 执行物理模拟，返回击倒球瓶数
*/
public int simulate() {
double dt = 0.001; // 时间步长1ms
double totalTime = 0;
List<Body> bodies = new ArrayList<>();
bodies.add(ball);
bodies.addAll(pins);
while (totalTime < 10.0) { // 最多模拟10秒
// 应用摩擦力减速
for (Body b : bodies) {
if (!b.active) continue;
double speed = b.velocity.length();
if (speed > 0.01) {
Vector2D friction = b.velocity.normalize().mul(-FRICTION * GRAVITY * dt);
b.velocity = b.velocity.add(friction);
if (b.velocity.length() < 0.01) {
b.velocity = new Vector2D(0, 0);
b.active = false;
}
}
}
// 检测并处理碰撞
PriorityQueue<Collision> collisions = new PriorityQueue<>();
for (int i = 0; i < bodies.size(); i++) {
for (int j = i + 1; j < bodies.size(); j++) {
Body a = bodies.get(i);
Body b = bodies.get(j);
if (!a.active || !b.active) continue;
double t = predictCollision(a, b);
if (t >= 0 && t < dt) {
collisions.add(new Collision(t, a, b));
}
}
}
// 处理碰撞事件
while (!collisions.isEmpty()) {
Collision col = collisions.poll();
resolveCollision(col.a, col.b);
}
// 更新位置
for (Body b : bodies) {
if (!b.active) continue;
b.position = b.position.add(b.velocity.mul(dt));
}
// 检查球瓶是否倒下
for (Pin pin : pins) {
if (!pin.standing) continue;
if (pin.velocity.length() > 0.5) {
pin.tiltAngle += pin.velocity.length() * dt * 10;
if (pin.tiltAngle > 15.0) {
pin.standing = false;
pin.active = false;
}
}
}
// 检查球是否出界或停止
if (!ball.active || ball.position.y > LANE_LENGTH ||
ball.position.x < 0 || ball.position.x > LANE_WIDTH) {
break;
}
totalTime += dt;
}
// 统计击倒数
int knocked = 0;
for (Pin pin : pins) {
if (!pin.standing) knocked++;
}
return knocked;
}
/**
* 预测两物体在dt时间内是否碰撞，返回碰撞时间(负值表示不碰撞)
*/
private double predictCollision(Body a, Body b) {
Vector2D relPos = b.position.sub(a.position);
Vector2D relVel = b.velocity.sub(a.velocity);
double r = a.radius + b.radius;
double c = relPos.dot(relPos) - r * r;
if (c < 0) return 0; // 已经重叠
double v = relVel.dot(relPos);
if (v >= 0) return -1; // 正在远离
double vv = relVel.dot(relVel);
double disc = v * v - vv * c;
if (disc < 0) return -1; // 无实数解
return (-v - Math.sqrt(disc)) / vv;
}
/**
* 解析碰撞，应用动量守恒
*/
private void resolveCollision(Body a, Body b) {
Vector2D normal = b.position.sub(a.position).normalize();
Vector2D relVel = b.velocity.sub(a.velocity);
double vRel = relVel.dot(normal);
if (vRel > 0) return; // 正在分离
double j = -(1 + RESTITUTION) * vRel / (1 / a.mass + 1 / b.mass);
Vector2D impulse = normal.mul(j);
a.velocity = a.velocity.sub(impulse.mul(1 / a.mass));
b.velocity = b.velocity.add(impulse.mul(1 / b.mass));
}
/**
* 贪心策略：寻找最优投球角度
* @return 最优角度和期望击倒数
*/
public double[] findOptimalAngle() {
double bestAngle = 0;
int bestScore = -1;
double startX = 0.5; // 从球道中央投掷
double speed = 7.0; // 初速度7m/s
for (double angle = -5.0; angle <= 5.0; angle += 0.5) {
// 重置游戏状态
pins.clear();
initPins();
throwBall(startX, angle, speed);
int score = simulate();
if (score > bestScore) {
bestScore = score;
bestAngle = angle;
}
}
return new double[]{bestAngle, bestScore};
}
public static void main(String[] args) {
BowlingGame game = new BowlingGame();
// 演示贪心策略
System.out.println("=== 保龄球贪心最优策略搜索 ===");
double[] result = game.findOptimalAngle();
System.out.printf("最优角度: %.1f°%n", result[0]);
System.out.printf("期望击倒: %.0f 个球瓶%n", result[1]);
// 演示单局投掷
System.out.println("\n=== 单局模拟演示 ===");
game = new BowlingGame();
game.throwBall(0.5, result[0], 7.0);
int score = game.simulate();
System.out.printf("实际击倒: %d 个球瓶%n", score);
System.out.print("球瓶状态: ");
for (int i = 0; i < game.pins.size(); i++) {
System.out.print(game.pins.get(i).standing ? "□" : "■");
}
System.out.println();
}
}
复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 碰撞检测 | $O(n^2)$ | $O(n)$ | 每帧检测所有物体对，$n$ 为物体总数 |
| 事件队列处理 | $O(k \log k)$ | $O(k)$ | $k$ 为单帧内碰撞事件数 |
| 贪心角度搜索 | $O(m \cdot T \cdot n^2)$ | $O(n)$ | $m$ 为角度枚举数，$T$ 为单局模拟步数 |
在实际保龄球场景中（1球+10瓶），$n=11$，贪心搜索约枚举 21 个角度，单局模拟约 5000 步，总计算量在 $10^6$ 量级，现代 CPU 可在毫秒级完成。
总结
本文实现了保龄球的核心物理模拟与 AI 决策系统。碰撞响应基于动量守恒定律，采用事件驱动机制处理连锁碰撞；贪心策略通过枚举投球角度并快速模拟评估，找出期望击倒数最大的方案。该框架可进一步扩展：引入旋转（hook）物理模型、使用蒙特卡洛方法评估随机因素、或通过强化学习训练更高级的投球策略。
