Minecraft
  1. Minecraft
  2. MC-10046

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

    Details

    • Type: Bug Bug
    • Status: Resolved
    • Resolution: Fixed
    • Affects Version/s: Minecraft 1.4.7, Minecraft 1.5, Minecraft 1.6.1, Minecraft 1.6.2, Minecraft 1.6.4, Minecraft 1.7.2
    • Security Level: Minecraft - Public (Viewable by everyone)
    • Labels:
      None
    • Confirmation Status:
      Plausible
    • Game Mode:
      Creative

      Description

      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.

      1. 2013-07-08_12.54.08.png
        1.56 MB
      2. 2013-10-07_21.38.02.png
        348 kB
      3. 2013-10-07_21.54.17.png
        762 kB
      4. NWtrend.png
        471 kB
      5. ScreenHunter025b.png
        53 kB

        Issue Links

          Activity

          Hide
          [Helper] Marcono1234 added a comment - - edited

          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

          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.

          /**
           * searches 10 blocks at random in a within par1(x,z) and par2 (y) distance, ignores those not in the direction of
           * par3Vec3, then points to the tile for which creature.getBlockPathWeight returns the highest number
           */
          private static Vec3d findRandomTargetBlock(EntityCreature entitycreatureIn, int xz, int y, Vec3d targetVec3)
          {
              PathNavigate pathnavigate = entitycreatureIn.getNavigator();
              Random random = entitycreatureIn.getRNG();
              boolean flag = false;
              int i = 0;
              int j = 0;
              int k = 0;
              float f = -99999.0F;
              boolean flag1;
          
              //...
          
              for (int j1 = 0; j1 < 10; ++j1)
              {
                  int l = random.nextInt(2 * xz + 1) - xz;
                  int k1 = random.nextInt(2 * y + 1) - y;
                  int i1 = random.nextInt(2 * xz + 1) - xz;
          
                  if (targetVec3 == null || (double)l * targetVec3.xCoord + (double)i1 * targetVec3.zCoord >= 0.0D)
                  {
                      //...
          
                      l = l + MathHelper.floor_double(entitycreatureIn.posX);
                      k1 = k1 + MathHelper.floor_double(entitycreatureIn.posY);
                      i1 = i1 + MathHelper.floor_double(entitycreatureIn.posZ);
                      BlockPos blockpos1 = new BlockPos(l, k1, i1);
          
                      if ((!flag1 || entitycreatureIn.isWithinHomeDistanceFromPosition(blockpos1)) && pathnavigate.func_188555_b(blockpos1))
                      {
                          float f1 = entitycreatureIn.getBlockPathWeight(blockpos1);
          
                          if (f1 > f)
                          {
                              f = f1;
                              i = l;
                              j = k1;
                              k = i1;
                              flag = true;
                          }
                      }
                  }
              }
          
              if (flag)
              {
                  // Still using floor method
                  return new Vec3d((double)i, (double)j, (double)k);
              }
              else
              {
                  return null;
              }
          }
          

          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().

          Show
          [Helper] Marcono1234 added a comment - - edited 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 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. /** * searches 10 blocks at random in a within par1(x,z) and par2 (y) distance, ignores those not in the direction of * par3Vec3, then points to the tile for which creature.getBlockPathWeight returns the highest number */ private static Vec3d findRandomTargetBlock(EntityCreature entitycreatureIn, int xz, int y, Vec3d targetVec3) { PathNavigate pathnavigate = entitycreatureIn.getNavigator(); Random random = entitycreatureIn.getRNG(); boolean flag = false ; int i = 0; int j = 0; int k = 0; float f = -99999.0F; boolean flag1; //... for ( int j1 = 0; j1 < 10; ++j1) { int l = random.nextInt(2 * xz + 1) - xz; int k1 = random.nextInt(2 * y + 1) - y; int i1 = random.nextInt(2 * xz + 1) - xz; if (targetVec3 == null || ( double )l * targetVec3.xCoord + ( double )i1 * targetVec3.zCoord >= 0.0D) { //... l = l + MathHelper.floor_double(entitycreatureIn.posX); k1 = k1 + MathHelper.floor_double(entitycreatureIn.posY); i1 = i1 + MathHelper.floor_double(entitycreatureIn.posZ); BlockPos blockpos1 = new BlockPos(l, k1, i1); if ((!flag1 || entitycreatureIn.isWithinHomeDistanceFromPosition(blockpos1)) && pathnavigate.func_188555_b(blockpos1)) { float f1 = entitycreatureIn.getBlockPathWeight(blockpos1); if (f1 > f) { f = f1; i = l; j = k1; k = i1; flag = true ; } } } } if (flag) { // Still using floor method return new Vec3d(( double )i, ( double )j, ( double )k); } else { return null ; } } 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() .
          Hide
          [Mod] FVbico (Steven Verberne) added a comment -

          Reopened, Markku please reduce the report to point 2 only.

          Show
          [Mod] FVbico (Steven Verberne) added a comment - Reopened, Markku please reduce the report to point 2 only.
          Hide
          Markku added a comment - - edited

          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.

          Show
          Markku added a comment - - edited 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.
          Hide
          [Mojang] Grum (Erik Broes) added a comment -

          Please verify it works as it should after the next snapshot! Thanks for the infos

          Show
          [Mojang] Grum (Erik Broes) added a comment - Please verify it works as it should after the next snapshot! Thanks for the infos
          Hide
          Anomonous Anomonous added a comment -

          I'm curious if this bug also affects pocket edition.

          Show
          Anomonous Anomonous added a comment - I'm curious if this bug also affects pocket edition.

            People

            • Assignee:
              [Mojang] Grum (Erik Broes)
              Reporter:
              Markku
            • Votes:
              22 Vote for this issue
              Watchers:
              12 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:
                CHK: