1 mod compat;
2 mod perma;
3
4 use crate::make::initial::lane_specs::get_lane_specs_ltr;
5 use crate::{
6 connectivity, AccessRestrictions, BusRouteID, ControlStopSign, ControlTrafficSignal, Direction,
7 IntersectionID, IntersectionType, LaneType, Map, PathConstraints, Pathfinder, Road, RoadID,
8 TurnID, Zone,
9 };
10 use abstutil::{retain_btreemap, retain_btreeset, Timer};
11 use geom::{Speed, Time};
12 pub use perma::PermanentMapEdits;
13 use serde::{Deserialize, Serialize};
14 use std::collections::{BTreeMap, BTreeSet};
15
16 #[derive(Debug, Clone, PartialEq)]
17 pub struct MapEdits {
18 pub edits_name: String,
19 pub commands: Vec<EditCmd>,
20
21 // Derived from commands, kept up to date by update_derived
22 pub changed_roads: BTreeSet<RoadID>,
23 pub original_intersections: BTreeMap<IntersectionID, EditIntersection>,
24 pub changed_routes: BTreeSet<BusRouteID>,
25
26 // Edits without these are player generated.
27 pub proposal_description: Vec<String>,
28 // The link is optional even for proposals
29 pub proposal_link: Option<String>,
30 }
31
32 #[derive(Debug, Clone, PartialEq)]
33 pub enum EditIntersection {
34 StopSign(ControlStopSign),
35 // Don't keep ControlTrafficSignal here, because it contains movements that should be
36 // generated after all lane edits are applied.
37 TrafficSignal(seattle_traffic_signals::TrafficSignal),
38 Closed,
39 }
40
41 #[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
42 pub struct EditRoad {
43 pub lanes_ltr: Vec<(LaneType, Direction)>,
44 pub speed_limit: Speed,
45 pub access_restrictions: AccessRestrictions,
46 }
47
48 impl EditRoad {
get_orig_from_osm(r: &Road) -> EditRoad49 pub fn get_orig_from_osm(r: &Road) -> EditRoad {
50 EditRoad {
51 lanes_ltr: get_lane_specs_ltr(&r.osm_tags)
52 .into_iter()
53 .map(|spec| (spec.lt, spec.dir))
54 .collect(),
55 speed_limit: r.speed_limit_from_osm(),
56 access_restrictions: r.access_restrictions_from_osm(),
57 }
58 }
59 }
60
61 #[derive(Debug, Clone, PartialEq)]
62 pub enum EditCmd {
63 ChangeRoad {
64 r: RoadID,
65 old: EditRoad,
66 new: EditRoad,
67 },
68 ChangeIntersection {
69 i: IntersectionID,
70 new: EditIntersection,
71 old: EditIntersection,
72 },
73 ChangeRouteSchedule {
74 id: BusRouteID,
75 old: Vec<Time>,
76 new: Vec<Time>,
77 },
78 }
79
80 pub struct EditEffects {
81 pub changed_roads: BTreeSet<RoadID>,
82 pub changed_intersections: BTreeSet<IntersectionID>,
83 pub added_turns: BTreeSet<TurnID>,
84 pub deleted_turns: BTreeSet<TurnID>,
85 }
86
87 impl MapEdits {
new() -> MapEdits88 pub fn new() -> MapEdits {
89 MapEdits {
90 // Something has to fill this out later
91 edits_name: "untitled edits".to_string(),
92 proposal_description: Vec::new(),
93 proposal_link: None,
94 commands: Vec::new(),
95
96 changed_roads: BTreeSet::new(),
97 original_intersections: BTreeMap::new(),
98 changed_routes: BTreeSet::new(),
99 }
100 }
101
load(map: &Map, path: String, timer: &mut Timer) -> Result<MapEdits, String>102 pub fn load(map: &Map, path: String, timer: &mut Timer) -> Result<MapEdits, String> {
103 match abstutil::maybe_read_json(path.clone(), timer) {
104 Ok(perma) => PermanentMapEdits::from_permanent(perma, map),
105 Err(_) => {
106 let bytes = abstutil::slurp_file(&path).map_err(|err| err.to_string())?;
107 let contents = std::str::from_utf8(&bytes).map_err(|err| err.to_string())?;
108 let value = serde_json::from_str(contents).map_err(|err| err.to_string())?;
109 let perma = compat::upgrade(value)?;
110 PermanentMapEdits::from_permanent(perma, map)
111 }
112 }
113 }
114
115 // TODO Version these? Or it's unnecessary, since we have a command stack.
save(&self, map: &Map)116 fn save(&self, map: &Map) {
117 assert_ne!(self.edits_name, "untitled edits");
118
119 abstutil::write_json(
120 abstutil::path_edits(map.get_name(), &self.edits_name),
121 &PermanentMapEdits::to_permanent(self, map),
122 );
123 }
124
update_derived(&mut self, map: &Map)125 fn update_derived(&mut self, map: &Map) {
126 self.changed_roads.clear();
127 self.original_intersections.clear();
128 self.changed_routes.clear();
129
130 for cmd in &self.commands {
131 match cmd {
132 EditCmd::ChangeRoad { r, .. } => {
133 self.changed_roads.insert(*r);
134 }
135 EditCmd::ChangeIntersection { i, ref old, .. } => {
136 if !self.original_intersections.contains_key(i) {
137 self.original_intersections.insert(*i, old.clone());
138 }
139 }
140 EditCmd::ChangeRouteSchedule { id, .. } => {
141 self.changed_routes.insert(*id);
142 }
143 }
144 }
145
146 retain_btreeset(&mut self.changed_roads, |r| {
147 map.get_r_edit(*r) != EditRoad::get_orig_from_osm(map.get_r(*r))
148 });
149 retain_btreemap(&mut self.original_intersections, |i, orig| {
150 map.get_i_edit(*i) != orig.clone()
151 });
152 retain_btreeset(&mut self.changed_routes, |br| {
153 let r = map.get_br(*br);
154 r.spawn_times != r.orig_spawn_times
155 });
156 }
157
158 // Assumes update_derived has been called.
compress(&mut self, map: &Map)159 pub fn compress(&mut self, map: &Map) {
160 for r in &self.changed_roads {
161 self.commands.push(EditCmd::ChangeRoad {
162 r: *r,
163 old: EditRoad::get_orig_from_osm(map.get_r(*r)),
164 new: map.get_r_edit(*r),
165 });
166 }
167 for (i, old) in &self.original_intersections {
168 self.commands.push(EditCmd::ChangeIntersection {
169 i: *i,
170 old: old.clone(),
171 new: map.get_i_edit(*i),
172 });
173 }
174 for r in &self.changed_routes {
175 let r = map.get_br(*r);
176 self.commands.push(EditCmd::ChangeRouteSchedule {
177 id: r.id,
178 new: r.spawn_times.clone(),
179 old: r.orig_spawn_times.clone(),
180 });
181 }
182 }
183 }
184
185 impl std::default::Default for MapEdits {
default() -> MapEdits186 fn default() -> MapEdits {
187 MapEdits::new()
188 }
189 }
190
191 impl EditEffects {
new() -> EditEffects192 pub fn new() -> EditEffects {
193 EditEffects {
194 changed_roads: BTreeSet::new(),
195 changed_intersections: BTreeSet::new(),
196 added_turns: BTreeSet::new(),
197 deleted_turns: BTreeSet::new(),
198 }
199 }
200 }
201
202 impl EditCmd {
short_name(&self, map: &Map) -> String203 pub fn short_name(&self, map: &Map) -> String {
204 match self {
205 // TODO Way more details
206 EditCmd::ChangeRoad { r, .. } => format!("road #{}", r.0),
207 EditCmd::ChangeIntersection { i, new, .. } => match new {
208 EditIntersection::StopSign(_) => format!("stop sign #{}", i.0),
209 EditIntersection::TrafficSignal(_) => format!("traffic signal #{}", i.0),
210 EditIntersection::Closed => format!("close {}", i),
211 },
212 EditCmd::ChangeRouteSchedule { id, .. } => {
213 format!("reschedule route {}", map.get_br(*id).short_name)
214 }
215 }
216 }
217
218 // Must be idempotent
apply(&self, effects: &mut EditEffects, map: &mut Map, timer: &mut Timer)219 fn apply(&self, effects: &mut EditEffects, map: &mut Map, timer: &mut Timer) {
220 match self {
221 EditCmd::ChangeRoad { r, ref new, .. } => {
222 if map.get_r_edit(*r) == new.clone() {
223 return;
224 }
225
226 let road = &mut map.roads[r.0];
227 road.speed_limit = new.speed_limit;
228 road.access_restrictions = new.access_restrictions.clone();
229 assert_eq!(road.lanes_ltr.len(), new.lanes_ltr.len());
230 for (idx, (lt, dir)) in new.lanes_ltr.clone().into_iter().enumerate() {
231 let lane = &mut map.lanes[(road.lanes_ltr[idx].0).0];
232 road.lanes_ltr[idx].2 = lt;
233 lane.lane_type = lt;
234
235 // Direction change?
236 if road.lanes_ltr[idx].1 != dir {
237 road.lanes_ltr[idx].1 = dir;
238 std::mem::swap(&mut lane.src_i, &mut lane.dst_i);
239 lane.lane_center_pts = lane.lane_center_pts.reversed();
240 }
241 }
242
243 effects.changed_roads.insert(road.id);
244 for i in vec![road.src_i, road.dst_i] {
245 effects.changed_intersections.insert(i);
246 let i = &mut map.intersections[i.0];
247 i.outgoing_lanes.clear();
248 i.incoming_lanes.clear();
249 for r in &i.roads {
250 for (l, _, _) in map.roads[r.0].lanes_ltr() {
251 if map.lanes[l.0].src_i == i.id {
252 i.outgoing_lanes.push(l);
253 } else {
254 assert_eq!(map.lanes[l.0].dst_i, i.id);
255 i.incoming_lanes.push(l);
256 }
257 }
258 }
259
260 recalculate_turns(i.id, map, effects, timer);
261 }
262 }
263 EditCmd::ChangeIntersection {
264 i,
265 ref new,
266 ref old,
267 } => {
268 if map.get_i_edit(*i) == new.clone() {
269 return;
270 }
271
272 map.stop_signs.remove(i);
273 map.traffic_signals.remove(i);
274 effects.changed_intersections.insert(*i);
275 match new {
276 EditIntersection::StopSign(ref ss) => {
277 map.intersections[i.0].intersection_type = IntersectionType::StopSign;
278 map.stop_signs.insert(*i, ss.clone());
279 }
280 EditIntersection::TrafficSignal(ref raw_ts) => {
281 map.intersections[i.0].intersection_type = IntersectionType::TrafficSignal;
282 if old == &EditIntersection::Closed {
283 recalculate_turns(*i, map, effects, timer);
284 }
285 map.traffic_signals.insert(
286 *i,
287 ControlTrafficSignal::import(raw_ts.clone(), *i, map).unwrap(),
288 );
289 }
290 EditIntersection::Closed => {
291 map.intersections[i.0].intersection_type = IntersectionType::Construction;
292 }
293 }
294
295 if old == &EditIntersection::Closed || new == &EditIntersection::Closed {
296 recalculate_turns(*i, map, effects, timer);
297 }
298 }
299 EditCmd::ChangeRouteSchedule { id, new, .. } => {
300 map.bus_routes[id.0].spawn_times = new.clone();
301 }
302 }
303 }
304
undo(self) -> EditCmd305 fn undo(self) -> EditCmd {
306 match self {
307 EditCmd::ChangeRoad { r, old, new } => EditCmd::ChangeRoad {
308 r,
309 old: new,
310 new: old,
311 },
312 EditCmd::ChangeIntersection { i, old, new } => EditCmd::ChangeIntersection {
313 i,
314 old: new,
315 new: old,
316 },
317 EditCmd::ChangeRouteSchedule { id, old, new } => EditCmd::ChangeRouteSchedule {
318 id,
319 old: new,
320 new: old,
321 },
322 }
323 }
324 }
325
326 // This clobbers previously set traffic signal overrides.
327 // TODO Step 1: Detect and warn about that
328 // TODO Step 2: Avoid when possible
recalculate_turns( id: IntersectionID, map: &mut Map, effects: &mut EditEffects, timer: &mut Timer, )329 fn recalculate_turns(
330 id: IntersectionID,
331 map: &mut Map,
332 effects: &mut EditEffects,
333 timer: &mut Timer,
334 ) {
335 let i = &mut map.intersections[id.0];
336
337 if i.is_border() {
338 assert!(i.turns.is_empty());
339 return;
340 }
341
342 let mut old_turns = Vec::new();
343 for t in std::mem::replace(&mut i.turns, BTreeSet::new()) {
344 old_turns.push(map.turns.remove(&t).unwrap());
345 effects.deleted_turns.insert(t);
346 }
347
348 if i.is_closed() {
349 return;
350 }
351
352 let turns = crate::make::turns::make_all_turns(map, map.get_i(id), timer);
353 let i = &mut map.intersections[id.0];
354 for t in turns {
355 effects.added_turns.insert(t.id);
356 i.turns.insert(t.id);
357 if let Some(_existing_t) = old_turns.iter().find(|turn| turn.id == t.id) {
358 // TODO Except for lookup_idx
359 //assert_eq!(t, *existing_t);
360 }
361 map.turns.insert(t.id, t);
362 }
363
364 match i.intersection_type {
365 IntersectionType::StopSign => {
366 // Stop sign policy usually doesn't depend on incoming lane types, except when changing
367 // to/from construction. To be safe, always regenerate. Edits to stop signs are rare
368 // anyway. And when we're smarter about preserving traffic signal changes in the face
369 // of lane changes, we can do the same here.
370 map.stop_signs.insert(id, ControlStopSign::new(map, id));
371 }
372 IntersectionType::TrafficSignal => {
373 map.traffic_signals
374 .insert(id, ControlTrafficSignal::new(map, id, timer));
375 }
376 IntersectionType::Border | IntersectionType::Construction => unreachable!(),
377 }
378 }
379
380 impl Map {
get_edits(&self) -> &MapEdits381 pub fn get_edits(&self) -> &MapEdits {
382 &self.edits
383 }
384
get_r_edit(&self, r: RoadID) -> EditRoad385 pub fn get_r_edit(&self, r: RoadID) -> EditRoad {
386 let r = self.get_r(r);
387 EditRoad {
388 lanes_ltr: r
389 .lanes_ltr()
390 .into_iter()
391 .map(|(_, dir, lt)| (lt, dir))
392 .collect(),
393 speed_limit: r.speed_limit,
394 access_restrictions: r.access_restrictions.clone(),
395 }
396 }
397
edit_road_cmd<F: Fn(&mut EditRoad)>(&self, r: RoadID, f: F) -> EditCmd398 pub fn edit_road_cmd<F: Fn(&mut EditRoad)>(&self, r: RoadID, f: F) -> EditCmd {
399 let old = self.get_r_edit(r);
400 let mut new = old.clone();
401 f(&mut new);
402 EditCmd::ChangeRoad { r, old, new }
403 }
404
405 // Panics on borders
get_i_edit(&self, i: IntersectionID) -> EditIntersection406 pub fn get_i_edit(&self, i: IntersectionID) -> EditIntersection {
407 match self.get_i(i).intersection_type {
408 IntersectionType::StopSign => EditIntersection::StopSign(self.get_stop_sign(i).clone()),
409 IntersectionType::TrafficSignal => {
410 EditIntersection::TrafficSignal(self.get_traffic_signal(i).export(self))
411 }
412 IntersectionType::Construction => EditIntersection::Closed,
413 IntersectionType::Border => unreachable!(),
414 }
415 }
416
save_edits(&self)417 pub fn save_edits(&self) {
418 // Don't overwrite the current edits with the compressed first. Otherwise, undo/redo order
419 // in the UI gets messed up.
420 let mut edits = self.edits.clone();
421 edits.commands.clear();
422 edits.compress(self);
423 edits.save(self);
424 }
425
must_apply_edits( &mut self, new_edits: MapEdits, timer: &mut Timer, ) -> ( BTreeSet<RoadID>, BTreeSet<TurnID>, BTreeSet<TurnID>, BTreeSet<IntersectionID>, )426 pub fn must_apply_edits(
427 &mut self,
428 new_edits: MapEdits,
429 timer: &mut Timer,
430 ) -> (
431 BTreeSet<RoadID>,
432 BTreeSet<TurnID>,
433 BTreeSet<TurnID>,
434 BTreeSet<IntersectionID>,
435 ) {
436 self.apply_edits(new_edits, true, timer)
437 }
438
try_apply_edits(&mut self, new_edits: MapEdits, timer: &mut Timer)439 pub fn try_apply_edits(&mut self, new_edits: MapEdits, timer: &mut Timer) {
440 self.apply_edits(new_edits, false, timer);
441 }
442
443 // new_edits don't necessarily have to be valid; this could be used for speculatively testing
444 // edits. Returns roads changed, turns deleted, turns added, intersections modified. Doesn't
445 // update pathfinding yet.
apply_edits( &mut self, mut new_edits: MapEdits, enforce_valid: bool, timer: &mut Timer, ) -> ( BTreeSet<RoadID>, BTreeSet<TurnID>, BTreeSet<TurnID>, BTreeSet<IntersectionID>, )446 fn apply_edits(
447 &mut self,
448 mut new_edits: MapEdits,
449 enforce_valid: bool,
450 timer: &mut Timer,
451 ) -> (
452 BTreeSet<RoadID>,
453 BTreeSet<TurnID>,
454 BTreeSet<TurnID>,
455 BTreeSet<IntersectionID>,
456 ) {
457 let mut effects = EditEffects::new();
458
459 // We need to undo() all of the current commands in reverse order, then apply() all of the
460 // new commands. But in many cases, new_edits is just the current edits with a few commands
461 // at the end. So a simple optimization with equivalent behavior is to skip the common
462 // prefix of commands.
463 let mut start_at_idx = 0;
464 for (cmd1, cmd2) in self.edits.commands.iter().zip(new_edits.commands.iter()) {
465 if cmd1 == cmd2 {
466 start_at_idx += 1;
467 } else {
468 break;
469 }
470 }
471
472 // Undo existing edits
473 for _ in start_at_idx..self.edits.commands.len() {
474 self.edits
475 .commands
476 .pop()
477 .unwrap()
478 .undo()
479 .apply(&mut effects, self, timer);
480 }
481
482 // Apply new edits.
483 for cmd in &new_edits.commands[start_at_idx..] {
484 cmd.apply(&mut effects, self, timer);
485 }
486
487 // Might need to update bus stops.
488 if enforce_valid {
489 for id in &effects.changed_roads {
490 let stops = self.get_r(*id).all_bus_stops(self);
491 for s in stops {
492 let sidewalk_pos = self.get_bs(s).sidewalk_pos;
493 // Must exist, because we aren't allowed to orphan a bus stop.
494 let driving_lane = self
495 .get_r(*id)
496 .find_closest_lane(
497 sidewalk_pos.lane(),
498 |l| PathConstraints::Bus.can_use(l, self),
499 self,
500 )
501 .unwrap();
502 let driving_pos = sidewalk_pos.equiv_pos(driving_lane, self);
503 self.bus_stops.get_mut(&s).unwrap().driving_pos = driving_pos;
504 }
505 }
506 }
507
508 if !effects.changed_roads.is_empty() {
509 self.zones = Zone::make_all(self);
510 }
511
512 new_edits.update_derived(self);
513 self.edits = new_edits;
514 self.pathfinder_dirty = true;
515 (
516 // TODO We just care about contraflow roads here
517 effects.changed_roads,
518 effects.deleted_turns,
519 // Some of these might've been added, then later deleted.
520 effects
521 .added_turns
522 .into_iter()
523 .filter(|t| self.turns.contains_key(t))
524 .collect(),
525 effects.changed_intersections,
526 )
527 }
528
recalculate_pathfinding_after_edits(&mut self, timer: &mut Timer)529 pub fn recalculate_pathfinding_after_edits(&mut self, timer: &mut Timer) {
530 if !self.pathfinder_dirty {
531 return;
532 }
533
534 let mut pathfinder = std::mem::replace(&mut self.pathfinder, Pathfinder::Dijkstra);
535 pathfinder.apply_edits(self, timer);
536 self.pathfinder = pathfinder;
537
538 // Also recompute blackholes. This is cheap enough to do from scratch.
539 timer.start("recompute blackholes");
540 for l in self.lanes.iter_mut() {
541 l.driving_blackhole = false;
542 l.biking_blackhole = false;
543 }
544 for l in connectivity::find_scc(self, PathConstraints::Car).1 {
545 self.lanes[l.0].driving_blackhole = true;
546 }
547 for l in connectivity::find_scc(self, PathConstraints::Bike).1 {
548 self.lanes[l.0].biking_blackhole = true;
549 }
550 timer.stop("recompute blackholes");
551
552 self.pathfinder_dirty = false;
553 }
554
555 // Since the player is in the middle of editing, the signal may not be valid. Don't go through
556 // the entire apply_edits flow.
incremental_edit_traffic_signal(&mut self, signal: ControlTrafficSignal)557 pub fn incremental_edit_traffic_signal(&mut self, signal: ControlTrafficSignal) {
558 assert_eq!(
559 self.get_i(signal.id).intersection_type,
560 IntersectionType::TrafficSignal
561 );
562 self.traffic_signals.insert(signal.id, signal);
563 }
564 }
565