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

bevy_input_focus/
directional_navigation.rs
