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.
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.
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.
Linked Issues
is duplicated by4
MC-12352Chicken movement biasDuplicateMC-89509As of 15w39c, villagers are once more North-West obsessed.DuplicateMC-97698villagers in the 1.9 snapshots don't want to go into houses at night and they all huddle up in one corner.DuplicateMC-3944Villagers in Minecraft, when given a roughly 5x5-10x10 area, will arbitrarily pack up in the north-west cornerDuplicaterelates to5
MC-100001Bat AI asymmetryCannot Reproduce
MCPE-41092Northwest Bias in Mob MovementFixedMC-113979Zombies of village siege spawn more likely in negative directionConfirmedMC-12427Mobs get stuck in the North-West corner of a fenceFixedMC-31153Bias in passive mob AI - still results in self-stranding passive mobs, even with Northwest bug fixedAwaiting Response
Created Issue:
Random destination routine has a small statistical tendency to move more north west (fix included)
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.
RandomPositionGeneratorprivate 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.
RandomPositionGeneratorprivate 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.
![[Mod] CubeTheThird](../../../data/assets/gravatar/cubethethird.jpeg){kind=small}
Minecraft (1).exe
is duplicated by
relates to
relates to
is duplicated by
is duplicated by
![[Mojang] Grum (Erik Broes)](../../../data/assets/gravatar/grum.png){kind=small}
[Mojang] Grum (Erik Broes)![[Mod] Torabi](../../../data/assets/gravatar/torabi.png){kind=small}
relates to
is duplicated by
relates to
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 hastwo 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.
RandomPositionGeneratorprivate 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.
RandomPositionGeneratorprivate 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.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 hastwosmall "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.
RandomPositionGeneratorprivate 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.
RandomPositionGeneratorprivate 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.
Update
(seehttps://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 hastwosmall "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.
RandomPositionGeneratorprivate 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.
RandomPositionGeneratorprivate 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.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 hastwosmall "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.
RandomPositionGeneratorprivate 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.
RandomPositionGeneratorprivate 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.
is duplicated by
![[Mod] Michael Wobst](../../../data/avatars/users/37868.png){kind=small}
relates to
![[Bot] Arisa](../../../data/avatars/users/43007.png){kind=small}
clones
is duplicated by
![[Mod] OcelotOnesie](../../../data/avatars/users/43220.png){kind=small}
relates to
ArmEagle: I haven't noticed any AI code that aims specifically to let animals escape their fenced areas. Also, it would be kind of counterproductive to code and give players fences to make farms, then code animals to try and make those fences useless. However, read below; the normal "wandering" goal does work so that it looks like they'd want to get out.
Gerrard: Nice work so far. I think I already made a try on this issue on the basis of an idea of floating-point problems during save or load (format conversion or such), but I also found out that part of code to look ok.
For the movement bias, check this out: MC-10046.
The animals gather in the corners for the same reason as villagers do (in the MC-3944): statistics. Note, when "wandering", entities roll a target location randomly (and somewhat evenly spread around current location), without any consideration on how to get there or even if it is possible to get there. Then the path finding tries to find a path to that target, or a location as close to the target as possible. In a typical small square "pen", this leads to ending up a lot in corners. Also, once the entity is in a corner, the probability for the next movement path end point to be in that same corner increases. (For villagers this corner-gathering effect is amplified with their additional AI goal to go and chat nose-to-nose with other villagers.)
For both animals and villagers, their mutual collision "pushing", they way it is currently coded, causes (statistically) increased issues at corners, as it seems that while the pushing does consider slipping sideways when something is being pushed into a "wall", but once at corner, there is no "sideways" space left and the coding fails to prevent all movement in such situation.)
Something completely unrelated: Please make a screenshot of your villager farm (like the start of your video) with debug screen enabled (F3) and post it in MC-10046 (Mobs have the tendency to move to the north west corner)
You didn't mention the direction of movement, but could this be a result of MC-10046?
Vit Musienko, what you're seeing is MC-10046, maybe that's still not properly fixed.
I agree that this is no longer a duplicate of MC-10046, but the current behavior is probably intended. The last time I looked into the mob AI, it does have a weighting system for preferring certain blocks as destinations. However, I don't remember if that's the old AI or the new AI, and I think it was always a weak preference. I believe the behaviors are weighted to prefer random movement over the strict sort of rules you're suggesting.
The algorithm also has a limited search range, so if mobs wander outside the range of any of their preferred block types, they'll wander as you've described. There's not really anything that can be done about that – the larger the search radius, the more computationally expensive it is, and it will affect performance.
I think Mojang will have to make a decision on this one, but I think they'll either consider it part of Minecraft's charm, or they'll decide to rework the AI in the future, unrelated to this ticket.
Possibly a regression or a new case of old problem MC-10046. Might add that as "related"...
Update by [Mod] GoldenHelmet
Steps to reproduce
- Make a reasonably large enclosure with a flat floor made of a single block type.
- Spawn mobs that have a wandering behavior at the center of the enclosure.
- Observe the mobs over a period of time.
Expected result
Mobs drift in all directions with equal probability. A group of mobs spreads out evenly in all directions.
Actual result
Mobs drift toward the north (-Z) and west (-X) over time. A group of mobs ends up bunched in the northwest corner of an enclosure.
Test world
See this comment.
Note: This bug existed in Java edition years ago and was fixed. See MC-10046 for details including code analysis. The issue seems to have been that using a floor function on a random number generated between maximum and minimum values results in a bias toward the minimum (e.g. the effective range is -10 to +9, instead of -10 to +10).
Original description
I've noticed that animal mobs tend to migrate to the northwest in my survival worlds. I've seen it in Bedrock on Windows 10 and iOS (iPhone). It seems similar to an old Java version bug.
To test it, I created a flat world in my Bedrock Windows 10 version 1.8, and put a 2-block high barrier around an 11x11 chunk region. I killed off everything, turned natural spawning off, then spawned 121 sheep in the center chunk. After an hour and a half of waiting in the center chunk, I put fences around every chunk. Code Connection helped with all this.
I then counted the sheep in each chuck. If the sheep spread out evenly, you would expect about one per chunk. Instead, I got the counts shown in the attached image. As you can see, there is a pretty strong bias towards the northwest.
Thanks.
I have had animals swim off , to (from kilometers away), and past my island home following a northwest path. By and large it seems all the animals in my world migrate northwest unless I enclose them. Actually, if you look at large animal enclosures you can see a slight northwest bias. I hope this gets fixed as it is an annoyance when you have lived in an area a long time. Good work.
Well, I can confirm this, due to all my animals stay in one corner of huge farm.
related?:
MC-12427@ANBO Motohiko
No, that is a problem with core path-drawing methods, explained in
MC-21109, which honestly is the same problem asMC-12427andMC-4661(which have the same cause in the code), but explained in more detail for more situations. In that bug, an entity is trying to path from inside a fence. In this bug the random destinations animals choose to move in tend to be weighted northwest of it. Both bugs are annoying and should be fixed however.This is the most convincing argument I've seen for these symptoms that I've seen to date, which combined with the animals-escaping-pen (which was recently supposedly fixed), meant animal enclosures were very hard to manage. I run a Bukkit server and have seen evidence of this numerous times; conveniently, there exists a large square pen with sheep, which leave evidence (in the form of eaten grass) which is viewable on DynMap, proving that they have migrated mostly north-west, but also north-east. See attached picture.
I placed a bunch of sheep around me, trying to place them a little south east of where I was standing at the origin. I left it on while I was gone from home for 6 hours and got the picture NWtrend as my result.
I think this bug is clearly confirmed and in 1.6.2.
Just to quantify this, in each quadrant I had the given number of sheep
Northwest: 12
Northeast: 3
Southeast: 0
Southwest: 4
If you play for any extended period of time I think this is very, very noticeable.
I checked at the code level, too, and updated the version list.
This is a very annoying glitch. Many of the mobs in my zoo get stick to the North-west corners of each exhibit. If I could post a picture, I would. It's very noticeable with spiders and horses.
A screenshot of an (artificial) iron golems farm.
We can see that the villagers go in the top-right hand corner of the screen, which is North-West.
Still in 1.6.4. Very annoying, especially with animal farms.
Told them cows to not group in the NorthWest anymore, they didn't even realise they were doing it. The chickens just clucked suspiciously.
Why are all these comments about a 1.8 bug when it's a non-existent version yet?
Hooray! Excited that this is fixed. I couldn't figure out why my villagers were all gathering in one corner of the village; I didn't even think about the fact that it might be a bug. Thanks, Grum!
Please link to this comment in the description
The following is based on a decompiled version of Minecraft 1.9 using MCP 9.24 beta.
The second part of this bug is not fixed in 1.9
Note: A problem is as well that the field net.minecraft.entity.EntityCreature.homePosition is a BlockPos, but its integer values are used to get a vector used for movement without using the center of the block. An example for this is the method net.minecraft.entity.ai.EntityAIMoveTowardsRestriction.shouldExecute().
Reopened, Markku please reduce the report to point 2 only.
For easier check of its history, I'm just going to strike-through the rest, keeping point 2.
I can not reduce the code parts, and most of the description still applies (even if e.g. with slightly different numbers), so it wasn't much of a reduction. Should be clear that point 1 is not in effect, though.
Please verify it works as it should after the next snapshot! Thanks for the infos
I'm curious if this bug also affects pocket edition.