跳一跳是微信小程序中极具代表性的休闲益智游戏，玩家通过控制按压屏幕的时间长短，决定小人从一个平台跳跃到另一个平台的距离。看似简单的操作背后，蕴含着丰富的算法设计空间：物理运动轨迹的数学建模、平台间最优落点的贪心决策、以及连续多跳得分的动态规划策略。本文将用Java完整实现带物理引擎的跳一跳核心逻辑，深入讲解抛物线运动模拟、距离估算与按压时间反解、贪心中心落点策略，以及多步前瞻的动态规划决策框架。
一、游戏机制与算法模型
跳一跳的核心玩法可以抽象为以下数学模型：
- 游戏世界由一系列矩形平台组成，平台中心坐标为
(targetX, targetY) - 玩家当前站在某个平台上，坐标为
(currentX, currentY) - 按住屏幕的时间
t（毫秒）决定起跳初速度，进而决定跳跃距离d - 跳跃轨迹遵循抛物线运动，受重力加速度
g影响 - 落点越靠近目标平台中心，得分越高；完美落中中心可获得额外加分
- 连续完美落在中心会触发连击加分机制
二、物理引擎：抛物线运动建模
在跳一跳中，小人离开平台后做斜抛运动。我们将三维空间投影到二维平面上，简化为水平方向的匀速直线运动和竖直方向的匀变速直线运动的合成。
2.1 运动学方程
设起跳时的水平初速度为 vx，竖直初速度为 vy，重力加速度为 g（取正值）。则任意时刻 t 的位置为：
x(t) = vx * t
y(t) = vy * t - 0.5 * g * t^2
小人落回地面（y = 0）时，竖直方向运动满足：
vy * t_flight - 0.5 * g * t_flight^2 = 0
解得飞行时间：
t_flight = 2 * vy / g
水平跳跃距离：
d = vx * t_flight = vx * (2 * vy / g) = (2 * vx * vy) / g
2.2 按压时间与初速度的映射
在游戏设计中，按压时间 pressTime 与初速度大小呈线性关系。设按压每毫秒增加的速度为 k，则：
v = k * pressTime
起跳角度 θ 固定（通常为45度以获得最远距离），因此：
vx = v * cos(θ) = k * pressTime * cos(θ)
vy = v * sin(θ) = k * pressTime * sin(θ)
将 vx 和 vy 代入距离公式：
d = (2 * k^2 * pressTime^2 * cos(θ) * sin(θ)) / g
= (k^2 * pressTime^2 * sin(2θ)) / g
当 θ = 45° 时，sin(2θ) = 1，公式简化为：
d = (k^2 * pressTime^2) / g
因此，按压时间与跳跃距离的平方根成正比：
pressTime = sqrt(d * g) / k
这一关系是游戏AI决策的核心——给定目标距离 d，反解出所需的按压时间。
三、平台距离检测与坐标计算
3.1 两点间距离公式
假设当前平台中心为 (x1, y1)，目标平台中心为 (x2, y2)，则水平跳跃距离为：
d = sqrt((x2 - x1)^2 + (y2 - y1)^2)
3.2 落点偏差评估
玩家实际落点与目标平台中心的偏差决定了得分。设平台边长为 L，落点偏差为 delta，则：
- 当
delta <= L/10时，完美落在中心，得分最高（如10分） - 当
L/10 < delta <= L/4时，良好落点，得分中等（如5分） - 当
delta > L/4时，普通落点，得分较低（如2分） - 当
delta > L/2时，掉落平台，游戏结束
四、贪心最优落点策略
贪心策略的核心思想是：在每一步跳跃中，选择使当前步收益最大化的落点。
4.1 单步贪心决策
对于单步跳跃，最优策略显然是尽量落在目标平台中心。由于按压时间可以精确控制（在模拟环境中），贪心策略的直接表现就是：
pressTime = calculatePressTime(distanceToTargetCenter)
4.2 带噪声的按压模拟
在真实游戏或更贴近现实的模拟中，玩家的按压操作会引入随机误差。我们可以用正态分布模拟这种不确定性：
actualPressTime = idealPressTime + randomGaussian(0, sigma)
其中 sigma 与平台距离正相关——距离越远，操作误差越大。
贪心策略在此场景下仍然适用：以平台中心为瞄准点，因为中心提供了最大的容错空间（掉落半径最大）。
五、多步前瞻的动态规划策略
当引入连击加分机制后，单步贪心可能不再全局最优。连续完美落在中心会获得递增的连击奖励（如第n连击额外加n分）。此时需要考虑多步规划。
5.1 状态定义
设状态为 (platformIndex, comboCount)，表示当前在第 platformIndex 个平台，已连续完美落点 comboCount 次。
5.2 状态转移
从状态 (i, c) 可以转移到下一个平台 i+1，转移结果取决于落点质量：
- 完美落点：新状态
(i+1, c+1)，得分baseScore + comboBonus(c+1) - 非完美落点：新状态
(i+1, 0)，得分baseScore - 掉落：游戏结束
5.3 带噪声的期望值DP
由于按压存在误差，每种落点结果都有一定的发生概率。设完美落点的概率为 p_perfect，则：
E[i][c] = max over all possible aim points (
p_perfect * (score_perfect + E[i+1][c+1]) +
p_good * (score_good + E[i+1][0]) +
p_fall * (-infinity)
)
在实际实现中，为了降低复杂度，可以采用有限前瞻（如只看接下来3-5步）而非全局最优。
六、完整Java实现
import java.util.*;
/**
* 跳一跳游戏核心算法实现
* 包含物理引擎、贪心策略与动态规划决策框架
*/
public class JumpJumpGame {
// ========== 物理常量 ==========
/** 重力加速度 (像素/毫秒²) */
private static final double GRAVITY = 0.004;
/** 按压每毫秒增加的速度系数 */
private static final double PRESS_VELOCITY_FACTOR = 0.15;
/** 起跳角度 (45度) */
private static final double LAUNCH_ANGLE = Math.PI / 4;
/** 按压时间随机误差标准差基数 */
private static final double SIGMA_BASE = 3.0;
// ========== 游戏常量 ==========
/** 平台边长 */
private static final double PLATFORM_SIZE = 60.0;
/** 完美落点半径 (平台尺寸的1/10) */
private static final double PERFECT_RADIUS = PLATFORM_SIZE / 10.0;
/** 良好落点半径 (平台尺寸的1/4) */
private static final double GOOD_RADIUS = PLATFORM_SIZE / 4.0;
/** 掉落半径 (平台尺寸的1/2) */
private static final double FALL_RADIUS = PLATFORM_SIZE / 2.0;
// ========== 得分常量 ==========
private static final int SCORE_PERFECT = 10;
private static final int SCORE_GOOD = 5;
private static final int SCORE_NORMAL = 2;
private static final int SCORE_COMBO_BONUS_BASE = 2;
/** 随机数生成器 */
private final Random random;
/** 当前平台索引 */
private int currentPlatform;
/** 连续完美落点次数 */
private int comboCount;
/** 总得分 */
private int totalScore;
public JumpJumpGame(long seed) {
this.random = new Random(seed);
this.currentPlatform = 0;
this.comboCount = 0;
this.totalScore = 0;
}
/**
* 根据目标距离计算理论按压时间
* 基于抛物线运动公式反解
*
* @param distance 目标水平距离
* @return 理论按压时间 (毫秒)
*/
public double calculatePressTime(double distance) {
// d = (k^2 * t^2 * sin(2θ)) / g
// 当 θ = 45° 时，sin(2θ) = 1
// t = sqrt(d * g) / k
double k = PRESS_VELOCITY_FACTOR;
double g = GRAVITY;
return Math.sqrt(distance * g) / k;
}
/**
* 计算两点之间的欧几里得距离
*/
public double calculateDistance(Point from, Point to) {
double dx = to.x - from.x;
double dy = to.y - from.y;
return Math.sqrt(dx * dx + dy * dy);
}
/**
* 模拟按压操作，加入随机误差
* 误差与距离正相关：距离越远，操作越难精确
*
* @param idealTime 理论按压时间
* @param distance 目标距离（用于计算误差幅度）
* @return 实际按压时间
*/
public double simulatePress(double idealTime, double distance) {
// 误差标准差与距离成正比，但设置上限
double sigma = Math.min(SIGMA_BASE * (distance / 200.0), 15.0);
double noise = random.nextGaussian() * sigma;
return Math.max(idealTime + noise, 0); // 按压时间不能为负
}
/**
* 根据按压时间计算实际跳跃距离
* 正向验证物理模型
*/
public double calculateJumpDistance(double pressTime) {
double v = PRESS_VELOCITY_FACTOR * pressTime;
double vx = v * Math.cos(LAUNCH_ANGLE);
double vy = v * Math.sin(LAUNCH_ANGLE);
double flightTime = 2 * vy / GRAVITY;
return vx * flightTime;
}
/**
* 评估落点质量并计算得分
*
* @param landingPoint 实际落点坐标
* @param targetCenter 目标平台中心
* @return 落点结果（包含得分和落点类型）
*/
public LandingResult evaluateLanding(Point landingPoint, Point targetCenter) {
double delta = calculateDistance(landingPoint, targetCenter);
if (delta <= PERFECT_RADIUS) {
return new LandingResult(LandingType.PERFECT, SCORE_PERFECT);
} else if (delta <= GOOD_RADIUS) {
return new LandingResult(LandingType.GOOD, SCORE_GOOD);
} else if (delta <= FALL_RADIUS) {
return new LandingResult(LandingType.NORMAL, SCORE_NORMAL);
} else {
return new LandingResult(LandingType.FALL, 0);
}
}
/**
* 贪心策略：单步最优决策
* 目标始终瞄准平台中心，因为中心提供最大容错空间
*
* @param current 当前位置
* @param target 目标平台中心
* @return 决策结果（按压时间）
*/
public GreedyDecision greedyDecision(Point current, Point target) {
double distance = calculateDistance(current, target);
double pressTime = calculatePressTime(distance);
return new GreedyDecision(pressTime, distance, target);
}
/**
* 执行一次跳跃（带噪声模拟）
*
* @param current 当前位置
* @param target 目标平台中心
* @return 跳跃结果
*/
public JumpResult performJump(Point current, Point target) {
double distance = calculateDistance(current, target);
double idealPress = calculatePressTime(distance);
double actualPress = simulatePress(idealPress, distance);
double actualDistance = calculateJumpDistance(actualPress);
// 计算实际落点（沿当前到目标的方向上按比例放置）
double ratio = actualDistance / distance;
if (ratio < 0) ratio = 0;
double landingX = current.x + (target.x - current.x) * ratio;
double landingY = current.y + (target.y - current.y) * ratio;
Point landingPoint = new Point(landingX, landingY);
LandingResult result = evaluateLanding(landingPoint, target);
// 更新连击计数和总分
if (result.type == LandingType.PERFECT) {
comboCount++;
int bonus = SCORE_COMBO_BONUS_BASE * comboCount;
totalScore += result.score + bonus;
} else if (result.type == LandingType.FALL) {
comboCount = 0;
// 游戏结束
} else {
comboCount = 0;
totalScore += result.score;
}
currentPlatform++;
return new JumpResult(landingPoint, result, comboCount, totalScore, actualPress);
}
/**
* 动态规划前瞻决策（有限深度）
* 在存在连击奖励时，评估多个可能瞄准点的期望收益
*
* @param current 当前位置
* @param targets 前方平台列表
* @param depth 前瞻步数
* @param combo 当前连击数
* @return 最优瞄准点
*/
public Point dpDecision(Point current, List<Point> targets, int depth, int combo) {
if (depth == 0 || targets.isEmpty()) {
return targets.isEmpty() ? current : targets.get(0);
}
Point nextTarget = targets.get(0);
double distance = calculateDistance(current, nextTarget);
// 生成候选瞄准点（中心及周围若干点）
List<Point> candidates = generateAimPoints(nextTarget);
double bestExpected = Double.NEGATIVE_INFINITY;
Point bestAim = candidates.get(0);
for (Point aim : candidates) {
double expectedScore = calculateExpectedScore(current, aim, nextTarget,
targets, depth, combo);
if (expectedScore > bestExpected) {
bestExpected = expectedScore;
bestAim = aim;
}
}
return bestAim;
}
/**
* 生成候选瞄准点
* 包括中心点及周围偏移点
*/
private List<Point> generateAimPoints(Point center) {
List<Point> points = new ArrayList<>();
points.add(center); // 中心点
// 在四个方向添加偏移候选点，用于评估不同瞄准策略
double offset = PLATFORM_SIZE / 8.0;
points.add(new Point(center.x + offset, center.y));
points.add(new Point(center.x - offset, center.y));
points.add(new Point(center.x, center.y + offset));
points.add(new Point(center.x, center.y - offset));
return points;
}
/**
* 计算某个瞄准点的期望得分（带噪声模拟）
* 使用蒙特卡洛方法估计期望值
*/
private double calculateExpectedScore(Point from, Point aim, Point actualTarget,
List<Point> remainingTargets, int depth, int combo) {
double aimDistance = calculateDistance(from, aim);
double idealPress = calculatePressTime(aimDistance);
final int SIMULATIONS = 100;
double totalScore = 0;
for (int i = 0; i < SIMULATIONS; i++) {
double actualPress = simulatePress(idealPress, aimDistance);
double actualDistance = calculateJumpDistance(actualPress);
double ratio = actualDistance / aimDistance;
if (ratio < 0) ratio = 0;
double landingX = from.x + (aim.x - from.x) * ratio;
double landingY = from.y + (aim.y - from.y) * ratio;
Point landing = new Point(landingX, landingY);
LandingResult result = evaluateLanding(landing, actualTarget);
int score;
int newCombo;
if (result.type == LandingType.PERFECT) {
newCombo = combo + 1;
score = result.score + SCORE_COMBO_BONUS_BASE * newCombo;
} else if (result.type == LandingType.FALL) {
score = -100; // 惩罚
newCombo = 0;
} else {
score = result.score;
newCombo = 0;
}
// 递归计算后续得分（简化：假设后续使用贪心策略）
if (result.type != LandingType.FALL && remainingTargets.size() > 1) {
List<Point> nextTargets = remainingTargets.subList(1, remainingTargets.size());
score += estimateFutureScore(actualTarget, nextTargets, depth - 1, newCombo);
}
totalScore += score;
}
return totalScore / SIMULATIONS;
}
/**
* 估计未来得分的简化函数
* 假设后续每步都使用贪心策略瞄准中心
*/
private double estimateFutureScore(Point current, List<Point> targets, int depth, int combo) {
if (depth == 0 || targets.isEmpty()) return 0;
Point target = targets.get(0);
double distance = calculateDistance(current, target);
double idealPress = calculatePressTime(distance);
// 使用无噪声的理想按压估算期望
double perfectProb = 0.6; // 假设60%概率完美落点
double goodProb = 0.3;
double normalProb = 0.08;
double fallProb = 0.02;
double expected = perfectProb * (SCORE_PERFECT + SCORE_COMBO_BONUS_BASE * (combo + 1))
+ goodProb * SCORE_GOOD
+ normalProb * SCORE_NORMAL
+ fallProb * (-50);
List<Point> nextTargets = targets.subList(1, targets.size());
expected += estimateFutureScore(target, nextTargets, depth - 1,
combo + 1); // 简化：假设连击持续
return expected;
}
// ========== 数据类定义 ==========
/** 二维坐标点 */
public static class Point {
public final double x;
public final double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return String.format("(%.1f, %.1f)", x, y);
}
}
/** 落点类型枚举 */
public enum LandingType {
PERFECT, GOOD, NORMAL, FALL
}
/** 落点结果 */
public static class LandingResult {
public final LandingType type;
public final int score;
public LandingResult(LandingType type, int score) {
this.type = type;
this.score = score;
}
}
/** 贪心决策结果 */
public static class GreedyDecision {
public final double pressTime;
public final double distance;
public final Point aimPoint;
public GreedyDecision(double pressTime, double distance, Point aimPoint) {
this.pressTime = pressTime;
this.distance = distance;
this.aimPoint = aimPoint;
}
}
/** 跳跃结果 */
public static class JumpResult {
public final Point landingPoint;
public final LandingResult landingResult;
public final int comboCount;
public final int totalScore;
public final double actualPressTime;
public JumpResult(Point landingPoint, LandingResult landingResult,
int comboCount, int totalScore, double actualPressTime) {
this.landingPoint = landingPoint;
this.landingResult = landingResult;
this.comboCount = comboCount;
this.totalScore = totalScore;
this.actualPressTime = actualPressTime;
}
@Override
public String toString() {
return String.format("落点: %s, 类型: %s, 连击: %d, 总分: %d, 按压: %.1fms",
landingPoint, landingResult.type, comboCount, totalScore, actualPressTime);
}
}
// ========== 主程序与测试 ==========
public static void main(String[] args) {
System.out.println("========== 跳一跳物理引擎测试 ==========\n");
JumpJumpGame game = new JumpJumpGame(42);
// 测试1：物理公式验证
System.out.println("【测试1】物理公式验证");
double[] testDistances = {100, 200, 300, 400, 500};
for (double d : testDistances) {
double pressTime = game.calculatePressTime(d);
double jumpDist = game.calculateJumpDistance(pressTime);
System.out.printf("目标距离: %.0fpx -> 按压时间: %.1fms -> 实际跳跃: %.1fpx (误差: %.2f%%)%n",
d, pressTime, jumpDist, Math.abs(jumpDist - d) / d * 100);
}
System.out.println("\n【测试2】贪心策略单步跳跃模拟");
Point current = new Point(0, 0);
Point[] platforms = {
new Point(150, 100),
new Point(280, 180),
new Point(420, 120),
new Point(550, 200),
new Point(700, 150)
};
for (int i = 0; i < platforms.length; i++) {
Point target = platforms[i];
GreedyDecision decision = game.greedyDecision(current, target);
JumpResult result = game.performJump(current, target);
System.out.printf("第%d跳: 当前%s -> 目标%s | 理论按压: %.1fms | %s%n",
i + 1, current, target, decision.pressTime, result);
if (result.landingResult.type == LandingType.FALL) {
System.out.println("!!! 游戏结束 !!!");
break;
}
current = target; // 更新当前位置
}
System.out.println("\n【测试3】动态规划前瞻决策对比");
JumpJumpGame game2 = new JumpJumpGame(42);
Point start = new Point(0, 0);
List<Point> targetList = Arrays.asList(platforms);
// 使用DP决策选择瞄准点
Point dpAim = game2.dpDecision(start, targetList, 3, 0);
Point greedyAim = targetList.get(0); // 贪心直接瞄中心
System.out.println("贪心瞄准点: " + greedyAim);
System.out.println("DP前瞻瞄准点: " + dpAim);
System.out.println("\n========== 测试完成 ==========");
}
}
七、复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 物理计算 | O(1) | O(1) | 公式直接计算 |
| 贪心单步决策 | O(1) | O(1) | 一次距离计算 |
| DP前瞻决策 | O(S × C × D) | O(D) | S为模拟次数，C为候选点数，D为前瞻深度 |
| 蒙特卡洛期望估计 | O(S × D) | O(D) | 递归深度由前瞻步数决定 |
其中，DP前瞻决策的时间开销主要来自蒙特卡洛模拟。在实际游戏中，通常取 S = 100、C = 5、D = 3，单次决策约需 1500 次模拟计算，在现代设备上完全可以实时运行。
八、扩展与优化方向
- 自适应物理参数校准：通过玩家历史数据在线估计
PRESS_VELOCITY_FACTOR，适应不同设备的触控延迟差异。 - 更精细的误差模型：将按压误差建模为与按压时间、平台距离、平台角度相关的多元函数，而非简单的正态分布。
- 强化学习策略：使用Q-Learning或策略梯度方法，让AI通过自对弈学习最优瞄准策略，而非依赖手工设计的DP模型。
- 3D场景扩展：将二维模型扩展到三维，加入平台高度差和视角变换，使物理模拟更加真实。
九、总结
跳一跳虽然规则极简，却涵盖了物理建模、贪心决策、动态规划与蒙特卡洛模拟等多种算法思想。本文从抛物线运动方程出发，推导了按压时间与跳跃距离的解析关系；通过贪心策略论证了中心瞄准的最优性；并引入带噪声的期望值动态规划，展示了在连击奖励机制下的多步前瞻决策框架。完整的Java实现提供了可直接运行的代码，读者可以在此基础上继续探索强化学习等更高级的AI策略。
