前言
⚠️硬核警告⚠️
英译版见『Minimum KB Click Frequency Lower Bound Analysis』.
本文包含大量数学公式和代码分析,建议具备一定理论基础阅读。
欢迎各位大佬指正🥰。
嗯……AI 帮了点小忙,还是挺好看出来的,对吧。
物理学框架下的 Minecraft 实体运动
经典力学下的运动
$$\frac{dv}{dt} = a - fv \tag{1.1.1}$$
$$v = v_0 e^{-ft} + \frac{a}{f} (1 - e^{-ft}) \tag{1.1.2}$$
$$\frac{v}{v_0} = \lim\limits_{t_0 \to 0} (1 - f t_0)^{\frac{t}{t_0}}, a = 0 \tag{1.1.3}$$
公式 (1.1.1) 描述了物体在恒定驱动力和正比于速度的阻力共同作用下,速度从变化逐渐达到稳定平衡的动态过程。这也是后续所有公式推导的基础。
公式 (1.1.2) 是通过求解公式 (1.1.1) 得到的精确解(通解)。其描述了在任何初始速度 $v_0$ 和任何驱动力 $a$ 的情况下,速度随时间变化的完整规律。
公式 (1.1.3) 则是将驱动力 $a=0$ 时的特殊情况代入公式 (1.1.2) 得到的结果。表明物体仅在阻力作用下,速度从初值 $v_0$ 开始指数衰减到零的过程。
其中,$f$ 为阻力系数。
但是,Minecraft 是以 tick(后续将称为 gt)为单位进行离散更新,即 $dt$ 和 $t_0$ 的最小值为 1gt,不能无限趋近于 0。因此这一规则在游戏中不能精确实现。
Mojang 对于实体运动的实现
以下是实体在水平和空中运动源代码简化版。已删去不必要和不相关的代码。
在 net/minecraft/entity/EntityLivingBase.java 中:
public void moveEntityWithHeading(float strafe, float forward) {
/**
* 环境检测与移动类型判断
* isInWater()、isInLava()、isFlying
* 水、岩浆、梯子等特殊状态移动处理(else if)
*/
float f4 = 0.91F; // 惯性系数
if (this.onGround) {
f4 = this.worldObj.getBlockState(
new BlockPos(
MathHelper.floor_double(this.posX),
MathHelper.floor_double(this.getEntityBoundingBox().minY) - 1,
MathHelper.floor_double(this.posZ)
)
)
.getBlock()
.slipperiness * 0.91F;
} // 获取下方方块滑度(后续将 slipperiness 称为滑度系数)
float f = 0.16277136F / (f4 * f4 * f4);
/**
* (0.6*0.91)^3 = 0.16277136
* 移动系数
*/
float f5;
if (this.onGround) f5 = this.getAIMoveSpeed() * f;
/**
* f5 = this.landMovementFactor * f;
* landMovementFactor 基础情况下为 0.1,疾跑时*1.3,受药水效果影响
*/
else f5 = this.jumpMovementFactor;
/**
* jumpMovementFactor = 0.02;
* 疾跑时*1.3,与药水效果无关
*/
this.moveFlying(strafe, forward, f5); // 速度计算
// 重新计算 f4
// 嗯···屎山代码这一块(
this.moveEntity(this.motionX, this.motionY, this.motionZ); // 实体移动
// 未加载区块重力处理
this.motionY -= 0.08D; // 重力
this.motionY *= 0.9800000190734863D; // 空气阻力
this.motionX *= (double)f4; this.motionZ *= (double)f4; // 摩擦力(水平)
// 玩家肢体动画更新
}
方块的滑度系数在 net/minecraft/block/Block.java 等文件中定义:
// Block.java
public class Block {
// 其它方块属性
public float slipperiness;
public Block(Material blockMaterialIn, MapColor blockMapColorIn) {
// 其它属性初始化
this.slipperiness = 0.6F;
}
}
// BlockIce.java
public class BlockIce extends BlockBreakable {
public BlockIce() {
this.slipperiness = 0.98F;
}
} // 冰
//BlockPackedIce.java
public class BlockPackedIce extends Block {
public BlockPackedIce() {
this.slipperiness = 0.98F;
}
} // 浮冰
// BlockSlime.java
public class BlockSlime extends BlockBreakable {
public BlockSlime() {
this.slipperiness = 0.8F;
}
} // 史莱姆块
滑度系数将用 $f_s$ 在后续的公式推导中来表示。
特别地,蓝冰在 1.13 被加入,滑度为 0.989。此处仅作补充。
实体在地面的移速(通过 getAIMoveSpeed() 函数返回,本质上是变量 landMovementFactor 的值)在文件 net/minecraft/entity/EntityLivingBase.java 定义:
public abstract class EntityLivingBase extends Entity {
private float landMovementFactor;
public float getAIMoveSpeed() {
return this.landMovementFactor;
}
}
其基本值在 net/minecraft/entity/player/PlayerCapabilities.java 给出:
public class PlayerCapabilities {
private float walkSpeed = 0.1F;
}
疾跑状态的修饰在 net/minecraft/entity/EntityLivingBase.java 中定义:
public abstract class EntityLivingBase extends Entity {
private static final AttributeModifier sprintingSpeedBoostModifier =
(new AttributeModifier(
sprintingSpeedBoostModifierUUID,
"Sprinting speed boost",
0.30000001192092896D,
2
)).setSaved(false);
}
疾跑速度则是通过 net/minecraft/entity/ai/attributes/ModifiableAttributeInstance.java 中的方法实现:
private double computeValue() {
double d0 = this.getBaseValue(); // 属性基本值获取
for (AttributeModifier attributemodifier : this.func_180375_b(0)) {
d0 += attributemodifier.getAmount();
}
double d1 = d0;
for (AttributeModifier attributemodifier1 : this.func_180375_b(1)) {
d1 += d0 * attributemodifier1.getAmount();
}
for (AttributeModifier attributemodifier2 : this.func_180375_b(2)) {
d1 *= 1.0D + attributemodifier2.getAmount();
}
// 三种类型修饰叠加
return this.genericAttribute.clampValue(d1);
}
实体在空中的移速(jumpMovementFactor)在 net/minecraft/entity/EntityLivingBase.java 中定义:
public abstract class EntityLivingBase extends Entity {
public float jumpMovementFactor = 0.02F;
}
疾跑时在 net/minecraft/entity/player/EntityPlayer.java 中更新:
public abstract class EntityPlayer extends EntityLivingBase {
public void onLivingUpdate() {
if (this.isSprinting()) {
this.jumpMovementFactor = (float)(
(double)this.jumpMovementFactor +
(double)this.speedInAir * 0.3D
);
}
}
}
屎山代码这两种运动实现还不一样 ):
实体的「motion」在 net/minecraft/entity/Entity.java 中更新:
public void moveFlying(float strafe, float forward, float friction) {
float f = strafe * strafe + forward * forward;
if (f >= 1.0E-4F) {
f = MathHelper.sqrt_float(f); // 模长为 1 的单位向量
if (f < 1.0F) {
f = 1.0F; // 避免斜向速度异常
}
f = friction / f;
strafe = strafe * f;
forward = forward * f;
// 摩擦系数应用
float f1 = MathHelper.sin(this.rotationYaw * (float)Math.PI / 180.0F);
float f2 = MathHelper.cos(this.rotationYaw * (float)Math.PI / 180.0F);
this.motionX += (double)(strafe * f2 - forward * f1);
this.motionZ += (double)(forward * f2 + strafe * f1);
// 2D 旋转矩阵
}
}
strafe 和 forward 变量在 net/minecraft/util/MovementInputFromOptions.java 中获取按键输入更新:
public void updatePlayerMoveState() {
this.moveStrafe = 0.0F;
this.moveForward = 0.0F;
if (this.gameSettings.keyBindForward.isKeyDown()) {
++this.moveForward;
}
if (this.gameSettings.keyBindBack.isKeyDown()) {
--this.moveForward;
}
if (this.gameSettings.keyBindLeft.isKeyDown()) {
++this.moveStrafe;
}
if (this.gameSettings.keyBindRight.isKeyDown()) {
--this.moveStrafe;
}
// 其它按键事件
/**
* 潜行事件
* moveStrafe 和 moveForward 乘以 0.3
*/
}
通过分析上述代码实现可以得知:
实体在水平方向上的「motion 属性」,在数值上等于当前速度向量在各坐标轴的分量乘以对应的阻力系数(垂直方向上的「motion」计算略有不同)。
若将 $t_0$ 时间内的「motion」视为平均速度 $M$,那么「motion」与阻力系数的乘积在物理意义上表示在该时间段内阻力对实体产生的冲量。
实体的「motion 属性」本质上是实体运动计算过程中的中间量,仅在游戏执行 moveFlying() 函数计算后,「motion 属性」可被视为实体的速度(或该时间段内的平均速度近似值)。
线性运动公式推导
为了方便理解公式,在这里定义一些必要参数:
- 速度:$v_H$、$v_Y$,实体在水平与垂直上的速度。
- 初始垂直速度:$v_{Y,1}$,取决于跳跃速度或服务器垂直击退参数。
- 滑度系数:$f_s = 0.6$(空气中不受该阻力影响)。
- 移动乘数:$k_M = 1.3 \times 0.98 = 1.274$(停止状态下为 0)。
- 效果乘数:$k_E = 1 \times 1 = 1$.
- 动量阈值:$v_{th} = 0.005$,当实体在某条轴上的速度经衰减后小于该值时,对应轴上的速度归零。
由此推导得到实体运动的递推关系(主要参考 Minecraft Parkour Wiki):
地面水平速度公式:$$v_{H,t} = \underbrace{v_{H,t-1} \times f_{s, t-1} \times 0.91} _ \text{动量保留} + \underbrace{0.1 \times \left( \frac{0.6}{f_{s,t}}\right)^3 \times k_M \times k_E} _ \text{加速度} \tag{1.3.1}$$
空中水平速度公式:$$v_{H,t} = \underbrace{v_{H,t-1} \times 0.91} _ \text{动量保留} + \underbrace{0.02 \times k_M} _ \text{加速度} \tag{1.3.2}$$
垂直速度公式:$$v_{Y,t} = ( v_{Y,t-1} - \mathop{0.08}\limits_\text{重力} ) \times \mathop{0.98}\limits_\text{阻力} \tag{1.3.3}$$
考虑到实际应用场景,上述推导中大部分系数或乘数均使用特殊值。
在后续『最优 kb 的点击频率下限分析』章节中,将加入点击行为对速度的影响机制。
鼠标点击分析
双击延迟
经测试,鼠标双击的触发延迟主要分布在 $[16, 27]\ \mathrm{ms}$ 区间范围内,受硬件性能、驱动程序、系统环境等影响,在不同的测试环境下略有差异。
若两次点击分别落在相邻的 tick 中,则称为「有效双击」。
有效双击的概率计算
设第一次点击的时间为 $T$,服从区间 $[0,50]$ 上的均匀分布:$$T \sim \mathcal{U}(0,50)$$
双击延迟为 $D$,服从区间 $[16,27]$ 上的均匀分布:$$D \sim \mathcal{U}(16,27)$$
则「有效双击」的概率:$$P(T + D \geq 50)$$
$T$ 和 $D$ 相互独立,其联合概率密度函数为:
$$f_{T,D}(t,d) = \frac{1}{50} \times \frac{1}{11} = \frac{1}{550},\ t \in [0,50],\ d \in [16,27]$$
展开积分并计算所求概率:
$$P(T + D \geq 50) = \iint\limits_{t + d \geq 50} f_{T,D}(t, d)\ dt\ dd = \int_{16}^{27} \int_{50 - d}^{50} \frac{1}{550}\ dt\ dd = \frac{473}{1100} = \frac{43}{100}$$
即「有效双击」的触发概率为 43%.
如果你不想阅读这部分略微令人头皮发麻的积分还可以通过条件期望来推导该概率:
$$P(T + D \geq 50) = P(T \geq 50 - D) = E[P(T \geq 50 - D \mid D)]$$
对于固定的 $D,\ T \sim \mathcal{U}(0, 50)$,且 $50 - D \in [23, 34] \subseteq [0, 50]$,有:
$$P(T \geq 50 - D \mid D) = \frac{50 - (50 - D)}{50} = \frac{D}{50}$$
得到:
$$P(T + D \geq 50) = E\left[\frac{D}{50}\right] = \frac{1}{50} E[D] = \frac{1}{50} \times \frac{16 + 27}{2} = \frac{43}{100}$$
与积分计算的结果一致。
🧠☠️
击退算法杂谈
原版击退算法
当玩家攻击时调用 net/minecraft/entity/player/EntityPlayer.java 文件中的 attackTargetEntityWithCurrentItem() 函数处理该过程:
public abstract class EntityPlayer extends EntityLivingBase {
public void attackTargetEntityWithCurrentItem(Entity targetEntity) {
/**
* 可攻击检查
* 基础伤害计算
* 附魔伤害计算
*/
int i = 0;
i = i + EnchantmentHelper.getKnockbackModifier(this);
if (this.isSprinting()) {
++i;
}
// 击退效果计算
/**
* 伤害有效性检查
* 暴击判断
* 火焰附加
*/
double d0 = targetEntity.motionX;
double d1 = targetEntity.motionY;
double d2 = targetEntity.motionZ;
boolean flag2 = targetEntity.attackEntityFrom(DamageSource.causePlayerDamage(this), f);
// 伤害应用
if (flag2) {
if (i > 0) {
targetEntity.addVelocity(
(double)(-MathHelper.sin(
this.rotationYaw * (float)Math.PI / 180.0F) * (float)i * 0.5F),
0.1D,
(double)(MathHelper.cos(
this.rotationYaw * (float)Math.PI / 180.0F) * (float)i * 0.5F)
); // 第二阶段击退计算
this.motionX *= 0.6D;
this.motionZ *= 0.6D;
this.setSprinting(false);
// 攻击者减速并取消疾跑状态
}
if (targetEntity instanceof EntityPlayerMP && targetEntity.velocityChanged) {
((EntityPlayerMP)targetEntity).playerNetServerHandler.sendPacket(
new S12PacketEntityVelocity(targetEntity)
);
targetEntity.velocityChanged = false;
targetEntity.motionX = d0;
targetEntity.motionY = d1;
targetEntity.motionZ = d2;
} // 避免重复叠加击退
/**
* 伤害成功后续处理
* 攻击失败处理
*/
}
}
// net/minecraft/entity/EntityLivingBase.java
public abstract class EntityLivingBase extends Entity {
public boolean attackEntityFrom(DamageSource source, float amount) {
/**
* 检查实体是否对特定伤害源免疫
* 客户端检查
* 死亡检查
* 特殊伤害免疫(抗火)
* 装备减伤
* 伤害刻(特别地,该时间段内更高的伤害会覆盖原有伤害)
* 攻击者判断
* 视觉更新(伤害动画)
*/
double d1 = entity.posX - this.posX;
double d0;
for(d0 = entity.posZ - this.posZ;
d1 * d1 + d0 * d0 < 1.0E-4D;
d0 = (Math.random() - Math.random()) * 0.01D) {
d1 = (Math.random() - Math.random()) * 0.01D;
} // 距离过近的随机击退
this.attackedAtYaw = (float)(
MathHelper.atan2(d0, d1) * 180.0D / Math.PI
- (double)this.rotationYaw
);
this.knockBack(entity, amount, d1, d0); // 执行击退
// 其它操作
}
public void knockBack(Entity entityIn, float amount, double d0, double d1) {
if (this.rand.nextDouble() >= this.getEntityAttribute(
SharedMonsterAttributes.knockbackResistance).getAttributeValue()) {
this.isAirBorne = true;
float f = MathHelper.sqrt_double(d0 * d0 + d1 * d1);
float f1 = 0.4F;
this.motionX /= 2.0D;
this.motionY /= 2.0D;
this.motionZ /= 2.0D;
// 受击者速度衰减
this.motionX -= d0 / (double)f * (double)f1;
this.motionY += (double)f1;
this.motionZ -= d1 / (double)f * (double)f1;
// 第一阶段击退计算
if (this.motionY > 0.4000000059604645D) {
this.motionY = 0.4000000059604645D;
} // 垂直击退上限
}
}
}
// net/minecraft/entity/Entity.java
public abstract class Entity implements ICommandSender {
protected void setBeenAttacked() {
this.velocityChanged = true;
}
public boolean attackEntityFrom(DamageSource source, float amount) {
if (this.isEntityInvulnerable(source)) {
return false;
} else {
this.setBeenAttacked();
return false;
}
}
}
为了更清晰地理解击退机制,在这里定义以下参数:
horizontal:基础水平击退。对应 knockBack() 函数中的 f1 变量,默认值为 0.4
vertical:基础垂直击退。其数值与基础水平击退相同,为 0.4
horizontalExtra:额外水平击退。仅考虑疾跑的因素,即 i = 1,值为 0.5
verticalExtra:额外垂直击退。addVelocity() 函数中的叠加固定额外垂直击退,默认值为 0.1
verticalLimit:垂直击退上限。motionY 的最大值 0.4
friction:暂无合适的译法。表示玩家受击时各轴的速度衰减(区别于方块的 friction),默认值为 2.0
基于上述代码分析可知玩家受到的击退效果主要分为两个阶段:
- 击退的第一阶段:仅与双方在 XZ 轴上的相对位置相关。
- 击退的第二阶段:仅与攻击者的偏航角(yaw)和攻击者的状态(本文只考虑疾跑)相关。
MMC 击退算法
本小节重点讨论与原版击退算法不同之处。
详细实现见 How MMC Knockback Actually Works.
MMC 引入了以下新的或修改的参数:
totalHorizontal = 0.8835d // 总水平击退
totalVertical = 0.9055d // 总垂直击退
rangeFactor = 0.035d // 距离影响系数
maxReduction = 0.4d // 最大距离减免
startRange = 3.0d // 距离减免起始计算距离
idleReduction = 0.6d // 基础击退倍率
attackBuffer = 1 // 攻击缓存
// 计算后的实际值
horizontal = totalHorizontal * idleReduction // 基础水平击退
horizontalExtra = totalHorizontal * (1 - idleReduction) // 额外水平击退
vertical = totalVertical * 0.4d // 基础垂直击退
verticalExtra = 0.0d // 额外垂直击退
verticalLimit = 0.4d // 垂直击退上限
attackerSlowdown = 0.6d
friction = 0.0d
不难看出:
idleReduction 决定了基础水平击退和额外水平击退的大小,并与 totalHorizontal 的值紧密相关。
verticalExtra 的值归零,即玩家的垂直击退固定。
attackBuffer 提供伤害刻结束前的攻击窗口。
- 增加了
rangeFactor、maxReduction、startRange 参数用于减免由于延迟造成的远距离攻击注册的击退。
特别地,当 friction = 0.0 时,受击者的动量归零,即击退完全覆盖原速度。
第一阶段击退算法:
void firstStage(EntityLiving attacker, EntityLiving victim) {
// 省略部分伪代码
double distance = Math.sqrt(distanceX * distanceX + distanceZ * distanceZ);
double rangeReduction = calculateRangeReduction(distance)
double modifiedHorizontal = horizontal - rangeReduction // 远距离击退衰减
double magnitude = Math.sqrt(distanceX * distanceX + distanceZ * distanceZ)
victim.motX -= (distanceX / magnitude) * (modifiedHorizontal * 0.5d)
victim.motZ -= (distanceZ / magnitude) * (modifiedHorizontal * 0.5d)
double yaw = Math.toRadians(attacker.yaw)
victim.motX += -Math.sin(yaw) * (modifiedHorizontal * 0.5d)
victim.motZ += Math.cos(yaw) * (modifiedHorizontal * 0.5d)
}
与原版不同的是,MMC 算法中第一阶段的击退同时与玩家的相对位置和攻击者的偏航角相关(占比各 50%)。并增加了 calculateRangeReduction() 函数用于减免远距离击退。
第二阶段击退算法与第一阶段相似:
void secondStage(EntityLiving attacker, EntityLiving victim, int knockbackEnchantLevel) {
// 省略部分伪代码
if (extraKBMult > 0) {
double distanceX = attacker.locX - victim.locX
double distanceZ = attacker.locZ - victim.locZ
double distance = Math.sqrt(distanceX * distanceX + distanceZ * distanceZ)
double modifiedExtraHorizontal = horizontalExtra * extraKBMult // 额外击退
double magnitude = Math.sqrt(distanceX * distanceX + distanceZ * distanceZ)
victim.motX -= (distanceX / magnitude) * (modifiedExtraHorizontal * 0.5d)
victim.motZ -= (distanceZ / magnitude) * (modifiedExtraHorizontal * 0.5d)
double yaw = Math.toRadians(attacker.yaw)
victim.motX += -Math.sin(yaw) * (modifiedExtraHorizontal * 0.5d)
victim.motZ += Math.cos(yaw) * (modifiedExtraHorizontal * 0.5d)
}
}
额外水平击退由 horizontalExtra 参数和 extraKBMult 共同决定。并保持与第一阶段相同的 50/50 分配。
最优 kb 的点击频率下限分析
一起来品鉴赤石 Mojang 的代码
参考资料
运动公式 - Minecraft Parkour Wiki
How MMC Knockback Actually Works
对我的世界中PVP击退的研究报告 - LSeng, CarmJos
关于修正并改进 xwj 的 MC 实体运动公式 —— 适用于MC中所有实体 - Bio-Hazard
Minecraft 实体运动研究与应用 - lovexyn0827
The ULTIMATE Guide to PING - sceyna
MCP-919 ( Fully decompiled )
NachoSpigot
致谢
蔚蓝天空Azure_Sky
时代地产
附件
更新日志
25.11.30 - 发布已基本写完的三章