bevy_input_focus/
directional_navigation.rs

1//! A navigation framework for moving between focusable elements based on directional input.
2//!
3//! While virtual cursors are a common way to navigate UIs with a gamepad (or arrow keys!),
4//! they are generally both slow and frustrating to use.
5//! Instead, directional inputs should provide a direct way to snap between focusable elements.
6//!
7//! Like the rest of this crate, the [`InputFocus`] resource is manipulated to track
8//! the current focus.
9//!
10//! Navigating between focusable entities (commonly UI nodes) is done by
11//! passing a [`CompassOctant`] into the [`navigate`](DirectionalNavigation::navigate) method
12//! from the [`DirectionalNavigation`] system parameter.
13//!
14//! Under the hood, the [`DirectionalNavigationMap`] stores a directed graph of focusable entities.
15//! Each entity can have up to 8 neighbors, one for each [`CompassOctant`], balancing flexibility and required precision.
16//! For now, this graph must be built manually, but in the future, it could be generated automatically.
17
18use bevy_app::prelude::*;
19use bevy_ecs::{
20    entity::{EntityHashMap, EntityHashSet},
21    prelude::*,
22    system::SystemParam,
23};
24use bevy_math::CompassOctant;
25use thiserror::Error;
26
27use crate::InputFocus;
28
29#[cfg(feature = "bevy_reflect")]
30use bevy_reflect::{prelude::*, Reflect};
31
32/// A plugin that sets up the directional navigation systems and resources.
33#[derive(Default)]
34pub struct DirectionalNavigationPlugin;
35
36impl Plugin for DirectionalNavigationPlugin {
37    fn build(&self, app: &mut App) {
38        app.init_resource::<DirectionalNavigationMap>();
39
40        #[cfg(feature = "bevy_reflect")]
41        app.register_type::<NavNeighbors>()
42            .register_type::<DirectionalNavigationMap>();
43    }
44}
45
46/// The up-to-eight neighbors of a focusable entity, one for each [`CompassOctant`].
47#[derive(Default, Debug, Clone, PartialEq)]
48#[cfg_attr(
49    feature = "bevy_reflect",
50    derive(Reflect),
51    reflect(Default, Debug, PartialEq, Clone)
52)]
53pub struct NavNeighbors {
54    /// The array of neighbors, one for each [`CompassOctant`].
55    /// The mapping between array elements and directions is determined by [`CompassOctant::to_index`].
56    ///
57    /// If no neighbor exists in a given direction, the value will be [`None`].
58    /// In most cases, using [`NavNeighbors::set`] and [`NavNeighbors::get`]
59    /// will be more ergonomic than directly accessing this array.
60    pub neighbors: [Option<Entity>; 8],
61}
62
63impl NavNeighbors {
64    /// An empty set of neighbors.
65    pub const EMPTY: NavNeighbors = NavNeighbors {
66        neighbors: [None; 8],
67    };
68
69    /// Get the neighbor for a given [`CompassOctant`].
70    pub const fn get(&self, octant: CompassOctant) -> Option<Entity> {
71        self.neighbors[octant.to_index()]
72    }
73
74    /// Set the neighbor for a given [`CompassOctant`].
75    pub const fn set(&mut self, octant: CompassOctant, entity: Entity) {
76        self.neighbors[octant.to_index()] = Some(entity);
77    }
78}
79
80/// A resource that stores the traversable graph of focusable entities.
81///
82/// Each entity can have up to 8 neighbors, one for each [`CompassOctant`].
83///
84/// To ensure that your graph is intuitive to navigate and generally works correctly, it should be:
85///
86/// - **Connected**: Every focusable entity should be reachable from every other focusable entity.
87/// - **Symmetric**: If entity A is a neighbor of entity B, then entity B should be a neighbor of entity A, ideally in the reverse direction.
88/// - **Physical**: The direction of navigation should match the layout of the entities when possible,
89///   although looping around the edges of the screen is also acceptable.
90/// - **Not self-connected**: An entity should not be a neighbor of itself; use [`None`] instead.
91///
92/// For now, this graph must be built manually, and the developer is responsible for ensuring that it meets the above criteria.
93#[derive(Resource, Debug, Default, Clone, PartialEq)]
94#[cfg_attr(
95    feature = "bevy_reflect",
96    derive(Reflect),
97    reflect(Resource, Debug, Default, PartialEq, Clone)
98)]
99pub struct DirectionalNavigationMap {
100    /// A directed graph of focusable entities.
101    ///
102    /// Pass in the current focus as a key, and get back a collection of up to 8 neighbors,
103    /// each keyed by a [`CompassOctant`].
104    pub neighbors: EntityHashMap<NavNeighbors>,
105}
106
107impl DirectionalNavigationMap {
108    /// Adds a new entity to the navigation map, overwriting any existing neighbors for that entity.
109    ///
110    /// Removes an entity from the navigation map, including all connections to and from it.
111    ///
112    /// Note that this is an O(n) operation, where n is the number of entities in the map,
113    /// as we must iterate over each entity to check for connections to the removed entity.
114    ///
115    /// If you are removing multiple entities, consider using [`remove_multiple`](Self::remove_multiple) instead.
116    pub fn remove(&mut self, entity: Entity) {
117        self.neighbors.remove(&entity);
118
119        for node in self.neighbors.values_mut() {
120            for neighbor in node.neighbors.iter_mut() {
121                if *neighbor == Some(entity) {
122                    *neighbor = None;
123                }
124            }
125        }
126    }
127
128    /// Removes a collection of entities from the navigation map.
129    ///
130    /// While this is still an O(n) operation, where n is the number of entities in the map,
131    /// it is more efficient than calling [`remove`](Self::remove) multiple times,
132    /// as we can check for connections to all removed entities in a single pass.
133    ///
134    /// An [`EntityHashSet`] must be provided as it is noticeably faster than the standard hasher or a [`Vec`](`alloc::vec::Vec`).
135    pub fn remove_multiple(&mut self, entities: EntityHashSet) {
136        for entity in &entities {
137            self.neighbors.remove(entity);
138        }
139
140        for node in self.neighbors.values_mut() {
141            for neighbor in node.neighbors.iter_mut() {
142                if let Some(entity) = *neighbor {
143                    if entities.contains(&entity) {
144                        *neighbor = None;
145                    }
146                }
147            }
148        }
149    }
150
151    /// Completely clears the navigation map, removing all entities and connections.
152    pub fn clear(&mut self) {
153        self.neighbors.clear();
154    }
155
156    /// Adds an edge between two entities in the navigation map.
157    /// Any existing edge from A in the provided direction will be overwritten.
158    ///
159    /// The reverse edge will not be added, so navigation will only be possible in one direction.
160    /// If you want to add a symmetrical edge, use [`add_symmetrical_edge`](Self::add_symmetrical_edge) instead.
161    pub fn add_edge(&mut self, a: Entity, b: Entity, direction: CompassOctant) {
162        self.neighbors
163            .entry(a)
164            .or_insert(NavNeighbors::EMPTY)
165            .set(direction, b);
166    }
167
168    /// Adds a symmetrical edge between two entities in the navigation map.
169    /// The A -> B path will use the provided direction, while B -> A will use the [`CompassOctant::opposite`] variant.
170    ///
171    /// Any existing connections between the two entities will be overwritten.
172    pub fn add_symmetrical_edge(&mut self, a: Entity, b: Entity, direction: CompassOctant) {
173        self.add_edge(a, b, direction);
174        self.add_edge(b, a, direction.opposite());
175    }
176
177    /// Add symmetrical edges between each consecutive pair of entities in the provided slice.
178    ///
179    /// Unlike [`add_looping_edges`](Self::add_looping_edges), this method does not loop back to the first entity.
180    pub fn add_edges(&mut self, entities: &[Entity], direction: CompassOctant) {
181        for pair in entities.windows(2) {
182            self.add_symmetrical_edge(pair[0], pair[1], direction);
183        }
184    }
185
186    /// Add symmetrical edges between each consecutive pair of entities in the provided slice, looping back to the first entity at the end.
187    ///
188    /// This is useful for creating a circular navigation path between a set of entities, such as a menu.
189    pub fn add_looping_edges(&mut self, entities: &[Entity], direction: CompassOctant) {
190        self.add_edges(entities, direction);
191        if let Some((first_entity, rest)) = entities.split_first() {
192            if let Some(last_entity) = rest.last() {
193                self.add_symmetrical_edge(*last_entity, *first_entity, direction);
194            }
195        }
196    }
197
198    /// Gets the entity in a given direction from the current focus, if any.
199    pub fn get_neighbor(&self, focus: Entity, octant: CompassOctant) -> Option<Entity> {
200        self.neighbors
201            .get(&focus)
202            .and_then(|neighbors| neighbors.get(octant))
203    }
204
205    /// Looks up the neighbors of a given entity.
206    ///
207    /// If the entity is not in the map, [`None`] will be returned.
208    /// Note that the set of neighbors is not guaranteed to be non-empty though!
209    pub fn get_neighbors(&self, entity: Entity) -> Option<&NavNeighbors> {
210        self.neighbors.get(&entity)
211    }
212}
213
214/// A system parameter for navigating between focusable entities in a directional way.
215#[derive(SystemParam, Debug)]
216pub struct DirectionalNavigation<'w> {
217    /// The currently focused entity.
218    pub focus: ResMut<'w, InputFocus>,
219    /// The navigation map containing the connections between entities.
220    pub map: Res<'w, DirectionalNavigationMap>,
221}
222
223impl DirectionalNavigation<'_> {
224    /// Navigates to the neighbor in a given direction from the current focus, if any.
225    ///
226    /// Returns the new focus if successful.
227    /// Returns an error if there is no focus set or if there is no neighbor in the requested direction.
228    ///
229    /// If the result was `Ok`, the [`InputFocus`] resource is updated to the new focus as part of this method call.
230    pub fn navigate(
231        &mut self,
232        direction: CompassOctant,
233    ) -> Result<Entity, DirectionalNavigationError> {
234        if let Some(current_focus) = self.focus.0 {
235            if let Some(new_focus) = self.map.get_neighbor(current_focus, direction) {
236                self.focus.set(new_focus);
237                Ok(new_focus)
238            } else {
239                Err(DirectionalNavigationError::NoNeighborInDirection {
240                    current_focus,
241                    direction,
242                })
243            }
244        } else {
245            Err(DirectionalNavigationError::NoFocus)
246        }
247    }
248}
249
250/// An error that can occur when navigating between focusable entities using [directional navigation](crate::directional_navigation).
251#[derive(Debug, PartialEq, Clone, Error)]
252pub enum DirectionalNavigationError {
253    /// No focusable entity is currently set.
254    #[error("No focusable entity is currently set.")]
255    NoFocus,
256    /// No neighbor in the requested direction.
257    #[error("No neighbor from {current_focus} in the {direction:?} direction.")]
258    NoNeighborInDirection {
259        /// The entity that was the focus when the error occurred.
260        current_focus: Entity,
261        /// The direction in which the navigation was attempted.
262        direction: CompassOctant,
263    },
264}
265
266#[cfg(test)]
267mod tests {
268    use bevy_ecs::system::RunSystemOnce;
269
270    use super::*;
271
272    #[test]
273    fn setting_and_getting_nav_neighbors() {
274        let mut neighbors = NavNeighbors::EMPTY;
275        assert_eq!(neighbors.get(CompassOctant::SouthEast), None);
276
277        neighbors.set(CompassOctant::SouthEast, Entity::PLACEHOLDER);
278
279        for i in 0..8 {
280            if i == CompassOctant::SouthEast.to_index() {
281                assert_eq!(
282                    neighbors.get(CompassOctant::SouthEast),
283                    Some(Entity::PLACEHOLDER)
284                );
285            } else {
286                assert_eq!(neighbors.get(CompassOctant::from_index(i).unwrap()), None);
287            }
288        }
289    }
290
291    #[test]
292    fn simple_set_and_get_navmap() {
293        let mut world = World::new();
294        let a = world.spawn_empty().id();
295        let b = world.spawn_empty().id();
296
297        let mut map = DirectionalNavigationMap::default();
298        map.add_edge(a, b, CompassOctant::SouthEast);
299
300        assert_eq!(map.get_neighbor(a, CompassOctant::SouthEast), Some(b));
301        assert_eq!(
302            map.get_neighbor(b, CompassOctant::SouthEast.opposite()),
303            None
304        );
305    }
306
307    #[test]
308    fn symmetrical_edges() {
309        let mut world = World::new();
310        let a = world.spawn_empty().id();
311        let b = world.spawn_empty().id();
312
313        let mut map = DirectionalNavigationMap::default();
314        map.add_symmetrical_edge(a, b, CompassOctant::North);
315
316        assert_eq!(map.get_neighbor(a, CompassOctant::North), Some(b));
317        assert_eq!(map.get_neighbor(b, CompassOctant::South), Some(a));
318    }
319
320    #[test]
321    fn remove_nodes() {
322        let mut world = World::new();
323        let a = world.spawn_empty().id();
324        let b = world.spawn_empty().id();
325
326        let mut map = DirectionalNavigationMap::default();
327        map.add_edge(a, b, CompassOctant::North);
328        map.add_edge(b, a, CompassOctant::South);
329
330        assert_eq!(map.get_neighbor(a, CompassOctant::North), Some(b));
331        assert_eq!(map.get_neighbor(b, CompassOctant::South), Some(a));
332
333        map.remove(b);
334
335        assert_eq!(map.get_neighbor(a, CompassOctant::North), None);
336        assert_eq!(map.get_neighbor(b, CompassOctant::South), None);
337    }
338
339    #[test]
340    fn remove_multiple_nodes() {
341        let mut world = World::new();
342        let a = world.spawn_empty().id();
343        let b = world.spawn_empty().id();
344        let c = world.spawn_empty().id();
345
346        let mut map = DirectionalNavigationMap::default();
347        map.add_edge(a, b, CompassOctant::North);
348        map.add_edge(b, a, CompassOctant::South);
349        map.add_edge(b, c, CompassOctant::East);
350        map.add_edge(c, b, CompassOctant::West);
351
352        let mut to_remove = EntityHashSet::default();
353        to_remove.insert(b);
354        to_remove.insert(c);
355
356        map.remove_multiple(to_remove);
357
358        assert_eq!(map.get_neighbor(a, CompassOctant::North), None);
359        assert_eq!(map.get_neighbor(b, CompassOctant::South), None);
360        assert_eq!(map.get_neighbor(b, CompassOctant::East), None);
361        assert_eq!(map.get_neighbor(c, CompassOctant::West), None);
362    }
363
364    #[test]
365    fn edges() {
366        let mut world = World::new();
367        let a = world.spawn_empty().id();
368        let b = world.spawn_empty().id();
369        let c = world.spawn_empty().id();
370
371        let mut map = DirectionalNavigationMap::default();
372        map.add_edges(&[a, b, c], CompassOctant::East);
373
374        assert_eq!(map.get_neighbor(a, CompassOctant::East), Some(b));
375        assert_eq!(map.get_neighbor(b, CompassOctant::East), Some(c));
376        assert_eq!(map.get_neighbor(c, CompassOctant::East), None);
377
378        assert_eq!(map.get_neighbor(a, CompassOctant::West), None);
379        assert_eq!(map.get_neighbor(b, CompassOctant::West), Some(a));
380        assert_eq!(map.get_neighbor(c, CompassOctant::West), Some(b));
381    }
382
383    #[test]
384    fn looping_edges() {
385        let mut world = World::new();
386        let a = world.spawn_empty().id();
387        let b = world.spawn_empty().id();
388        let c = world.spawn_empty().id();
389
390        let mut map = DirectionalNavigationMap::default();
391        map.add_looping_edges(&[a, b, c], CompassOctant::East);
392
393        assert_eq!(map.get_neighbor(a, CompassOctant::East), Some(b));
394        assert_eq!(map.get_neighbor(b, CompassOctant::East), Some(c));
395        assert_eq!(map.get_neighbor(c, CompassOctant::East), Some(a));
396
397        assert_eq!(map.get_neighbor(a, CompassOctant::West), Some(c));
398        assert_eq!(map.get_neighbor(b, CompassOctant::West), Some(a));
399        assert_eq!(map.get_neighbor(c, CompassOctant::West), Some(b));
400    }
401
402    #[test]
403    fn nav_with_system_param() {
404        let mut world = World::new();
405        let a = world.spawn_empty().id();
406        let b = world.spawn_empty().id();
407        let c = world.spawn_empty().id();
408
409        let mut map = DirectionalNavigationMap::default();
410        map.add_looping_edges(&[a, b, c], CompassOctant::East);
411
412        world.insert_resource(map);
413
414        let mut focus = InputFocus::default();
415        focus.set(a);
416        world.insert_resource(focus);
417
418        assert_eq!(world.resource::<InputFocus>().get(), Some(a));
419
420        fn navigate_east(mut nav: DirectionalNavigation) {
421            nav.navigate(CompassOctant::East).unwrap();
422        }
423
424        world.run_system_once(navigate_east).unwrap();
425        assert_eq!(world.resource::<InputFocus>().get(), Some(b));
426
427        world.run_system_once(navigate_east).unwrap();
428        assert_eq!(world.resource::<InputFocus>().get(), Some(c));
429
430        world.run_system_once(navigate_east).unwrap();
431        assert_eq!(world.resource::<InputFocus>().get(), Some(a));
432    }
433}
bevy_input_focus/directional_navigation.rs

bevy_input_focus/
directional_navigation.rs
