Would an any-angle search (Theta*) fit the library?

[tachsin]

Following the precedent in #730 — asking about fit before writing code rather than after.

The gap

astar and friends return paths constrained to the edges of the graph. On a grid that means movement is locked to 4 or 8 compass directions, so a path across open ground comes back as a staircase rather than a straight line. The path is optimal for the graph, but it is longer than the straight line it approximates, and for anything steering a physical vehicle the corners are artefacts of the discretisation rather than features of the terrain.

The usual fix is post-smoothing the A* result, which only removes corners the search already committed to.

Theta* (Nash, Daniel, Koenig, Felner) instead relaxes the constraint during the search: it propagates along graph edges as A* does, but when it reaches a node it first asks whether that node's grandparent can see the successor directly, and if so attaches the successor straight to the grandparent. The result is a path whose waypoints are graph nodes but whose segments are straight lines at any angle.

Proposed shape

The interesting part for this library is that no geometry needs to enter it. Theta* needs exactly one thing A* does not: given two nodes that may not be adjacent, can you travel straight between them, and at what cost. That is one closure, in the same style as heuristic and success:

/// `sight` reports the cost of travelling straight from one node to another,
/// or `None` when the line between them is blocked.
pub fn theta_star<N, C, FN, IN, FH, FL, FS>(
    start: &N,
    successors: FN,
    heuristic: FH,
    sight: FL,
    success: FS,
) -> Option<(Vec<N>, C)>
where
    N: Eq + Hash + Clone,
    C: Zero + Ord + Copy,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = (N, C)>,
    FH: FnMut(&N) -> C,
    FL: FnMut(&N, &N) -> Option<C>,
    FS: FnMut(&N) -> bool,

Line-of-sight and the straight-line metric both live with the caller, so N stays an opaque hashable value, C stays Zero + Ord + Copy, and nothing in the crate gains a dependency on coordinates or floating point. The body is astar with one changed relaxation step — on the order of 120 lines.

Two things that are not like the rest of the crate

Worth settling before any code exists, because both are visible in the API:

It is not optimal. Theta* finds paths no longer than the grid-constrained A* path, and in practice very close to the true any-angle optimum, but unlike astar and dijkstra it carries no optimality guarantee — the true optimum needs a visibility graph. Every other search here is exact, so this would be the first that is not, and the documentation would have to lead with that.

Consecutive path nodes need not be adjacent. The returned path is a sequence of waypoints joined by straight lines, so path.windows(2) are not necessarily edges of the successor graph. That is the whole point of the algorithm, but it differs from every other path this crate returns, and anything validating a path edge by edge would be surprised.

There is also a requirement on the caller that is worth writing down: the shortcut is only sound when a straight line is never dearer than going round, so sight has to agree with the edge costs in the triangle-inequality sense.

Questions

1. Is an inexact search something you want in the crate at all, given the above?
2. Does the single sight closure look right, or would you rather see the predicate and the metric as two parameters?
3. Grid users would otherwise have to write their own supercover line walk. Would a line-of-sight helper on Grid be welcome as a follow-up, or is that geometry you would rather keep out?
4. Lazy Theta* does roughly one line-of-sight check per expansion instead of one per generated node, for slightly longer paths. Worth having as well, or is one variant enough?

I will put a draft pull request behind this so there is something concrete to react to, but it is a proposal rather than a finished thing — happy to reshape or drop it depending on your answers, particularly to question 1.