blockworx/widget/

waypoint_router.rs

use std::collections::BTreeMap;

use blockworx_router::{
    ClosedRouter, Direction, WIRE_COST, cost::Cost, direction_between, point::Point,
};

use crate::{
    edit::create::PathOrdinal,
    widget::{edge::RouteEdge, segmentkind::SegmentKind},
};

/// Route one leg, but PREFER a straight axis-aligned segment whenever one is
/// legal: if `a` and `b` share a row or column and the direct wire neither crosses
/// nor hugs a block, take it — even if the pathfinder could find a lower-cost
/// detour around existing wires. Legs that are non-colinear, cross a block, or
/// would hug one (run alongside an edge within the routing gutter) fall back to
/// [`ClosedRouter::route_leg`], which bows out into the gutter. This keeps a
/// hand-placed waypoint path literal: a straight run between two waypoints stays
/// straight.
fn route_leg_preferring_straight(
    router: &mut ClosedRouter,
    a: Point,
    b: Point,
    incoming: Option<Direction>,
) -> (Vec<Point>, Option<Direction>) {
    if a != b
        && (a.x == b.x || a.y == b.y)
        && !router.is_wire_blocked(a, b)
        && !router.wire_hugs_block(a, b)
    {
        (vec![a, b], direction_between(a, b))
    } else {
        router.route_leg(a, b, incoming)
    }
}

#[derive(Copy, Clone)]
pub struct TaggedPoint {
    pub segment: SegmentKind,
    pub pos: Point,
}

impl std::fmt::Debug for TaggedPoint {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self.segment {
            SegmentKind::StartToEnd => write!(f, "s->e {}", self.pos),
            SegmentKind::StartToWaypoint(wp) => {
                write!(f, "s->wp[{}] {}", usize::from(wp), self.pos)
            }
            SegmentKind::WaypointToWaypoint(wp0, wp1) => {
                write!(
                    f,
                    "wp[{}]->wp[{}] {}",
                    usize::from(wp0),
                    usize::from(wp1),
                    self.pos
                )
            }
            SegmentKind::WaypointToEnd(wp) => {
                write!(f, "wp[{}] -> e {}", usize::from(wp), self.pos)
            }
        }
    }
}

// ── Closed-router bridge ────────────────────────────────────────────────────
// The closed router is store-agnostic (it knows only `Point`s), so these
// widget-layer free functions carry the `PathOrdinal`/`RouteEdge` types across the
// boundary, keeping the router/widget layering clean.

/// Route `start → each waypoint (by id) → end` on a [`ClosedRouter`], resolving
/// waypoint positions through `wp_positions`. Adds NO geometry (channels were
/// seeded at build): each leg is routed with [`ClosedRouter::route_leg`].
///
/// When `apply_self_cost` is true, each leg's `WIRE_COST` occupancy is applied in
/// place with [`ClosedRouter::bump_leg`] so the route's later legs spread off its
/// earlier ones — used when committing/routing a real route. When false, the
/// router is left byte-identical (read-only routing) — used for the live `RouteTool`
/// preview against a cached router that must not accumulate the in-progress route's
/// own occupancy between frames. `wp_positions` must contain every id in `wp_ids`.
/// Whether a routed leg adds its own occupancy to the graph, so later legs of
/// the same route avoid it. The live preview skips it: it re-routes the head
/// leg every frame and must not accumulate cost.
///
/// Only the router's own comparison test builds the `Skip` form today: the live
/// preview reaches the same result through [`route_fixed_legs`] + [`route_to_head`]
/// rather than this entry point.
#[cfg_attr(
    not(test),
    allow(dead_code, reason = "Skip is exercised by tests only")
)]
#[derive(Clone, Copy, PartialEq, Eq)]
pub enum SelfCost {
    Apply,
    Skip,
}

/// A route to lay out: its two endpoints and the waypoints in between (ids in
/// order, positions by id), plus whether each routed leg adds its own occupancy.
pub struct RouteRequest<'a> {
    pub start: Point,
    pub end: Point,
    pub wp_ids: &'a [PathOrdinal],
    pub wp_positions: &'a BTreeMap<PathOrdinal, Point>,
    pub self_cost: SelfCost,
}

