Uploaded image for project: 'Minecraft: Java Edition'
  1. Minecraft: Java Edition
  2. MC-21109

Pathfinding is Fundamentally Flawed (it strictly follows the grid)

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Reopened
    • Resolution: Unresolved
    • Affects Version/s: Minecraft 1.5.1, Minecraft 1.5.2, Minecraft 1.6, Minecraft 1.6.1, Minecraft 1.6.2, Minecraft 1.6.4, Minecraft 1.7.1, Minecraft 1.7.2, Minecraft 13w47e, Minecraft 13w48a, Minecraft 13w48b, Minecraft 1.7.4, Minecraft 14w02c, Minecraft 14w03a, Minecraft 14w03b, Minecraft 14w05b, Minecraft 14w06b, Minecraft 14w07a, Minecraft 14w08a, Minecraft 1.7.5, Minecraft 1.7.9, Minecraft 14w18b, Minecraft 14w20b, Minecraft 14w21a, Minecraft 14w21b, Minecraft 1.8, Minecraft 1.8.1-pre3, Minecraft 1.8.8, Minecraft 15w43c, Minecraft 15w44a, Minecraft 15w46a, Minecraft 15w51b, Minecraft 1.9, Minecraft 1.9.1 Pre-Release 3, Minecraft 1.10.2, Minecraft 1.12, Minecraft 1.12.2
    • Fix Version/s: None
    • Confirmation Status:
      Confirmed
    • Category:
      Mob behaviour

      Description

      I will say right now that both MC-12427 and MC-4661 are included in what I am about to report. However, I am reporting exactly what the problem is, how they are in reality the same issue, examples of other pathfinding issues which also occur, and how it could all be fixed with a single theoretical solution. It seems sort of conceded to ask if they could be consolidated into this report, but I feel like this single one is more constructive than a bunch of little ones out there which are all symptoms of the same bug.

      The problem
      The problem with the pathfinding in Minecraft is that is uses a strictly grid-based system. This would be okay except that collisions are not as strictly grid-based. Entity movement accounts for this, but pathfinding does not. The consequences of this are far reaching. Basically there are many ways in which an entity may conclude that it cannot move when in reality it can and vice versa. Fixing this bug would make farming less frustrating and hiding from monsters much harder. Let me explain each of the four images inside the larger image I posted.

      1. Mobs (the creeper) get stuck in northwest corners
      This is a combination of things. For one thing, entities begin pathfinding from their northwest corner instead of their center. For another, they do not take into account collisions properly. This means the creeper pictured begins his pathfinding from inside the corner fence. This creeper believes he can travel both north and west because it is air, and he cannot travel either south or east because they are fences. All four of these assertions are wrong. If he were to analyze collisions instead of just the grid he would know this.

      2. Mobs are incapable of passing through half slab gaps
      Some people like and utilize this, but it is a flaw. The creeper knows he can pathfind through the center of the hole, but reasons he is too tall to put his feet through the center and his head through the half slab. This is false. He does not take into account where his feet will land, and the same can be said about his head.

      3. Mobs, especially small ones, get stuck inside walls
      The picture is a special case in which the sheep has his northwest corner inside a wall. He can clearly step back and walk through the opening in the fence to my character, but he believes the fastest way is to walk through, because he is already "inside" the fence and does not take collisions into account. This same thing will happen with small entities far more frequently because their entire collision box can fit inside the fence block. This makes it a pain to lead animals along/through fences and other thin walls.

      4. Mobs cannot navigate through gaps between blocks
      This is the same issue as the creeper who cannot walk through the half slabs but in the x and z dimensions. If the chicken were to acknowledge the size of its bounding box and which blocks it would collide with, it could reason that it is possible to fit through the gap.

      More details
      It has recently come to my attention that small entities like chickens cannot pathfind out of fence corners even if they are told they can pathfind literally anywhere. This is because they cannot draw a vector out of the fence wireframe without concluding they will collide with it.

      Theoretical solution
      Ideally, if the code could be more double-based, relying on the actual bounding box, this problem would be fixed in all instances. But, unfortunately, that would likely require a significant amount of processing. Instead, it is probably best to add more conditions to the code which allow pathing along but not through fences.

      At the very least, changing pathfinding so that entities begin from their center should fix situations 1 and 3 (MC-12427 and MC-4661 respectively) for the majority of creatures (everything but babies, silverfish, and chickens).

        Attachments

        1. 2016-03-19_13.04.06.png
          2016-03-19_13.04.06.png
          219 kB
        2. 2016-08-10_16.10.12.png
          2016-08-10_16.10.12.png
          109 kB
        3. 2018-08-18_21.52.40.png
          2018-08-18_21.52.40.png
          493 kB
        4. 2018-08-18_21.56.53.png
          2018-08-18_21.56.53.png
          486 kB
        5. 2018-08-18_21.56.53.png
          2018-08-18_21.56.53.png
          486 kB
        6. pathfind.png
          pathfind.png
          653 kB

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                DV King Daniel King
              • Votes:
                49 Vote for this issue
                Watchers:
                25 Start watching this issue

                Dates

                • Created:
                  Updated:
                  CHK: