elevator_core/dispatch/

mod.rs

//! Pluggable dispatch strategies for assigning elevators to stops.
//!
//! Strategies express preferences as scores on `(car, stop)` pairs via
//! [`DispatchStrategy::rank`]. The dispatch system then runs an optimal
//! bipartite assignment (Kuhn–Munkres / Hungarian algorithm) so coordination
//! — one car per hall call — is a library invariant, not a per-strategy
//! responsibility. Cars left unassigned are handed to
//! [`DispatchStrategy::fallback`] for per-car policy (idle, park, etc.).
//!
//! # Example: custom dispatch strategy
//!
//! ```rust
//! use elevator_core::prelude::*;
//! use elevator_core::dispatch::{
//!     DispatchDecision, DispatchManifest, ElevatorGroup,
//! };
//!
//! struct AlwaysFirstStop;
//!
//! impl DispatchStrategy for AlwaysFirstStop {
//!     fn rank(
//!         &mut self,
//!         _car: EntityId,
//!         car_position: f64,
//!         stop: EntityId,
//!         stop_position: f64,
//!         group: &ElevatorGroup,
//!         _manifest: &DispatchManifest,
//!         _world: &elevator_core::world::World,
//!     ) -> Option<f64> {
//!         // Prefer the group's first stop; everything else is unavailable.
//!         if Some(&stop) == group.stop_entities().first() {
//!             Some((car_position - stop_position).abs())
//!         } else {
//!             None
//!         }
//!     }
//! }
//!
//! let sim = SimulationBuilder::demo()
//!     .dispatch(AlwaysFirstStop)
//!     .build()
//!     .unwrap();
//! ```

/// Hall-call destination dispatch algorithm.
pub mod destination;
/// Estimated Time to Destination dispatch algorithm.
pub mod etd;
/// LOOK dispatch algorithm.
pub mod look;
/// Nearest-car dispatch algorithm.
pub mod nearest_car;
/// Built-in repositioning strategies.
pub mod reposition;
/// SCAN dispatch algorithm.
pub mod scan;
/// Shared sweep-direction logic used by SCAN and LOOK.
pub(crate) mod sweep;

pub use destination::{AssignedCar, DestinationDispatch};
pub use etd::EtdDispatch;
pub use look::LookDispatch;
pub use nearest_car::NearestCarDispatch;
pub use scan::ScanDispatch;

use serde::{Deserialize, Serialize};

use crate::entity::EntityId;
use crate::ids::GroupId;
use crate::world::World;
use std::collections::BTreeMap;

/// Metadata about a single rider, available to dispatch strategies.
#[derive(Debug, Clone)]
#[non_exhaustive]
pub struct RiderInfo {
    /// Rider entity ID.
    pub id: EntityId,
    /// Rider's destination stop entity (from route).
    pub destination: Option<EntityId>,
    /// Rider weight.
    pub weight: f64,
    /// Ticks this rider has been waiting (0 if riding).
    pub wait_ticks: u64,
}

/// Full demand picture for dispatch decisions.
///
/// Contains per-rider metadata grouped by stop, enabling entity-aware
/// dispatch strategies (priority, weight-aware, VIP-first, etc.).
///
/// Uses `BTreeMap` for deterministic iteration order.
#[derive(Debug, Clone, Default)]
pub struct DispatchManifest {
    /// Riders waiting at each stop, with full per-rider metadata.
    pub waiting_at_stop: BTreeMap<EntityId, Vec<RiderInfo>>,
    /// Riders currently aboard elevators, grouped by their destination stop.
    pub riding_to_stop: BTreeMap<EntityId, Vec<RiderInfo>>,
    /// Number of residents at each stop (read-only hint for dispatch strategies).
    pub resident_count_at_stop: BTreeMap<EntityId, usize>,
}

impl DispatchManifest {
    /// Number of riders waiting at a stop.
    #[must_use]
    pub fn waiting_count_at(&self, stop: EntityId) -> usize {
        self.waiting_at_stop.get(&stop).map_or(0, Vec::len)
    }

