map_model/make/traffic_signals/
lagging_green.rs

1use super::*;
2
3/// Create a traffic signal which has a stage that is: protected straight, protected right,
4/// unprotected left, unprotected right on red. Followed by a variable stage that has protected
5/// left, unprotected right on red. With a last stage that is all-walk and variable.
6/// In some degenerate cases, usually with one or more one-way, this can reduce to stage per road.
7/// In some rare cases, usually with an alleyway, oncoming lanes can't both be protected left turns.
8/// In such cases the stage is split into two stages with each having a protected and yield turn.
9pub fn make_traffic_signal(map: &Map, i: &Intersection) -> Option<ControlTrafficSignal> {
10    // Try to create the stages, this returns a unoptimized signal, which is then optimized.
11    if let Some(ts) = make_signal(i, map) {
12        return optimize(ts, i);
13    }
14    None
15}
16
17fn make_signal(i: &Intersection, map: &Map) -> Option<ControlTrafficSignal> {
18    let mut ts = new(i.id);
19    if let Some(other) = three_way_three_stage(i, map) {
20        ts.stages = other.stages;
21    } else if let Some(other) = four_way_four_stage(i, map) {
22        ts.stages = other.stages;
23    }
24    ts.convert_to_ped_scramble_without_promotion(i);
25    // We don't always get a valid traffic signal from the default 3-way and 4-way. When we don't
26    // we need to try assembling stages with a more complex algorithm.
27    if ts.validate(i).is_err() {
28        if let Some(other) = multi_way_stages(i) {
29            ts.stages = other.stages;
30            ts.convert_to_ped_scramble_without_promotion(i);
31        }
32    }
33    if let Err(err) = ts.validate(i) {
34        // when all else fails, use stage per road and all-walk stage at the end
35        debug!("multi-way validation_error={} ts={:#?}", err, ts);
36        ts = stage_per_road(i);
37        ts.convert_to_ped_scramble(i);
38    }
39    Some(ts)
40}
41
42fn optimize(mut ts: ControlTrafficSignal, i: &Intersection) -> Option<ControlTrafficSignal> {
43    // Remove stages which don't contain a protected route.
44    ts.stages.retain(|s| !s.protected_movements.is_empty());
45    // Determine if any stages can be merged. We could merge turns, but if we end up not reducing
46    // the stage as a result, its probably not worth doing, or can be easily added by the user.
47    while let Some(merged_ts) = merge_stages(&ts, i) {
48        ts = merged_ts;
49    }
50    make_lagging_green_variable(&mut ts);
51    make_crosswalk_variable(&mut ts, i);
52    Some(ts)
53}
54
55// convert walk to variable with a min duration not less than 15 seconds
56fn make_crosswalk_variable(ts: &mut ControlTrafficSignal, i: &Intersection) {
57    const MIN_CROSSWALK_TIME: Duration = Duration::const_seconds(15.0);
58    for s in &mut ts.stages {
59        if let Some(duration) = s.max_crosswalk_time(i) {
60            if let StageType::Fixed(_) = s.stage_type {
61                s.stage_type = StageType::Variable(
62                    duration.max(MIN_CROSSWALK_TIME),
63                    Duration::const_seconds(1.0),
64                    Duration::const_seconds(1.0),
65                )
66            }
67        }
68    }
69}
70
71fn merge_stages(ts: &ControlTrafficSignal, i: &Intersection) -> Option<ControlTrafficSignal> {
72    for s_src in &ts.stages {
73        // s_src is the stage we want to apply to the other stages
74        for s_dst in &ts.stages {
75            if s_src == s_dst {
76                continue;
77            }
78            let mut merged_stage = s_dst.clone();
79            merged_stage
80                .protected_movements
81                .extend(s_src.protected_movements.clone());
82
83            let mut maybe_ts = ts.clone();
84            // insert at the head, keeping crosswalk last
85            maybe_ts.stages.insert(0, merged_stage);
86            if maybe_ts.validate(i).is_ok() {
87                let mut stages: Vec<Stage> = Vec::new();
88                for s in maybe_ts.stages {
89                    if s != *s_src && s != *s_dst {
90                        stages.push(s);
91                    }
92                }
93                maybe_ts.stages = stages;
94                return Some(maybe_ts);
95            }
96        }
97    }
98    None
99}
100
101// Sometimes protected oncoming left turns aren't possible.
102fn is_conflict(stage: &Stage, i: &Intersection) -> Option<(MovementID, MovementID)> {
103    for m1 in stage.protected_movements.iter().map(|m| &i.movements[m]) {
104        for m2 in stage.protected_movements.iter().map(|m| &i.movements[m]) {
105            // Use low-level turn conflict, since we know this a road to road movement.
106            if m1.id != m2.id && m1.geom.intersection(&m2.geom).is_some() {
107                return Some((m1.id, m2.id));
108            }
109        }
110    }
111    None
112}
113
114fn protected_yield_stage(p: MovementID, y: MovementID) -> Stage {
115    let mut stage = Stage::new();
116    stage.protected_movements.insert(p);
117    stage.yield_movements.insert(y);
118    stage
119}
120
121/// Build stages. First find roads that are straight across, they are either one-way or two-way.
122/// For one-way, add any right or left turns, thus completing the stage. For two-way, two
123/// stages will be added. The first stage has protected straight, and right and yield left.
124/// The second stage has protected left. Lastly, sometimes oncomming left turns can't both
125/// be protected, if this occurs the 2nd stage will have one direction protected and the
126/// other yield and a 3rd, inverse, stage will be added which has the other direction's left
127/// protected and other yield. Finally, any turns which weren't assigned, because there
128/// are no straights or there are more than just pairs of straight intersections, are assigned a
129/// stage. These, too are handled as pairs until one remains, which is handled as a one-way.
130fn multi_way_stages(i: &Intersection) -> Option<ControlTrafficSignal> {
131    let mut ts = new(i.id);
132    let (mut right, mut left, straight, mut roads) = movements(i);
133    let (one_way, two_way) = straight_types(&straight);
134    for m in &one_way {
135        let mut stage = Stage::new();
136        stage.protected_movements.insert(*m);
137        for t in movements_from(m.from.road, &right) {
138            stage.protected_movements.insert(t);
139        }
140        for t in movements_from(m.from.road, &left) {
141            stage.protected_movements.insert(t);
142        }
143        add_stage(&mut ts, stage);
144        roads.remove(&m.from.road);
145    }
146    for (m1, m2) in &two_way {
147        let mut stage1 = Stage::new();
148        let mut stage2 = Stage::new();
149        // Insert the straight movements, followed by the right and then the left.
150        stage1.protected_movements.insert(*m1);
151        stage1.protected_movements.insert(*m2);
152        stage1
153            .protected_movements
154            .extend(movements_from(m1.from.road, &right));
155        stage1
156            .protected_movements
157            .extend(movements_from(m2.from.road, &right));
158        for t in movements_from(m1.from.road, &left) {
159            stage1.yield_movements.insert(t);
160            stage2.protected_movements.insert(t);
161        }
162        for t in movements_from(m2.from.road, &left) {
163            stage1.yield_movements.insert(t);
164            stage2.protected_movements.insert(t);
165        }
166        add_stage(&mut ts, stage1);
167        if let Some((m1, m2)) = is_conflict(&stage2, i) {
168            // We've hit the case where oncoming left turns can't both be protected.
169            add_stage(&mut ts, protected_yield_stage(m1, m2));
170            add_stage(&mut ts, protected_yield_stage(m2, m1));
171        } else {
172            add_stage(&mut ts, stage2);
173        }
174        roads.remove(&m1.from.road);
175        roads.remove(&m2.from.road);
176    }
177    // We may be done assigning, or we may have some roads we haven't dealt with yet.
178    let mut vec: Vec<_> = roads.into_iter().collect();
179    // We're going to treat the roads as if thery are straight. Otherwise,
180    // we'd end up with overlapping protected left turns.
181    while let Some(r1) = vec.pop() {
182        let mut stage1 = Stage::new();
183        let mut stage2 = Stage::new();
184        if let Some(r2) = vec.pop() {
185            // dual stage, with lagging left turns
186            if let Some(m) = remove_movement(r1, r2, &mut right) {
187                stage1.protected_movements.insert(m);
188            } else if let Some(m) = remove_movement(r1, r2, &mut left) {
189                stage1.protected_movements.insert(m);
190            }
191            if let Some(m) = remove_movement(r2, r1, &mut right) {
192                stage1.protected_movements.insert(m);
193            } else if let Some(m) = remove_movement(r2, r1, &mut left) {
194                stage1.protected_movements.insert(m);
195            }
196
197            // add right turns
198            stage1
199                .protected_movements
200                .extend(movements_from(r1, &right));
201            stage1
202                .protected_movements
203                .extend(movements_from(r2, &right));
204
205            // add left turns
206            for t in movements_from(r1, &left) {
207                stage1.yield_movements.insert(t);
208                stage2.protected_movements.insert(t);
209            }
210            for t in movements_from(r2, &left) {
211                stage1.yield_movements.insert(t);
212                stage2.protected_movements.insert(t);
213            }
214            // add the stages
215            add_stage(&mut ts, stage1);
216            add_stage(&mut ts, stage2);
217        } else {
218            // single stage without lagging left turns
219            stage1
220                .protected_movements
221                .extend(movements_from(r1, &right));
222            stage1.protected_movements.extend(movements_from(r1, &left));
223            add_stage(&mut ts, stage1);
224        }
225    }
226    Some(ts)
227}
228
229fn add_stage(ts: &mut ControlTrafficSignal, stage: Stage) {
230    // If there aren't any protected movements, don't add it.
231    if stage.protected_movements.is_empty() {
232        return;
233    }
234    // Ensure a duplicate isn't added.
235    if ts.stages.iter().all(|s| *s != stage) {
236        ts.stages.push(stage)
237    }
238}
239
240fn movements_from(from: RoadID, movements: &[MovementID]) -> Vec<MovementID> {
241    movements
242        .iter()
243        .filter_map(|mvmnt| {
244            if from == mvmnt.from.road {
245                Some(*mvmnt)
246            } else {
247                None
248            }
249        })
250        .collect()
251}
252
253fn remove_movement(
254    from: RoadID,
255    to: RoadID,
256    movements: &mut Vec<MovementID>,
257) -> Option<MovementID> {
258    let idx = movements
259        .iter()
260        .position(|mvmnt| mvmnt.from.road == from && mvmnt.to.road == to)?;
261    Some(movements.remove(idx))
262}
263
264fn three_way_three_stage(i: &Intersection, map: &Map) -> Option<ControlTrafficSignal> {
265    let roads = i.get_sorted_incoming_roads(map);
266    if roads.len() != 3 {
267        return None;
268    }
269    let mut ts = new(i.id);
270
271    // Picture a T intersection. Use turn angles to figure out the "main" two roads.
272    let straight = i
273        .movements
274        .values()
275        .find(|g| g.turn_type == TurnType::Straight)?;
276    let (north, south) = (straight.id.from.road, straight.id.to.road);
277    let east = roads
278        .into_iter()
279        .find(|r| *r != north && *r != south)
280        .unwrap();
281
282    // Three-stage with protected lefts, right turn on red
283    make_stages(
284        &mut ts,
285        &map.config,
286        i,
287        vec![
288            vec![
289                (vec![north, south], TurnType::Straight, PROTECTED),
290                (vec![north, south], TurnType::Right, PROTECTED),
291                (vec![north, south], TurnType::Left, YIELD),
292                (vec![east], TurnType::Right, YIELD),
293            ],
294            vec![
295                (vec![north, south], TurnType::Left, PROTECTED),
296                (vec![east], TurnType::Right, YIELD),
297            ],
298            vec![
299                (vec![east], TurnType::Straight, PROTECTED),
300                (vec![east], TurnType::Right, PROTECTED),
301                (vec![east], TurnType::Left, PROTECTED),
302                (vec![north, south], TurnType::Right, YIELD),
303            ],
304        ],
305    );
306    Some(ts)
307}
308
309fn four_way_four_stage(i: &Intersection, map: &Map) -> Option<ControlTrafficSignal> {
310    let roads = i.get_sorted_incoming_roads(map);
311    if roads.len() != 4 {
312        return None;
313    }
314
315    // Just to refer to these easily, label with directions. Imagine an axis-aligned four-way.
316    let (north, west, south, east) = (roads[0], roads[1], roads[2], roads[3]);
317
318    // Four-stage with protected lefts, right turn on red (except for the protected lefts),
319    // turning cars yield to peds
320    let mut ts = new(i.id);
321    make_stages(
322        &mut ts,
323        &map.config,
324        i,
325        vec![
326            vec![
327                (vec![north, south], TurnType::Straight, PROTECTED),
328                (vec![north, south], TurnType::Left, YIELD),
329                (vec![north, south], TurnType::Right, PROTECTED),
330                (vec![east, west], TurnType::Right, YIELD),
331            ],
332            vec![
333                (vec![north, south], TurnType::Left, PROTECTED),
334                (vec![east, west], TurnType::Right, YIELD),
335            ],
336            vec![
337                (vec![east, west], TurnType::Straight, PROTECTED),
338                (vec![east, west], TurnType::Left, YIELD),
339                (vec![east, west], TurnType::Right, PROTECTED),
340                (vec![north, south], TurnType::Right, YIELD),
341            ],
342            vec![
343                (vec![east, west], TurnType::Left, PROTECTED),
344                (vec![north, south], TurnType::Right, YIELD),
345            ],
346        ],
347    );
348    Some(ts)
349}
350
351fn movements(
352    i: &Intersection,
353) -> (
354    Vec<MovementID>,
355    Vec<MovementID>,
356    Vec<MovementID>,
357    BTreeSet<RoadID>,
358) {
359    let mut right: Vec<MovementID> = Vec::new();
360    let mut left: Vec<MovementID> = Vec::new();
361    let mut straight: Vec<MovementID> = Vec::new();
362    let mut set: BTreeSet<RoadID> = BTreeSet::new();
363
364    for (id, m) in &i.movements {
365        if !id.crosswalk {
366            match m.turn_type {
367                TurnType::Right => right.push(*id),
368                TurnType::Left => left.push(*id),
369                TurnType::Straight => straight.push(*id),
370                _ => (),
371            }
372            set.insert(id.from.road);
373        }
374    }
375    (right, left, straight, set)
376}
377
378fn straight_types(movements: &[MovementID]) -> (Vec<MovementID>, Vec<(MovementID, MovementID)>) {
379    let mut one_way: Vec<MovementID> = Vec::new();
380    let mut two_way: Vec<(MovementID, MovementID)> = Vec::new();
381    for m in movements {
382        if let Some(other) = movements
383            .iter()
384            .find(|&other| m.from.road == other.to.road && m.to.road == other.from.road)
385        {
386            two_way.push((*m, *other));
387        } else {
388            one_way.push(*m);
389        }
390    }
391    (one_way, two_way)
392}
393
394fn make_lagging_green_variable(ts: &mut ControlTrafficSignal) {
395    const EXTENT_DURATION: Duration = Duration::const_seconds(10.0);
396    const MAX_DURATION: Duration = Duration::const_seconds(20.0);
397    let mut prev_stage: Option<&mut Stage> = None;
398    for stage in ts.stages.iter_mut() {
399        // Lagging green: if this stage's protected movements were yield movements in the
400        // previous stage, make this stage optional.
401        if let Some(prev) = prev_stage {
402            if stage
403                .protected_movements
404                .iter()
405                .all(|m| prev.yield_movements.contains(m))
406            {
407                if let StageType::Fixed(_) = stage.stage_type {
408                    stage.stage_type =
409                        StageType::Variable(Duration::ZERO, EXTENT_DURATION, MAX_DURATION);
410                }
411            }
412        }
413        prev_stage = Some(stage);
414    }
415}