Add support for computing an early abort for Astar based on cost

[RaminKav]

The problem im trying to solve is for astar calls that run forever. This typically happens when the target is unreachable (enclosed in walls, or on an unreachable tile, etc).

Bidirectional AStar would solve this, but another hacky way is to set a fallback limit on depth/steps for the astar search. An easy way would be to pass in the total cost as part of the success callback, so one could do something like |pos, cost| pos == target || cost > 500.

Im curious on if there are better ways to solve this issue in general, I would love to hear any thoughts on this, although perhaps it is a bit out of scope of this crate!

If the parameter approach is interesting, id be happy to open a PR for this.

[samueltardieu]

I would think that you would want to limit the number of steps rather than the cost. You can already do that by incrementing a variable in the success function and returning true if it reaches a given value. You would then have to check the return of astar to see if this is a true, or you could also set an additional boolean in the success function to reflect the fact that you have aborted the search.

Another way, as you suggest, would be to pass a state to the success function (with the cost, number of steps, etc.), and let it return either Success, Failure, or Abort. It you have a signature to suggest, that might be useful for what you want to do.

[RaminKav]

Ah yes, steps would be ideal, good point. Using a counter in the success function worked great, I had tried incrementing in the successors and heuristic callbacks and was running into BC issues, didnt realize i could increment inside the success function too, that makes a lot more sense!

I think as i thought about it more, i might still need to do some extra work before calling astar to detect if the target is in a separate "island" using a flood-fill algorithem.

For the signature, did you mean something like FS: FnMut(&N, usize, &C) -> bool, for success ? This would pass in the index (for number of steps) and cost.

[samueltardieu]

Either that, or something like

pub struct AstarProgress<'C> {
  number_of_steps: usize,
  current_cost: C,
  current_depth: usize,  // Depth since the start of the A* search
}

pub enum AstarResult {
  Success,
  Continue,
  Abort,
}

with FS: FnMut(&N, &AstarProgress) -> AstarResult.

It would be easy to maintain the current API while offering a new one with the full capabilities without duplicating the code. It would also make sense to replicate this scheme for other exploration methods. Also, AstarProgress could be easily extended in the future if needed.