Try a min-cut inspired heuristic for filter placement. The results are
surprising (I didn't spot the bottleneck), but quite good!
@@ -18,6 +18,8 @@ pub enum Heuristic {
/// Try adding one filter to every possible road, counting the rat-runs after. Choose the next
/// step by the least resulting rat runs.
BruteForce,
+ /// Find one filter that splits a cell, maximizing the number of streets in each new cell.
+ SplitCells,
/// Per cell, close all borders except for one. This doesn't affect connectivity, but prevents
/// all rat-runs.
OnlyOneBorder,
@@ -28,6 +30,7 @@ impl Heuristic {
vec![
Choice::new("greedy", Heuristic::Greedy),
Choice::new("brute-force", Heuristic::BruteForce),
+ Choice::new("split cells", Heuristic::SplitCells),
Choice::new("only one border", Heuristic::OnlyOneBorder),
]
}
@@ -59,6 +62,7 @@ impl Heuristic {
match self {
Heuristic::Greedy => greedy(ctx, app, neighborhood, timer),
Heuristic::BruteForce => brute_force(ctx, app, neighborhood, timer),
+ Heuristic::SplitCells => split_cells(ctx, app, neighborhood, timer),
Heuristic::OnlyOneBorder => only_one_border(app, neighborhood),
}
@@ -121,6 +125,52 @@ fn brute_force(ctx: &EventCtx, app: &mut App, neighborhood: &Neighborhood, timer
}
}
+fn split_cells(ctx: &EventCtx, app: &mut App, neighborhood: &Neighborhood, timer: &mut Timer) {
+ // Filtering which road leads to new cells with the MOST streets in the smaller cell?
+ let mut best: Option<(RoadID, usize)> = None;
+
+ let orig_filters = app.session.modal_filters.roads.len();
+ timer.start_iter(
+ "evaluate candidate filters",
+ neighborhood.orig_perimeter.interior.len(),
+ );
+ for r in &neighborhood.orig_perimeter.interior {
+ timer.next();
+ if app.session.modal_filters.roads.contains_key(r) {
+ continue;
+ }
+ if let Some(new) = try_to_filter_road(ctx, app, neighborhood, *r) {
+ // Did we split the cell?
+ if new.cells.len() > neighborhood.cells.len() {
+ // Find the two new cells
+ let split_cells: Vec<_> = new
+ .cells
+ .iter()
+ .filter(|cell| cell.roads.contains_key(r))
+ .collect();
+ assert_eq!(2, split_cells.len());
+ // We want cells to be roughly evenly-sized. Just count the number of road segments
+ // as a proxy for that.
+ let new_score = split_cells[0].roads.len().min(split_cells[1].roads.len());
+ if best
+ .map(|(_, old_score)| new_score > old_score)
+ .unwrap_or(true)
+ {
+ best = Some((*r, new_score));
+ }
+ }
+ // Always undo the new filter between each test
+ app.session.modal_filters.roads.remove(r).unwrap();
+ }
+
+ assert_eq!(orig_filters, app.session.modal_filters.roads.len());
+ }
+
+ if let Some((r, _)) = best {
+ try_to_filter_road(ctx, app, neighborhood, r).unwrap();
+ }
+}
+
fn only_one_border(app: &mut App, neighborhood: &Neighborhood) {
for cell in &neighborhood.cells {
if cell.borders.len() > 1 {
