节奏大师是一款经典的音乐节奏游戏，玩家需要根据音乐节奏在特定时间点按下对应按键。本文用Java实现节奏游戏的核心判定引擎，包括音符时序解析、动态时间规整（DTW）对齐以及最优按键序列的判定算法。
游戏机制建模
节奏游戏的核心数据结构包括：
– 音符序列：每个音符包含轨道编号、目标时间点、音符类型（单点、长按、滑动）
– 玩家输入：每次按键包含轨道编号和实际时间戳
– 判定窗口：根据时间差将输入判定为Perfect/Great/Good/Miss
public class RhythmGameEngine {
// 判定等级
enum Judgment { PERFECT, GREAT, GOOD, BAD, MISS }
// 音符类型
enum NoteType { TAP, HOLD, SLIDE }
static class Note {
int track; // 轨道编号（0-3或0-6）
long targetTime; // 目标时间戳（毫秒）
NoteType type;
long duration; // 长按持续时间（仅限HOLD类型）
Note(int track, long targetTime, NoteType type, long duration) {
this.track = track;
this.targetTime = targetTime;
this.type = type;
this.duration = duration;
}
}
static class InputEvent {
int track;
long actualTime;
boolean pressed; // true=按下, false=松开
InputEvent(int track, long time, boolean pressed) {
this.track = track;
this.actualTime = time;
this.pressed = pressed;
}
}
// 判定窗口（毫秒）
static final int PERFECT_WINDOW = 45;
static final int GREAT_WINDOW = 90;
static final int GOOD_WINDOW = 135;
static final int BAD_WINDOW = 180;
private final List<Note> notes;
private final List<InputEvent> inputs;
public RhythmGameEngine(List<Note> notes) {
this.notes = new ArrayList<>(notes);
this.inputs = new ArrayList<>();
}
/**
* 接收玩家输入
*/
public void onInput(InputEvent event) {
inputs.add(event);
}
}
动态时间规整（DTW）对齐
由于玩家可能整体偏移（提前或延后按键），直接使用固定窗口判定会导致系统性误差。DTW算法可以找到两个时间序列之间的最优非线性对齐，从而自适应地调整判定窗口。
public class RhythmGameEngine {
/**
* 使用DTW计算玩家输入与目标音符的最优对齐
* @param targetSequence 目标时间点序列
* @param actualSequence 实际输入时间点序列
* @return 对齐路径和总扭曲代价
*/
public DTWResult computeDTWAlignment(long[] targetSequence, long[] actualSequence) {
int n = targetSequence.length;
int m = actualSequence.length;
// 代价矩阵：|target[i] - actual[j]|
double[][] cost = new double[n + 1][m + 1];
for (int i = 0; i <= n; i++) Arrays.fill(cost[i], Double.POSITIVE_INFINITY);
cost[0][0] = 0;
// 累积代价矩阵
double[][] dp = new double[n + 1][m + 1];
for (int i = 0; i <= n; i++) Arrays.fill(dp[i], Double.POSITIVE_INFINITY);
dp[0][0] = 0;
// DTW核心递推：min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + cost
for (int i = 1; i <= n; i++) {
for (int j = Math.max(1, i - m / 2); j <= Math.min(m, i + m / 2); j++) {
double diff = Math.abs(targetSequence[i - 1] - actualSequence[j - 1]);
dp[i][j] = diff + Math.min(
dp[i - 1][j], // 插入：目标音符无对应输入
Math.min(
dp[i][j - 1], // 删除：多余输入
dp[i - 1][j - 1] // 匹配
)
);
}
}
// 回溯找最优路径
List<int[]> path = new ArrayList<>();
int i = n, j = m;
while (i > 0 || j > 0) {
path.add(new int[]{i, j});
if (i == 0) {
j--;
} else if (j == 0) {
i--;
} else {
double diag = dp[i - 1][j - 1];
double up = dp[i - 1][j];
double left = dp[i][j - 1];
if (diag <= up && diag <= left) {
i--; j--;
} else if (up <= left) {
i--;
} else {
j--;
}
}
}
Collections.reverse(path);
return new DTWResult(path, dp[n][m] / path.size());
}
/**
* 基于DTW对齐结果计算每帧的时间偏移量
* 用于动态调整判定窗口
*/
public double[] computeTimeOffsets(long[] targetSequence, long[] actualSequence) {
DTWResult dtw = computeDTWAlignment(targetSequence, actualSequence);
double[] offsets = new double[targetSequence.length];
Arrays.fill(offsets, 0.0);
for (int[] pair : dtw.path) {
int ti = pair[0] - 1;
int ai = pair[1] - 1;
if (ti >= 0 && ti < targetSequence.length &&
ai >= 0 && ai < actualSequence.length) {
offsets[ti] = actualSequence[ai] - targetSequence[ti];
}
}
// 平滑处理：使用滑动窗口平均
return smoothOffsets(offsets, 5);
}
/**
* 滑动窗口平滑偏移量
*/
private double[] smoothOffsets(double[] offsets, int windowSize) {
double[] smoothed = new double[offsets.length];
for (int i = 0; i < offsets.length; i++) {
double sum = 0;
int count = 0;
for (int j = Math.max(0, i - windowSize / 2);
j <= Math.min(offsets.length - 1, i + windowSize / 2); j++) {
sum += offsets[j];
count++;
}
smoothed[i] = sum / count;
}
return smoothed;
}
static class DTWResult {
List<int[]> path;
double averageCost;
DTWResult(List<int[]> path, double cost) {
this.path = path;
this.averageCost = cost;
}
}
}
最优按键序列判定
对于多轨道节奏游戏，玩家输入可能与目标音符存在轨道错乱。我们需要找到输入序列与音符序列之间的最优匹配，使整体判定得分最高。
public class RhythmGameEngine {
/**
* 计算单次输入的判定结果
* 考虑DTW计算出的动态偏移量
*/
public Judgment judgeInput(Note note, InputEvent input, double timeOffset) {
if (note.track != input.track) return Judgment.MISS;
// 应用动态偏移修正
long adjustedTarget = note.targetTime + (long) timeOffset;
long diff = Math.abs(input.actualTime - adjustedTarget);
if (diff <= PERFECT_WINDOW) return Judgment.PERFECT;
if (diff <= GREAT_WINDOW) return Judgment.GREAT;
if (diff <= GOOD_WINDOW) return Judgment.GOOD;
if (diff <= BAD_WINDOW) return Judgment.BAD;
return Judgment.MISS;
}
/**
* 使用匈牙利算法求解最优输入-音符匹配
* 最大化总判定得分
*/
public MatchResult findOptimalMatching(List<Note> noteBatch,
List<InputEvent> inputBatch) {
int n = noteBatch.size();
int m = inputBatch.size();
int size = Math.max(n, m);
// 构建得分矩阵
int[][] scoreMatrix = new int[size][size];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scoreMatrix[i][j] = computeMatchScore(noteBatch.get(i), inputBatch.get(j));
}
}
// 匈牙利算法求最大权匹配
HungarianAlgorithm ha = new HungarianAlgorithm(scoreMatrix);
int[] match = ha.execute();
List<NoteJudgment> results = new ArrayList<>();
int totalScore = 0;
for (int i = 0; i < n; i++) {
int j = match[i];
if (j < m && scoreMatrix[i][j] > 0) {
Judgment jdg = scoreToJudgment(scoreMatrix[i][j]);
results.add(new NoteJudgment(noteBatch.get(i), inputBatch.get(j), jdg));
totalScore += scoreMatrix[i][j];
} else {
results.add(new NoteJudgment(noteBatch.get(i), null, Judgment.MISS));
}
}
return new MatchResult(results, totalScore);
}
/**
* 计算音符与输入的匹配得分
*/
private int computeMatchScore(Note note, InputEvent input) {
if (note.track != input.track) return 0;
long diff = Math.abs(input.actualTime - note.targetTime);
if (diff <= PERFECT_WINDOW) return 100;
if (diff <= GREAT_WINDOW) return 80;
if (diff <= GOOD_WINDOW) return 50;
if (diff <= BAD_WINDOW) return 20;
return 0;
}
private Judgment scoreToJudgment(int score) {
return switch (score) {
case 100 -> Judgment.PERFECT;
case 80 -> Judgment.GREAT;
case 50 -> Judgment.GOOD;
case 20 -> Judgment.BAD;
default -> Judgment.MISS;
};
}
static class NoteJudgment {
Note note;
InputEvent input;
Judgment judgment;
NoteJudgment(Note n, InputEvent i, Judgment j) {
this.note = n;
this.input = i;
this.judgment = j;
}
}
static class MatchResult {
List<NoteJudgment> judgments;
int totalScore;
MatchResult(List<NoteJudgment> j, int s) {
this.judgments = j;
this.totalScore = s;
}
}
}
匈牙利算法实现
/**
* 匈牙利算法：求解指派问题（最大权匹配）
*/
public class HungarianAlgorithm {
private final int[][] costMatrix;
private final int n;
private final int[] matchX, matchY;
private final int[] lx, ly;
private final boolean[] sx, sy;
private final int[] slack;
private final int[] slackX;
public HungarianAlgorithm(int[][] matrix) {
this.n = matrix.length;
this.costMatrix = matrix;
this.matchX = new int[n];
this.matchY = new int[n];
this.lx = new int[n];
this.ly = new int[n];
this.sx = new boolean[n];
this.sy = new boolean[n];
this.slack = new int[n];
this.slackX = new int[n];
}
public int[] execute() {
Arrays.fill(matchX, -1);
Arrays.fill(matchY, -1);
Arrays.fill(ly, 0);
// 初始化顶标
for (int i = 0; i < n; i++) {
lx[i] = Integer.MIN_VALUE;
for (int j = 0; j < n; j++) {
lx[i] = Math.max(lx[i], costMatrix[i][j]);
}
}
// 为每个X节点找匹配
for (int x = 0; x < n; x++) {
Arrays.fill(slack, Integer.MAX_VALUE);
while (true) {
Arrays.fill(sx, false);
Arrays.fill(sy, false);
if (dfs(x)) break;
// 更新顶标
int delta = Integer.MAX_VALUE;
for (int y = 0; y < n; y++) {
if (!sy[y] && slack[y] < delta) {
delta = slack[y];
}
}
for (int i = 0; i < n; i++) {
if (sx[i]) lx[i] -= delta;
if (sy[i]) ly[i] += delta;
}
}
}
return matchX;
}
private boolean dfs(int x) {
sx[x] = true;
for (int y = 0; y < n; y++) {
if (sy[y]) continue;
int gap = lx[x] + ly[y] - costMatrix[x][y];
if (gap == 0) {
sy[y] = true;
if (matchY[y] == -1 || dfs(matchY[y])) {
matchX[x] = y;
matchY[y] = x;
return true;
}
} else if (gap < slack[y]) {
slack[y] = gap;
slackX[y] = x;
}
}
return false;
}
}
完整判定流程
public class RhythmGameEngine {
/**
* 处理一整首歌曲的判定
*/
public GameResult processSong() {
// 1. 提取时间序列
long[] targetTimes = notes.stream().mapToLong(n -> n.targetTime).toArray();
long[] inputTimes = inputs.stream().mapToLong(i -> i.actualTime).toArray();
// 2. DTW对齐计算动态偏移
double[] offsets = computeTimeOffsets(targetTimes, inputTimes);
// 3. 按时间窗口分批处理
List<NoteJudgment> allJudgments = new ArrayList<>();
int perfect = 0, great = 0, good = 0, bad = 0, miss = 0;
int totalScore = 0;
int maxCombo = 0, currentCombo = 0;
for (int i = 0; i < notes.size(); i++) {
Note note = notes.get(i);
// 找到最近的输入（在修正窗口内）
InputEvent bestInput = null;
int bestScore = 0;
for (InputEvent input : inputs) {
if (input.track != note.track) continue;
long adjustedTarget = note.targetTime + (long) offsets[i];
long diff = Math.abs(input.actualTime - adjustedTarget);
int score = diff <= PERFECT_WINDOW ? 100 :
diff <= GREAT_WINDOW ? 80 :
diff <= GOOD_WINDOW ? 50 :
diff <= BAD_WINDOW ? 20 : 0;
if (score > bestScore) {
bestScore = score;
bestInput = input;
}
}
Judgment jdg = scoreToJudgment(bestScore);
allJudgments.add(new NoteJudgment(note, bestInput, jdg));
// 统计
switch (jdg) {
case PERFECT -> { perfect++; currentCombo++; }
case GREAT -> { great++; currentCombo++; }
case GOOD -> { good++; currentCombo = 0; }
case BAD -> { bad++; currentCombo = 0; }
case MISS -> { miss++; currentCombo = 0; }
}
maxCombo = Math.max(maxCombo, currentCombo);
totalScore += bestScore * (1 + currentCombo / 10); // Combo加成
}
return new GameResult(allJudgments, totalScore, perfect, great, good, bad, miss, maxCombo);
}
static class GameResult {
List<NoteJudgment> judgments;
int totalScore, perfect, great, good, bad, miss, maxCombo;
double accuracy;
GameResult(List<NoteJudgment> j, int score, int p, int gr, int go, int b, int m, int mc) {
this.judgments = j;
this.totalScore = score;
this.perfect = p; this.great = gr; this.good = go;
this.bad = b; this.miss = m; this.maxCombo = mc;
this.accuracy = (p * 100.0 + gr * 80.0 + go * 50.0 + b * 20.0) /
(j.size() * 100.0) * 100;
}
@Override
public String toString() {
return String.format("总分:%d | 准确率:%.2f%% | P:%d G:%d Go:%d B:%d M:%d | 最大连击:%d",
totalScore, accuracy, perfect, great, good, bad, miss, maxCombo);
}
}
}
复杂度分析
- DTW算法：时间复杂度
O(n × m)，空间复杂度O(n × m)，其中 n 和 m 分别是目标序列和输入序列长度。通过Sakoe-Chiba band限制搜索范围可优化到O(n × w)，w为带宽。 - 匈牙利算法：时间复杂度
O(n³)，适用于每小节的音符批量匹配（通常n≤20）。 - 整体判定：对于一首1000音符的歌曲，DTW预处理约
O(10⁶)操作，后续逐音符判定为O(n × k)，k为每音符附近的候选输入数。
扩展方向
- 实时判定优化：使用在线DTW变体，在演奏过程中实时更新对齐
- 多指协调分析：检测玩家在多轨道快速切换时的手指独立性和协调性
- 难度动态调整：根据玩家历史表现，使用EMA（指数移动平均）动态调整判定窗口宽度
- 谱面自动生成：基于音频节拍检测和旋律分析，自动生成适合玩家水平的音符谱面
