map_model/connectivity/
walking.rs

Help
1use std::collections::{BinaryHeap, HashMap, HashSet};
2
3use abstutil::{MultiMap, PriorityQueueItem};
4use geom::{Duration, Speed};
5
6use crate::connectivity::Spot;
7use crate::pathfind::{zone_cost, WalkingNode};
8use crate::{BuildingID, Lane, LaneType, Map, PathConstraints, PathStep};
9
10#[derive(Clone)]
11pub struct WalkingOptions {
12    /// If true, allow walking on shoulders.
13    pub allow_shoulders: bool,
14    pub walking_speed: Speed,
15}
16
17impl WalkingOptions {
18    pub fn default() -> WalkingOptions {
19        WalkingOptions {
20            allow_shoulders: true,
21            walking_speed: WalkingOptions::default_speed(),
22        }
23    }
24
25    pub fn common_speeds() -> Vec<(&'static str, Speed)> {
26        vec![
27            ("3 mph (average for an adult)", Speed::miles_per_hour(3.0)),
28            ("1 mph (manual wheelchair)", Speed::miles_per_hour(1.0)),
29            ("5 mph (moderate jog)", Speed::miles_per_hour(5.0)),
30        ]
31    }
32
33    pub fn default_speed() -> Speed {
34        WalkingOptions::common_speeds()[0].1
35    }
36}
37
38/// Starting from some initial buildings, calculate the cost to all others. If a destination isn't
39/// reachable, it won't be included in the results. Ignore results greater than the time_limit
40/// away.
41///
42/// If all of the start buildings are on the shoulder of a road and `!opts.allow_shoulders`, then
43/// the results will always be empty.
44pub fn all_walking_costs_from(
45    map: &Map,
46    starts: Vec<Spot>,
47    time_limit: Duration,
48    opts: WalkingOptions,
49) -> HashMap<BuildingID, Duration> {
50    let mut queue: BinaryHeap<PriorityQueueItem<Duration, WalkingNode>> = BinaryHeap::new();
51
52    for spot in starts {
53        match spot {
54            Spot::Building(b_id) => {
55                queue.push(PriorityQueueItem {
56                    cost: Duration::ZERO,
57                    value: WalkingNode::closest(map.get_b(b_id).sidewalk_pos, map),
58                });
59            }
60            Spot::Border(i_id) => {
61                let intersection = map.get_i(i_id);
62                let incoming_lanes = intersection.incoming_lanes.clone();
63                let mut outgoing_lanes = intersection.outgoing_lanes.clone();
64                let mut all_lanes = incoming_lanes;
65                all_lanes.append(&mut outgoing_lanes);
66                let walkable_lanes: Vec<&Lane> = all_lanes
67                    .into_iter()
68                    .map(|l_id| map.get_l(l_id))
69                    .filter(|l| l.is_walkable())
70                    .collect();
71                for lane in walkable_lanes {
72                    queue.push(PriorityQueueItem {
73                        cost: Duration::ZERO,
74                        value: WalkingNode::SidewalkEndpoint(
75                            lane.get_directed_parent(),
76                            lane.src_i == i_id,
77                        ),
78                    });
79                }
80            }
81            Spot::DirectedRoad(dr) => {
82                // Start from either end
83                queue.push(PriorityQueueItem {
84                    cost: Duration::ZERO,
85                    value: WalkingNode::SidewalkEndpoint(dr, false),
86                });
87                queue.push(PriorityQueueItem {
88                    cost: Duration::ZERO,
89                    value: WalkingNode::SidewalkEndpoint(dr, true),
90                });
91            }
92        }
93    }
94
95    if !opts.allow_shoulders {
96        let mut shoulder_endpoint = Vec::new();
97        for q in &queue {
98            if let WalkingNode::SidewalkEndpoint(dir_r, _) = q.value {
99                for lane in &map.get_r(dir_r.road).lanes {
100                    shoulder_endpoint.push(lane.lane_type == LaneType::Shoulder);
101                }
102            }
103        }
104        if shoulder_endpoint.into_iter().all(|x| x) {
105            return HashMap::new();
106        }
107    }
108
109    let mut sidewalk_to_bldgs = MultiMap::new();
110    for b in map.all_buildings() {
111        sidewalk_to_bldgs.insert(b.sidewalk(), b.id);
112    }
113
114    let mut results = HashMap::new();
115
116    let mut visited_nodes = HashSet::new();
117    while let Some(current) = queue.pop() {
118        if visited_nodes.contains(&current.value) {
119            continue;
120        }
121        if current.cost > time_limit {
122            continue;
123        }
124        visited_nodes.insert(current.value);
125
126        let (r, is_dst_i) = match current.value {
127            WalkingNode::SidewalkEndpoint(r, is_dst_i) => (r, is_dst_i),
128            _ => unreachable!(),
129        };
130        let lane = map.get_l(r.must_get_sidewalk(map));
131        // Cross the lane
132        if opts.allow_shoulders || lane.lane_type != LaneType::Shoulder {
133            let sidewalk_len = lane.length();
134            let step = if is_dst_i {
135                PathStep::ContraflowLane(lane.id)
136            } else {
137                PathStep::Lane(lane.id)
138            };
139            let speed =
140                step.max_speed_along(Some(opts.walking_speed), PathConstraints::Pedestrian, map);
141            let cross_to_node = WalkingNode::SidewalkEndpoint(r, !is_dst_i);
142
143            // We're crossing the sidewalk from one end to the other. If we haven't already found a
144            // shorter path to the other end of this sidewalk, then fill out the exact distance to
145            // each building. We need to know the direction along the sidewalk we're moving to fill
146            // this out properly, so that's why the order of graph nodes visited matters and we're
147            // doing this work here.
148            if !visited_nodes.contains(&cross_to_node) {
149                for b in sidewalk_to_bldgs.get(lane.id) {
150                    let bldg_dist_along = map.get_b(*b).sidewalk_pos.dist_along();
151                    let dist_to_bldg = if is_dst_i {
152                        // Crossing from the end of the sidewalk to the beginning
153                        sidewalk_len - bldg_dist_along
154                    } else {
155                        bldg_dist_along
156                    };
157                    let bldg_cost = current.cost + dist_to_bldg / speed;
158                    if bldg_cost <= time_limit {
159                        results.insert(*b, bldg_cost);
160                    }
161                }
162
163                queue.push(PriorityQueueItem {
164                    cost: current.cost + sidewalk_len / speed,
165                    value: cross_to_node,
166                });
167            }
168        }
169        // All turns from the lane
170        for turn in map.get_turns_for(lane.id, PathConstraints::Pedestrian) {
171            if (turn.id.parent == lane.dst_i) != is_dst_i {
172                continue;
173            }
174            queue.push(PriorityQueueItem {
175                cost: current.cost
176                    + turn.geom.length()
177                        / PathStep::Turn(turn.id).max_speed_along(
178                            Some(opts.walking_speed),
179                            PathConstraints::Pedestrian,
180                            map,
181                        )
182                    + zone_cost(turn.id.to_movement(map), PathConstraints::Pedestrian, map),
183                value: WalkingNode::SidewalkEndpoint(
184                    map.get_l(turn.id.dst).get_directed_parent(),
185                    map.get_l(turn.id.dst).dst_i == turn.id.parent,
186                ),
187            });
188        }
189    }
190
191    results
192}
map_model/connectivity/walking.rs

map_model/connectivity/
walking.rs
