bevy_input_focus/
navigator.rs

1//! Functions used by navigators to determine where to go next.
2use crate::directional_navigation::{AutoNavigationConfig, FocusableArea};
3use bevy_ecs::prelude::*;
4use bevy_math::{CompassOctant, Dir2, Rect, Vec2};
5
6// We can't directly implement this for `bevy_ui` types here without circular dependencies,
7// so we'll use a more generic approach with separate functions for different component sets.
8
9/// Calculate 1D overlap between two ranges.
10///
11/// Returns a value between 0.0 (no overlap) and 1.0 (perfect overlap).
12fn calculate_1d_overlap(
13    origin_pos: f32,
14    origin_size: f32,
15    candidate_pos: f32,
16    candidate_size: f32,
17) -> f32 {
18    let origin_min = origin_pos - origin_size / 2.0;
19    let origin_max = origin_pos + origin_size / 2.0;
20    let cand_min = candidate_pos - candidate_size / 2.0;
21    let cand_max = candidate_pos + candidate_size / 2.0;
22
23    let overlap = (origin_max.min(cand_max) - origin_min.max(cand_min)).max(0.0);
24    let max_overlap = origin_size.min(candidate_size);
25    if max_overlap > 0.0 {
26        overlap / max_overlap
27    } else {
28        0.0
29    }
30}
31
32/// Calculate the overlap factor between two nodes in the perpendicular axis.
33///
34/// Returns a value between 0.0 (no overlap) and 1.0 (perfect overlap).
35/// For diagonal directions, always returns 1.0.
36fn calculate_overlap(
37    origin_pos: Vec2,
38    origin_size: Vec2,
39    candidate_pos: Vec2,
40    candidate_size: Vec2,
41    octant: CompassOctant,
42) -> f32 {
43    match octant {
44        CompassOctant::North | CompassOctant::South => {
45            // Check horizontal overlap
46            calculate_1d_overlap(
47                origin_pos.x,
48                origin_size.x,
49                candidate_pos.x,
50                candidate_size.x,
51            )
52        }
53        CompassOctant::East | CompassOctant::West => {
54            // Check vertical overlap
55            calculate_1d_overlap(
56                origin_pos.y,
57                origin_size.y,
58                candidate_pos.y,
59                candidate_size.y,
60            )
61        }
62        // Diagonal directions don't require strict overlap
63        _ => 1.0,
64    }
65}
66
67/// Score a candidate node for navigation in a given direction.
68///
69/// Lower score is better. Returns `f32::INFINITY` for unreachable nodes.
70fn score_candidate(
71    origin_pos: Vec2,
72    origin_size: Vec2,
73    candidate_pos: Vec2,
74    candidate_size: Vec2,
75    octant: CompassOctant,
76    config: &AutoNavigationConfig,
77) -> f32 {
78    // Get direction in mathematical coordinates, then flip Y for UI coordinates
79    let dir = Dir2::from(octant).as_vec2() * Vec2::new(1.0, -1.0);
80    let to_candidate = candidate_pos - origin_pos;
81
82    // Check direction first
83    // Convert UI coordinates (Y+ = down) to mathematical coordinates (Y+ = up) by flipping Y
84    let origin_math = Vec2::new(origin_pos.x, -origin_pos.y);
85    let candidate_math = Vec2::new(candidate_pos.x, -candidate_pos.y);
86    if !octant.is_in_direction(origin_math, candidate_math) {
87        return f32::INFINITY;
88    }
89
90    // Check overlap for cardinal directions
91    let overlap_factor = calculate_overlap(
92        origin_pos,
93        origin_size,
94        candidate_pos,
95        candidate_size,
96        octant,
97    );
98
99    if overlap_factor < config.min_alignment_factor {
100        return f32::INFINITY;
101    }
102
103    // Calculate distance between rectangle edges, not centers
104    let origin_rect = Rect::from_center_size(origin_pos, origin_size);
105    let candidate_rect = Rect::from_center_size(candidate_pos, candidate_size);
106    let dx = (candidate_rect.min.x - origin_rect.max.x)
107        .max(origin_rect.min.x - candidate_rect.max.x)
108        .max(0.0);
109    let dy = (candidate_rect.min.y - origin_rect.max.y)
110        .max(origin_rect.min.y - candidate_rect.max.y)
111        .max(0.0);
112    let distance = (dx * dx + dy * dy).sqrt();
113
114    // Check max distance
115    if let Some(max_dist) = config.max_search_distance {
116        if distance > max_dist {
117            return f32::INFINITY;
118        }
119    }
120
121    // Calculate alignment score using center-to-center direction
122    let center_distance = to_candidate.length();
123    let alignment = if center_distance > 0.0 {
124        to_candidate.normalize().dot(dir).max(0.0)
125    } else {
126        1.0
127    };
128
129    // Combine distance and alignment
130    // Prefer aligned nodes by penalizing misalignment
131    let alignment_penalty = if config.prefer_aligned {
132        (1.0 - alignment) * distance * 2.0 // Misalignment scales with distance
133    } else {
134        0.0
135    };
136
137    distance + alignment_penalty
138}
139
140/// Finds the best entity to navigate to from the origin towards the given direction.
141///
142/// For details on what "best" means here, refer to [`AutoNavigationConfig`], which configures
143/// how candidates are scored.
144pub fn find_best_candidate(
145    origin: &FocusableArea,
146    direction: CompassOctant,
147    candidates: &[FocusableArea],
148    config: &AutoNavigationConfig,
149) -> Option<Entity> {
150    // Find best candidate in this direction
151    let mut best_candidate = None;
152    let mut best_score = f32::INFINITY;
153
154    for candidate in candidates {
155        // Skip self
156        if candidate.entity == origin.entity {
157            continue;
158        }
159
160        // Score the candidate
161        let score = score_candidate(
162            origin.position,
163            origin.size,
164            candidate.position,
165            candidate.size,
166            direction,
167            config,
168        );
169
170        if score < best_score {
171            best_score = score;
172            best_candidate = Some(candidate.entity);
173        }
174    }
175
176    best_candidate
177}
178
179#[cfg(test)]
180mod tests {
181    use super::*;
182
183    #[test]
184    fn test_is_in_direction() {
185        let origin = Vec2::new(100.0, 100.0);
186
187        // Node to the north (mathematically up) should have larger Y
188        let north_node = Vec2::new(100.0, 150.0);
189        assert!(CompassOctant::North.is_in_direction(origin, north_node));
190        assert!(!CompassOctant::South.is_in_direction(origin, north_node));
191
192        // Node to the south (mathematically down) should have smaller Y
193        let south_node = Vec2::new(100.0, 50.0);
194        assert!(CompassOctant::South.is_in_direction(origin, south_node));
195        assert!(!CompassOctant::North.is_in_direction(origin, south_node));
196
197        // Node to the east should be in East direction
198        let east_node = Vec2::new(150.0, 100.0);
199        assert!(CompassOctant::East.is_in_direction(origin, east_node));
200        assert!(!CompassOctant::West.is_in_direction(origin, east_node));
201
202        // Node to the northeast (mathematically up-right) should have larger Y, larger X
203        let ne_node = Vec2::new(150.0, 150.0);
204        assert!(CompassOctant::NorthEast.is_in_direction(origin, ne_node));
205        assert!(!CompassOctant::SouthWest.is_in_direction(origin, ne_node));
206    }
207
208    #[test]
209    fn test_calculate_overlap_horizontal() {
210        let origin_pos = Vec2::new(100.0, 100.0);
211        let origin_size = Vec2::new(50.0, 50.0);
212
213        // Fully overlapping node to the north
214        let north_pos = Vec2::new(100.0, 200.0);
215        let north_size = Vec2::new(50.0, 50.0);
216        let overlap = calculate_overlap(
217            origin_pos,
218            origin_size,
219            north_pos,
220            north_size,
221            CompassOctant::North,
222        );
223        assert_eq!(overlap, 1.0); // Full overlap
224
225        // Partially overlapping node to the north
226        let north_pos = Vec2::new(110.0, 200.0);
227        let partial_overlap = calculate_overlap(
228            origin_pos,
229            origin_size,
230            north_pos,
231            north_size,
232            CompassOctant::North,
233        );
234        assert!(partial_overlap > 0.0 && partial_overlap < 1.0);
235
236        // No overlap
237        let north_pos = Vec2::new(200.0, 200.0);
238        let no_overlap = calculate_overlap(
239            origin_pos,
240            origin_size,
241            north_pos,
242            north_size,
243            CompassOctant::North,
244        );
245        assert_eq!(no_overlap, 0.0);
246    }
247
248    #[test]
249    fn test_score_candidate() {
250        let config = AutoNavigationConfig::default();
251        let origin_pos = Vec2::new(100.0, 100.0);
252        let origin_size = Vec2::new(50.0, 50.0);
253
254        // Node directly to the north (up on screen = smaller Y)
255        let north_pos = Vec2::new(100.0, 0.0);
256        let north_size = Vec2::new(50.0, 50.0);
257        let north_score = score_candidate(
258            origin_pos,
259            origin_size,
260            north_pos,
261            north_size,
262            CompassOctant::North,
263            &config,
264        );
265        assert!(north_score < f32::INFINITY);
266        assert!(north_score < 150.0); // Should be close to the distance (100)
267
268        // Node in opposite direction (should be unreachable)
269        let south_pos = Vec2::new(100.0, 200.0);
270        let south_size = Vec2::new(50.0, 50.0);
271        let invalid_score = score_candidate(
272            origin_pos,
273            origin_size,
274            south_pos,
275            south_size,
276            CompassOctant::North,
277            &config,
278        );
279        assert_eq!(invalid_score, f32::INFINITY);
280
281        // Closer node should have better score than farther node
282        let close_pos = Vec2::new(100.0, 50.0);
283        let far_pos = Vec2::new(100.0, -100.0);
284        let close_score = score_candidate(
285            origin_pos,
286            origin_size,
287            close_pos,
288            north_size,
289            CompassOctant::North,
290            &config,
291        );
292        let far_score = score_candidate(
293            origin_pos,
294            origin_size,
295            far_pos,
296            north_size,
297            CompassOctant::North,
298            &config,
299        );
300        assert!(close_score < far_score);
301    }
302}
bevy_input_focus/navigator.rs

bevy_input_focus/
navigator.rs