impl RouteRequest<'_> {
    pub fn route(&self, router: &mut ClosedRouter) -> Vec<TaggedPoint> {
        let Self {
            start,
            end,
            wp_ids,
            wp_positions,
            self_cost,
        } = *self;
        let bump = |router: &mut ClosedRouter, subpath: &[Point]| {
            if self_cost == SelfCost::Apply {
                router.bump_leg(subpath, WIRE_COST);
            }
        };
        let mut path = Vec::new();
        let mut incoming: Option<Direction> = None;
        let Some(&first_id) = wp_ids.first() else {
            // No waypoints: a single start → end leg.
            let (subpath, _) = route_leg_preferring_straight(router, start, end, incoming);
            bump(router, &subpath);
            return subpath
                .into_iter()
                .map(|pos| TaggedPoint {
                    pos,
                    segment: SegmentKind::StartToEnd,
                })
                .collect();
        };

        let (subpath, outgoing) =
            route_leg_preferring_straight(router, start, wp_positions[&first_id], incoming);
        incoming = outgoing;
        bump(router, &subpath);
        path.extend(subpath.into_iter().map(|pos| TaggedPoint {
            pos,
            segment: SegmentKind::StartToWaypoint(first_id),
        }));

        for w in wp_ids.windows(2) {
            let (a_id, b_id) = (w[0], w[1]);
            let (subpath, outgoing) = route_leg_preferring_straight(
                router,
                wp_positions[&a_id],
                wp_positions[&b_id],
                incoming,
            );
            incoming = outgoing;
            bump(router, &subpath);
            path.extend(subpath.into_iter().map(|pos| TaggedPoint {
                pos,
                segment: SegmentKind::WaypointToWaypoint(a_id, b_id),
            }));
        }

        let last_id = wp_ids.last().copied().unwrap_or(first_id);
        let (subpath, _) =
            route_leg_preferring_straight(router, wp_positions[&last_id], end, incoming);
        bump(router, &subpath);
        path.extend(subpath.into_iter().map(|pos| TaggedPoint {
            pos,
            segment: SegmentKind::WaypointToEnd(last_id),
        }));
        path
    }
}

/// The fixed portion of an in-progress route — `start → each waypoint → the last
/// waypoint` — computed once and reused while only the cursor (`head`) moves. Split
/// out of [`RouteRequest::route`] so the live `RouteTool` preview recomputes only the
/// trailing head leg per frame. Read-only (no occupancy applied).
pub struct FixedLegs {
    /// Tagged points for `start → … → last waypoint`; empty when there are no
    /// waypoints (then the whole route is the single head leg).
    path: Vec<TaggedPoint>,
    /// Where the trailing head leg starts: the last waypoint, or `start`.
    tail: Point,
    /// The last waypoint id (head leg is `WaypointToEnd`) or `None` (`StartToEnd`).
    tail_wp: Option<PathOrdinal>,
    /// Direction of travel arriving at `tail`, threaded into the head leg so it
    /// cannot double back.
    incoming: Option<Direction>,
}

/// Route the fixed `start → … → last waypoint` portion of an in-progress route.
/// Identical to the corresponding legs of [`RouteRequest::route`] with
/// [`SelfCost::Skip`]. `wp_positions` must contain every id in `wp_ids`.
pub fn route_fixed_legs(
    router: &mut ClosedRouter,
    wp_positions: &BTreeMap<PathOrdinal, Point>,
    start: Point,
    wp_ids: &[PathOrdinal],
) -> FixedLegs {
    let mut path = Vec::new();
    let mut incoming: Option<Direction> = None;
    let Some(&first_id) = wp_ids.first() else {
        return FixedLegs {
            path,
            tail: start,
            tail_wp: None,
            incoming,
        };
    };
    let (subpath, outgoing) =
        route_leg_preferring_straight(router, start, wp_positions[&first_id], incoming);
    incoming = outgoing;
    path.extend(subpath.into_iter().map(|pos| TaggedPoint {
        pos,
        segment: SegmentKind::StartToWaypoint(first_id),
    }));
    for w in wp_ids.windows(2) {
        let (a_id, b_id) = (w[0], w[1]);
        let (subpath, outgoing) = route_leg_preferring_straight(
            router,
            wp_positions[&a_id],
            wp_positions[&b_id],
            incoming,
        );
        incoming = outgoing;
        path.extend(subpath.into_iter().map(|pos| TaggedPoint {
            pos,
            segment: SegmentKind::WaypointToWaypoint(a_id, b_id),
        }));
    }
    let last_id = wp_ids.last().copied().unwrap_or(first_id);
    FixedLegs {
        path,
        tail: wp_positions[&last_id],
        tail_wp: Some(last_id),
        incoming,
    }
}