    /// Total weight of riders waiting at a stop.
    #[must_use]
    pub fn total_weight_at(&self, stop: EntityId) -> f64 {
        self.waiting_at_stop
            .get(&stop)
            .map_or(0.0, |riders| riders.iter().map(|r| r.weight).sum())
    }

    /// Number of riders heading to a stop (aboard elevators).
    #[must_use]
    pub fn riding_count_to(&self, stop: EntityId) -> usize {
        self.riding_to_stop.get(&stop).map_or(0, Vec::len)
    }

    /// Whether a stop has any demand (waiting riders or riders heading there).
    #[must_use]
    pub fn has_demand(&self, stop: EntityId) -> bool {
        self.waiting_count_at(stop) > 0 || self.riding_count_to(stop) > 0
    }

    /// Number of residents at a stop (read-only hint, not active demand).
    #[must_use]
    pub fn resident_count_at(&self, stop: EntityId) -> usize {
        self.resident_count_at_stop.get(&stop).copied().unwrap_or(0)
    }
}

/// Serializable identifier for built-in dispatch strategies.
///
/// Used in snapshots and config files to restore the correct strategy
/// without requiring the game to manually re-wire dispatch. Custom strategies
/// are represented by the `Custom(String)` variant.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[non_exhaustive]
pub enum BuiltinStrategy {
    /// SCAN (elevator) algorithm — sweeps end-to-end.
    Scan,
    /// LOOK algorithm — reverses at last request.
    Look,
    /// Nearest-car — assigns closest idle elevator.
    NearestCar,
    /// Estimated Time to Destination — minimizes total cost.
    Etd,
    /// Hall-call destination dispatch — sticky per-rider assignment.
    Destination,
    /// Custom strategy identified by name. The game must provide a factory.
    Custom(String),
}

impl std::fmt::Display for BuiltinStrategy {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Scan => write!(f, "Scan"),
            Self::Look => write!(f, "Look"),
            Self::NearestCar => write!(f, "NearestCar"),
            Self::Etd => write!(f, "Etd"),
            Self::Destination => write!(f, "Destination"),
            Self::Custom(name) => write!(f, "Custom({name})"),
        }
    }
}

impl BuiltinStrategy {
    /// Instantiate the dispatch strategy for this variant.
    ///
    /// Returns `None` for `Custom` — the game must provide those via
    /// a factory function.
    #[must_use]
    pub fn instantiate(&self) -> Option<Box<dyn DispatchStrategy>> {
        match self {
            Self::Scan => Some(Box::new(scan::ScanDispatch::new())),
            Self::Look => Some(Box::new(look::LookDispatch::new())),
            Self::NearestCar => Some(Box::new(nearest_car::NearestCarDispatch::new())),
            Self::Etd => Some(Box::new(etd::EtdDispatch::new())),
            Self::Destination => Some(Box::new(destination::DestinationDispatch::new())),
            Self::Custom(_) => None,
        }
    }
}

/// Decision returned by a dispatch strategy.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[non_exhaustive]
pub enum DispatchDecision {
    /// Go to the specified stop entity.
    GoToStop(EntityId),
    /// Remain idle.
    Idle,
}

/// Per-line relationship data within an [`ElevatorGroup`].
///
/// This is a denormalized cache maintained by [`Simulation`](crate::sim::Simulation).
/// The source of truth for intrinsic line properties is the
/// [`Line`](crate::components::Line) component in World.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct LineInfo {
    /// Line entity ID.
    entity: EntityId,
    /// Elevator entities on this line.
    elevators: Vec<EntityId>,
    /// Stop entities served by this line.
    serves: Vec<EntityId>,
}

impl LineInfo {
    /// Create a new `LineInfo`.
    #[must_use]
    pub const fn new(entity: EntityId, elevators: Vec<EntityId>, serves: Vec<EntityId>) -> Self {
        Self {
            entity,
            elevators,
            serves,
        }
    }

