游戏场景里的数学问题
百战天虫（Worms）系列最迷人的地方在于那条弯曲的抛物线：你调整角度和力度，按下空格，炮弹在空中划出一道弧线，在重力和风速的作用下落在对手脚下。玩家在屏幕上看到的是”手感”，代码里其实是常微分方程初值问题。
如果只用中学物理的 x = v₀cosθ·t、y = v₀sinθ·t - ½gt² 消去 t 求落点，那么只要加入风力（水平恒定加速度）依然可以得到解析解；但百战天虫的经典设定里还有随速度变化的空气阻力（阻力与速度平方成正比），这时轨迹方程不再可积，必须做数值积分。
本文会实现三件事：
1. 用 RK4（四阶龙格-库塔） 对带二次风阻的弹道做高精度数值积分；
2. 用二次方程解析解处理无阻力/线性阻力情形，作为数值解的校验基准；
3. 在此之上做一个把”角度 + 力度”两维参数搜索出最优发射方案的小型求解器（给 AI 用）。
物理模型
炮弹质量 m、初速度 v₀、发射角 θ、重力 g、风速 w（水平分速度）、阻力系数 k。取阻力与相对速度平方成正比：
F_drag = -k·|v_rel|·v_rel 其中 v_rel = v_aircraft - w
拆成分量：
dvx/dt = -k·|v_rel|·(vx - w)
dvy/dt = -k·|v_rel|·vy - g
dx/dt = vx
dy/dt = vy
这是一个四维一阶方程组 y' = f(t, y)，标准 RK4 每步：
k1 = f(y_n)
k2 = f(y_n + h/2·k1)
k3 = f(y_n + h/2·k2)
k4 = f(y_n + h·k3)
y_{n+1} = y_n + h/6·(k1 + 2k2 + 2k3 + k4)
RK4 是四阶精度，误差 O(h⁴)，在游戏里用 h = 1/120 秒就能达到肉眼无法分辨的精度，且比 Euler 稳得多——后者在阻力存在时容易在高速段”抖”出错误轨迹。
落点求解：为什么还需要二次方程
地形是一条高度函数 height(x)。轨迹的落点是第一个满足 y ≤ height(x) 的采样点。如果只取采样点，误差就是”一帧的位移”，高速时可达几十像素。工程上常用割线插值：在越界的前后两个采样点上用线性插值估计精确交点的 x。
但纯解析路线依然有价值：当 k = 0（无阻力）时，轨迹是可积的。此时令 y = 0 得到
½gt² - (v₀ sinθ)t - y₀ = 0
t = [(v₀ sinθ) + sqrt((v₀ sinθ)² + 2g y₀)] / g
x = x₀ + v₀ cosθ · t
这就是”二次方程落点求解”。它有两个用途：一是给数值积分器做单元测试（k→0 时两者必须收敛到同一个值），二是给 AI 做解析初筛——先算出无阻力落点，把搜索范围收窄，再在局部调用昂贵的 RK4。
项目结构
worms-ballistics/
└── src/main/java/com/example/worms/
├── Vec2.java // 二维向量
├── Terrain.java // 地形与落点判定
├── BallisticsSolver.java // RK4 积分 + 二次方程解析解
├── Shot.java // 一次发射的参数与结果
└── AimSearch.java // 角度/力度二维搜索
Vec2 与 Terrain
package com.example.worms;
/** 不可变二维向量，避免积分过程中意外修改状态。 */
public final class Vec2 {
public final double x, y;
public Vec2(double x, double y) {
this.x = x;
this.y = y;
}
public Vec2 add(Vec2 o) { return new Vec2(x + o.x, y + o.y); }
public Vec2 sub(Vec2 o) { return new Vec2(x - o.x, y - o.y); }
public Vec2 mul(double s) { return new Vec2(x * s, y * s); }
public double len() { return Math.sqrt(x * x + y * y); }
@Override public String toString() {
return String.format("(%.2f, %.2f)", x, y);
}
}
package com.example.worms;
/**
* 地形。用"分段折线 + 若干圆形土丘"表示，height(x) 返回该位置的地表高度。
* 坐标约定：y 向下为正（屏幕坐标系），因此"高度更高"意味着 y 更小。
*/
public final class Terrain {
private final double[] xs; // 折线顶点 x，必须升序
private final double[] ys; // 折线顶点 y
private final double[][] hills; // {cx, cy, r} 圆形土丘
public Terrain(double[] xs, double[] ys, double[][] hills) {
this.xs = xs;
this.ys = ys;
this.hills = hills;
}
/** 地表 y 值（越小越"高"）。超出折线范围时取端点值。 */
public double height(double x) {
double y = interpolatePolyline(x);
// 圆形土丘会抬高地形：取"更小"的 y
for (double[] h : hills) {
double dx = x - h[0];
double r = h[2];
if (Math.abs(dx) <= r) {
double circleY = h[1] - Math.sqrt(r * r - dx * dx);
y = Math.min(y, circleY);
}
}
return y;
}
private double interpolatePolyline(double x) {
if (x <= xs[0]) return ys[0];
if (x >= xs[xs.length - 1]) return ys[ys.length - 1];
// 二分查找所在区间
int lo = 0, hi = xs.length - 1;
while (hi - lo > 1) {
int mid = (lo + hi) >>> 1;
if (xs[mid] <= x) lo = mid; else hi = mid;
}
double t = (x - xs[lo]) / (xs[hi] - xs[lo]);
return ys[lo] + t * (ys[hi] - ys[lo]);
}
}
核心：BallisticsSolver
package com.example.worms;
/**
* 弹道求解器。
* 同时提供两条路径：
* 1) rk4Trace —— 带二次风阻的数值积分（游戏实际使用）
* 2) analyticLanding —— 无阻力情形的解析解（用于校验与初筛）
*/
public final class BallisticsSolver {
/** 物理与世界参数。 */
public static final class Params {
public double gravity = 900.0; // 像素/秒²
public double dragK = 0.0012; // 阻力系数，0 表示无阻力
public double wind = 0.0; // 风速（水平分速度，向右为正）
public double dt = 1.0 / 240.0; // 积分步长
public int maxSteps = 20000;
}
/** 一次积分的结果。 */
public static final class Result {
public final double landX, landY; // 落点
public final double flightTime; // 飞行时间
public final boolean hitTerrain; // 是否撞到地形（否则飞出界）
public Result(double x, double y, double t, boolean hit) {
landX = x; landY = y; flightTime = t; hitTerrain = hit;
}
@Override public String toString() {
return String.format("land=(%.2f,%.2f) t=%.3fs hit=%s",
landX, landY, flightTime, hitTerrain);
}
}
private final Params p;
private final Terrain terrain;
public BallisticsSolver(Params p, Terrain terrain) {
this.p = p;
this.terrain = terrain;
}
/**
* 状态向量 y = {x, y, vx, vy} 的导数。
* 阻力与相对空气速度的平方成正比，方向与相对速度相反。
*/
private double[] deriv(double[] s) {
double vx = s[2], vy = s[3];
double relVx = vx - p.wind;
double relVy = vy;
double speed = Math.sqrt(relVx * relVx + relVy * relVy);
// 阻力加速度 = -k·|v_rel|·v_rel / m，这里把 m 归一化为 1
double ax = -p.dragK * speed * relVx;
double ay = -p.dragK * speed * relVy + p.gravity;
return new double[]{ vx, vy, ax, ay };
}
/**
* 四阶龙格-库塔积分，返回轨迹与落点。
* @param x0,y0 发射点
* @param angleDeg 发射角（度，向上为正）
* @param power 初速度
*/
public Result rk4Trace(double x0, double y0, double angleDeg, double power,
java.util.List<Vec2> traceOut) {
double rad = Math.toRadians(angleDeg);
double[] s = {
x0, y0,
power * Math.cos(rad),
-power * Math.sin(rad) // y 向下为正，因此向上是负
};
double t = 0;
double prevX = s[0], prevY = s[1];
double prevF = s[1] - terrain.height(s[0]); // 与地表的"穿透量"
for (int step = 0; step < p.maxSteps; step++) {
double[] k1 = deriv(s);
double[] s2 = addScaled(s, k1, p.dt / 2);
double[] k2 = deriv(s2);
double[] s3 = addScaled(s, k2, p.dt / 2);
double[] k3 = deriv(s3);
double[] s4 = addScaled(s, k3, p.dt);
double[] k4 = deriv(s4);
for (int i = 0; i < 4; i++) {
s[i] += p.dt / 6.0 * (k1[i] + 2 * k2[i] + 2 * k3[i] + k4[i]);
}
t += p.dt;
double curF = s[1] - terrain.height(s[0]);
if (traceOut != null) traceOut.add(new Vec2(s[0], s[1]));
// 越界判定：这一步首次穿入地表
if (curF >= 0) {
// 用前后两步做线性插值，把落点精确到子像素级
double ratio = prevF / (prevF - curF); // prevF<0, curF>=0
double lx = prevX + ratio * (s[0] - prevX);
double ly = terrain.height(lx);
return new Result(lx, ly, t - p.dt + ratio * p.dt, true);
}
prevF = curF;
prevX = s[0];
prevY = s[1];
// 飞出世界边界
if (s[0] < -5000 || s[0] > 20000 || s[1] > 5000) break;
}
return new Result(s[0], s[1], t, false);
}
private static double[] addScaled(double[] s, double[] d, double h) {
return new double[]{ s[0] + h * d[0], s[1] + h * d[1],
s[2] + h * d[2], s[3] + h * d[3] };
}
/**
* 无阻力解析落点：解二次方程 ½gt² - (v₀ sinθ)t - y₀ = 0。
* 注意坐标系 y 向下为正，因此"下落"是 +y 方向。
* 返回 {landX, flightTime}；若解无意义返回 null。
*/
public double[] analyticLanding(double x0, double y0, double angleDeg, double power) {
double rad = Math.toRadians(angleDeg);
double vx = power * Math.cos(rad);
double vy = -power * Math.sin(rad); // 向上为负
// 以 y0 为高度基准：落到 y=0 平面
double g = p.gravity;
double a = 0.5 * g;
double b = vy;
double c = y0;
double disc = b * b - 4 * a * c;
if (disc < 0) return null;
// 取较大的正根（炮弹最终落地的那一次穿越）
double t = (-b + Math.sqrt(disc)) / (2 * a);
if (t < 0) t = (-b - Math.sqrt(disc)) / (2 * a);
if (t < 0) return null;
return new double[]{ x0 + vx * t, t };
}
}
瞄准搜索：给 AI 用的二维参数搜索
有了精确落点函数，AI 的任务变成：在 (角度, 力度) 二维空间里找一组参数，使落点尽量靠近目标。目标函数非凸、地形多峰，纯梯度法不可靠。实战做法是分层：
package com.example.worms;
import java.util.*;
/** 在 (角度, 力度) 空间搜索最优发射方案。 */
public final class AimSearch {
private final BallisticsSolver solver;
public AimSearch(BallisticsSolver solver) {
this.solver = solver;
}
public static final class Shot {
public final double angle, power, landX, score;
Shot(double a, double pw, double lx, double s) {
angle = a; power = pw; landX = lx; score = s;
}
@Override public String toString() {
return String.format("angle=%.1f° power=%.1f land=%.1f score=%.1f",
angle, power, landX, score);
}
}
/**
* 粗网格 + 局部精修的混合搜索。
* @param targetX 目标 x 坐标
* @param tolerance 命中半径
*/
public Shot search(double fromX, double fromY, double targetX, double tolerance) {
Shot best = null;
// 阶段1：粗网格。角度 5°~85°，力度 200~1200
for (double ang = 5; ang <= 85; ang += 2) {
for (double pw = 200; pw <= 1200; pw += 20) {
var r = solver.rk4Trace(fromX, fromY, ang, pw, null);
if (!r.hitTerrain) continue;
double err = Math.abs(r.landX - targetX);
if (best == null || err < best.score) {
best = new Shot(ang, pw, r.landX, err);
}
if (err <= tolerance) return best; // 早期退出
}
}
if (best == null) return null;
// 阶段2：以粗网格最优点为中心做黄金分割精修（先角后力）
double lo = best.angle - 2, hi = best.angle + 2;
for (int i = 0; i < 12; i++) { // 角度精修
double mid = (lo + hi) / 2;
double mLand = landAt(fromX, fromY, mid, best.power);
double rLand = landAt(fromX, fromY, hi, best.power);
if (Math.abs(mLand - targetX) < Math.abs(rLand - targetX)) hi = mid;
else lo = mid;
}
double refinedAngle = (lo + hi) / 2;
// 力度精修：落点随力度单调递增（其它条件固定），可直接二分
double pLo = Math.max(100, best.power - 60);
double pHi = best.power + 60;
for (int i = 0; i < 20; i++) {
double mid = (pLo + pHi) / 2;
double land = landAt(fromX, fromY, refinedAngle, mid);
if (land < targetX) pLo = mid; else pHi = mid;
}
double refinedPower = (pLo + pHi) / 2;
double finalLand = landAt(fromX, fromY, refinedAngle, refinedPower);
return new Shot(refinedAngle, refinedPower, finalLand,
Math.abs(finalLand - targetX));
}
private double landAt(double x, double y, double ang, double pw) {
var r = solver.rk4Trace(x, y, ang, pw, null);
return r.hitTerrain ? r.landX : Double.NaN;
}
}
注意阶段 2 的力度二分：在固定角度下，”落点 x 关于力度单调递增”这一性质在实践中成立（力度越大飞得越远），因此二分有效；但如果地形复杂、存在”打在山脊上”的非单调区间，就需要退化成三分搜索或多起点重试。
可运行的入口
package com.example.worms;
import java.util.ArrayList;
import java.util.List;
public final class Main {
public static void main(String[] args) {
// 一条起伏地形
Terrain terrain = new Terrain(
new double[]{-500, 200, 700, 1200, 1800, 2400, 3000},
new double[]{600, 620, 540, 700, 660, 760, 720},
new double[][]{{1500, 600, 120}});
BallisticsSolver.Params p = new BallisticsSolver.Params();
p.wind = 35; // 顺风
p.dragK = 0.0012;
BallisticsSolver solver = new BallisticsSolver(p, terrain);
// 1) 数值积分 vs 解析解（把阻力置零后对比）
BallisticsSolver.Params noDrag = new BallisticsSolver.Params();
noDrag.dragK = 0;
noDrag.wind = 0;
BallisticsSolver s2 = new BallisticsSolver(noDrag, terrain);
double[] analytic = s2.analyticLanding(200, 620, 45, 900);
var numeric = s2.rk4Trace(200, 620, 45, 900, null);
System.out.println("analytic land x = " + analytic[0]);
System.out.println("rk4 land x = " + numeric.landX);
// 2) 带风阻的完整轨迹（打印关键采样）
List<Vec2> trace = new ArrayList<>();
var res = solver.rk4Trace(200, 620, 40, 950, trace);
System.out.println("with wind+drag: " + res);
int stride = Math.max(1, trace.size() / 12);
for (int i = 0; i < trace.size(); i += stride) {
System.out.println(" t≈" + (i * p.dt) + " " + trace.get(i));
}
// 3) AI 瞄准
AimSearch aim = new AimSearch(solver);
Shot best = aim.search(200, 620, 1600, 15);
System.out.println("best shot: " + best);
}
}
运行后你会在控制台看到解析解与 RK4 的落点相差不到 1 像素（说明积分器正确），随后是一条被侧风推偏的弧线，最后是 AI 给出的”41° / 983″这类可直接喂给游戏引擎的发射参数。
复杂度与精度分析
| 环节 | 复杂度 | 说明 |
|---|---|---|
| 单次 RK4 轨迹 | O(N) | N = 飞行时间 / dt，典型 100~300 步 |
| 粗网格搜索 | O(A · P · N) | A≈40 角度档、P≈50 力度档，约 60 万次浮点步 |
| 局部精修 | O(log(1/ε) · N) | 二分/黄金分割，十几轮即收敛 |
精度上，RK4 的局部误差 O(h⁵)、全局误差 O(h⁴)；dt 减半误差降为 1/16。若追求更高精度可换 自适应步长 RK45（Dormand-Prince），在弹道平直段自动放大步长，整体开销反而下降。
若把落点误差当成”命中率”，还有一个工程细节：同一条轨迹只算一次。游戏中玩家连续微调角度时，可以对上一帧的轨迹做增量重积分（前 90% 顶点不变），这在百战天虫的 AI 批量试算里能省掉一个数量级的计算。
小结
百战天虫的”抛物线”背后是一个标准的常微分方程初值问题。用 RK4 处理二次风阻得到稳定高精度的轨迹，用二次方程解析解做校验与初筛，再在 (角度, 力度) 空间做”粗网格 + 局部精修”的两级搜索，就构成了一套可用的炮弹 AI。这套结构可以平移到任何抛射类游戏——愤怒的小鸟、坦克大战、弓箭传说，差别只在阻力模型与地形表达。
