map_model/pathfind/
mod.rs

1//! Everything related to pathfinding through a map for different types of agents.
2
3use std::collections::BTreeSet;
4
5use enumset::EnumSetType;
6use serde::{Deserialize, Serialize};
7
8use geom::Duration;
9
10pub use self::engine::CreateEngine;
11pub use self::pathfinder::{Pathfinder, PathfinderCache, PathfinderCaching};
12pub use self::v1::{Path, PathRequest, PathStep};
13pub use self::v2::{PathStepV2, PathV2};
14pub use self::vehicles::vehicle_cost;
15pub use self::walking::WalkingNode;
16use crate::{osm, Lane, LaneID, LaneType, Map, MovementID, Road, RoadID, TurnType};
17
18mod engine;
19mod node_map;
20mod pathfinder;
21// TODO tmp
22pub mod uber_turns;
23mod v1;
24mod v2;
25mod vehicles;
26mod walking;
27
28/// Who's asking for a path?
29// TODO This is an awful name.
30#[derive(Debug, Serialize, Deserialize, PartialOrd, Ord, EnumSetType)]
31pub enum PathConstraints {
32    Pedestrian,
33    Car,
34    Bike,
35    Bus,
36    Train,
37}
38
39impl PathConstraints {
40    pub fn all() -> Vec<PathConstraints> {
41        vec![
42            PathConstraints::Pedestrian,
43            PathConstraints::Car,
44            PathConstraints::Bike,
45            PathConstraints::Bus,
46            PathConstraints::Train,
47        ]
48    }
49
50    /// Not bijective, but this is the best guess of user intent
51    pub fn from_lt(lt: LaneType) -> PathConstraints {
52        match lt {
53            LaneType::Sidewalk | LaneType::Shoulder => PathConstraints::Pedestrian,
54            LaneType::Driving => PathConstraints::Car,
55            LaneType::Biking => PathConstraints::Bike,
56            LaneType::Bus => PathConstraints::Bus,
57            LaneType::LightRail => PathConstraints::Train,
58            _ => panic!("PathConstraints::from_lt({:?}) doesn't make sense", lt),
59        }
60    }
61
62    /// Can an agent use a lane? There are some subtle exceptions with using bus-only lanes for
63    /// turns.
64    pub fn can_use(self, lane: &Lane, map: &Map) -> bool {
65        let result = match self {
66            PathConstraints::Pedestrian => {
67                return lane.is_walkable();
68            }
69            PathConstraints::Car => lane.is_driving(),
70            PathConstraints::Bike => {
71                if lane.is_biking() {
72                    true
73                } else if lane.is_driving() || (lane.is_bus() && map.config.bikes_can_use_bus_lanes)
74                {
75                    let road = map.get_r(lane.id.road);
76                    !road.osm_tags.is("bicycle", "no")
77                        && !road
78                            .osm_tags
79                            .is_any(osm::HIGHWAY, vec!["motorway", "motorway_link"])
80                } else {
81                    false
82                }
83            }
84            PathConstraints::Bus => {
85                return lane.is_driving() || lane.is_bus();
86            }
87            PathConstraints::Train => {
88                return lane.is_light_rail();
89            }
90        };
91        if result {
92            return true;
93        }
94        // Second chance for cars and bikes trying to use a bus-only lane that also happens to be a
95        // turn lane.
96        //
97        // TODO This check could be made stricter in two ways:
98        // 1) Verify that the bus-only lanes are the ONLY way to make this movement; if there's a
99        //    general purpose lane that can also turn, we shouldn't allow this.
100        // 2) Verify that the turn->lane->turn sequence is the only way to reach the destination
101        //    road. Since this function operates on a single lane, a vehicle could abuse this to
102        //    stay in the bus lane and go straight, even if there was another lane for that. Fixing
103        //    this is hard, since it requires so much context about the sequence of movements. In
104        //    practice this isn't an issue; a bus lane often leads to another one, but the next bus
105        //    lane won't also be an exclusive turn lane.
106        if lane.is_bus() {
107            if let Some(types) =
108                lane.get_lane_level_turn_restrictions(map.get_r(lane.id.road), true)
109            {
110                if types.contains(&TurnType::Right) || types.contains(&TurnType::Left) {
111                    return true;
112                }
113            }
114        }
115        false
116    }
117
118    /// Can an agent use a road in either direction? There are some subtle exceptions with using
119    /// bus-only lanes for turns.
120    pub fn can_use_road(self, road: &Road, map: &Map) -> bool {
121        road.lanes.iter().any(|lane| self.can_use(lane, map))
122    }
123
124    /// Strict for bikes. If there are bike lanes, not allowed to use other lanes.
125    pub(crate) fn filter_lanes(self, mut choices: Vec<LaneID>, map: &Map) -> Vec<LaneID> {
126        choices.retain(|l| self.can_use(map.get_l(*l), map));
127        if self == PathConstraints::Bike {
128            let just_bike_lanes: Vec<LaneID> = choices
129                .iter()
130                .copied()
131                .filter(|l| map.get_l(*l).is_biking())
132                .collect();
133            if !just_bike_lanes.is_empty() {
134                return just_bike_lanes;
135            }
136        }
137        choices
138    }
139}
140
141/// Heavily penalize crossing into an access-restricted zone that doesn't allow this mode.
142pub(crate) fn zone_cost(mvmnt: MovementID, constraints: PathConstraints, map: &Map) -> Duration {
143    // Detect when we cross into a new zone that doesn't allow constraints.
144    if map
145        .get_r(mvmnt.from.road)
146        .access_restrictions
147        .allow_through_traffic
148        .contains(constraints)
149        && !map
150            .get_r(mvmnt.to.road)
151            .access_restrictions
152            .allow_through_traffic
153            .contains(constraints)
154    {
155        // This should be high enough to achieve the desired effect of somebody not entering
156        // the zone unless absolutely necessary. Someone would violate that and cut through anyway
157        // only when the alternative route would take more than 3 hours longer!
158        Duration::hours(3)
159    } else {
160        Duration::ZERO
161    }
162}
163
164/// Tuneable parameters for all types of routing.
165// These will maybe become part of the PathRequest later, but that's an extremely invasive and
166// space-expensive change right now.
167#[derive(Clone, PartialEq, Debug, Serialize, Deserialize)]
168pub struct RoutingParams {
169    // For all vehicles. This is added to the cost of a movement as an additional delay.
170    pub unprotected_turn_penalty: Duration,
171
172    // For bike routing. Multiplied by the base cost, since spending more time on the wrong lane
173    // type matters.
174    pub bike_lane_penalty: f64,
175    pub bus_lane_penalty: f64,
176    pub driving_lane_penalty: f64,
177
178    // For bike routing.
179    // "Steep" is a fixed threshold of 8% incline, uphill only. Multiply by the base cost. (Note
180    // that cost already includes a reduction of speed to account for the incline -- this is a
181    // further "delay" on top of that!)
182    // TODO But even steeper roads matter more!
183    pub avoid_steep_incline_penalty: f64,
184    // If the road is `high_stress_for_bikes`, multiply by the base cost.
185    pub avoid_high_stress: f64,
186
187    /// When crossing an arterial or highway road, multiply the base cost by this penalty. When
188    /// greater than 1, this will encourage routes to use local roads more.
189    pub main_road_penalty: f64,
190
191    /// Don't allow crossing these roads at all. Only affects vehicle routing, not pedestrian.
192    ///
193    /// TODO The route may cross one of these roads if it's the start or end!
194    pub avoid_roads: BTreeSet<RoadID>,
195    /// Related to `avoid_roads`, but used as an optimization in map construction
196    pub only_use_roads: BTreeSet<RoadID>,
197
198    /// Don't allow movements between these roads at all. Only affects vehicle routing, not
199    /// pedestrian.
200    pub avoid_movements_between: BTreeSet<(RoadID, RoadID)>,
201}
202
203impl Default for RoutingParams {
204    fn default() -> Self {
205        Self {
206            // This is a total guess -- it really depends on the traffic patterns of the particular
207            // road at the time we're routing.
208            unprotected_turn_penalty: Duration::const_seconds(30.0),
209
210            bike_lane_penalty: 1.0,
211            bus_lane_penalty: 1.1,
212            driving_lane_penalty: 1.5,
213
214            avoid_steep_incline_penalty: 1.0,
215            avoid_high_stress: 1.0,
216
217            main_road_penalty: 1.0,
218
219            avoid_roads: BTreeSet::new(),
220            avoid_movements_between: BTreeSet::new(),
221            only_use_roads: BTreeSet::new(),
222        }
223    }
224}
225
226pub fn round(cost: Duration) -> usize {
227    // Round up! 0 cost edges are ignored
228    (cost.inner_seconds().round() as usize).max(1)
229}
230
231pub fn unround(cost: usize) -> Duration {
232    Duration::seconds(cost as f64)
233}
map_model/pathfind/mod.rs

map_model/pathfind/
mod.rs
