MK: Ultra

MK: Ultra

59.5k Downloads

EntityUtils.travelTimeForDistance can get stuck in infinite loop

notcake opened this issue ยท 1 comments

commented

Version: 0.99.10

Screenshot 2019-12-12 21 56 53

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:

  1. 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. For speed = 1 and drag = 0.8, the sum to infinity is 5, so travelTimeForDistance(distance=5.00000001, speed=1.0, drag=0.8) will loop forever because the destination will never be reached.
  2. 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).
  3. The for (int i = 0; i < travelTimeInTicks; i++) loop in shootProjectileAtTarget can also take a long time if travelTimeInTicks 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.

commented

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.