map_model/pathfind/
pathfinder.rs

1use std::cell::RefCell;
2use std::collections::HashMap;
3
4use serde::{Deserialize, Serialize};
5use thread_local::ThreadLocal;
6
7use abstutil::{Timer, VecMap};
8use geom::Duration;
9
10use crate::pathfind::engine::CreateEngine;
11use crate::pathfind::vehicles::VehiclePathfinder;
12use crate::pathfind::walking::SidewalkPathfinder;
13use crate::{
14    DirectedRoadID, Map, PathConstraints, PathRequest, PathV2, Position, RoutingParams,
15    TransitRouteID, TransitStopID,
16};
17
18#[derive(Serialize, Deserialize)]
19pub struct Pathfinder {
20    car_graph: VehiclePathfinder,
21    bike_graph: VehiclePathfinder,
22    bus_graph: VehiclePathfinder,
23    train_graph: VehiclePathfinder,
24    walking_graph: SidewalkPathfinder,
25    walking_with_transit_graph: SidewalkPathfinder,
26
27    // These params cover the main graphs
28    params: RoutingParams,
29
30    // Callers can opt into caching with pathfind_with_params
31    // TODO VecMap is probably fast enough. RoutingParams is annoying to implement Hash.
32    #[serde(skip_serializing, skip_deserializing)]
33    cached_alternatives: ThreadLocal<RefCell<VecMap<(PathConstraints, RoutingParams), Pathfinder>>>,
34}
35
36/// When pathfinding with different `RoutingParams` is done, a temporary pathfinder must be
37/// created. This specifies what type of pathfinder and whether to cache it.
38// TODO Deprecated
39#[derive(Clone, Copy, PartialEq)]
40pub enum PathfinderCaching {
41    /// Create a fast-to-build but slow-to-use Dijkstra-based pathfinder and don't cache it
42    NoCache,
43    /// Create a fast-to-build but slow-to-use Dijkstra-based pathfinder and cache it
44    CacheDijkstra,
45    /// Create a slow-to-build but fast-to-use contraction hierarchy-based pathfinder and cache it
46    CacheCH,
47}
48
49// Implemented manually to deal with the ThreadLocal
50impl Clone for Pathfinder {
51    fn clone(&self) -> Self {
52        Self {
53            car_graph: self.car_graph.clone(),
54            bike_graph: self.bike_graph.clone(),
55            bus_graph: self.bus_graph.clone(),
56            train_graph: self.train_graph.clone(),
57            walking_graph: self.walking_graph.clone(),
58            walking_with_transit_graph: self.walking_with_transit_graph.clone(),
59            params: self.params.clone(),
60            cached_alternatives: ThreadLocal::new(),
61        }
62    }
63}
64
65impl Pathfinder {
66    /// Quickly create an invalid pathfinder, just to make borrow checking / initialization order
67    /// work.
68    pub fn empty() -> Pathfinder {
69        Pathfinder {
70            car_graph: VehiclePathfinder::empty(),
71            bike_graph: VehiclePathfinder::empty(),
72            bus_graph: VehiclePathfinder::empty(),
73            train_graph: VehiclePathfinder::empty(),
74            walking_graph: SidewalkPathfinder::empty(),
75            walking_with_transit_graph: SidewalkPathfinder::empty(),
76            params: RoutingParams::default(),
77            cached_alternatives: ThreadLocal::new(),
78        }
79    }
80
81    pub(crate) fn new(
82        map: &Map,
83        params: RoutingParams,
84        engine: &CreateEngine,
85        timer: &mut Timer,
86    ) -> Pathfinder {
87        timer.start("prepare pathfinding for cars");
88        let car_graph = VehiclePathfinder::new(map, PathConstraints::Car, &params, engine);
89        timer.stop("prepare pathfinding for cars");
90
91        // The edge weights for bikes are so different from the driving graph that reusing the node
92        // ordering actually hurts!
93        timer.start("prepare pathfinding for bikes");
94        let bike_graph = VehiclePathfinder::new(map, PathConstraints::Bike, &params, engine);
95        timer.stop("prepare pathfinding for bikes");
96
97        timer.start("prepare pathfinding for buses");
98        let bus_graph = VehiclePathfinder::new(
99            map,
100            PathConstraints::Bus,
101            &params,
102            &car_graph.engine.reuse_ordering(),
103        );
104        timer.stop("prepare pathfinding for buses");
105
106        // Light rail networks are absolutely tiny; using a contraction hierarchy for them is
107        // overkill. And in fact, it costs a bit of memory and file size, so don't do it!
108        timer.start("prepare pathfinding for trains");
109        let train_graph = VehiclePathfinder::new(
110            map,
111            PathConstraints::Train,
112            &params,
113            &CreateEngine::Dijkstra,
114        );
115        timer.stop("prepare pathfinding for trains");
116
117        timer.start("prepare pathfinding for pedestrians");
118        let walking_graph = SidewalkPathfinder::new(map, None, engine);
119        timer.stop("prepare pathfinding for pedestrians");
120
121        // Transit routes haven't been created yet, so defer this step
122        let walking_with_transit_graph = SidewalkPathfinder::empty();
123
124        Pathfinder {
125            car_graph,
126            bike_graph,
127            bus_graph,
128            train_graph,
129            walking_graph,
130            walking_with_transit_graph,
131
132            params,
133            cached_alternatives: ThreadLocal::new(),
134        }
135    }
136
137    /// Create a new Pathfinder with custom routing params that can only serve some modes. Fast to
138    /// create, slow to use.
139    pub fn new_dijkstra(
140        map: &Map,
141        params: RoutingParams,
142        modes: Vec<PathConstraints>,
143        timer: &mut Timer,
144    ) -> Self {
145        Self::new_limited(map, params, CreateEngine::Dijkstra, modes, timer)
146    }
147
148    /// Create a new Pathfinder with custom routing params that can only serve some modes. Slow to
149    /// create, fast to use. Doesn't re-use the node ordering when building the CH.
150    pub fn new_ch(
151        map: &Map,
152        params: RoutingParams,
153        modes: Vec<PathConstraints>,
154        timer: &mut Timer,
155    ) -> Self {
156        Self::new_limited(map, params, CreateEngine::CH, modes, timer)
157    }
158
159    /// Create a new Pathfinder with custom routing params that can only serve some modes.
160    pub(crate) fn new_limited(
161        map: &Map,
162        params: RoutingParams,
163        engine: CreateEngine,
164        modes: Vec<PathConstraints>,
165        timer: &mut Timer,
166    ) -> Pathfinder {
167        let mut p = Pathfinder::empty();
168        for constraints in modes {
169            timer.start(format!("prepare pathfinding for just {:?}", constraints));
170            match constraints {
171                PathConstraints::Pedestrian => {
172                    p.walking_graph = SidewalkPathfinder::new(map, None, &engine);
173                }
174                PathConstraints::Car => {
175                    p.car_graph = VehiclePathfinder::new(map, constraints, &params, &engine);
176                }
177                PathConstraints::Bike => {
178                    p.bike_graph = VehiclePathfinder::new(map, constraints, &params, &engine);
179                }
180                PathConstraints::Bus => {
181                    p.bus_graph = VehiclePathfinder::new(map, constraints, &params, &engine);
182                }
183                PathConstraints::Train => {
184                    p.train_graph = VehiclePathfinder::new(map, constraints, &params, &engine);
185                }
186            }
187            timer.stop(format!("prepare pathfinding for just {:?}", constraints));
188        }
189        p.params = params;
190        p
191    }
192
193    pub(crate) fn finalize_transit(&mut self, map: &Map, engine: &CreateEngine) {
194        self.walking_with_transit_graph =
195            SidewalkPathfinder::new(map, Some((&self.bus_graph, &self.train_graph)), engine);
196    }
197
198    /// Finds a path from a start to an end for a certain type of agent.
199    pub fn pathfind(&self, req: PathRequest, map: &Map) -> Option<PathV2> {
200        self.pathfind_with_params(req, map.routing_params(), PathfinderCaching::NoCache, map)
201    }
202
203    /// Finds a path from a start to an end for a certain type of agent. Uses the RoutingParams
204    /// built into this Pathfinder.
205    pub fn pathfind_v2(&self, req: PathRequest, map: &Map) -> Option<PathV2> {
206        match req.constraints {
207            PathConstraints::Pedestrian => self.walking_graph.pathfind(req, map),
208            PathConstraints::Car => self.car_graph.pathfind(req, map),
209            PathConstraints::Bike => self.bike_graph.pathfind(req, map),
210            PathConstraints::Bus => self.bus_graph.pathfind(req, map),
211            PathConstraints::Train => self.train_graph.pathfind(req, map),
212        }
213    }
214
215    /// Finds a path from a start to an end for a certain type of agent. May use custom routing
216    /// parameters. If caching is requested and custom routing parameters are used, then the
217    /// intermediate graph is saved to speed up future calls with the same routing parameters.
218    // TODO Deprecated
219    pub fn pathfind_with_params(
220        &self,
221        req: PathRequest,
222        params: &RoutingParams,
223        cache_custom: PathfinderCaching,
224        map: &Map,
225    ) -> Option<PathV2> {
226        let constraints = req.constraints;
227        if params == &self.params {
228            return match constraints {
229                PathConstraints::Pedestrian => self.walking_graph.pathfind(req, map),
230                PathConstraints::Car => self.car_graph.pathfind(req, map),
231                PathConstraints::Bike => self.bike_graph.pathfind(req, map),
232                PathConstraints::Bus => self.bus_graph.pathfind(req, map),
233                PathConstraints::Train => self.train_graph.pathfind(req, map),
234            };
235        }
236
237        // If the params differ from the ones baked into the map, the CHs won't match. Do we have a
238        // cached alternative?
239        if let Some(alt) = self
240            .cached_alternatives
241            .get_or(|| RefCell::new(VecMap::new()))
242            .borrow()
243            .get(&(constraints, params.clone()))
244        {
245            return alt.pathfind_with_params(req, params, PathfinderCaching::NoCache, map);
246        }
247
248        // If somebody's repeatedly calling this without caching, log very obnoxiously.
249        let mut timer = Timer::new(format!("Pathfinding slowly for {} with custom params", req));
250        let tmp_pathfinder = Pathfinder::new_limited(
251            map,
252            params.clone(),
253            match cache_custom {
254                PathfinderCaching::NoCache | PathfinderCaching::CacheDijkstra => {
255                    CreateEngine::Dijkstra
256                }
257                // TODO Can we pick the right seed?
258                PathfinderCaching::CacheCH => CreateEngine::CH,
259            },
260            vec![constraints],
261            &mut timer,
262        );
263        let result =
264            tmp_pathfinder.pathfind_with_params(req, params, PathfinderCaching::NoCache, map);
265        if cache_custom != PathfinderCaching::NoCache {
266            self.cached_alternatives
267                .get_or(|| RefCell::new(VecMap::new()))
268                .borrow_mut()
269                .push((constraints, params.clone()), tmp_pathfinder);
270        }
271        result
272    }
273
274    pub fn all_costs_from(
275        &self,
276        req: PathRequest,
277        map: &Map,
278    ) -> Option<(Duration, HashMap<DirectedRoadID, Duration>)> {
279        let req_cost = self.pathfind(req.clone(), map)?.get_cost();
280        let all_costs = match req.constraints {
281            PathConstraints::Pedestrian => self.walking_graph.all_costs_from(req.start, map),
282            PathConstraints::Car => self.car_graph.all_costs_from(req.start, map),
283            PathConstraints::Bike => self.bike_graph.all_costs_from(req.start, map),
284            PathConstraints::Bus | PathConstraints::Train => unreachable!(),
285        };
286        Some((req_cost, all_costs))
287    }
288
289    // TODO Consider returning the walking-only path in the failure case, to avoid wasting work
290    pub fn should_use_transit(
291        &self,
292        map: &Map,
293        start: Position,
294        end: Position,
295    ) -> Option<(TransitStopID, Option<TransitStopID>, TransitRouteID)> {
296        self.walking_with_transit_graph
297            .should_use_transit(map, start, end)
298    }
299
300    pub(crate) fn apply_edits(&mut self, map: &Map, timer: &mut Timer) {
301        timer.start("apply edits to car pathfinding");
302        self.car_graph.apply_edits(map);
303        timer.stop("apply edits to car pathfinding");
304
305        timer.start("apply edits to bike pathfinding");
306        self.bike_graph.apply_edits(map);
307        timer.stop("apply edits to bike pathfinding");
308
309        timer.start("apply edits to bus pathfinding");
310        self.bus_graph.apply_edits(map);
311        timer.stop("apply edits to bus pathfinding");
312
313        timer.start("apply edits to train pathfinding");
314        self.train_graph.apply_edits(map);
315        timer.stop("apply edits to train pathfinding");
316
317        timer.start("apply edits to pedestrian pathfinding");
318        self.walking_graph.apply_edits(map, None);
319        timer.stop("apply edits to pedestrian pathfinding");
320
321        timer.start("apply edits to pedestrian using transit pathfinding");
322        self.walking_with_transit_graph
323            .apply_edits(map, Some((&self.bus_graph, &self.train_graph)));
324        timer.stop("apply edits to pedestrian using transit pathfinding");
325    }
326}
327
328/// For callers needing to request paths with a variety of RoutingParams. The caller is in charge
329/// of the lifetime, so they can clear it out when appropriate.
330pub struct PathfinderCache {
331    cache: VecMap<(PathConstraints, RoutingParams), Pathfinder>,
332}
333
334impl PathfinderCache {
335    pub fn new() -> Self {
336        Self {
337            cache: VecMap::new(),
338        }
339    }
340
341    /// New pathfinders will be created as-needed using Dijkstra's, no spammy logging
342    pub fn pathfind_with_params(
343        &mut self,
344        map: &Map,
345        req: PathRequest,
346        params: RoutingParams,
347    ) -> Option<PathV2> {
348        if let Some(pathfinder) = self.cache.get(&(req.constraints, params.clone())) {
349            return pathfinder.pathfind_v2(req, map);
350        }
351
352        let pathfinder = Pathfinder::new_limited(
353            map,
354            params.clone(),
355            CreateEngine::Dijkstra,
356            vec![req.constraints],
357            &mut Timer::throwaway(),
358        );
359        let result = pathfinder.pathfind_v2(req.clone(), map);
360        self.cache.push((req.constraints, params), pathfinder);
361        result
362    }
363}
map_model/pathfind/pathfinder.rs

map_model/pathfind/
pathfinder.rs
