game/debug/
floodfill.rs

1use std::collections::HashSet;
2
3use map_gui::tools::ColorDiscrete;
4use map_model::{connectivity, LaneID, Map, PathConstraints};
5use widgetry::mapspace::ToggleZoomed;
6use widgetry::{
7    Choice, Color, EventCtx, GfxCtx, HorizontalAlignment, Line, Outcome, Panel, State, TextExt,
8    VerticalAlignment, Widget,
9};
10
11use crate::app::App;
12use crate::app::Transition;
13
14pub struct Floodfiller {
15    panel: Panel,
16    draw: ToggleZoomed,
17    source: Source,
18}
19
20impl Floodfiller {
21    pub fn floodfill(ctx: &mut EventCtx, app: &App, l: LaneID) -> Box<dyn State<App>> {
22        let constraints = PathConstraints::from_lt(app.primary.map.get_l(l).lane_type);
23        Floodfiller::new_state(ctx, app, Source::Floodfill(l), constraints)
24    }
25    pub fn scc(ctx: &mut EventCtx, app: &App, l: LaneID) -> Box<dyn State<App>> {
26        let constraints = PathConstraints::from_lt(app.primary.map.get_l(l).lane_type);
27        Floodfiller::new_state(ctx, app, Source::Scc, constraints)
28    }
29
30    fn new_state(
31        ctx: &mut EventCtx,
32        app: &App,
33        source: Source,
34        constraints: PathConstraints,
35    ) -> Box<dyn State<App>> {
36        let (reachable_lanes, unreachable_lanes, title) =
37            source.calculate(&app.primary.map, constraints);
38        let mut colorer = ColorDiscrete::new(
39            app,
40            vec![("unreachable", Color::RED), ("reachable", Color::GREEN)],
41        );
42        for l in reachable_lanes {
43            colorer.add_l(l, "reachable");
44        }
45        let num_unreachable = unreachable_lanes.len();
46        for l in unreachable_lanes {
47            colorer.add_l(l, "unreachable");
48        }
49
50        let (draw, legend) = colorer.build(ctx);
51        Box::new(Floodfiller {
52            panel: Panel::new_builder(Widget::col(vec![
53                Widget::row(vec![
54                    Line(title).small_heading().into_widget(ctx),
55                    ctx.style().btn_close_widget(ctx),
56                ]),
57                format!("{} unreachable lanes", num_unreachable).text_widget(ctx),
58                legend,
59                Widget::row(vec![
60                    "Connectivity type:".text_widget(ctx),
61                    Widget::dropdown(
62                        ctx,
63                        "constraints",
64                        constraints,
65                        PathConstraints::all()
66                            .into_iter()
67                            .map(|c| Choice::new(format!("{:?}", c), c))
68                            .collect(),
69                    ),
70                ]),
71            ]))
72            .aligned(HorizontalAlignment::Center, VerticalAlignment::Top)
73            .build(ctx),
74            draw,
75            source,
76        })
77    }
78}
79
80impl State<App> for Floodfiller {
81    fn event(&mut self, ctx: &mut EventCtx, app: &mut App) -> Transition {
82        if ctx.redo_mouseover() {
83            app.recalculate_current_selection(ctx);
84        }
85        ctx.canvas_movement();
86
87        match self.panel.event(ctx) {
88            Outcome::Clicked(x) => match x.as_ref() {
89                "close" => {
90                    return Transition::Pop;
91                }
92                _ => unreachable!(),
93            },
94            Outcome::Changed(_) => {
95                return Transition::Replace(Floodfiller::new_state(
96                    ctx,
97                    app,
98                    self.source.clone(),
99                    self.panel.dropdown_value("constraints"),
100                ));
101            }
102            _ => {}
103        }
104
105        Transition::Keep
106    }
107
108    fn draw(&self, g: &mut GfxCtx, _: &App) {
109        self.draw.draw(g);
110        self.panel.draw(g);
111    }
112}
113
114#[derive(Clone)]
115enum Source {
116    Floodfill(LaneID),
117    Scc,
118}
119
120impl Source {
121    // (reachable, unreachable, a title)
122    fn calculate(
123        &self,
124        map: &Map,
125        constraints: PathConstraints,
126    ) -> (HashSet<LaneID>, HashSet<LaneID>, String) {
127        match self {
128            Source::Floodfill(start) => {
129                let mut visited = HashSet::new();
130                let mut queue = vec![*start];
131                while !queue.is_empty() {
132                    let current = queue.pop().unwrap();
133                    if visited.contains(&current) {
134                        continue;
135                    }
136                    visited.insert(current);
137                    for (_, l) in map.get_next_turns_and_lanes_for(current, constraints) {
138                        if !visited.contains(&l.id) {
139                            queue.push(l.id);
140                        }
141                    }
142                }
143
144                let mut unreached = HashSet::new();
145                for l in map.all_lanes() {
146                    if constraints.can_use(l, map) && !visited.contains(&l.id) {
147                        unreached.insert(l.id);
148                    }
149                }
150
151                (visited, unreached, format!("Floodfill from {}", start))
152            }
153            Source::Scc => {
154                let (good, bad) = connectivity::find_scc(map, constraints);
155                (good, bad, "strongly-connected component".to_string())
156            }
157        }
158    }
159}