Random destination routine has a small statistical tendency to move more north west (fix included)

Update (see https://bugs.mojang.com/browse/MC-10046?focusedCommentId=304613&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-304613):
seems the second part of the bug is still (or again?) in effect in 1.9. I do not change my code examples below, since I do not have the latest code to check the changes against, but looks like the fix would be obvious.

This bug is somewhat difficult (or at least slow) to reproduce, because it needs a long time and controlled environment to be noticed. While issue MC-3944 (perhaps related) sounds like it would be seen easily, this issue here can not be seen easily or quickly (unless certain range is temporarily changed to a smaller value).

It should affect both survival and creative, and any and all activities and mob types that use the same method. Some activities are not affected as badly by this, as they do not accumulate over time.

• Wander

  • Villager, iron golem, animals, skeleton, zombie, witch, wither, ...

• Move through village

• Panic

• Play

• Avoid entity

• ...

The bug
When the AI routine for wandering requests a random destination, the method used to roll and calculate that random destination has two small "math" mistakes.

-1) It rolls the relative random target location using random.nextInt(2*range) - range. For example, if range is 10 (i.e. +/-10 blocks from current location), the possible result range will be 10 to +9, with even distribution. This already has a small (but significant) statistical shift to negative value (i.e. north and west).

2) The result is then added the Math.floor(entity.pos) to make it absolute coordinate. However, this truncation discards any fractional part of entity position (towards north and west), and the thrown away part is never brought back or compensated.

The end effect is seen as tendency to move, on the average, about 0.6 to 0.9 blocks per AI activity launched towards north west. I confirmed this by letting the game keep calculating the average relative movements over couple thousand "wanderings", both for villagers and for chickens (separately for each type), and results were indeed values like -0.6 to -0.9 (fits within normal random differences due to "small" set of data). (The expected value would naturally be very near 0.)

Showing the original method in complete as the changes are quite spread in it. Using MCP naming and my own renamings.

RandomPositionGenerator

private static Vec3 findRandomTargetBlock(EntityCreature entity, int hor, int ver, Vec3 inDir) {
        Random rng = entity.getRNG();
        boolean foundTarget = false;
        int x = 0;
        int y = 0;
        int z = 0;
        float bestValue = -99999.0F;
        boolean var10;

        if (entity.hasHome()) {
            double var11 = (double) (entity.getHomePosition().getDistanceSquared(MathHelper.floor_double(entity.posX), MathHelper.floor_double(entity.posY), MathHelper.floor_double(entity.posZ)) + 4.0F);
            double var13 = (double) (entity.getMaximumHomeDistance() + (float) hor);
            var10 = var11 < var13 * var13;
        } else {
            var10 = false;
        }

        for (int var16 = 0; var16 < 10; ++var16) {
            int var12 = rng.nextInt(2 * hor) - hor;
            int var17 = rng.nextInt(2 * ver) - ver;
            int var14 = rng.nextInt(2 * hor) - hor;

            if (inDir == null || (double) var12 * inDir.xCoord + (double) var14 * inDir.zCoord >= 0.0D) {
                var12 += MathHelper.floor_double(entity.posX);
                var17 += MathHelper.floor_double(entity.posY);
                var14 += MathHelper.floor_double(entity.posZ);

                if (!var10 || entity.isWithinHomeDistance(var12, var17, var14)) {
                    float pathValue = entity.getBlockPathWeight(var12, var17, var14);
                    if (pathValue > bestValue) {
                        bestValue = pathValue;
                        x = var12;
                        y = var17;
                        z = var14;
                        foundTarget = true;
                    }
                }
            }
        }

        if (foundTarget) {
            return entity.worldObj.getWorldVec3Pool().getVecFromPool((double) x, (double) y, (double) z);
        } else {
            return null;
        }
    }

The fix
-1) random.nextInt(2*range+1) - range. This gives results between range and +range, with even distribution and average of 0.

2) Use the truncated absolute destination position for checking various things, but then the full value to set where to move. Thus, the effect will be 0.

RandomPositionGenerator

private static Vec3 findRandomTargetBlock(EntityCreature entity, int hor, int ver, Vec3 inDir) {
        Random rng = entity.getRNG();
        boolean foundTarget = false;
        double x = 0;
        double y = 0;
        double z = 0;
        float bestValue = -99999.0F;
        boolean var10;

        if (entity.hasHome()) {
            double var11 = (double) (entity.getHomePosition().getDistanceSquared(MathHelper.floor_double(entity.posX), MathHelper.floor_double(entity.posY), MathHelper.floor_double(entity.posZ)) + 4.0F);
            double var13 = (double) (entity.getMaximumHomeDistance() + (float) hor);
            var10 = var11 < var13 * var13;
        } else {
            var10 = false;
        }

        for (int var16 = 0; var16 < 10; ++var16) {
            int var12 = rng.nextInt(2 * hor + 1) - hor;
            int var17 = rng.nextInt(2 * ver + 1) - ver;
            int var14 = rng.nextInt(2 * hor + 1) - hor;

            if (inDir == null || (double) var12 * inDir.xCoord + (double) var14 * inDir.zCoord >= 0.0D) {
                int var12b = var12 + MathHelper.floor_double(entity.posX);
                int var17b = var17 + MathHelper.floor_double(entity.posY);
                int var14b = var14 + MathHelper.floor_double(entity.posZ);

                if (!var10 || entity.isWithinHomeDistance(var12b, var17b, var14b)) {
                    float pathValue = entity.getBlockPathWeight(var12b, var17b, var14b);

                    if (pathValue > bestValue) {
                        bestValue = pathValue;
                        x = entity.posX + var12;
                        y = entity.posY + var17;
                        z = entity.posZ + var14;
                        foundTarget = true;
                    }
                }
            }
        }

        if (foundTarget) {
            return entity.worldObj.getWorldVec3Pool().getVecFromPool(x, y, z);
        } else {
            return null;
        }
    }

When testing the fixes on 1.4.7, the corresponding results for chickens were now like this: "Average wander delta now (3477): -0,0538, 2,0290, 0,0060". Very decent values, though they do naturally vary randomly from run to run, with small values on both sides of zero (as expected). Ignore the vertical delta of 2; chickens' specialty. The 3477 is how many wanderings were averaged.

Minor optimization possibility in the same method, while at it
For villagers, the entity.getBlockPathWeight() method always return 0. Thus, the first roll will end up being the chosen destination, but all the 10 tries will always be rolled. Something might be done for that so that there won't be any wasted extra tries.