EntityUtils.travelTimeForDistance can get stuck in infinite loop
notcake opened this issue ยท 1 comments
Version: 0.99.10
java.lang.Error: ServerHangWatchdog detected that a single server tick took 300.00 seconds (should be max 0.05)
at com.chaosbuffalo.mkultra.utils.EntityUtils.travelTimeForDistance(EntityUtils.java:69)
at com.chaosbuffalo.mkultra.utils.EntityUtils.shootProjectileAtTarget(EntityUtils.java:81)
at com.chaosbuffalo.mkultra.core.mob_abilities.Drown.execute(Drown.java:61)
at com.chaosbuffalo.mkultra.core.MobAbilityTracker.useAbility(MobAbilityTracker.java:48)
at com.chaosbuffalo.mkultra.mob_ai.EntityAISpellCastingBase.func_75246_d(EntityAISpellCastingBase.java:234)
at net.minecraft.entity.ai.EntityAITasks.func_75774_a(SourceFile:129)
at net.minecraft.entity.EntityLiving.func_70626_be(EntityLiving.java:763)
at net.minecraft.entity.EntityLivingBase.func_70636_d(EntityLivingBase.java:2359)
at net.minecraft.entity.EntityLiving.func_70636_d(EntityLiving.java:577)
at net.minecraft.entity.monster.EntityMob.func_70636_d(EntityMob.java:45)
at net.minecraft.entity.monster.AbstractSkeleton.func_70636_d(AbstractSkeleton.java:144)
at net.minecraft.entity.EntityLivingBase.func_70071_h_(EntityLivingBase.java:2179)
at net.minecraft.entity.EntityLiving.func_70071_h_(EntityLiving.java:295)
at net.minecraft.entity.monster.EntityMob.func_70071_h_(EntityMob.java:50)
at net.minecraft.world.World.func_72866_a(World.java:1996)
at net.minecraft.world.WorldServer.func_72866_a(WorldServer.java:832)
at net.minecraft.world.World.func_72870_g(World.java:1958)
at net.minecraft.world.World.func_72939_s(World.java:1762)
at net.minecraft.world.WorldServer.func_72939_s(WorldServer.java:613)
at net.minecraft.server.MinecraftServer.func_71190_q(MinecraftServer.java:767)
at net.minecraft.server.dedicated.DedicatedServer.func_71190_q(DedicatedServer.java:397)
at net.minecraft.server.MinecraftServer.func_71217_p(MinecraftServer.java:668)
at net.minecraft.server.MinecraftServer.run(MinecraftServer.java:526)
at java.lang.Thread.run(Thread.java:748)
From reading the code, EntityUtils.travelTimeForDistance
gets called with speed=1.0
(PROJECTILE_SPEED
from the Drown
mob ability) and drag = 0.99
or 0.8
(EntityBaseProjectile.getFlightDrag
/EntityBaseProjectile.getWaterDrag
) for the case above.
travelTimeForDistance
is implemented as:
public static int travelTimeForDistance(double distance, double speed, double drag, float gravity) {
int ticks = 0;
while (distance > 0) {
distance -= speed * Math.pow(drag, ticks);
ticks++;
}
return ticks;
}
which effectively tries to count the number of terms of a sum of a geometric series until the sum exceeds distance
.
There are two or three issues here:
- When distance is greater than or equal to the sum of infinite terms of the series (the formula is
speed * (1 - drag)
),travelTimeForDistance
will never return.
eg. Forspeed = 1
anddrag = 0.8
, the sum to infinity is5
, sotravelTimeForDistance(distance=5.00000001, speed=1.0, drag=0.8)
will loop forever because the destination will never be reached. travelTimeForDistance(distance=4.99999999, speed=1.0, drag=0.8)
won't loop forever but will take a long time to terminate (or would if it weren't for floating point error).- The
for (int i = 0; i < travelTimeInTicks; i++)
loop inshootProjectileAtTarget
can also take a long time iftravelTimeInTicks
is large.
For the first issue, logic to handle projectiles that will never reach their targets is missing.
For the second issue, a formula exists for the sum of n
terms of a geometric series that can be computed much faster: distance = speed * (1 - pow(drag, ticks)) / (1 - drag)
, which can be rearranged into ticks = log(1 - distance / speed * (1 - drag)) / log(drag)
.
I have no idea what to do about the third issue since the code in the loop looks questionable anyway.
I did some testing of a faster version of travelTimeForDistance
here: http://codepad.org/Mq7jTYU4
Feel free to translate it back into Java and use it.
This is a fantastic find and one of the best bug reports I've seen in my time maintaining open-source code. Thank you very much, and you are right that this whole section is questionable. It's got to do with the fact that Minecraft's ballistics are essentially a geometric series instead of a real physics simulation, which makes it significantly harder to perform these calculations.
I may look into making our projectiles behave more realistically than the way other vanilla projectiles do in order to solve this problem in a neater way.