[1.12.2] Entity pathfinder doesn't like going uphill?

[ItsTheKais]

So, I have an EntityTameable that can be told to search for a block. When it finds that block, it tries to walk as close as it can to that block, using getNavigator().tryMoveToXYZ([block coords + one y level]). Only, if the target coordinates are above the entity, the entity's navigator seems to prioritize a short path that takes the entity below the target over a longer path that will actually reach the target.

Example: In this setup, if I spawn the entity on the ground and tell it to find emerald ore, I expect that it should climb up and around the quartz path to stand on the emerald ore, since that's as close as possible to get to it. Instead, it just moseys over next to the base of the pillar (which is directly underneath the ore) and calls it a day.

It looks like this isn't only an issue with my implementation, either; I made a tamed wolf and a cow follow me, and neither of them would attempt to climb up the path to get to me unless I was within ~5 blocks of the start. This implies to me that the problem might not just be me using the pathfinder incorrectly...

I have tried:

• As a test: moving the entity partway up the path and starting there; success varied but the entity seemed more likely to jump off and hug the pillar the closer it was to the bottom.
• As a test: moving the entity to the top platform and having it find one of the ores on the ground; it correctly walks the entire path down to the ground.
• As a test: moving the entity to the top platform, building extensions that would allow it to stand directly above the ores on the ground, and having it find one of those ores. It still walks the entire path to the ground to stand right on the ores. Downhill does not seem to have this pathing problem.
• As a test: building a small labyrinth on flat ground and having it find a block at the end; it's a little confused at first and wanders around the outside wall near where the block is, but after a few seconds it figures it out. Seems to work well enough on flat ground.
• Verifying that the AI is indeed finding the correct block and sending the navigator the correct coordinates.
• Increasing the entity's follow range to 64, then to 128. I saw that this value was used for something like pathfinding range (?) and guessed that this might encourage the entity to pathfind for greater distances. I verified that the path range changed using GetNavigator().getPathSearchRange(), but it had seemingly no effect on the pathfinding.
• Going around tryMoveToXYZ() using some of the other PathNavigate and PathNavigateGround methods, which at best gave the same results.
• Extending EntityAIMoveToBlock and attempting to use it. (EntityAIMoveToBlock apparently does not path vertically at all, worthless!)

TL,DR: my fatass pet is too lazy to climb the damn stairs, wat do?

[Alexiy]

If this is a vanilla bug, then using vanilla AI tasks is worthless. While writing my mod I also have found several bugs in minecraft pathfinding code. This made me write own implementations of NodeProcessor,  PathNavigateGround and PathFinder. I can't help you with this, though, because their code is really difficult to understand. You'll have to experiment with mentioned classes.

[jabelar]

They're usually not "bugs" in the pathfinding but rather performance optimization. If you study pathfinding you see that making a pathfinding that can handle every case can quickly cause performance problems. You can easily create tricky paths (like the one in your picture, or things like large mazes) where the pathfinding will have to give up before it solves it otherwise would cause lag. Think about it -- a path finding algorithm may have to try every possible combination of path within the 3D space and that will grow quickly.

 

It is possible to implement your own pathfinding. For example, one time I was trying an entity that could destroy blocks in its way so I had to figure out some custom pathfinding that allowed it to find paths through those blocks. Pathfinding is extremely well documented in both math and computer science so you can google to find algorithms that help you. But eventually the sheer number of possible paths in a large 3D space will limit your ability to explore them all.

[ItsTheKais]

Well... out of curiosity, I did some more tests in an actual Minecraft world (random terrain and caves and all). The pathfinder seemed to work much smoother under those circumstances, figuring out paths through winding caves at least mostly-reliably? I can't think of why it would work better in a chaotic, randomly-generated environment than in my test world with simple single correct paths to follow, but I guess that means I have a lot of learning to do.

I might take a crack at writing a new pathfinder, but that's getting filed under "maybe in an update" for now.

 

Thank you for your advice.

[Draco18s]

8 minutes ago, ItsTheKais said:

with simple single correct paths to follow

Because the area outside your test location is flat and unbounded in all directions.

[jabelar]

1 hour ago, ItsTheKais said:

I can't think of why it would work better in a chaotic, randomly-generated environment than in my test world with simple single correct paths to follow, but I guess that means I have a lot of learning to do.

 

It has nothing to do with randomness and more about how specific each step has to be. In most cases in the Minecraft world there are several paths between two points, but in your case there is exactly one correct next step.

 

Then if you think about the general problem of finding the best path when there is only one exact path that works you can see how the problem gets extremely hard. Think about actually trying to code it. What should the first step be? You might think that stepping in the direction of the target is best, but in general case that isn't guaranteed. Maybe you should go sideways a bit, or backwards. Your example only goes upwards but what about a case where you have to go down a bit and then back up? No matter how you code your pathfinding you can always build a case that is bad for that algorithm.

 

In the end the only way to guarantee finding a path is by brute force, meaning try every possible valid move. But that is still hard.  In your example, if you spawned the entity right under the target block the correct block requires about 30 exact steps to get to. So you would need an algorithm that finds every combination of 30 steps to ensure you find the correct one. Sometimes it will be found early and sometimes at the end. With smarter algorithms you can make sure you don't include trying paths that cover ground you've already been on. But it still adds up. If you just do the first level of math, in each step you have 4 directions you can go. So the number of actual paths is 4 raised to the power of 30! That is 1.15x10^18 paths -- or 1.15 million million million! You can cut that down by assuming you don't go back to the space you just came from, but that is still 3^30.

 

Anyway, the number of possible paths is extremely large. The only way to really make it manageable is to limit the number of steps that the pathfinding can look for and hope that getting closer to the target is helpful overall (not always true, but often is).

 

The interesting thing is this shows how good humans are at pathfinding. We can look at a picture and almost instantly understand the path, probably because our brain can take advantage of some massively parallel processing that isn't available on a PC running Minecraft.

 

Again, there is a lot of research into this -- it is important for robotics and gaming and is interesting from a general math and computer science theory. But even the best algorithms are pretty limited.

 

EDIT: If you really want the entity to find the path using vanilla pathfinding I think it should be possible by adding more "waypoints" -- basically intermediate targets within the range of the pathfinding.

Edited June 7, 2018 by jabelar