game/debug/
blocked_by.rs

1use std::collections::{BTreeMap, HashSet};
2
3use abstutil::Counter;
4use geom::{ArrowCap, Circle, Distance, Duration, PolyLine, Polygon, Pt2D};
5use sim::{AgentID, DelayCause};
6use widgetry::tools::PopupMsg;
7use widgetry::{
8    Cached, Color, Drawable, EventCtx, GeomBatch, GfxCtx, HorizontalAlignment, Line, Outcome,
9    Panel, State, Text, TextExt, VerticalAlignment, Widget,
10};
11
12use crate::app::App;
13use crate::app::Transition;
14use crate::common::{warp_to_id, CommonState};
15
16/// Visualize the graph of what agents are blocked by others.
17pub struct Viewer {
18    panel: Panel,
19    graph: BTreeMap<AgentID, (Duration, DelayCause)>,
20    agent_positions: BTreeMap<AgentID, Pt2D>,
21    arrows: Drawable,
22
23    root_cause: Cached<AgentID, (Drawable, Text)>,
24}
25
26impl Viewer {
27    pub fn new_state(ctx: &mut EventCtx, app: &App) -> Box<dyn State<App>> {
28        let mut viewer = Viewer {
29            graph: app.primary.sim.get_blocked_by_graph(&app.primary.map),
30            agent_positions: app
31                .primary
32                .sim
33                .get_unzoomed_agents(&app.primary.map)
34                .into_iter()
35                .map(|a| (a.id, a.pos))
36                .collect(),
37            arrows: Drawable::empty(ctx),
38            panel: Panel::new_builder(Widget::col(vec![
39                Widget::row(vec![
40                    Line("What agents are blocked by others?")
41                        .small_heading()
42                        .into_widget(ctx),
43                    ctx.style().btn_close_widget(ctx),
44                ]),
45                Text::from("Root causes")
46                    .into_widget(ctx)
47                    .named("root causes"),
48            ]))
49            .aligned(HorizontalAlignment::Center, VerticalAlignment::Top)
50            .build(ctx),
51
52            root_cause: Cached::new(),
53        };
54
55        let mut arrows = GeomBatch::new();
56        for id in viewer.agent_positions.keys() {
57            if let Some((arrow, color)) = viewer.arrow_for(app, *id) {
58                arrows.push(color.alpha(0.5), arrow);
59            }
60        }
61        let (batch, col) = viewer.find_worst_problems(ctx, app);
62        arrows.append(batch);
63        viewer.panel.replace(ctx, "root causes", col);
64
65        viewer.arrows = ctx.upload(arrows);
66        Box::new(viewer)
67    }
68
69    fn arrow_for(&self, app: &App, id: AgentID) -> Option<(Polygon, Color)> {
70        let (_, cause) = self.graph.get(&id)?;
71        let (to, color) = match cause {
72            DelayCause::Agent(a) => {
73                if let Some(pos) = self.agent_positions.get(a) {
74                    (*pos, Color::RED)
75                } else {
76                    warn!("{} blocked by {}, but they're gone?", id, a);
77                    return None;
78                }
79            }
80            DelayCause::Intersection(i) => {
81                (app.primary.map.get_i(*i).polygon.center(), Color::BLUE)
82            }
83        };
84        let arrow = PolyLine::must_new(vec![self.agent_positions[&id], to])
85            .make_arrow(Distance::meters(0.5), ArrowCap::Triangle);
86        Some((arrow, color))
87    }
88
89    /// Figure out why some agent is blocked. Draws an arrow for each hop in the dependency chain,
90    /// and gives a description of the root cause.
91    fn trace_root_cause(&self, app: &App, start: AgentID) -> (GeomBatch, String) {
92        let mut batch = GeomBatch::new();
93        let mut seen: HashSet<AgentID> = HashSet::new();
94
95        let mut current = start;
96        let reason;
97        loop {
98            if seen.contains(&current) {
99                reason = format!("cycle involving {}", current);
100                break;
101            }
102            seen.insert(current);
103            if let Some((arrow, _)) = self.arrow_for(app, current) {
104                batch.push(Color::CYAN, arrow);
105            }
106            match self.graph.get(&current) {
107                Some((_, DelayCause::Agent(a))) => {
108                    current = *a;
109                }
110                Some((_, DelayCause::Intersection(i))) => {
111                    reason = i.to_string();
112                    break;
113                }
114                None => {
115                    reason = current.to_string();
116                    break;
117                }
118            }
119        }
120        (batch, reason)
121    }
122
123    /// Trace the root cause for everyone, find the most common sources, highlight them, and
124    /// describe them.
125    fn find_worst_problems(&self, ctx: &EventCtx, app: &App) -> (GeomBatch, Widget) {
126        let mut problems: Counter<DelayCause> = Counter::new();
127        for start in self.graph.keys() {
128            problems.inc(self.simple_root_cause(*start));
129        }
130
131        let mut batch = GeomBatch::new();
132        let mut col = vec!["Root causes".text_widget(ctx)];
133        for (cause, cnt) in problems.highest_n(3) {
134            let pt = match cause {
135                DelayCause::Agent(a) => {
136                    let warp_id = match a {
137                        AgentID::Car(c) => format!("c{}", c.id),
138                        AgentID::Pedestrian(p) => format!("p{}", p.0),
139                        // There's always that ONE passenger lugging some inappropriate amount of
140                        // furniture, somehow causing gridlock, right?
141                        AgentID::BusPassenger(_, c) => format!("c{}", c.id),
142                    };
143                    col.push(
144                        ctx.style()
145                            .btn_plain
146                            .icon("system/assets/tools/location.svg")
147                            .label_text(format!("{} is blocking {} agents", a, cnt))
148                            .build_widget(ctx, warp_id),
149                    );
150
151                    if let Some(pt) = self.agent_positions.get(&a) {
152                        *pt
153                    } else {
154                        continue;
155                    }
156                }
157                DelayCause::Intersection(i) => {
158                    col.push(
159                        ctx.style()
160                            .btn_plain
161                            .icon("system/assets/tools/location.svg")
162                            .label_text(format!("{} is blocking {} agents", i, cnt))
163                            .build_widget(ctx, format!("i{}", i.0)),
164                    );
165
166                    app.primary.map.get_i(i).polygon.center()
167                }
168            };
169            batch.push(
170                Color::YELLOW,
171                Circle::new(pt, Distance::meters(5.0))
172                    .to_outline(Distance::meters(1.0))
173                    .unwrap(),
174            );
175        }
176
177        (batch, Widget::col(col))
178    }
179
180    fn simple_root_cause(&self, start: AgentID) -> DelayCause {
181        let mut seen: HashSet<AgentID> = HashSet::new();
182
183        let mut current = start;
184        loop {
185            if seen.contains(&current) {
186                return DelayCause::Agent(current);
187            }
188            seen.insert(current);
189            match self.graph.get(&current) {
190                Some((_, DelayCause::Agent(a))) => {
191                    current = *a;
192                }
193                Some((_, DelayCause::Intersection(i))) => {
194                    return DelayCause::Intersection(*i);
195                }
196                None => {
197                    return DelayCause::Agent(current);
198                }
199            }
200        }
201    }
202}
203
204impl State<App> for Viewer {
205    fn event(&mut self, ctx: &mut EventCtx, app: &mut App) -> Transition {
206        ctx.canvas_movement();
207        if ctx.redo_mouseover() {
208            app.recalculate_current_selection(ctx);
209
210            // TODO Awkward dances around the borrow checker. Maybe make a method in Cached if we
211            // need to do this frequently.
212            let mut root_cause = std::mem::replace(&mut self.root_cause, Cached::new());
213            root_cause.update(
214                app.primary
215                    .current_selection
216                    .as_ref()
217                    .and_then(|id| id.agent_id()),
218                |agent| {
219                    if let Some((delay, _)) = self.graph.get(&agent) {
220                        let (batch, problem) = self.trace_root_cause(app, agent);
221                        let txt = Text::from_multiline(vec![
222                            Line(format!("Waiting {}", delay)),
223                            Line(problem),
224                        ]);
225                        (ctx.upload(batch), txt)
226                    } else {
227                        (Drawable::empty(ctx), Text::new())
228                    }
229                },
230            );
231            self.root_cause = root_cause;
232        }
233
234        if let Outcome::Clicked(x) = self.panel.event(ctx) {
235            match x.as_ref() {
236                "close" => {
237                    return Transition::Pop;
238                }
239                x => {
240                    // warp_to_id always replaces the current state, so insert a dummy one for it
241                    // to clobber
242                    return Transition::Multi(vec![
243                        Transition::Push(PopupMsg::new_state(ctx, "Warping", vec![""])),
244                        warp_to_id(ctx, app, x),
245                    ]);
246                }
247            }
248        }
249
250        Transition::Keep
251    }
252
253    fn draw(&self, g: &mut GfxCtx, app: &App) {
254        self.panel.draw(g);
255        CommonState::draw_osd(g, app);
256        g.redraw(&self.arrows);
257
258        if let Some((draw, txt)) = self.root_cause.value() {
259            g.redraw(draw);
260            if !txt.is_empty() {
261                g.draw_mouse_tooltip(txt.clone());
262            }
263        }
264    }
265}