ltn/logic/
auto_filters.rs

1//! Experiments to make a neighbourhood be low-traffic by automatically placing filters to prevent
2//! all shortcuts.
3
4use anyhow::Result;
5
6use abstutil::Timer;
7use map_model::RoadFilter;
8use map_model::RoadID;
9use widgetry::{Choice, EventCtx};
10
11use crate::{redraw_all_icons, App, Neighbourhood};
12
13#[derive(Clone, Copy, Debug, PartialEq)]
14pub enum AutoFilterHeuristic {
15    /// Find the road with the most shortcuts that can be closed without creating a disconnected
16    /// cell, and filter it.
17    ///
18    /// There's a vague intuition or observation that the "bottleneck" will have the most shortcuts
19    /// going through it, so tackle the worst problem first.
20    Greedy,
21    /// Try adding one filter to every possible road, counting the shortcuts after. Choose the next
22    /// step by the least resulting shortcuts.
23    BruteForce,
24    /// Find one filter that splits a cell, maximizing the number of streets in each new cell.
25    SplitCells,
26    /// Per cell, close all borders except for one. This doesn't affect connectivity, but prevents
27    /// all shortcuts.
28    OnlyOneBorder,
29}
30
31impl AutoFilterHeuristic {
32    pub fn choices() -> Vec<Choice<Self>> {
33        vec![
34            Choice::new(
35                "filter the road with the most shortcuts (greedy)",
36                AutoFilterHeuristic::Greedy,
37            ),
38            Choice::new(
39                "stop the most shortcuts (brute-force)",
40                AutoFilterHeuristic::BruteForce,
41            ),
42            Choice::new("split large cells", AutoFilterHeuristic::SplitCells),
43            Choice::new(
44                "only one entrance per cell",
45                AutoFilterHeuristic::OnlyOneBorder,
46            ),
47        ]
48    }
49
50    pub fn apply(
51        self,
52        ctx: &mut EventCtx,
53        app: &mut App,
54        neighbourhood: &Neighbourhood,
55        timer: &mut Timer,
56    ) -> Result<()> {
57        if neighbourhood
58            .cells
59            .iter()
60            .filter(|c| c.is_disconnected())
61            .count()
62            != 0
63        {
64            bail!("This neighbourhood has a disconnected cell; fix that first");
65        }
66
67        // TODO If we already have no shortcuts, stop
68
69        match self {
70            AutoFilterHeuristic::Greedy => greedy(app, neighbourhood),
71            AutoFilterHeuristic::BruteForce => brute_force(app, neighbourhood, timer),
72            AutoFilterHeuristic::SplitCells => split_cells(app, neighbourhood, timer),
73            AutoFilterHeuristic::OnlyOneBorder => only_one_border(app, neighbourhood),
74        }
75
76        // TODO Detect if we changed anything
77        let empty = false;
78        redraw_all_icons(ctx, app);
79        if empty {
80            bail!("No new filters created");
81        } else {
82            Ok(())
83        }
84    }
85}
86
87fn greedy(app: &mut App, neighbourhood: &Neighbourhood) {
88    // TODO How should we break ties? Some shortcuts are worse than others; use that weight?
89    // TODO Should this operation be per cell instead? We could hover on a road belonging to that
90    // cell to select it
91    if let Some((r, _)) = neighbourhood
92        .shortcuts
93        .count_per_road
94        .borrow()
95        .iter()
96        .max_by_key(|pair| pair.1)
97    {
98        if try_to_filter_road(app, neighbourhood, *r).is_none() {
99            warn!("Filtering {} disconnects a cell, never mind", r);
100            // TODO Try the next choice
101        }
102    }
103}
104
105fn brute_force(app: &mut App, neighbourhood: &Neighbourhood, timer: &mut Timer) {
106    // Which road leads to the fewest shortcuts?
107    let mut best: Option<(RoadID, usize)> = None;
108
109    let orig_filters = app.per_map.map.all_roads_with_modal_filter().count();
110    timer.start_iter(
111        "evaluate candidate filters",
112        neighbourhood.interior_roads.len(),
113    );
114    for r in &neighbourhood.interior_roads {
115        timer.next();
116        if app.per_map.map.get_r(*r).modal_filter.is_some() {
117            continue;
118        }
119        if let Some(new) = try_to_filter_road(app, neighbourhood, *r) {
120            let num_shortcuts = new.shortcuts.paths.len();
121            // TODO Again, break ties. Just the number of paths is kind of a weak metric.
122            if best.map(|(_, score)| num_shortcuts < score).unwrap_or(true) {
123                best = Some((*r, num_shortcuts));
124            }
125            // Always undo the new filter between each test
126            remove_filter(app, *r);
127        }
128
129        assert_eq!(
130            orig_filters,
131            app.per_map.map.all_roads_with_modal_filter().count()
132        );
133    }
134
135    if let Some((r, _)) = best {
136        try_to_filter_road(app, neighbourhood, r).unwrap();
137    }
138}
139
140fn split_cells(app: &mut App, neighbourhood: &Neighbourhood, timer: &mut Timer) {
141    // Filtering which road leads to new cells with the MOST streets in the smaller cell?
142    let mut best: Option<(RoadID, usize)> = None;
143
144    let orig_filters = app.per_map.map.all_roads_with_modal_filter().count();
145    timer.start_iter(
146        "evaluate candidate filters",
147        neighbourhood.interior_roads.len(),
148    );
149    for r in &neighbourhood.interior_roads {
150        timer.next();
151        if app.per_map.map.get_r(*r).modal_filter.is_some() {
152            continue;
153        }
154        if let Some(new) = try_to_filter_road(app, neighbourhood, *r) {
155            // Did we split the cell?
156            if new.cells.len() > neighbourhood.cells.len() {
157                // Find the two new cells
158                let split_cells: Vec<_> = new
159                    .cells
160                    .iter()
161                    .filter(|cell| cell.roads.contains_key(r))
162                    .collect();
163                if split_cells.len() == 2 {
164                    // We want cells to be roughly evenly-sized. Just count the number of road
165                    // segments as a proxy for that.
166                    let new_score = split_cells[0].roads.len().min(split_cells[1].roads.len());
167                    if best
168                        .map(|(_, old_score)| new_score > old_score)
169                        .unwrap_or(true)
170                    {
171                        best = Some((*r, new_score));
172                    }
173                } else {
174                    // Happens for example at https://www.openstreetmap.org/way/514353312, a
175                    // dead-end and private road
176                    warn!("The split cell heuristic wound up with an unexpected number of cells after trying to split {r}; skipping");
177                }
178            }
179            // Always undo the new filter between each test
180            remove_filter(app, *r);
181        }
182
183        assert_eq!(
184            orig_filters,
185            app.per_map.map.all_roads_with_modal_filter().count()
186        );
187    }
188
189    if let Some((r, _)) = best {
190        try_to_filter_road(app, neighbourhood, r).unwrap();
191    }
192}
193
194fn only_one_border(app: &mut App, neighbourhood: &Neighbourhood) {
195    for cell in &neighbourhood.cells {
196        if cell.borders.len() > 1 {
197            // TODO How to pick which one to leave open?
198            for i in cell.borders.iter().skip(1) {
199                // Find the road in this cell connected to this border
200                for r in cell.roads.keys() {
201                    let road = app.per_map.map.get_r(*r);
202                    if road.src_i == *i {
203                        add_filter(app, *r, 0.1);
204                        break;
205                    } else if road.dst_i == *i {
206                        add_filter(app, *r, 0.9);
207                        break;
208                    }
209                }
210            }
211        }
212    }
213}
214
215// If successful, returns a Neighbourhood and leaves the new filter in place. If it disconncts a
216// cell, reverts the change and returns None
217fn try_to_filter_road(
218    app: &mut App,
219    neighbourhood: &Neighbourhood,
220    r: RoadID,
221) -> Option<Neighbourhood> {
222    add_filter(app, r, 0.5);
223    let new_neighbourhood = Neighbourhood::new(app, neighbourhood.id);
224    if new_neighbourhood.cells.iter().any(|c| c.is_disconnected()) {
225        remove_filter(app, r);
226        None
227    } else {
228        Some(new_neighbourhood)
229    }
230}
231
232fn add_filter(app: &mut App, r: RoadID, pct: f64) {
233    let map = &app.per_map.map;
234    let mut edits = map.get_edits().clone();
235    let road = map.get_r(r);
236    edits.commands.push(map.edit_road_cmd(r, |new| {
237        new.modal_filter = Some(RoadFilter::new(
238            pct * road.length(),
239            app.session.filter_type,
240        ));
241    }));
242    app.apply_edits(edits);
243}
244
245fn remove_filter(app: &mut App, r: RoadID) {
246    let map = &app.per_map.map;
247    let mut edits = map.get_edits().clone();
248    edits.commands.push(map.edit_road_cmd(r, |new| {
249        new.modal_filter = None;
250    }));
251    app.apply_edits(edits);
252}
ltn/logic/auto_filters.rs

ltn/logic/
auto_filters.rs
