condor-pathfinding-navmesh 0.4.0

Navmesh pathfinding algorithms and prepared routing structures for Condor.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

//! Funnel / string-pull over a navmesh corridor to shorten a seed polyline.
//!
//! # Role
//!
//! Shared geometric post-process for every public navmesh router. After cell
//! search yields a [`NavmeshCorridor`] and seed points (portal midpoints, TRA*
//! waypoint-DB seeds, or Polyanya waypoints), [`pull_string`] drops intermediate
//! vertices while [`Navmesh::segment_is_walkable`] still holds. It never expands
//! cells or portals and does not re-plan the corridor—only tautens the seed
//! polyline inside the existing channel.

use super::corridor::NavmeshCorridor;
use crate::{Navmesh, Point2};

/// Tautens `initial_points` inside `corridor` using navmesh segment walkability.
///
/// Forces the polyline to begin at `corridor.start` and end at `corridor.goal`,
/// deduplicating consecutive equal points. For each remaining vertex, pops prior
/// vertices while the segment from the second-to-last kept point to the candidate
/// stays walkable. Does not re-verify that intermediates stay inside `corridor.cells`
/// beyond what [`Navmesh::segment_is_walkable`] already enforces on the mesh.
pub fn pull_string(
    navmesh: &Navmesh,
    corridor: &NavmeshCorridor,
    initial_points: Vec<Point2>,
) -> Vec<Point2> {
    let mut deduped = Vec::with_capacity(initial_points.len() + 2);
    deduped.push(corridor.start);
    for point in initial_points {
        if deduped
            .last()
            .is_some_and(|last| points_equal(*last, point))
        {
            continue;
        }
        deduped.push(point);
    }
    if deduped
        .last()
        .is_none_or(|last| !points_equal(*last, corridor.goal))
    {
        deduped.push(corridor.goal);
    }

    let mut taut = Vec::with_capacity(deduped.len());
    for point in deduped {
        while taut.len() >= 2 && navmesh.segment_is_walkable(taut[taut.len() - 2], point) {
            taut.pop();
        }
        taut.push(point);
    }
    taut
}

fn points_equal(a: Point2, b: Point2) -> bool {
    (a.x - b.x).abs() <= 1e-9 && (a.y - b.y).abs() <= 1e-9
}