halley_core/
cluster_policy.rs

1use std::collections::{HashMap, HashSet};
2
3use crate::cluster::ClusterId;
4use crate::field::{Field, NodeId, NodeKind, Vec2};
5
6/// Configuration for auto cluster formation.
7///
8/// Default idea:
9/// - Nodes that remain within `distance_px` of each other for `dwell_ms`
10///   can be clustered (as a connected component).
11/// - Can be disabled (`enabled = false`) or tuned.
12#[derive(Clone, Copy, Debug)]
13pub struct ClusterPolicy {
14    pub enabled: bool,
15
16    /// Max distance between nodes to be considered "near".
17    pub distance_px: f32,
18
19    /// How long nodes must remain near to qualify (ms).
20    pub dwell_ms: u64,
21
22    /// Minimum component size to form a cluster.
23    pub min_members: usize,
24
25    /// Include anchored nodes in auto-clustering.
26    pub include_anchored: bool,
27
28    /// Include currently Active windows in auto-clustering.
29    /// Keeping this false avoids grouping freshly opened app windows.
30    pub include_active: bool,
31}
32
33impl Default for ClusterPolicy {
34    fn default() -> Self {
35        Self {
36            enabled: true,
37            distance_px: 220.0,
38            dwell_ms: 1_500,
39            min_members: 2,
40            include_anchored: false,
41            include_active: false,
42        }
43    }
44}
45
46/// Stateful tracker for cluster formation.
47/// Keep this in the outer loop / world manager, not inside Field.
48#[derive(Clone, Debug, Default)]
49pub struct ClusterFormationState {
50    /// When did we first observe this pair within threshold?
51    /// Key is ordered (min, max) for stability.
52    near_since: HashMap<(NodeId, NodeId), u64>,
53}
54
55// Squared edge-to-edge gap between two axis-aligned node footprints.
56// 0 means touching or overlapping.
57fn footprint_gap2(a_pos: Vec2, a_size: Vec2, b_pos: Vec2, b_size: Vec2) -> f32 {
58    let dx = (a_pos.x - b_pos.x).abs() - (a_size.x.abs() * 0.5 + b_size.x.abs() * 0.5);
59    let dy = (a_pos.y - b_pos.y).abs() - (a_size.y.abs() * 0.5 + b_size.y.abs() * 0.5);
60    let gx = dx.max(0.0);
61    let gy = dy.max(0.0);
62    gx * gx + gy * gy
63}
64
65fn ordered_pair(a: NodeId, b: NodeId) -> (NodeId, NodeId) {
66    if a.as_u64() <= b.as_u64() {
67        (a, b)
68    } else {
69        (b, a)
70    }
71}
72
73/// Tick auto cluster formation.
74///
75/// Returns any newly created ClusterIds.
76pub fn tick_cluster_formation(
77    field: &mut Field,
78    now_ms: u64,
79    policy: ClusterPolicy,
80    state: &mut ClusterFormationState,
81) -> Vec<ClusterId> {
82    if !policy.enabled {
83        state.near_since.clear();
84        return Vec::new();
85    }
86
87    // Exclude nodes already belonging to any cluster.
88    let mut already_clustered: HashSet<NodeId> = HashSet::new();
89    for c in field.clusters_iter() {
90        for &m in c.members() {
91            already_clustered.insert(m);
92        }
93        if let Some(core) = c.core {
94            already_clustered.insert(core);
95        }
96    }
97
98    // Candidate nodes: visible, Surface (not Core), not detached/hidden, not already in cluster.
99    let mut candidates: Vec<NodeId> = field
100        .nodes()
101        .keys()
102        .copied()
103        .filter(|&id| field.participates_in_field_view(id))
104        .filter(|&id| field.is_visible(id))
105        .filter(|&id| !already_clustered.contains(&id))
106        .filter(|&id| field.node(id).is_some_and(|n| n.kind == NodeKind::Surface))
107        .filter(|&id| {
108            if policy.include_active {
109                true
110            } else {
111                field.node(id).is_some_and(|n| {
112                    n.state != crate::field::NodeState::Active
113                        && n.state != crate::field::NodeState::Core
114                })
115            }
116        })
117        .filter(|&id| {
118            if policy.include_anchored {
119                true
120            } else {
121                field.node(id).is_some_and(|n| !n.pinned)
122            }
123        })
124        .collect();
125
126    // Deterministic ordering
127    candidates.sort_by_key(|id| id.as_u64());
128
129    let thr2 = policy.distance_px * policy.distance_px;
130
131    // Track which pairs are "currently near" this tick.
132    let mut near_now: HashSet<(NodeId, NodeId)> = HashSet::new();
133
134    // Identify near pairs and update timers.
135    for i in 0..candidates.len() {
136        for j in (i + 1)..candidates.len() {
137            let a = candidates[i];
138            let b = candidates[j];
139
140            let (pa, sa, pb, sb) = match (field.node(a), field.node(b)) {
141                (Some(na), Some(nb)) => (na.pos, na.footprint, nb.pos, nb.footprint),
142                _ => continue,
143            };
144
145            if footprint_gap2(pa, sa, pb, sb) <= thr2 {
146                let key = ordered_pair(a, b);
147                near_now.insert(key);
148                state.near_since.entry(key).or_insert(now_ms);
149            }
150        }
151    }
152
153    // Drop any pairs that are no longer near.
154    state.near_since.retain(|k, _| near_now.contains(k));
155
156    // Build a graph of "mature" near-pairs (dwell satisfied).
157    let mut adj: HashMap<NodeId, Vec<NodeId>> = HashMap::new();
158    for (&(a, b), &since) in state.near_since.iter() {
159        if now_ms.saturating_sub(since) >= policy.dwell_ms {
160            adj.entry(a).or_default().push(b);
161            adj.entry(b).or_default().push(a);
162        }
163    }
164
165    // Find connected components among candidates based on mature edges.
166    let mut seen: HashSet<NodeId> = HashSet::new();
167    let mut created: Vec<ClusterId> = Vec::new();
168
169    for &start in &candidates {
170        if seen.contains(&start) {
171            continue;
172        }
173        if !adj.contains_key(&start) {
174            seen.insert(start);
175            continue;
176        }
177
178        // DFS
179        let mut stack = vec![start];
180        let mut comp: Vec<NodeId> = Vec::new();
181        seen.insert(start);
182
183        while let Some(x) = stack.pop() {
184            comp.push(x);
185            if let Some(neis) = adj.get(&x) {
186                for &y in neis {
187                    if !seen.contains(&y) {
188                        seen.insert(y);
189                        stack.push(y);
190                    }
191                }
192            }
193        }
194
195        // Only form a cluster if large enough.
196        if comp.len() >= policy.min_members {
197            // Attempt to create the cluster.
198            if let Ok(cid) = field.create_cluster(comp.clone()) {
199                created.push(cid);
200
201                // Clear any pair timers involving these nodes to avoid instant re-cluster.
202                let comp_set: HashSet<NodeId> = comp.into_iter().collect();
203                state
204                    .near_since
205                    .retain(|&(a, b), _| !comp_set.contains(&a) && !comp_set.contains(&b));
206            }
207        }
208    }
209
210    created
211}
212
213#[cfg(test)]
214mod tests {
215    use super::*;
216    use crate::field::Vec2;
217
218    #[test]
219    fn forms_cluster_after_dwell() {
220        let mut f = Field::new();
221        let a = f.spawn_surface("A", Vec2 { x: 0.0, y: 0.0 }, Vec2 { x: 10.0, y: 10.0 });
222        let b = f.spawn_surface("B", Vec2 { x: 50.0, y: 0.0 }, Vec2 { x: 10.0, y: 10.0 });
223
224        let mut st = ClusterFormationState::default();
225        let policy = ClusterPolicy {
226            enabled: true,
227            distance_px: 100.0,
228            dwell_ms: 1_000,
229            min_members: 2,
230            include_anchored: false,
231            include_active: true,
232        };
233
234        // t=0: start timer but not mature
235        let c0 = tick_cluster_formation(&mut f, 0, policy, &mut st);
236        assert!(c0.is_empty());
237
238        // t=999: still not mature
239        let c1 = tick_cluster_formation(&mut f, 999, policy, &mut st);
240        assert!(c1.is_empty());
241
242        // t=1000: should form
243        let c2 = tick_cluster_formation(&mut f, 1000, policy, &mut st);
244        assert_eq!(c2.len(), 1);
245
246        // nodes should now be in a cluster
247        let cid = c2[0];
248        let cl = f.cluster(cid).unwrap();
249        assert!(cl.contains(a));
250        assert!(cl.contains(b));
251    }
252
253    #[test]
254    fn disabled_clears_state_and_does_nothing() {
255        let mut f = Field::new();
256        let _a = f.spawn_surface("A", Vec2 { x: 0.0, y: 0.0 }, Vec2 { x: 10.0, y: 10.0 });
257        let _b = f.spawn_surface("B", Vec2 { x: 50.0, y: 0.0 }, Vec2 { x: 10.0, y: 10.0 });
258
259        let mut st = ClusterFormationState::default();
260        st.near_since.insert((NodeId::new(1), NodeId::new(2)), 0);
261
262        let policy = ClusterPolicy {
263            enabled: false,
264            ..Default::default()
265        };
266        let out = tick_cluster_formation(&mut f, 1234, policy, &mut st);
267        assert!(out.is_empty());
268        assert!(st.near_since.is_empty());
269    }
270
271    #[test]
272    fn moving_apart_resets_dwell_timer() {
273        let mut f = Field::new();
274        let a = f.spawn_surface("A", Vec2 { x: 0.0, y: 0.0 }, Vec2 { x: 10.0, y: 10.0 });
275        let b = f.spawn_surface("B", Vec2 { x: 50.0, y: 0.0 }, Vec2 { x: 10.0, y: 10.0 });
276
277        let mut st = ClusterFormationState::default();
278        let policy = ClusterPolicy {
279            enabled: true,
280            distance_px: 100.0,
281            dwell_ms: 1_000,
282            min_members: 2,
283            include_anchored: false,
284            include_active: true,
285        };
286
287        // Start near
288        assert!(tick_cluster_formation(&mut f, 0, policy, &mut st).is_empty());
289
290        // Move far away before dwell
291        assert!(f.carry(
292            b,
293            Vec2 {
294                x: 10_000.0,
295                y: 0.0
296            }
297        ));
298        assert!(tick_cluster_formation(&mut f, 500, policy, &mut st).is_empty());
299
300        // Move back near; timer should restart
301        assert!(f.carry(b, Vec2 { x: 50.0, y: 0.0 }));
302        assert!(tick_cluster_formation(&mut f, 800, policy, &mut st).is_empty());
303
304        // Not enough time since "back near" (800 -> 1700 is 900)
305        assert!(tick_cluster_formation(&mut f, 1700, policy, &mut st).is_empty());
306
307        // Now enough since restarted (800 -> 1800 is 1000)
308        let out = tick_cluster_formation(&mut f, 1800, policy, &mut st);
309        assert_eq!(out.len(), 1);
310        let cid = out[0];
311        let cl = f.cluster(cid).unwrap();
312        assert!(cl.contains(a));
313        assert!(cl.contains(b));
314    }
315}
halley_core/cluster_policy.rs

halley_core/
cluster_policy.rs
