API tools faq
paste
Advertisement
theosib

MC-4 fix description

theosib
May 20th, 2018
360
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.78 KB | None | 0 0
raw download clone embed print report
  1. *The following describes what we believe to be a complete and proper fix for MC-4*
  2.  
  3. Earlier, I mentioned that fixing this would be a waste of Mojang developer time, but I picked this as a *personal* challenge, because it's such an old bug, and so many people have thought it was "too hard" to fix. It did take me a few tries and a few days to get to this solution, but the final solution is comprehensive while being relatively noninvasive and compact.
  4.  
  5. Some inspiration came from experience I have with lossy video compression algorithms; predictively-encoded video frames must be computed based on full knowledge of what the decoder is going to compute from the compressed frame data or else compression artifacts will compound. Moreover, over the years, better quality and compression has been squeezed out of older video formats by encoding frames in ways that are legal but not necessarily anticipated by the original developers of the protocol.
  6.  
  7. My fix (I argue not merely a hack or workaround) for MC-4 is server-side only, doesn't impact many classes, adds negligible CPU overhead (I profiled it), works with any kind of edge (block, wall, stair, open trap door, etc.), has no unwanted side-effects that we can detect, naturally keeps all clients in agreement, works with the existing wire protocol, and doesn't generate any additional protocol traffic.
  8.  
  9. I restrict the following explanation to item entities, although my solution DOES apply to position updates of all entities that rely on code in the Entity base class to compute relative motion packets. Moreover, the technique could probably be abstracted to other kinds of entity data, such as velocity.
  10.  
  11. h1. Background
  12.  
  13. Entities are created and have their positions updated on clients by a combination of spawn, teleport, and relative motion/orientation network packets. (Others like head motion, velocity, are out of scope and not relevant.)
  14.  
  15. Spawn packets use full double precision floating point, giving the client the exact same coordinates as the server. Periodically and when entities move more than 7 or 8 blocks in any direction, teleport packets are used, which also use full double precision.
  16.  
  17. For smaller movements, relative motion (and orientation) packets are used. They rely on encoding position deltas in a 4.12 fixed-point format (4 integer bits including sign, 12 fractional bits). They are computed by subtracting a fixed-point version of the previously known position from a fixed-point conversion of the entity's current position. Algebraically, the delta is equivalent to the following (for X, Y, and Z):
  18. {noformat}
  19. deltaX = floor(currentX * 4096) - floor(previousX * 4096)
  20. {noformat}
  21.  
  22. An important realization for me was that these packets do not represent motion relative the previously known position. Rather, they are motion relative to a *quantized* version of the previously known location. The client implements the correct inverse function, which is equivalent to the following (for X, Y, and Z):
  23. {noformat}
  24. newX = (floor(oldX * 4096) + deltaX) / 4096
  25. {noformat}
  26.  
  27. Even if an entity has not moved at all, the server periodically sends position updates. So a very short time after a spawn or teleport packet is sent, a zero-delta relative motion packet is sent, immediately quantizing the position on the client side. The rounding caused by this quantization is always towards negative infinity (because of floor). As a result, if an entity overlaps the edge of a block (or other shape) by less than 1/4096, then this bug will manifest if the entity is on the -X or -Z side. The bug DOES NOT manifest if the entity is resting on the +X or +Z side.
  28.  
  29.  
  30. h1. The solution
  31.  
  32. This fixed-point encoding employed by Minecraft to send relative motion has been criticized as being a flawed design. I disagree: It is an engineering choice as good as any other. The problem stems from fact that the rounding is always in the same direction (towards negative infinity). The solution is therefore to add the ability to round towards *positive infinity instead* when that achieves the desired result on the client.
  33.  
  34. h2. Computing better quantized coordinates for the client
  35.  
  36. The heart of my solution is a method ({{computeCorrectedClientPos}}) added to the Entity base class to compute quantized coordinates that are more suitable for computing fixed-point motion deltas. This method is only used when fixed-point/quantized coordinates are required, and the results are cached in the Entity object. As a result, this method does not need to be executed very often and it's certainly FAR cheaper than the "move" method. When entity double-precision coordinates are updated, the cached quantized coordinates are invalidated.
  37.  
  38. The code for this is provided in an attachment and works as follows:
  39.  
  40. * Compute quantized versions of the current Entity X,Y,Z in the following manner:
  41. ** {{double quantX = Math.floor(posX * 4096.0) / 4096.0;}} (etc.)
  42.  
  43. * Compute any necessary rounding correction on Y as follows:
  44. ** Make a copy of the full precision Entity AABB, but assign the value of {{minY}} to {{maxY}}, so that the box is _zero height_ and at at the bottom. (See Footnote) Call this the {{serverAABB}}.
  45. ** Make another copy of the Entity AABB, this time setting minY and maxY to the quantized version of the entity Y coordinate. Call this {{clientAABB}}.
  46. ** Ask World to compute collision box lists for {{serverAABB}} and {{clientAABB}}.
  47. ** Subtract the server list from the client list, yielding a list of collisions that will occur on the client _but not_ on the server.
  48. ** If this difference list is not empty, add 1/4096 to {{quantY}} to correct the rounding artifact.
  49.  
  50. * Compute any necessary rounding correction on X and Z as follows:
  51. ** Compute a {{bottomY}} that is the server AABB minY minus a very small fractional value. We will use this to determine what the entity is "resting on" by computing world collisions with a zero-height AABB at a slightly lower Y value.
  52. ** Make a copy of the full precision Entity AABB, but set both {{minY}} and {{maxY}} equal to {{bottomY}}. Call this {{serverAABB}}.
  53. ** We need to compare {{serverAABB}} to how quantization is going to shift the box on the client. A {{clientAABB}} is computed as follows:
  54. *** min X,Y,Z are set to {{quantX-width/2}}, {{bottomY}}, {{quantZ-width/2}}
  55. *** max X,Y,Z are set to {{quantX+width/2}}, {{bottomY}}, {{quantZ+width/2}}
  56. ** Ask World to compute collision box lists for {{serverAABB}} and {{clientAABB}}.
  57. ** Subtract the client list from the server list (opposite to how Y is handled), yielding a list of collisions that exist on the server _but not_ on the client.
  58. ** If the difference list is _not empty_, iterate over it, using the name {{box}} to refer to each list entry:
  59. *** If there exists at least one one box such that {{(serverAABB.maxX > box.minX && clientAABB.maxX <= box.minX)}}, then the final quantX shall be increased by 1/4096.
  60. *** If there exists at least one one box such that {{(serverAABB.maxZ > box.minZ && clientAABB.maxZ <= box.minZ)}}, then the final quantZ shall be increased by 1/4096.
  61.  
  62. * Finally, store the quantized and potentially adjusted X,Y,Z coordinates in double precision Entity member variables (i.e. {{clientPosX}}, etc.).
  63.  
  64.  
  65. h2. Using computeCorrectedClientPos for relative motion
  66.  
  67. The first place computeCorrectedClientPos is used is in {{net.minecraft.entity.EntityTrackerEntry#updatePlayerList()}}, which accepts a list of EntityPlayer and sends packets to all players currently able to see the Entity being tracked by the EntityTrackerEntry object. Based on the latest MCP symbols, there is the currently existing code:
  68. {code:java}
  69. i1 = EntityTracker.getPositionLong(this.trackedEntity.posX);
  70. i2 = EntityTracker.getPositionLong(this.trackedEntity.posY);
  71. j2 = EntityTracker.getPositionLong(this.trackedEntity.posZ);
  72. {code}
  73.  
  74. I replaced it with the following:
  75. {code:java}
  76. if (mc4_fix && this.updateCounter > 0) {
  77. corrected = trackedEntity.computeCorrectedClientPos();
  78. i1 = EntityTracker.getPositionLong(this.trackedEntity.clientPosX);
  79. i2 = EntityTracker.getPositionLong(this.trackedEntity.clientPosY);
  80. j2 = EntityTracker.getPositionLong(this.trackedEntity.clientPosZ);
  81. } else {
  82. i1 = EntityTracker.getPositionLong(this.trackedEntity.posX);
  83. i2 = EntityTracker.getPositionLong(this.trackedEntity.posY);
  84. j2 = EntityTracker.getPositionLong(this.trackedEntity.posZ);
  85. }
  86. {code}
  87.  
  88. The computeCorrectedClientPos method returns a boolean (assigned here to "corrected") that is true if (a) new client quantized coordinates had to be calculated, *and) (b) any rounding corrections were made. When this flag is set, we need to ensure that if *any* of the SPacketEntity subclasses (relmove, look, lookmove) is used (which will cause the client to immediately quantize its coordinates and wrongly), then the correction is applied, even if the square of the magnitude of the translation is less than 128/4096 (which is the usual threshold for deciding to send a position change to the client). So this:
  89. {code:java}
  90. boolean flag = j * j + k * k + l * l >= 128L || this.updateCounter % 60 == 0;
  91. {code}
  92.  
  93. becomes this:
  94. {code:java}
  95. boolean flag = j * j + k * k + l * l >= 128L || this.updateCounter % 60 == 0 || corrected;
  96. {code}
  97.  
  98. If any of the fixed-point relative motion/orientation packets (SPacketEntity) is sent, then a flag (clientPosQuantized) is set on the tracked entity, indicating that clients are now using quantized coordinates.
  99.  
  100. If any of the conditions for sending a SPacketEntity packet fails, then a teleport packet is generated, which uses double precision floating point. In that case, the clientPosQuantized is cleared, and the quantized coordinates are marked invalid.
  101.  
  102. Existing code in {{EntityTrackerEntry#updatePlayerList}} stores the last-known fixed-point coordinates, and the coordinates computed include any rounding corrections so that the server knows exactly where clients think the entity is. Thus, when a subsequent relative motion packet it sent (based on new quantized coordinates with or without rounding corrections), the correct fixed-point deltas will always be computed and sent.
  103.  
  104.  
  105. h2. ending the right coordinates in spawn packets for new clients
  106.  
  107. It is important that all clients agree on entity coordinates. If a user is logged in and drops an item, it will spawn with floating point coordinates, but those will very quickly get quantized. If another user logs in, their client finds out about entities via spawn packets (SPacketSpawnObject), but those use floating point. This new client would have coordinates that lack any corrections applied to coordinates for other clients. Therefore, it was also necessary modify how spawn packet coordinates are chosen. If the most recent coordinates sent to clients were absolute (double precision), then the Entity will have its clientPosQuantized flag cleared, so the spawn packet will send the Entity's "real" coordinates. If the most recent coordinates for the Entity were updated by a relative motion packet, then the clientPosQuantized flat will be sent, and the spawn packet will have to use those quantized coordinates in order to ensure that the new client is in agreement with all the other clients. The two spawn packet types modified are SPacketSpawnObject and SPacketSpawnMob, where this code:
  108. {code:java}
  109. this.x = entityIn.posX;
  110. this.y = entityIn.posY;
  111. this.z = entityIn.posZ;
  112. {code}
  113.  
  114. is changed to this:
  115. {code:java}
  116. if (EntityTrackerEntry.mc4_fix && entityIn.clientPosQuantized) {
  117. entityIn.computeBestClientPos();
  118. this.x = entityIn.clientPosX;
  119. this.y = entityIn.clientPosY;
  120. this.z = entityIn.clientPosZ;
  121. } else {
  122. this.x = entityIn.posX;
  123. this.y = entityIn.posY;
  124. this.z = entityIn.posZ;
  125. }
  126. {code}
  127.  
  128.  
  129.  
  130. h1. Justification for this being a valid fix
  131.  
  132. I argue that this is a "proper fix" and not merely a hack or work-around, because what it does is correct an algorithmic flaw in how coordinates are rounded when converting them to fixed-point. No matter what, the quantization of the existing approach sends *inaccurate* information to the client, where that inaccuracy is caused by a loss of precision. Despite the precision loss, my solution improves the *accuracy* of the final position computed by the client, within the limits of the existing protocol.
  133.  
  134. h1. Acknowledgements
  135.  
  136. I must first acknowledge the numerous people who have commented on this bug report, including my one of my heroes, Panda4994. They have provided critical information that made investigating and fixing this bug much easier than it otherwise would have been. When getting started on fixing this bug, I got information from and questions answered by number of people on the EigenCraft Discord. And then with great patience through three attempts to solve this problem over the last three days, they comprehensively tested this fix, finding flaws in my earlier designs. I want to credit the following people (hopefully nobody was left out):
  137. * Xcom, nessie (Frogthink), DuckDuckLoop, tryashtar, commandblockguy, NarcolepticFrog, 0n-s, Earthcomputer, Pokechu22, masa, EDDxample, RubiksExplosion, RaysWorks, Nodnam.
  138.  
  139.  
  140.  
  141.  
  142. *Footnote:* We _really_ only care about the "feet" position. We are only trying to adjust rounding so that client and server agree about what the entity is resting on. Also, by making it zero-height, computing collisions with the world and other entities is super cheap. The search volume is very small, and the size of the resulting collision list is also minimized, making other computations cheap as well.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!