AStar2D pathfinding does not always find shortest path by weight

[ToyWalrus]

Godot version

v3.4.4.stable.official [419e713a2]

System information

Windows 10 64-bit

Issue description

When using the AStar2D class for pathfinding with some tiles weighted differently than others, the calculation does not always return the lowest cost path. (Though it always returns the same path route for the same start and end points, which is expected)

When looking through previous issue posts I came across this one, which, from the description, sounded most like the issue I was seeing. https://github.com/godotengine/godot/issues/37944 However I didn't understand the user's conclusion and even after reading through the C++ source myself I couldn't figure out what they meant by "cost" instead of "weight."

I have one theory, which is that the issue lies in the calculation of the _computed_cost() function. If a point on a grid is diagonal from an origin point and they're connected as neighbors, the distance between those two points is going to be longer than another neighboring point which is orthogonal to the origin point. #ThanksPythagoras Thus when calculating the distance, pathfinding will always prefer a straight path over a path with diagonals, all other things being equal. I'm not familiar enough with the exact C++ implementation in the Godot source to be able to point it out exactly, but that's my initial thought.

Steps to reproduce

Some preliminary knowledge: the blank tiles are weighted as 1 and water tiles are weighted as 2. This weight only applies when entering a tile, since that's how the AStar algorithm works with my implementation.

1. Run the crop.py script in assets/tiles/0x72_DungeonTileset which will populate a new folder with individual sprites that are used as the tilemap and character
2. Open and run the MovementDemo scene
3. Click on the tile two spaces directly above the knight (the one right above water)
4. Observe the knight goes diagonal up left then diagonal up right because the cost of that path is 2 and going through the water would be a 3 cost path.
5. Click on the tile where the knight started
6. See that the knight does not move because his max speed is 3, but the AStar pathfinding returns a path of cost 4 instead of the 3 cost path it should be in order to get back.
   • You can also see that if you click the tiles individually in the expected path back to the start position that they're not 1-way tiles either

The relevant script would be scripts/environment/pathfinder.gd in the path_cost() method.

Minimal reproduction project

https://github.com/ToyWalrus/ProjectDelve/tree/astar-issue (can't seem to upload the zip) This branch has a .gif file in the root that displays the issue

[smix8]

Short: Your Pathfinder class cost function assumes that weights are fixed costs and they are not. They are named weight_scale because they scale the geometry distance cost between two points by the weight scale of the endpoint.

Long: AStar Classes do not know if a grid restriction is used. They work with geometry distances between points.

AStar Classes by default use the geometry distance between two points as the section cost. The weight is a scale not a fixed cost and it scales the distance between two points by multiplying the geometry distance from point A to point B with the weight scale value of point B.

Grid pathfinding has the core problem that only the left / top / right/ bottom neighbor cells have a distance of 1 unit. The top-left / top-right / bottom-right / bottom-left have a distance of 1.4 units with diagonal movement.

Looking at your animated gif.

The cost for the path zigzag up is 2.8 (1.4 geometry unit x 1 weight scale x 2 cells). The cost for the path zigzag back down is 4.2 (1.4 geometry unit x 1 weight + 1.4 unit x 2 weight to enter water).

The cost for a straight path up would be 3.0 (1 unit x 2 weight + 1 unit x 1 weight) The cost for a straight path back down would be 4.0 (1 unit x 2 weight x 2 cells).

I hope I did not add any typo / math error (I am falling asleep rightnow) but I think you get the gist what is wrong and how to fix.

[ToyWalrus]

@smix8 Thank you for that explanation, that makes sense. I guess I had made the assumption that AStar would assume a grid pattern, but I guess I was wrong there.

I guess I could write a grid scaling function that would transform the points before giving them to AStar so that the distance between two diagonal points is 1, but I'm not sure if that would have any unforseen consequences of incorrectly calculating orthogonal distances... It would probably only happen when the distance would be long enough that rounding might say the distance is 1 shorter than it looks...

Is there a better way to handle this problem? Have you seen it before?

[smix8]

The current way to handle this is to extend the AStar Classes with a script and override the methods _compute_cost() and _estimate_cost() with a custom function. E.g. replaced with a function that uses no geometry distances between points but calculates the cost with fixed cell units.