    /// Line entity ID.
    #[must_use]
    pub const fn entity(&self) -> EntityId {
        self.entity
    }

    /// Elevator entities on this line.
    #[must_use]
    pub fn elevators(&self) -> &[EntityId] {
        &self.elevators
    }

    /// Stop entities served by this line.
    #[must_use]
    pub fn serves(&self) -> &[EntityId] {
        &self.serves
    }

    /// Set the line entity ID (used during snapshot restore).
    pub(crate) const fn set_entity(&mut self, entity: EntityId) {
        self.entity = entity;
    }

    /// Mutable access to elevator entities on this line.
    pub(crate) const fn elevators_mut(&mut self) -> &mut Vec<EntityId> {
        &mut self.elevators
    }

    /// Mutable access to stop entities served by this line.
    pub(crate) const fn serves_mut(&mut self) -> &mut Vec<EntityId> {
        &mut self.serves
    }
}

/// Runtime elevator group: a set of lines sharing a dispatch strategy.
///
/// A group is the logical dispatch unit. It contains one or more
/// [`LineInfo`] entries, each representing a physical path with its
/// elevators and served stops.
///
/// The flat `elevator_entities` and `stop_entities` fields are derived
/// caches (union of all lines' elevators/stops), rebuilt automatically
/// via [`rebuild_caches()`](Self::rebuild_caches).
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ElevatorGroup {
    /// Unique group identifier.
    id: GroupId,
    /// Human-readable group name.
    name: String,
    /// Lines belonging to this group.
    lines: Vec<LineInfo>,
    /// Derived flat cache — rebuilt by `rebuild_caches()`.
    elevator_entities: Vec<EntityId>,
    /// Derived flat cache — rebuilt by `rebuild_caches()`.
    stop_entities: Vec<EntityId>,
}

impl ElevatorGroup {
    /// Create a new group with the given lines. Caches are built automatically.
    #[must_use]
    pub fn new(id: GroupId, name: String, lines: Vec<LineInfo>) -> Self {
        let mut group = Self {
            id,
            name,
            lines,
            elevator_entities: Vec::new(),
            stop_entities: Vec::new(),
        };
        group.rebuild_caches();
        group
    }

    /// Unique group identifier.
    #[must_use]
    pub const fn id(&self) -> GroupId {
        self.id
    }

    /// Human-readable group name.
    #[must_use]
    pub fn name(&self) -> &str {
        &self.name
    }

    /// Lines belonging to this group.
    #[must_use]
    pub fn lines(&self) -> &[LineInfo] {
        &self.lines
    }

    /// Mutable access to lines (call [`rebuild_caches()`](Self::rebuild_caches) after mutating).
    pub const fn lines_mut(&mut self) -> &mut Vec<LineInfo> {
        &mut self.lines
    }

    /// Elevator entities belonging to this group (derived from lines).
    #[must_use]
    pub fn elevator_entities(&self) -> &[EntityId] {
        &self.elevator_entities
    }

    /// Stop entities served by this group (derived from lines, deduplicated).
    #[must_use]
    pub fn stop_entities(&self) -> &[EntityId] {
        &self.stop_entities
    }

    /// Push a stop entity directly into the group's stop cache.
    ///
    /// Use when a stop belongs to the group for dispatch purposes but is
    /// not (yet) assigned to any line. Call `add_stop_to_line` later to
    /// wire it into the topology graph.
    pub(crate) fn push_stop(&mut self, stop: EntityId) {
        if !self.stop_entities.contains(&stop) {
            self.stop_entities.push(stop);
        }
    }

    /// Push an elevator entity directly into the group's elevator cache
    /// (in addition to the line it belongs to).
    pub(crate) fn push_elevator(&mut self, elevator: EntityId) {
        if !self.elevator_entities.contains(&elevator) {
            self.elevator_entities.push(elevator);
        }
    }

