Bevy Gamepad Navigation

• Virtual cursors are terrible: lots of time wasted travelling between interactive elements, poor discoverability, bad for unconventional input devices (a11y)
• Tab cycling is… better, but still doesn't take advantage of full capabilities
• The natural choice is to navigate directly between elements based on quadrants (or octants, or directions)
• This creates a focus graph, made out of focus paths
  • Digraph time!
• A good focus graph would be:
  • Fully connected: no stranded UI elements
  • Reversible: reversing the input should go back to the previous element
  • Intuitive: paths map to the directions displayed on the screen
  • Forgiving: precise inputs are not needed to navigate to a specific element
• We can probably do a decent job autogenerating these
• But devs require more customizability!
  • Reversibility is tricky when you have multiple segments to navigate between: storing a bit of history would be nice
  • Implementing cycling at the end of a list
  • Probably other cursed things
• Strategy:
  • Use octants for navigation path directions as a balance between good control and being forgiving
  • Automatically generate focus graph when things are spawned
  • Regenerate it when things change (ideally only focusing on local changes to save work)
  • Allow for custom behavior, overwriting any existing path
  • Store previous focus on InputFocus, and pass in InputFocus as context for custom behavior
  • Don't overwrite custom behavior when regenerating
  • Return a Result from each navigation operation

PR strategy:

1. Store previous focus
   • Not actually useful: this is widget logic. Was implemented at https://github.com/alice-i-cecile/bevy/tree/previous-focus
2. Return a result from navigation operation
3. Manually constructed navigation graphs + manual navigation + example
4. Helper to automatically generate a navigation graph, building out from any existing manually constructed graph
5. Incremental + automatic regeneration of navigation graph

struct FocusGraph {
    edges: HashMap<Entity, FocusNode>
}

impl FocusGraph {
    fn navigate(direction: CompassOctant, input_focus: &InputFocus) -> Result<Entity, NavigationError>{
        todo!()
    }
}

struct FocusNode {
    // Probably actually an array for perf
    edges: HashMap<CompassOctant, FocusPath>
}

enum FocusPath {
    Generated(Entity),
    Manual(Entity),
    Contextual(Box<dyn Fn(InputFocus) -> Entity>),
    None,
}