fix(astar): Ord impl on SmallestCostHolder was half backward

[rjooske]

The Ord is implemented on SmallestCostHolder backward so the heap becomes a min-heap, except that SmallestCostHolder::cost wasn't compared backward. I think this is a bug but maybe I'm not seeing something and it's intentional, I'm not sure. One test case also needs to be fixed if this is a bug, which this PR does too.

[codspeed-hq[bot]]

CodSpeed Performance Report

Merging #577 will degrade performances by 95.41%

_{Comparing rjooske:fix/astar_ord_impl (dc8a3e7) with main (3c3f05f)}

Summary

⚡ 2 improvements ❌ 4 regressions ✅ 28 untouched benchmarks

:warning: _Please fix the performance issues or acknowledge them on CodSpeed._

Benchmarks breakdown

	Benchmark	main	rjooske:fix/astar_ord_impl	Change
❌	fill-corner_to_corner_astar	121.7 µs	1,559.2 µs	-92.19%
❌	fill-corner_to_corner_bfs	1.3 ms	1.5 ms	-11.78%
⚡	fill-corner_to_corner_dijkstra	1.4 ms	1.2 ms	+17.3%
❌	fill-corner_to_corner_fringe	107.4 µs	142.7 µs	-24.75%
⚡	fill-no_path_astar	1.6 ms	1.2 ms	+25.97%
❌	corner_to_corner_astar	90 µs	1,962.3 µs	-95.41%

[samueltardieu]

Hi.

From what I remember, it was on purpose, but I should have added some comments to SmallestCostHolder. Here are the one I propose to add:

/// This structure is used to implement Rust's max-heap as a min-heap
/// version for A*. The smallest `estimated_cost` (which is the sum of
/// the `cost` and the heuristic) is preferred. For the same
/// `estimated_cost`, the highest `cost` will be favored, as it may
/// indicate that the goal is nearer, thereby requiring fewer
/// exploration steps.

This is reflected by the test you had to modify, in which the number of steps increased from 11 to 14 when applying your proposed change.

Thanks for helping me bettering pathfinding, don't hesitate to reopen if you think I missed something.

[rjooske]

estimated_cost (which is the sum of the cost and the heuristic)

Ohh right, that's what I was missing. I assumed that it was just the value from the heuristic. Thank you for your explanation!