    /// Rebuild derived caches from lines. Call after mutating lines.
    pub fn rebuild_caches(&mut self) {
        self.elevator_entities = self
            .lines
            .iter()
            .flat_map(|li| li.elevators.iter().copied())
            .collect();
        let mut stops: Vec<EntityId> = self
            .lines
            .iter()
            .flat_map(|li| li.serves.iter().copied())
            .collect();
        stops.sort_unstable();
        stops.dedup();
        self.stop_entities = stops;
    }
}

/// Pluggable dispatch algorithm.
///
/// Strategies implement [`rank`](Self::rank) to score each `(car, stop)`
/// pair; the dispatch system then performs an optimal assignment across
/// the whole group, guaranteeing that no two cars are sent to the same
/// hall call.
///
/// Returning `None` from `rank` excludes a pair from assignment — useful
/// for capacity limits, direction preferences, restricted stops, or
/// sticky commitments.
///
/// Cars that receive no stop fall through to [`fallback`](Self::fallback),
/// which returns the policy for that car (idle, park, etc.).
pub trait DispatchStrategy: Send + Sync {
    /// Optional hook called once per group before the assignment pass.
    ///
    /// Strategies that need to mutate [`World`] extension storage (e.g.
    /// [`DestinationDispatch`] writing sticky rider → car assignments)
    /// or pre-populate [`crate::components::DestinationQueue`] entries
    /// override this. Default: no-op.
    fn pre_dispatch(
        &mut self,
        _group: &ElevatorGroup,
        _manifest: &DispatchManifest,
        _world: &mut World,
    ) {
    }

    /// Optional hook called once per candidate car, before any
    /// [`rank`](Self::rank) calls for that car in the current pass.
    ///
    /// Strategies whose ranking depends on stable per-car state (e.g. the
    /// sweep direction used by SCAN/LOOK) set that state here so later
    /// `rank` calls see a consistent view regardless of iteration order.
    /// The default is a no-op.
    fn prepare_car(
        &mut self,
        _car: EntityId,
        _car_position: f64,
        _group: &ElevatorGroup,
        _manifest: &DispatchManifest,
        _world: &World,
    ) {
    }

    /// Score the cost of sending `car` to `stop`. Lower is better.
    ///
    /// Returning `None` marks this `(car, stop)` pair as unavailable;
    /// the assignment algorithm will never pair them. Use this for
    /// capacity limits, wrong-direction stops, stops outside the line's
    /// topology, or pairs already committed via a sticky assignment.
    ///
    /// Must return a finite, non-negative value if `Some` — infinities
    /// and NaN can destabilize the underlying Hungarian solver.
    ///
    /// Implementations must not mutate per-car state inside `rank`: the
    /// dispatch system calls `rank(car, stop_0..stop_m)` in a loop, so
    /// mutating `self` on one call affects subsequent calls for the same
    /// car within the same pass and produces an asymmetric cost matrix
    /// whose results depend on iteration order. Use
    /// [`prepare_car`](Self::prepare_car) to compute and store any
    /// per-car state before `rank` is called.
    #[allow(clippy::too_many_arguments)]
    fn rank(
        &mut self,
        car: EntityId,
        car_position: f64,
        stop: EntityId,
        stop_position: f64,
        group: &ElevatorGroup,
        manifest: &DispatchManifest,
        world: &World,
    ) -> Option<f64>;

    /// Decide what an idle car should do when no stop was assigned to it.
    ///
    /// Called for each car the assignment phase could not pair with a
    /// stop (because there were no stops, or all candidate stops had
    /// rank `None` for this car). Default: [`DispatchDecision::Idle`].
    fn fallback(
        &mut self,
        _car: EntityId,
        _car_position: f64,
        _group: &ElevatorGroup,
        _manifest: &DispatchManifest,
        _world: &World,
    ) -> DispatchDecision {
        DispatchDecision::Idle
    }

