1 use crate::raw::RestrictionType;
2 use crate::{Intersection, Lane, LaneID, Map, Turn, TurnID, TurnType};
3 use abstutil::Timer;
4 use geom::{Distance, PolyLine, Pt2D};
5 use nbez::{Bez3o, BezCurve, Point2d};
6 use std::collections::{BTreeSet, HashMap, HashSet};
7
make_all_turns(map: &Map, i: &Intersection, timer: &mut Timer) -> Vec<Turn>8 pub fn make_all_turns(map: &Map, i: &Intersection, timer: &mut Timer) -> Vec<Turn> {
9 assert!(!i.is_border());
10
11 let mut raw_turns: Vec<Turn> = Vec::new();
12 raw_turns.extend(make_vehicle_turns(i, map, timer));
13 raw_turns.extend(crate::make::walking_turns::make_walking_turns(
14 map, i, timer,
15 ));
16 let unique_turns = ensure_unique(raw_turns);
17
18 let mut final_turns: Vec<Turn> = Vec::new();
19 let mut filtered_turns: HashMap<LaneID, Vec<Turn>> = HashMap::new();
20 for turn in unique_turns {
21 if !does_turn_pass_restrictions(&turn, i, map) {
22 continue;
23 }
24
25 if is_turn_allowed(&turn, map) {
26 final_turns.push(turn);
27 } else {
28 filtered_turns
29 .entry(turn.id.src)
30 .or_insert_with(Vec::new)
31 .push(turn);
32 }
33 }
34
35 // Make sure every incoming lane has a turn originating from it, and every outgoing lane has a
36 // turn leading to it.
37 let mut incoming_missing: HashSet<LaneID> = HashSet::new();
38 for l in &i.incoming_lanes {
39 if map.get_l(*l).lane_type.supports_any_movement() {
40 incoming_missing.insert(*l);
41 }
42 }
43 for t in &final_turns {
44 incoming_missing.remove(&t.id.src);
45 }
46 for (l, turns) in filtered_turns {
47 // Do turn restrictions orphan a lane?
48 if incoming_missing.contains(&l) {
49 // Restrictions on turn lanes may sometimes actually be more like change:lanes
50 // (https://wiki.openstreetmap.org/wiki/Key:change). Try to interpret them that way
51 // here, choosing one turn from a bunch of options.
52
53 // If all the turns go to a single road, then ignore the turn type.
54 let dst_r = map.get_l(turns[0].id.dst).parent;
55 let single_group: Vec<Turn> =
56 if turns.iter().all(|t| map.get_l(t.id.dst).parent == dst_r) {
57 turns.clone()
58 } else {
59 // Fall back to preferring all the straight turns
60 turns
61 .iter()
62 .filter(|t| t.turn_type == TurnType::Straight)
63 .cloned()
64 .collect()
65 };
66 if !single_group.is_empty() {
67 // Just pick one, with the lowest lane-changing cost. Not using Turn's penalty()
68 // here, because
69 // 1) We haven't populated turns yet, so from_idx won't work
70 // 2) It counts from the right, but I think we actually want to count from the left
71 let best = single_group
72 .into_iter()
73 .min_by_key(|t| lc_penalty(t, map))
74 .unwrap();
75 final_turns.push(best);
76 timer.note(format!(
77 "Restricted lane-changing on approach to turn lanes at {}",
78 l
79 ));
80 } else {
81 timer.warn(format!(
82 "Turn restrictions broke {} outbound, so restoring turns",
83 l
84 ));
85 final_turns.extend(turns);
86 }
87 incoming_missing.remove(&l);
88 }
89 }
90
91 let mut outgoing_missing: HashSet<LaneID> = HashSet::new();
92 for l in &i.outgoing_lanes {
93 if map.get_l(*l).lane_type.supports_any_movement() {
94 outgoing_missing.insert(*l);
95 }
96 }
97 for t in &final_turns {
98 outgoing_missing.remove(&t.id.dst);
99 }
100
101 if !incoming_missing.is_empty() || !outgoing_missing.is_empty() {
102 timer.warn(format!(
103 "Turns for {} orphan some lanes. Incoming: {:?}, outgoing: {:?}",
104 i.id, incoming_missing, outgoing_missing
105 ));
106 }
107
108 final_turns
109 }
110
ensure_unique(turns: Vec<Turn>) -> Vec<Turn>111 fn ensure_unique(turns: Vec<Turn>) -> Vec<Turn> {
112 let mut ids = HashSet::new();
113 let mut keep: Vec<Turn> = Vec::new();
114 for t in turns.into_iter() {
115 if ids.contains(&t.id) {
116 // TODO This was once an assertion, but disabled for
117 // https://github.com/dabreegster/abstreet/issues/84. A crosswalk gets created twice
118 // and deduplicated here. Not sure why it was double-created in the first place.
119 println!("Duplicate turns {}!", t.id);
120 } else {
121 ids.insert(t.id);
122 keep.push(t);
123 }
124 }
125 keep
126 }
127
is_turn_allowed(turn: &Turn, map: &Map) -> bool128 fn is_turn_allowed(turn: &Turn, map: &Map) -> bool {
129 if let Some(mut types) = map
130 .get_l(turn.id.src)
131 .get_turn_restrictions(map.get_parent(turn.id.src))
132 {
133 types.any(|turn_type| turn_type == turn.turn_type)
134 } else {
135 true
136 }
137 }
138
does_turn_pass_restrictions(turn: &Turn, i: &Intersection, map: &Map) -> bool139 fn does_turn_pass_restrictions(turn: &Turn, i: &Intersection, map: &Map) -> bool {
140 if turn.between_sidewalks() {
141 return true;
142 }
143
144 let src = map.get_parent(turn.id.src);
145 let dst = map.get_l(turn.id.dst).parent;
146
147 for (restriction, to) in &src.turn_restrictions {
148 // The restriction only applies to one direction of the road.
149 if !i.roads.contains(to) {
150 continue;
151 }
152 match restriction {
153 RestrictionType::BanTurns => {
154 if dst == *to {
155 return false;
156 }
157 }
158 RestrictionType::OnlyAllowTurns => {
159 if dst != *to {
160 return false;
161 }
162 }
163 }
164 }
165
166 true
167 }
168
make_vehicle_turns(i: &Intersection, map: &Map, timer: &mut Timer) -> Vec<Turn>169 fn make_vehicle_turns(i: &Intersection, map: &Map, timer: &mut Timer) -> Vec<Turn> {
170 let mut turns = Vec::new();
171
172 // Just generate every possible combination of turns between incoming and outgoing lanes.
173 let is_deadend = i.roads.len() == 1;
174 for src in &i.incoming_lanes {
175 let src = map.get_l(*src);
176 if !src.lane_type.is_for_moving_vehicles() {
177 continue;
178 }
179 for dst in &i.outgoing_lanes {
180 let dst = map.get_l(*dst);
181 if !dst.lane_type.is_for_moving_vehicles() {
182 continue;
183 }
184 // Only allow U-turns at deadends
185 if src.parent == dst.parent && !is_deadend {
186 continue;
187 }
188 // Can't go between light rail and normal roads
189 if src.is_light_rail() != dst.is_light_rail() {
190 continue;
191 }
192 if src.last_pt() == dst.first_pt() {
193 timer.warn(format!(
194 "No turn from {} to {}; the endpoints are the same",
195 src.id, dst.id
196 ));
197 continue;
198 }
199
200 let turn_type =
201 TurnType::from_angles(src.last_line().angle(), dst.first_line().angle());
202 let geom = if turn_type == TurnType::Straight {
203 PolyLine::must_new(vec![src.last_pt(), dst.first_pt()])
204 } else {
205 curvey_turn(src, dst)
206 .unwrap_or_else(|_| PolyLine::must_new(vec![src.last_pt(), dst.first_pt()]))
207 };
208
209 turns.push(Turn {
210 id: TurnID {
211 parent: i.id,
212 src: src.id,
213 dst: dst.id,
214 },
215 turn_type,
216 other_crosswalk_ids: BTreeSet::new(),
217 geom,
218 });
219 }
220 }
221
222 turns
223 }
224
curvey_turn(src: &Lane, dst: &Lane) -> Result<PolyLine, String>225 fn curvey_turn(src: &Lane, dst: &Lane) -> Result<PolyLine, String> {
226 // The control points are straight out/in from the source/destination lanes, so
227 // that the car exits and enters at the same angle as the road.
228 let src_line = src.last_line();
229 let dst_line = dst.first_line().reverse();
230
231 // TODO Tune the 5.0 and pieces
232 let curve = Bez3o::new(
233 to_pt(src.last_pt()),
234 to_pt(src_line.unbounded_dist_along(src_line.length() + Distance::meters(5.0))),
235 to_pt(dst_line.unbounded_dist_along(dst_line.length() + Distance::meters(5.0))),
236 to_pt(dst.first_pt()),
237 );
238 let pieces = 5;
239 let mut curve: Vec<Pt2D> = (0..=pieces)
240 .map(|i| {
241 from_pt(
242 curve
243 .interp(1.0 / f64::from(pieces) * f64::from(i))
244 .unwrap(),
245 )
246 })
247 .collect();
248 curve.dedup();
249 PolyLine::new(curve)
250 }
251
to_pt(pt: Pt2D) -> Point2d<f64>252 fn to_pt(pt: Pt2D) -> Point2d<f64> {
253 Point2d::new(pt.x(), pt.y())
254 }
255
from_pt(pt: Point2d<f64>) -> Pt2D256 fn from_pt(pt: Point2d<f64>) -> Pt2D {
257 Pt2D::new(pt.x, pt.y)
258 }
259
lc_penalty(t: &Turn, map: &Map) -> isize260 fn lc_penalty(t: &Turn, map: &Map) -> isize {
261 let from = map.get_l(t.id.src);
262 let to = map.get_l(t.id.dst);
263
264 let from_idx = {
265 let mut cnt = 0;
266 let r = map.get_r(from.parent);
267 for (l, lt) in r.children(r.dir(from.id)) {
268 if from.lane_type != lt {
269 continue;
270 }
271 cnt += 1;
272 if from.id == l {
273 break;
274 }
275 }
276 cnt
277 };
278
279 let to_idx = {
280 let mut cnt = 0;
281 let r = map.get_r(to.parent);
282 for (l, lt) in r.children(r.dir(to.id)) {
283 if to.lane_type != lt {
284 continue;
285 }
286 cnt += 1;
287 if to.id == l {
288 break;
289 }
290 }
291 cnt
292 };
293
294 ((from_idx as isize) - (to_idx as isize)).abs()
295 }
296