game/debug/
blockfinder.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use abstutil::Timer;
4use blockfinding::{Block, Perimeter};
5use geom::Distance;
6use map_model::osm::RoadRank;
7use widgetry::mapspace::{ObjectID, World, WorldOutcome};
8use widgetry::{
9    Color, Drawable, EventCtx, GeomBatch, GfxCtx, HorizontalAlignment, Key, Line, Outcome, Panel,
10    SimpleState, State, Text, TextExt, VerticalAlignment, Widget,
11};
12
13use crate::app::{App, Transition};
14use crate::debug::polygons;
15
16const COLORS: [Color; 6] = [
17    Color::BLUE,
18    Color::YELLOW,
19    Color::GREEN,
20    Color::PURPLE,
21    Color::PINK,
22    Color::ORANGE,
23];
24const MODIFIED: Color = Color::RED;
25const TO_MERGE: Color = Color::CYAN;
26
27pub struct Blockfinder {
28    panel: Panel,
29    id_counter: usize,
30    blocks: BTreeMap<Obj, Block>,
31    world: World<Obj>,
32    to_merge: BTreeSet<Obj>,
33
34    // Since we can't easily color adjacent groups of blocks differently when we classify but don't
35    // merge, just remember the groups here
36    partitions: Vec<Vec<Obj>>,
37}
38
39#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
40struct Obj(usize);
41impl ObjectID for Obj {}
42
43impl Blockfinder {
44    pub fn new_state(ctx: &mut EventCtx, app: &App) -> Box<dyn State<App>> {
45        let mut state = Blockfinder {
46            panel: make_panel(ctx),
47            id_counter: 0,
48            blocks: BTreeMap::new(),
49            world: World::new(),
50            to_merge: BTreeSet::new(),
51
52            partitions: Vec::new(),
53        };
54
55        ctx.loading_screen("calculate all blocks", |ctx, timer| {
56            timer.start("find single blocks");
57            let perimeters = Perimeter::find_all_single_blocks(&app.primary.map);
58            timer.stop("find single blocks");
59            state.add_blocks_with_coloring(ctx, app, perimeters, timer);
60        });
61        state.world.initialize_hover(ctx);
62        Box::new(state)
63    }
64
65    fn new_id(&mut self) -> Obj {
66        let id = Obj(self.id_counter);
67        self.id_counter += 1;
68        id
69    }
70
71    fn add_block(&mut self, ctx: &mut EventCtx, app: &App, id: Obj, color: Color, block: Block) {
72        // Label the order of the perimeter roads while hovering
73        let mut hovered = GeomBatch::from(vec![(color.alpha(0.5), block.polygon.clone())]);
74        hovered.push(
75            Color::BLACK,
76            block.polygon.to_outline(Distance::meters(5.0)),
77        );
78        for (idx, id) in block.perimeter.roads.iter().enumerate().skip(1) {
79            hovered.append(
80                Text::from(Line(format!("{}", idx)).fg(Color::RED))
81                    .bg(Color::BLACK)
82                    .render_autocropped(ctx)
83                    .scale(1.0)
84                    .centered_on(
85                        id.get_outermost_lane(&app.primary.map)
86                            .lane_center_pts
87                            .middle(),
88                    ),
89            );
90        }
91
92        let mut obj = self
93            .world
94            .add(id)
95            .hitbox(block.polygon.clone())
96            .draw_color(color.alpha(0.5))
97            .draw_hovered(hovered)
98            .clickable();
99        if self.to_merge.contains(&id) {
100            obj = obj.hotkey(Key::Space, "remove from merge set")
101        } else {
102            obj = obj.hotkey(Key::Space, "add to merge set")
103        }
104        obj.build(ctx);
105        self.blocks.insert(id, block);
106    }
107
108    fn add_blocks_with_coloring(
109        &mut self,
110        ctx: &mut EventCtx,
111        app: &App,
112        perimeters: Vec<Perimeter>,
113        timer: &mut Timer,
114    ) {
115        let mut colors = Perimeter::calculate_coloring(&perimeters, COLORS.len())
116            .unwrap_or_else(|| (0..perimeters.len()).collect());
117
118        timer.start_iter("blockify", perimeters.len());
119        let mut blocks = Vec::new();
120        for perimeter in perimeters {
121            timer.next();
122
123            // TODO Match the LTN partitioning and strip out blocks that break after collapsing
124            // deadends. See https://github.com/a-b-street/abstreet/issues/841.
125            let mut copy = perimeter.clone();
126            copy.collapse_deadends();
127            if let Err(err) = copy.to_block(&app.primary.map) {
128                error!(
129                    "A perimeter won't blockify after collapsing deadends: {}",
130                    err
131                );
132                continue;
133            }
134
135            match perimeter.to_block(&app.primary.map) {
136                Ok(block) => {
137                    blocks.push(block);
138                }
139                Err(err) => {
140                    warn!("Failed to make a block from a perimeter: {}", err);
141                    // We assigned a color, so don't let the indices get out of sync!
142                    colors.remove(blocks.len());
143                }
144            }
145        }
146
147        for (block, color_idx) in blocks.into_iter().zip(colors.into_iter()) {
148            let id = self.new_id();
149            self.add_block(ctx, app, id, COLORS[color_idx % COLORS.len()], block);
150        }
151    }
152}
153
154impl State<App> for Blockfinder {
155    fn event(&mut self, ctx: &mut EventCtx, app: &mut App) -> Transition {
156        if let Outcome::Clicked(x) = self.panel.event(ctx) {
157            match x.as_ref() {
158                "close" => {
159                    return Transition::Pop;
160                }
161                "Merge" => {
162                    // TODO We could update the panel, but meh
163                    let mut perimeters = Vec::new();
164                    for id in std::mem::take(&mut self.to_merge) {
165                        perimeters.push(self.blocks.remove(&id).unwrap().perimeter);
166                        // TODO If we happen to be hovering on one, uh oh! It's going to change
167                        // ID...
168                        self.world.delete(id);
169                    }
170                    let stepwise_debug = true;
171                    let results =
172                        Perimeter::merge_all(&app.primary.map, perimeters, stepwise_debug);
173                    let debug = results.len() > 1;
174                    for perimeter in results {
175                        let id = self.new_id();
176                        let block = perimeter
177                            .to_block(&app.primary.map)
178                            .expect("Merged perimeter broke the polygon");
179                        // To make the one-merge-at-a-time debugging easier, keep these in the
180                        // merge set
181                        if debug {
182                            self.to_merge.insert(id);
183                            self.add_block(ctx, app, id, TO_MERGE, block);
184                        } else {
185                            self.add_block(ctx, app, id, MODIFIED, block);
186                        }
187                    }
188                    return Transition::Keep;
189                }
190                "Collapse dead-ends" => {
191                    for id in std::mem::take(&mut self.to_merge) {
192                        let mut perimeter = self.blocks.remove(&id).unwrap().perimeter;
193                        perimeter.collapse_deadends();
194                        let block = perimeter
195                            .to_block(&app.primary.map)
196                            .expect("collapsing deadends broke the polygon shape");
197                        self.world.delete_before_replacement(id);
198                        // We'll lose the original coloring, oh well
199                        self.add_block(ctx, app, id, MODIFIED, block);
200                    }
201                }
202                "Classify neighborhoods (but don't merge)" | "Auto-merge all neighborhoods" => {
203                    let perimeters: Vec<Perimeter> = std::mem::take(&mut self.blocks)
204                        .into_iter()
205                        .map(|(_, b)| b.perimeter)
206                        .collect();
207                    let map = &app.primary.map;
208                    let partitions = Perimeter::partition_by_predicate(perimeters, |r| {
209                        // "Interior" roads of a neighborhood aren't classified as arterial
210                        let road = map.get_r(r);
211                        road.get_rank() == RoadRank::Local
212                    });
213
214                    // Reset pretty much all of our state
215                    self.id_counter = 0;
216                    self.world = World::new();
217                    self.to_merge.clear();
218                    self.partitions = Vec::new();
219
220                    if x == "Auto-merge all neighborhoods" {
221                        // Actually merge the partitions
222                        let mut merged = Vec::new();
223                        for perimeters in partitions {
224                            // If we got more than one result back, merging partially failed. Oh
225                            // well?
226                            let stepwise_debug = false;
227                            merged.extend(Perimeter::merge_all(
228                                &app.primary.map,
229                                perimeters,
230                                stepwise_debug,
231                            ));
232                        }
233                        self.add_blocks_with_coloring(ctx, app, merged, &mut Timer::throwaway());
234                    } else {
235                        // Until we can actually do the merge, just color the partition to show
236                        // results. The coloring is half-useless; adjacent partitions might be the
237                        // same.
238                        for (color_idx, perimeters) in partitions.into_iter().enumerate() {
239                            let color = COLORS[color_idx % COLORS.len()];
240                            let mut group = Vec::new();
241                            for perimeter in perimeters {
242                                if let Ok(block) = perimeter.to_block(map) {
243                                    let id = self.new_id();
244                                    self.add_block(ctx, app, id, color, block);
245                                    group.push(id);
246                                }
247                            }
248                            self.partitions.push(group);
249                        }
250                    }
251                }
252                "Merge all holes" => {
253                    let perimeters: Vec<Perimeter> = std::mem::take(&mut self.blocks)
254                        .into_iter()
255                        .map(|(_, b)| b.perimeter)
256                        .collect();
257                    let perimeters = Perimeter::merge_holes(&app.primary.map, perimeters);
258
259                    // Reset pretty much all of our state
260                    self.id_counter = 0;
261                    self.world = World::new();
262                    self.to_merge.clear();
263                    self.partitions = Vec::new();
264
265                    self.add_blocks_with_coloring(ctx, app, perimeters, &mut Timer::throwaway());
266                }
267                "Reset" => {
268                    return Transition::Replace(Blockfinder::new_state(ctx, app));
269                }
270                _ => unreachable!(),
271            }
272        }
273
274        match self.world.event(ctx) {
275            WorldOutcome::Keypress("add to merge set", id) => {
276                self.to_merge.insert(id);
277                let block = self.blocks.remove(&id).unwrap();
278                self.world.delete_before_replacement(id);
279                self.add_block(ctx, app, id, TO_MERGE, block);
280            }
281            WorldOutcome::Keypress("remove from merge set", id) => {
282                self.to_merge.remove(&id);
283                let block = self.blocks.remove(&id).unwrap();
284                self.world.delete_before_replacement(id);
285                // We'll lose the original coloring, oh well
286                self.add_block(ctx, app, id, MODIFIED, block);
287            }
288            WorldOutcome::ClickedObject(id) => {
289                return Transition::Push(OneBlock::new_state(ctx, app, self.blocks[&id].clone()));
290            }
291            _ => {}
292        }
293
294        if ctx.redo_mouseover() {
295            if ctx.is_key_down(Key::LeftControl) {
296                if let Some(id) = self.world.get_hovering() {
297                    if !self.to_merge.contains(&id) {
298                        self.to_merge.insert(id);
299                        let block = self.blocks.remove(&id).unwrap();
300                        self.world.delete_before_replacement(id);
301                        self.add_block(ctx, app, id, TO_MERGE, block);
302                    }
303                }
304            }
305        }
306
307        Transition::Keep
308    }
309
310    fn draw(&self, g: &mut GfxCtx, _: &App) {
311        self.world.draw(g);
312        self.panel.draw(g);
313
314        // If we've partitioned by neighborhood but not merged, show the grouping when hovering
315        if let Some(id) = self.world.get_hovering() {
316            let mut batch = GeomBatch::new();
317            for group in &self.partitions {
318                if group.contains(&id) {
319                    for block in group {
320                        // Some of the block IDs will vanish if we start merging pieces based on
321                        // the partitioning
322                        if let Some(block) = self.blocks.get(block) {
323                            batch.push(Color::RED.alpha(0.5), block.polygon.clone());
324                        }
325                    }
326                    break;
327                }
328            }
329            batch.draw(g);
330        }
331    }
332}
333
334pub struct OneBlock {
335    block: Block,
336    draw: Drawable,
337}
338
339impl OneBlock {
340    pub fn new_state(ctx: &mut EventCtx, app: &App, block: Block) -> Box<dyn State<App>> {
341        let mut batch = GeomBatch::new();
342        batch.push(Color::RED.alpha(0.5), block.polygon.clone());
343        for r in &block.perimeter.interior {
344            batch.push(
345                Color::CYAN.alpha(0.5),
346                app.primary.map.get_r(*r).get_thick_polygon(),
347            );
348        }
349
350        let panel = Panel::new_builder(Widget::col(vec![
351            Widget::row(vec![
352                Line("Blockfinder").small_heading().into_widget(ctx),
353                ctx.style().btn_close_widget(ctx),
354            ]),
355            "You can also hold LCtrl to quickly highlight".text_widget(ctx),
356            ctx.style()
357                .btn_outline
358                .text("Show perimeter in order")
359                .hotkey(Key::O)
360                .build_def(ctx),
361            ctx.style()
362                .btn_outline
363                .text("Debug polygon by points")
364                .hotkey(Key::D)
365                .build_def(ctx),
366            ctx.style()
367                .btn_outline
368                .text("Debug polygon by triangles")
369                .build_def(ctx),
370        ]))
371        .aligned(HorizontalAlignment::Center, VerticalAlignment::Top)
372        .build(ctx);
373        <dyn SimpleState<_>>::new_state(
374            panel,
375            Box::new(OneBlock {
376                block,
377                draw: batch.upload(ctx),
378            }),
379        )
380    }
381}
382
383impl SimpleState<App> for OneBlock {
384    fn on_click(
385        &mut self,
386        ctx: &mut EventCtx,
387        app: &mut App,
388        x: &str,
389        _: &mut Panel,
390    ) -> Transition {
391        match x {
392            "close" => Transition::Pop,
393            "Show perimeter in order" => {
394                let mut items = Vec::new();
395                let map = &app.primary.map;
396                for road_side in &self.block.perimeter.roads {
397                    let lane = road_side.get_outermost_lane(map);
398                    items.push(polygons::Item::Polygon(lane.get_thick_polygon()));
399                }
400                return Transition::Push(polygons::PolygonDebugger::new_state(
401                    ctx,
402                    "side of road",
403                    items,
404                    None,
405                ));
406            }
407            "Debug polygon by points" => {
408                return Transition::Push(polygons::PolygonDebugger::new_state(
409                    ctx,
410                    "pt",
411                    self.block
412                        .polygon
413                        .get_outer_ring()
414                        .clone()
415                        .into_points()
416                        .into_iter()
417                        .map(polygons::Item::Point)
418                        .collect(),
419                    None,
420                ));
421            }
422            "Debug polygon by triangles" => {
423                return Transition::Push(polygons::PolygonDebugger::new_state(
424                    ctx,
425                    "pt",
426                    self.block
427                        .polygon
428                        .triangles()
429                        .into_iter()
430                        .map(polygons::Item::Triangle)
431                        .collect(),
432                    None,
433                ));
434            }
435            _ => unreachable!(),
436        }
437    }
438
439    fn other_event(&mut self, ctx: &mut EventCtx, _: &mut App) -> Transition {
440        ctx.canvas_movement();
441        Transition::Keep
442    }
443
444    fn draw(&self, g: &mut GfxCtx, _: &App) {
445        g.redraw(&self.draw);
446    }
447}
448
449fn make_panel(ctx: &mut EventCtx) -> Panel {
450    Panel::new_builder(Widget::col(vec![
451        Widget::row(vec![
452            Line("Blockfinder").small_heading().into_widget(ctx),
453            ctx.style().btn_close_widget(ctx),
454        ]),
455        "Click a block to examine.".text_widget(ctx),
456        "Press space to mark/unmark for merging".text_widget(ctx),
457        ctx.style()
458            .btn_outline
459            .text("Merge")
460            .hotkey(Key::M)
461            .build_def(ctx),
462        ctx.style()
463            .btn_outline
464            .text("Collapse dead-ends")
465            .hotkey(Key::D)
466            .build_def(ctx),
467        ctx.style()
468            .btn_outline
469            .text("Classify neighborhoods (but don't merge)")
470            .hotkey(Key::C)
471            .build_def(ctx),
472        ctx.style()
473            .btn_outline
474            .text("Auto-merge all neighborhoods")
475            .hotkey(Key::A)
476            .build_def(ctx),
477        ctx.style()
478            .btn_outline
479            .text("Merge all holes")
480            .hotkey(Key::H)
481            .build_def(ctx),
482        ctx.style()
483            .btn_solid_destructive
484            .text("Reset")
485            .hotkey(Key::R)
486            .build_def(ctx),
487    ]))
488    .aligned(HorizontalAlignment::Left, VerticalAlignment::Top)
489    .build(ctx)
490}