/// Append the trailing head leg (`fixed.tail → head`) to the fixed legs — the only
/// part that changes as the cursor moves. `head` is typically not a graph node, so
/// this leg is the L-path fallback. Together with [`route_fixed_legs`] this equals
/// [`RouteRequest::route`] with [`SelfCost::Skip`].
pub fn route_to_head(
    router: &mut ClosedRouter,
    fixed: &FixedLegs,
    head: Point,
) -> Vec<TaggedPoint> {
    let (subpath, _) = route_leg_preferring_straight(router, fixed.tail, head, fixed.incoming);
    let segment = match fixed.tail_wp {
        Some(id) => SegmentKind::WaypointToEnd(id),
        None => SegmentKind::StartToEnd,
    };
    let mut path = fixed.path.clone();
    path.extend(subpath.into_iter().map(|pos| TaggedPoint { segment, pos }));
    path
}

/// Occupy a completed route on a [`ClosedRouter`] by adding `cost` to the graph
/// edges each wire covers (the in-place analogue of the old segment-based occupancy).
pub fn add_route_cost<'a>(
    router: &mut ClosedRouter,
    edges: impl Iterator<Item = &'a RouteEdge>,
    cost: Cost,
) {
    for edge in edges {
        router.add_wire_cost(edge.start.into(), edge.end.into(), cost);
    }
}

/// Whether any of a route's edges crosses a blocked rectangle on a [`ClosedRouter`]
/// (read-only; no rebuild).
pub fn route_edges_blocked<'a>(
    router: &ClosedRouter,
    mut edges: impl Iterator<Item = &'a RouteEdge>,
) -> bool {
    edges.any(|edge| router.is_wire_blocked(edge.start.into(), edge.end.into()))
}

#[cfg(test)]
mod tests {
    use super::*;
    use blockworx_router::RouterNGBuilder;
    use blockworx_router::point::point;

    #[test]
    fn a_legal_straight_leg_is_taken_verbatim() {
        // Two colinear points with a clear path between them: the leg must be the
        // straight segment, NOT a lower-cost router detour. This is the behaviour a
        // hand-placed waypoint path relies on.
        let a = point(0, 0);
        let b = point(10, 0);
        let mut builder = RouterNGBuilder::default();
        builder.add_seed_point(a);
        builder.add_seed_point(b);
        let mut router = builder.build_closed();

        let (path, dir) = route_leg_preferring_straight(&mut router, a, b, None);
        assert_eq!(path, vec![a, b], "a legal straight leg is taken verbatim");
        assert_eq!(dir, Some(Direction::East));
    }

    #[test]
    fn a_hugging_straight_leg_routes_around_the_block() {
        // Two colinear points one cell off the block's East edge (x = right + 1):
        // the straight run hugs the block's right side, so it must bow out into the
        // gutter rather than be taken verbatim.
        let mut builder = RouterNGBuilder::default();
        builder.add_block(point(0, 0), point(10, 10));
        let a = point(11, 2);
        let b = point(11, 8);
        builder.add_seed_point(a);
        builder.add_seed_point(b);
        let mut router = builder.build_closed();

        let (path, _) = route_leg_preferring_straight(&mut router, a, b, None);
        assert_ne!(
            path,
            vec![a, b],
            "a hugging straight leg must not stay verbatim"
        );
        assert!(path.len() > 2, "the leg bowed out around the block");
    }
}