    /// Notify the strategy that an elevator has been removed.
    ///
    /// Implementations with per-elevator state (e.g. direction tracking)
    /// should clean up here to prevent unbounded memory growth.
    fn notify_removed(&mut self, _elevator: EntityId) {}
}

/// Resolution of a single dispatch assignment pass for one group.
///
/// Produced by [`assign`] and consumed by
/// [`crate::systems::dispatch::run`] to apply decisions to the world.
#[derive(Debug, Clone)]
pub struct AssignmentResult {
    /// `(car, decision)` pairs for every idle car in the group.
    pub decisions: Vec<(EntityId, DispatchDecision)>,
}

/// Sentinel weight used to pad unavailable `(car, stop)` pairs when
/// building the cost matrix for the Hungarian solver. Chosen so that
/// `n · SENTINEL` can't overflow `i64`: the Kuhn–Munkres implementation
/// sums weights and potentials across each row/column internally, so
/// headroom of ~2¹⁵ above the sentinel lets groups scale past 30 000
/// cars or stops before any arithmetic risk appears.
const ASSIGNMENT_SENTINEL: i64 = 1 << 48;
/// Fixed-point scale for converting `f64` costs to the `i64` values the
/// Hungarian solver requires. One unit ≈ one micro-tick / millimeter.
const ASSIGNMENT_SCALE: f64 = 1_000_000.0;

/// Convert a `f64` rank cost into the fixed-point `i64` the Hungarian
/// solver consumes. Non-finite, negative, or overflow-prone inputs map
/// to the unavailable sentinel.
fn scale_cost(cost: f64) -> i64 {
    if !cost.is_finite() || cost < 0.0 {
        return ASSIGNMENT_SENTINEL;
    }
    // Cap at just below sentinel so any real rank always beats unavailable.
    (cost * ASSIGNMENT_SCALE)
        .round()
        .clamp(0.0, (ASSIGNMENT_SENTINEL - 1) as f64) as i64
}

/// Run one group's assignment pass: build the cost matrix, solve the
/// optimal bipartite matching, then resolve unassigned cars via
/// [`DispatchStrategy::fallback`].
///
/// Visible to the `systems` module; not part of the public API.
pub(crate) fn assign(
    strategy: &mut dyn DispatchStrategy,
    idle_cars: &[(EntityId, f64)],
    group: &ElevatorGroup,
    manifest: &DispatchManifest,
    world: &World,
) -> AssignmentResult {
    // Collect stops with active demand and known positions.
    let pending_stops: Vec<(EntityId, f64)> = group
        .stop_entities()
        .iter()
        .filter(|s| manifest.has_demand(**s))
        .filter_map(|s| world.stop_position(*s).map(|p| (*s, p)))
        .collect();

    let n = idle_cars.len();
    let m = pending_stops.len();

    if n == 0 {
        return AssignmentResult {
            decisions: Vec::new(),
        };
    }

    let mut decisions: Vec<(EntityId, DispatchDecision)> = Vec::with_capacity(n);

    if m == 0 {
        for &(eid, pos) in idle_cars {
            let d = strategy.fallback(eid, pos, group, manifest, world);
            decisions.push((eid, d));
        }
        return AssignmentResult { decisions };
    }

    // Build cost matrix. Hungarian requires rows <= cols.
    let cols = n.max(m);
    let mut data: Vec<i64> = vec![ASSIGNMENT_SENTINEL; n * cols];
    for (i, &(car_eid, car_pos)) in idle_cars.iter().enumerate() {
        strategy.prepare_car(car_eid, car_pos, group, manifest, world);
        for (j, &(stop_eid, stop_pos)) in pending_stops.iter().enumerate() {
            let scaled = strategy
                .rank(car_eid, car_pos, stop_eid, stop_pos, group, manifest, world)
                .map_or(ASSIGNMENT_SENTINEL, scale_cost);
            data[i * cols + j] = scaled;
        }
    }
    // `from_vec` only fails if `n * cols != data.len()` — both derived
    // from `n` and `cols` above, so the construction is infallible. Fall
    // back to an empty-result shape in the unlikely event the invariant
    // is violated in future refactors.
    let Ok(matrix) = pathfinding::matrix::Matrix::from_vec(n, cols, data) else {
        for &(car_eid, car_pos) in idle_cars {
            let d = strategy.fallback(car_eid, car_pos, group, manifest, world);
            decisions.push((car_eid, d));
        }
        return AssignmentResult { decisions };
    };
    let (_, assignments) = pathfinding::kuhn_munkres::kuhn_munkres_min(&matrix);

    for (i, &(car_eid, car_pos)) in idle_cars.iter().enumerate() {
        let col = assignments[i];
        // A real assignment is: col points to a real stop (col < m) AND
        // the cost isn't sentinel-padded (meaning rank() returned Some).
        if col < m && matrix[(i, col)] < ASSIGNMENT_SENTINEL {
            let (stop_eid, _) = pending_stops[col];
            decisions.push((car_eid, DispatchDecision::GoToStop(stop_eid)));
        } else {
            let d = strategy.fallback(car_eid, car_pos, group, manifest, world);
            decisions.push((car_eid, d));
        }
    }

    AssignmentResult { decisions }
}

