赛车游戏是电子游戏史上最具代表性的类型之一，其核心乐趣不仅在于操控手感，更在于赛道设计的艺术性与AI寻路的智能性。本文将带你从零开始，用Java实现一个包含贝塞尔曲线（Bézier Curve） procedural 赛道生成与贪心最优赛车线计算的极简赛车游戏框架。读完本文，你将掌握三次贝塞尔曲线的数学原理、赛道网格化采样方法，以及基于贪心策略的逐段最优路径逼近算法。
一、问题建模：赛道是什么？
在算法层面，一条赛车赛道可以抽象为两条平行的三维曲线——左边界与右边界，中间区域为可行驶路面。为了简化问题，本文将赛道限制在二维平面上，并用以下数据结构描述：
- 中心线（Center Line）：赛道的几何中轴线，由一系列贝塞尔曲线段拼接而成。
- 路宽（Track Width）：垂直于中心线向两侧扩展的固定距离。
- 赛车线（Racing Line）：车辆实际行驶的最优路径，通常比中心线更短、弯心更靠内。
我们的目标分为两步：
1. 生成阶段：给定若干控制点，用三次贝塞尔曲线生成平滑的中心线，并计算左右边界。
2. 寻路阶段：在生成的赛道上，用贪心策略逐段计算使总曲率最小、总路程最短的赛车线。
二、贝塞尔曲线：平滑赛道的数学基础
2.1 三次贝塞尔曲线公式
给定四个控制点 P0, P1, P2, P3，三次贝塞尔曲线上任意一点 B(t) 的参数方程为：
B(t) = (1-t)³·P0 + 3(1-t)²t·P1 + 3(1-t)t²·P2 + t³·P3 ， t ∈ [0,1]
该曲线始终经过起点 P0 和终点 P3，而 P1、P2 用于控制曲线的切线方向与弯曲程度。将多段三次贝塞尔曲线首尾相连（前一段的终点作为下一段的起点），即可得到一条曲率连续的平滑赛道中心线。
2.2 一阶导数与法向量
为了从中心线向两侧扩展出路宽，需要计算每个采样点处的法向量。对 B(t) 求导得到切线方向：
B'(t) = 3(1-t)²(P1-P0) + 6(1-t)t(P2-P1) + 3t²(P3-P2)
将切向量逆时针旋转90度并单位化，即得到该点的单位法向量 N(t)。左边界点为 B(t) + width·N(t)，右边界点为 B(t) - width·N(t)。
三、Java 实现：赛道生成引擎
3.1 核心数据结构
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.List;
/**
* 二维向量工具类，支持加减、数乘、点积、叉积、旋转与单位化
*/
class Vec2 {
public 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 k) { return new Vec2(x * k, y * k); }
public double dot(Vec2 o) { return x * o.x + y * o.y; }
public double cross(Vec2 o) { return x * o.y - y * o.x; }
public double len() { return Math.sqrt(x * x + y * y); }
public Vec2 normalize() {
double l = len();
if (l < 1e-9) return new Vec2(0, 0);
return new Vec2(x / l, y / l);
}
/** 逆时针旋转90度 */
public Vec2 perp() { return new Vec2(-y, x); }
@Override
public String toString() { return String.format("(%.3f, %.3f)", x, y); }
}
/**
* 三次贝塞尔曲线段，由四个控制点定义
*/
class CubicBezier {
private final Vec2 p0, p1, p2, p3;
public CubicBezier(Vec2 p0, Vec2 p1, Vec2 p2, Vec2 p3) {
this.p0 = p0; this.p1 = p1; this.p2 = p2; this.p3 = p3;
}
/**
* 计算参数 t 处的曲线点 B(t)
*/
public Vec2 pointAt(double t) {
double u = 1 - t;
double u2 = u * u, u3 = u2 * u;
double t2 = t * t, t3 = t2 * t;
return p0.mul(u3)
.add(p1.mul(3 * u2 * t))
.add(p2.mul(3 * u * t2))
.add(p3.mul(t3));
}
/**
* 计算参数 t 处的一阶导数 B'(t)，即切线方向
*/
public Vec2 derivativeAt(double t) {
double u = 1 - t;
Vec2 d0 = p1.sub(p0).mul(3 * u * u);
Vec2 d1 = p2.sub(p1).mul(6 * u * t);
Vec2 d2 = p3.sub(p2).mul(3 * t * t);
return d0.add(d1).add(d2);
}
/**
* 计算参数 t 处的单位法向量（逆时针旋转切线90度后单位化）
*/
public Vec2 normalAt(double t) {
return derivativeAt(t).perp().normalize();
}
}
/**
* 赛道采样点，包含中心点、左右边界与单位法向量
*/
class TrackPoint {
public Vec2 center; // 中心线点
public Vec2 left; // 左边界点
public Vec2 right; // 右边界点
public Vec2 normal; // 指向左边界方向的单位法向量
public TrackPoint(Vec2 center, Vec2 left, Vec2 right, Vec2 normal) {
this.center = center; this.left = left; this.right = right; this.normal = normal;
}
}
3.2 赛道生成器
/**
* 赛道生成器：将控制点序列转换为带左右边界的采样点序列
*/
class TrackGenerator {
private final double trackWidth; // 赛道半宽（单侧宽度）
private final int samplesPerSegment; // 每段贝塞尔曲线的采样数
public TrackGenerator(double trackWidth, int samplesPerSegment) {
this.trackWidth = trackWidth;
this.samplesPerSegment = samplesPerSegment;
}
/**
* 根据控制点列表生成赛道。
* 控制点数量须 >= 4，且采用连续三次贝塞尔拼接策略：
* 每段使用 [P[i], P[i+1], P[i+2], P[i+3]] 作为控制点，
* 下一段起点复用上一段终点，保证曲线连续。
*/
public List<TrackPoint> generateTrack(List<Vec2> controlPoints) {
if (controlPoints.size() < 4) {
throw new IllegalArgumentException("控制点至少4个");
}
List<TrackPoint> track = new ArrayList<>();
int n = controlPoints.size();
// 采用循环赛道模式：最后几个控制点与开头衔接
for (int i = 0; i < n - 3; i++) {
CubicBezier bez = new CubicBezier(
controlPoints.get(i),
controlPoints.get(i + 1),
controlPoints.get(i + 2),
controlPoints.get(i + 3)
);
// 每段均匀采样；最后一段包含 t=1.0 的终点
int steps = (i == n - 4) ? samplesPerSegment + 1 : samplesPerSegment;
for (int s = 0; s < steps; s++) {
double t = s / (double) samplesPerSegment;
Vec2 center = bez.pointAt(t);
Vec2 normal = bez.normalAt(t);
Vec2 left = center.add(normal.mul(trackWidth));
Vec2 right = center.sub(normal.mul(trackWidth));
track.add(new TrackPoint(center, left, right, normal));
}
}
return track;
}
}
四、贪心最优赛车线算法
4.1 算法思想
人类车手过弯的直觉是：尽量贴内道、减少转向幅度、出弯尽早加速。将其抽象为算法语言，即：
- 离散化：将赛道宽度方向离散为若干候选偏移位置（如左边界、中心线、右边界，或更细的粒度）。
- 逐段决策：从起点开始，对于当前赛道段，评估每个候选位置到达下一个候选位置的”代价”。
- 贪心选择：每次选择局部代价最小的转移，作为赛车线在该段的走向。
本文定义的局部代价函数包含三项：
– 路程代价：当前候选点到下一段候选点的欧氏距离。
– 曲率代价：当前点与下一点形成的转向角度，角度越大代价越高。
– 偏离代价：当前点距离中心线的横向偏移，鼓励车辆尽量保持在路面内。
4.2 候选点生成与贪心搜索
/**
* 赛车线规划器：基于贪心策略的逐段最优路径计算
*/
class RacingLinePlanner {
private final int lateralSamples; // 横向采样数（如 5 表示从左到右 5 个候选位置）
public RacingLinePlanner(int lateralSamples) {
this.lateralSamples = Math.max(2, lateralSamples);
}
/**
* 对每一段赛道生成横向候选点。
* lateralRatio 为 [-1, 1]，-1 表示贴右边界，1 表示贴左边界，0 为中心线。
*/
private Vec2 getCandidate(TrackPoint tp, double lateralRatio) {
// center + normal * (lateralRatio * halfWidth)
// tp.normal 指向左边界，lateralRatio=1 时到达左边界
double halfWidth = tp.center.sub(tp.right).len();
return tp.center.add(tp.normal.mul(lateralRatio * halfWidth));
}
/**
* 计算从当前候选点到下一候选点的局部代价。
* 代价 = wDist * distance + wAngle * anglePenalty + wDev * deviationPenalty
*/
private double cost(Vec2 from, Vec2 to, Vec2 nextCenter,
double wDist, double wAngle, double wDev) {
double dist = to.sub(from).len();
// 转向角度惩罚：用向量夹角近似曲率
Vec2 dir1 = to.sub(from);
Vec2 dir2 = nextCenter.sub(to); // 用下一段中心线方向近似预期方向
double angle = 0;
if (dir1.len() > 1e-9 && dir2.len() > 1e-9) {
double cos = dir1.normalize().dot(dir2.normalize());
cos = Math.max(-1.0, Math.min(1.0, cos));
angle = Math.acos(cos); // 弧度制，0~π
}
// 偏离中心线惩罚：到下一中心线的距离
double deviation = to.sub(nextCenter).len();
return wDist * dist + wAngle * angle + wDev * deviation;
}
/**
* 贪心计算赛车线。
* 返回的列表长度等于 track.size()，每个元素为该段选定的赛车线点。
*/
public List<Vec2> computeRacingLine(List<TrackPoint> track,
double wDist, double wAngle, double wDev) {
int n = track.size();
List<Vec2> racingLine = new ArrayList<>(n);
// 预计算横向采样比例：均匀分布在 [-1, 1]
double[] ratios = new double[lateralSamples];
for (int i = 0; i < lateralSamples; i++) {
ratios[i] = -1.0 + 2.0 * i / (lateralSamples - 1);
}
// 第0段：选择最靠近中心线的位置作为起点
int bestIdx = lateralSamples / 2;
racingLine.add(getCandidate(track.get(0), ratios[bestIdx]));
// 逐段贪心决策
for (int i = 0; i < n - 1; i++) {
Vec2 current = racingLine.get(i);
TrackPoint nextTp = track.get((i + 1) % n);
TrackPoint nextNextTp = track.get((i + 2) % n);
double minCost = Double.MAX_VALUE;
int chosenIdx = bestIdx;
for (int j = 0; j < lateralSamples; j++) {
Vec2 candidate = getCandidate(nextTp, ratios[j]);
double c = cost(current, candidate, nextNextTp.center, wDist, wAngle, wDev);
if (c < minCost) {
minCost = c;
chosenIdx = j;
}
}
racingLine.add(getCandidate(nextTp, ratios[chosenIdx]));
bestIdx = chosenIdx;
}
return racingLine;
}
}
五、完整可运行示例
以下 Main 类将上述组件串联，生成一条环形赛道并计算贪心赛车线，同时在控制台打印关键数据：
public class RacingGameDemo {
public static void main(String[] args) {
// 1. 定义控制点：一个带 S 弯与发夹弯的环形赛道
List<Vec2> controlPoints = new ArrayList<>();
controlPoints.add(new Vec2(100, 300));
controlPoints.add(new Vec2(200, 100));
controlPoints.add(new Vec2(400, 100));
controlPoints.add(new Vec2(500, 300));
controlPoints.add(new Vec2(600, 500));
controlPoints.add(new Vec2(400, 600));
controlPoints.add(new Vec2(200, 500));
controlPoints.add(new Vec2(150, 400));
// 为了让赛道闭合，复制前几个点到末尾
controlPoints.add(new Vec2(100, 300));
controlPoints.add(new Vec2(200, 100));
controlPoints.add(new Vec2(400, 100));
// 2. 生成赛道
TrackGenerator generator = new TrackGenerator(40.0, 20);
List<TrackPoint> track = generator.generateTrack(controlPoints);
System.out.println("赛道总采样点数: " + track.size());
// 3. 计算贪心赛车线
RacingLinePlanner planner = new RacingLinePlanner(7); // 横向7个候选点
List<Vec2> racingLine = planner.computeRacingLine(track, 1.0, 5.0, 0.5);
// 4. 评估：计算赛车线总长度与平均曲率
double totalLen = 0;
double totalAngle = 0;
for (int i = 0; i < racingLine.size() - 1; i++) {
Vec2 a = racingLine.get(i);
Vec2 b = racingLine.get((i + 1) % racingLine.size());
totalLen += b.sub(a).len();
Vec2 c = racingLine.get((i + 2) % racingLine.size());
Vec2 d1 = b.sub(a).normalize();
Vec2 d2 = c.sub(b).normalize();
double cos = Math.max(-1.0, Math.min(1.0, d1.dot(d2)));
totalAngle += Math.acos(cos);
}
System.out.printf("赛车线总长度: %.2f%n", totalLen);
System.out.printf("总转向角: %.4f rad%n", totalAngle);
// 5. 同时计算中心线做对比
double centerLen = 0;
for (int i = 0; i < track.size() - 1; i++) {
Vec2 a = track.get(i).center;
Vec2 b = track.get((i + 1) % track.size()).center;
centerLen += b.sub(a).len();
}
System.out.printf("中心线总长度: %.2f%n", centerLen);
System.out.printf("赛车线缩短比例: %.2f%%%n", (1 - totalLen / centerLen) * 100);
}
}
六、算法复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 贝塞尔曲线采样 | O(S × N) | O(S × N) | S 为每段采样数，N 为控制点构成的段数 |
| 贪心赛车线计算 | O(L × M²) | O(L × M) | L 为赛道总采样点数，M 为横向候选数 |
| 整体框架 | O(S × N + L × M²) | O(S × N) | 实际运行时 M 通常取 3~7，可视为常数 |
贪心算法的优势在于线性时间复杂度（横向采样数 M 固定时），适合实时游戏场景。其缺点在于缺乏全局最优保证——某些连续弯道组合可能存在”当前最优导致后续陷入劣解”的情况。若需更高精度，可将贪心策略升级为 动态规划（DP） 或 A* 搜索，在状态空间 (段索引, 横向位置) 上寻找全局最优。
七、扩展方向
- 闭合赛道与循环索引：真实赛车多为环形跑道，处理时建议将赛道数组视为循环链表，最后一段与第一段平滑衔接。
- 动态障碍物与实时重规划：若赛道上出现其他车辆或油渍，可每隔若干帧重新运行贪心规划器，将障碍物建模为局部高代价区域。
- 物理引擎耦合：将赛车线输出给简单的车辆动力学模型（如自行车模型），结合速度剖面规划（braking point / apex / exit acceleration），即可得到更逼真的AI驾驶行为。
- 多段贝塞尔 G1/G2 连续：若控制点间距差异较大，可在拼接处引入 Catmull-Rom 样条或 B-样条，保证曲率连续，避免视觉上的”折痕”。
八、总结
本文从数学原理到Java工程实现，完整演示了赛车游戏中两大核心算法：
– 贝塞尔曲线负责平滑、可控的赛道 procedural 生成；
– 贪心策略在离散化的状态空间中快速逼近最优赛车线。
两者结合，既保证了赛道的美观与多样性，又让AI车辆能在毫秒级时间内做出合理的过弯决策。你可以在此基础上叠加更复杂的路径搜索（A*、DP）或车辆物理模型，逐步构建出完整的赛车AI系统。
