Hands-on Rust: Dijkstra's/A* questions

Pragmatic Bookshelf PragProg Customers
,
4

You got me curious (dangerous!), so I hacked in a diagonal distance heuristic.

fn distance2d_diagonal(start: Point, end: Point) -> f32 {
    i32::max(
        (start.x - end.x).abs(),
        (start.y - end.y).abs()
    ) as f32
}

Running the A* example using this heuristic gives a good path:

image
image567×339 1.58 KB

Benchmarking it:

Pythagoras: 812.22 us (best), 822.55 us (average), 835.07 us (worst)
Diagonal: 792.95 us (best), 801.07 us (average), 811.37 us (worst)

Edit: I took out the && self.closed_list[&idx] < s.f and benchmarked it. It gives a small improvement: 810.87 us (best), 819.79 us (average), 830.17 us (worst) - using the Pythagoras default in the benchmark. I’ll set my computer testing that over a few million maps overnight to make sure it doesn’t break anything before I push the change upstream.

So I think you’re onto a winner, albeit by a small margin. I’ll look to include that as an option in the next bracket-pathfinding crate release. Thanks!

1 Like