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

Community PragProg Customers
,
1

Excellent book. I like it very much. Just a few questions that occurred to me while reading the pathfinding section in Chapter 9 on page 171.

  1. On line 3, why is there a self.in_bounds wrapping can_enter_tile when can_enter_tile has a map bounds check

  2. On page 173, why do we use pathing distance? It is my understanding the Dijkstra maps do not use heuristics. Will we be using A* pathfinding at some point?

  3. Further related to that, I noticed the heuristic shown is a euclidean distance. Why is a slower heuristic used for 4-directional movement? It is my understanding that a straight line is always going to be shorter than a manhattan distance, thus causing an A* search to take longer. Not to mention that square root call. Same idea for those players wanting 8-directional movement. Why not a diagonal distance instead of a euclidean.

I also looked at bracket-lib and have a related question to the A*. Nice, by the way, with the use of the min-heap and hashmaps. I’m just curious as to why the closed_list would contain an f cost conditional.

if should_add && self.closed_list.contains_key(&idx) && self.closed_list[&idx] < s.f {

My understanding is that the closed list is just used to check where the algorithm has traversed. I can’t imagine a situation where a closed node would be revisited when using a consistent heuristic. Is that why it is there, in case someone wants to use an inconsistent heuristic.

I was also wondering why the call to add_successor adds the parents f cost to the successor instead of parents’s g cost.
.for_each(|s| self.add_successor(q, s.0, s.1 + q.f, map));

Thanks. Once again, I love this book and am looking forward to your responses.

1 Like