/// Pluggable strategy for repositioning idle elevators.
///
/// After the dispatch phase, elevators that remain idle (no pending
/// assignments) are candidates for repositioning. The strategy decides
/// where each idle elevator should move to improve coverage and reduce
/// expected response times.
///
/// Implementations receive the set of idle elevator positions and the
/// group's stop positions, then return a target stop for each elevator
/// (or `None` to leave it in place).
pub trait RepositionStrategy: Send + Sync {
    /// Decide where to reposition idle elevators.
    ///
    /// Returns a vec of `(elevator_entity, target_stop_entity)` pairs.
    /// Elevators not in the returned vec remain idle.
    fn reposition(
        &mut self,
        idle_elevators: &[(EntityId, f64)],
        stop_positions: &[(EntityId, f64)],
        group: &ElevatorGroup,
        world: &World,
    ) -> Vec<(EntityId, EntityId)>;
}

/// Serializable identifier for built-in repositioning strategies.
///
/// Used in config and snapshots to restore the correct strategy.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[non_exhaustive]
pub enum BuiltinReposition {
    /// Distribute idle elevators evenly across stops.
    SpreadEvenly,
    /// Return idle elevators to a configured home stop.
    ReturnToLobby,
    /// Position near stops with historically high demand.
    DemandWeighted,
    /// Keep idle elevators where they are (no-op).
    NearestIdle,
    /// Custom strategy identified by name.
    Custom(String),
}

impl std::fmt::Display for BuiltinReposition {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::SpreadEvenly => write!(f, "SpreadEvenly"),
            Self::ReturnToLobby => write!(f, "ReturnToLobby"),
            Self::DemandWeighted => write!(f, "DemandWeighted"),
            Self::NearestIdle => write!(f, "NearestIdle"),
            Self::Custom(name) => write!(f, "Custom({name})"),
        }
    }
}

impl BuiltinReposition {
    /// Instantiate the reposition strategy for this variant.
    ///
    /// Returns `None` for `Custom` — the game must provide those via
    /// a factory function. `ReturnToLobby` uses stop index 0 as default.
    #[must_use]
    pub fn instantiate(&self) -> Option<Box<dyn RepositionStrategy>> {
        match self {
            Self::SpreadEvenly => Some(Box::new(reposition::SpreadEvenly)),
            Self::ReturnToLobby => Some(Box::new(reposition::ReturnToLobby::new())),
            Self::DemandWeighted => Some(Box::new(reposition::DemandWeighted)),
            Self::NearestIdle => Some(Box::new(reposition::NearestIdle)),
            Self::Custom(_) => None,
        }
    }
}