AStarGrid2D allow_partial_path does not always find the shortest path about godot HOT 2 OPEN

I haven't officially confirmed this or anything, but my suspicion on why this happens is on how the path finding would generally go in this case trying to get to the end you labeled.

So it goes great until it reaches what I labeled as 4.
Then it would move to (unlabeled sorry) red 5, 6 and it hits a disabled location and starts checking neighbors. The lower six, then the two 7 sevens, it might follow this red path for a bit as it's searching for where there might be an opening in this line of disabled points. Eventually it wraps all the way around and it has two paths, a path of distance 15 (the one it picks), and a path of distance 17, which it doesn't because that costs more.
At this point the algorithm realizes it cannot actually reach the destination and gives up. Because you selected the option to return a partial path, it will return the last path it had (as that's how it has been implemented) which would be the path distance of 15.

You'd expect that path of 6 that you labeled, but it didn't just stop there since in theory there could've been a valid path on the opposite side of your blocked box. When it gives up is when it returns the path, which it does after it's visited all possible points that could've been enabled.

I think it might be tricky to make this a consistent thing. It could, after realizing it has no valid path at all, try again ignoring disabled points and working backwards to discard points in disconnected paths. But by ignoring disabled points you might get shorter paths than expected, like if point labeled 4 was actually disabled, then you might just get a path to 3 and that's it. You'd need to figure out a "smart" way to ignore some points, which might just be iteratively ignoring N disabled points where you increment N by one every time it completely fails. That would probably fix the potential shorter path problem, but now you're rerunning the path potentially a lot of times which would be a little wasteful. There may be some optimizations here and there too.

As I work on #93409 this might see some improvements but can't promise for sure, it'll be something I try and think on though and I'll try to "officially confirm" this bug when I have a chance as well.

from godot.

While testing this I noticed something interesting. This seems to be present only if using HEURISTIC_EUCLIDEAN or HEURISTIC_OCTILE but not present if using HEURISTIC_MANHATTAN, HEURISTIC_CHEBYSHEV as the heuristic of choice for compute/estimate.

Using Manhattan or Chebyshev you get that expected short path. Technically Chebyshev is one off, but it's still close enough, and for all your other test cases both are identical and hitting your expected label.

If you mix and match the estimate and compute methods you'll often get strange results though, typically not your expected, but also doing that is a bit strange and to be expected I think. (If the estimated cost is greater than the compute cost, AStar returns strange results. This may be happening when you mix and match heuristics and this isn't inherently an engine bug in itself, that's just a consequence of the AStar algorithm. It's not recommended to have an estimate > compute.)

Manhattan

Chebyshev

from godot.