Spatial navigation

[Paril]

I'm using a fairly basic setup where I have a list of menu options, and inside the focusable item there may be a controllable object that should be modified when the parent is selected - essentially the parent element should be highlighted with focus, but the underlying input is what's actually being modified, if that makes sense. Here's a very rough example of the kind of setup I'm using currently:

.item.button, .item input, .item select
{
	focus: auto;
	nav-up: auto;
	nav-down: auto;
	tab-index: auto;
}

.item:focus, .item:hover
{
	background: red;
}

<div class="item">
  <label for="test">Check Me A</label>
  <input id="test" type="checkbox" />
</div>
<div class="item button">Button</div>
<div class="item">
  <label for="test2">Check Me B</label>
  <select id="test2"><option>A</option><option>B</option><option>C</option></select>
</div>
<div class="item button">Button</div>

I've been running into a few issues, though, and I'm wondering if I'm maybe doing something wrong here;

• at one point the focus was auto-wrapping when reaching the top or bottom and hitting up or down respectively, but that doesn't seem to happen any more - I'm not sure what I could have changed to break that
• if I have a checkbox focused (the .item type is flexbox, if that's related at all), hitting Up causes it to jump all the way to the top of the focusable items. If I limit the focusability solely to .item it seems to be OK, but that doesn't allow pass-through to work properly for enter/space and left/right arrows
• sliders don't seem to have any auto-repeat support, so you have to slowly step through one press at a time which is quite painful on the fingers
• the :focus selector seems to propagate upwards to the .item, which isn't mentioned in the documentation and seems to have non-standard behavior; is it intentional that it acts more like :focus-within than :focus in regular CSS?
• having the nav CSS property refer to a DOM id is very odd - wouldn't this be more appropriate as a DOM attribute? it makes setting up custom navigation graphs difficult since we have to make a single style per item

[mikke89]

Hey, this feature is very new, so it's cool to hear feedback. You could also take a look at some of the design decisions in the pull request for this feature. Let me know if you have some suggestions, I'm sure we can improve this.

To answer your specific questions.

1. I believe it's not supposed to wrap-around. So if you do see this behavior, please report it as a bug. Keep in mind though, pressing the tab key does wrap around.
2. Hm, yes, we haven't fully considered how it should behave for nested elements. I'll turn the question around to you, how should we pick the "nearest" element when some of the target candidates intersect the source element?
3. This repeat behavior should be implemented in the backend as repeated key strokes. Which backend are you using?
4. Indeed, you're correct here. Could you submit a pull request to improve the documentation you refer to?
5. Essentially we're trying to follow the CSS UI specs here. One advantage with this approach is that the behavior is defined by one source, rather than being spread on both CSS properties and element attributes, and with that having to define interactions between them. And you can always add inline style <div style="nav-right: #name">, which isn't too much trouble in my view, and essentially does what an attribute would do.

[Paril]

Hey mikke!

1. I think you're right, I have no idea why it was wrapping around before. I am like 100% certain it was wrapping at some point back when I had the .item itself be focusable, but I can't reproduce it now. If I manage to get it to happen again, I'll dig out a minimal sample, but the main reason I asked is because I actually do need wrap-around behavior, heh. Some of the menus can get large sometimes, and people tend to expect that it will wrap back around (like opening the main menu will auto-select the first element, but hitting Up will wrap to Quit). Perhaps this could be a CSS-driven feature?
2. I was thinking about this during a nap and I realized it may have to do with intersections, as I remember reading about you using rectangles for 'collision' testing of sorts. I noticed that, for instance, my .item elements sometimes have backgrounds that intersect each other, even though they are laid out sequentially and should not be touching, and I wonder if that's part of the problem. I'm using the dp unit with a scalar set in code so that a DOS resolution menu (like 320x240) is always scaled up to the proper central size of the window. I noticed that the :focus/:hover pseudo-selector backgrounds (with alpha) were intersecting. I don't think it's a rounding error, though, because if I use the native 1:1 resolution, it still has this weird jump behavior.

I'm not really sure offhand what a good solution is here regarding nested elements. I have not played with spatial navigation in proper CSS either. In my case, I'm only using it like an alternate approach to HTML's tabindex - essentially, I need down to always fetch the next element and up to always fetch the previous element. Using TAB and SHIFT+TAB does exactly what I need it to do in my case, but I can't get up and down arrows to follow the same rules (without making an explicit nav graph). I'm kind of lucky in our case because we only need up/down to work (as left/right are reserved for acting on sliders, etc), so this isn't so much "spatial" navigation as it is sequential navigation, which I'm willing to wager is a large percentage of console UIs, heh.
3. I realized that after posting that I hooked our key_down event but not our key_repeat event, so this was a me problem. We're using a backend for our own Kex engine (Nightdive Studios), not one of the existing backends. It might still be handy to have a CSS/HTML attribute for sliders that causes them to slide while the button is held instead of requiring repeats, though - there's quite a few sliders in games that would be rough without this behavior. I guess I could use a custom element, though.
4. Can do
5. This one I'm still kind of fighting with; if I can't get auto to work for focusing because of point 2, manually defining a nav graph is an option, but because we have a lot of elements that may or may not be there depending on platform it can create a lot of splits in the graph and be hard to maintain. In these cases, I actually can't use inline styles. As a very basic example:

<div id="video" style="nav-up: #input; nav-down: #display;" class="item">Video</div>
<div id="display" style="nav-up: #video; nav-down: #input;" class="item not_console">Display</div>
<div id="input" style="nav-up: #display; nav-down: #video;" class="item">Input</div>

The nice thing about HTML's tabindex is that this still works as intended; if you have tabindexes set on multiple elements (whether manually defined tabindex numbers, or just having them all set to 0), it will automatically go to the next available one even if something in-between isn't visible. This doesn't seem to be possible with the current setup though - it just selects nothing if you spatially navigate from Video, as it can't find #display, and there's no way to set a fallback. I don't know if a proper approach here might be to check if the element it's trying to tab to is available but not displayed, and if so, recursively act as if that is the focused element instead, so that it properly skips to what would be the next element had that element been there.

(EDIT 2: apparently this is also in the spec, but not implemented anywhere yet; just came across this while poking the document, and I think they have the right idea: Note: there were other options under consideration for such "not otherwise focusable" elements, including focus to the next otherwise focusable element in the document tree (including descendants of such a not otherwise focusable element). Input on such other options is welcome and explicitly solicited, especially from implementation experiences and author experience using the directional navigation properties in their content.)

Alternatively, perhaps specifying a list of tabbable in order would be an alternative:

#video
{
nav-up: #input;
nav-down: #display #input;
}

First come first serve, basically. It would not be backwards compatible with the nav specification though, as you'd have to adjust it to require commas between the four elements if you wanted to add in multiple selectors:

#video
{
nav: #input, none, #display #input, none;
}

In theory, I can already fix this in CSS with a media query (as we have media queries for platforms), but this just brings me back to needing to make sure I keep these synced up and it's a bit of a mouthful to type in for larger menus. I'm also not looking forward to using this technique if there's a menu with multiple conditional elements in a row - it requires an exponential amount of selectors to handle every potential case. It's at least a workaround, though.

EDIT: one thing I also didn't think to mention was something like a dynamic player list, where the elements are all inserted via code. Consider something like this:

<div id="players">
<div id="player_template">Player Name <button class='kick not_host' /><button class='mute' /><button class='add_friend not_friend' /></div>
</div>

Imagine the player list rendered top to bottom, but the icons are anchored to the right of the player name, and the player list is kept up to date via code. I don't know how you'd do sequential navigation entirely in RML/RCSS with this; functionality-wise we'll say that the player template itself is focusable, and pressing enter just moves it to the next available button on the right. Up/down on any element will move it to the next player, but never the next button (that is to say, if you're on Mute for one player, pressing down should just select the next players' label, not the Mute button below the player). The only approach I could see working here is managing the entire nav list by code, and using ElementStyle to set up the nav values by hand each time the player list changes.

[Paril]

I found a simple case where auto-nav breaks down @mikke89 - this is a drop-in for demo.rml:

<rml>
	<head>
		<title>Demo</title>
		<link type="text/template" href="window.rml" />
		<style>
			body
			{
				width: 300dp;
				height: 225dp;

				margin: auto;
			}

			div#title_bar div#icon
			{
				display: none;
			}

			div#content
			{
				text-align: left;
			}

			div.grid
			{
				display: block;
				width: 90dp;
				height: 90dp;
				line-height: 0;
			}

			div.grid > div
			{
				display: inline-block;
				box-sizing: border-box;
				border: 1px red;
				width: 30dp;
				height: 30dp;
				focus: auto;
				nav: auto;
				tab-index: auto;
			}

			div.grid > div:focus
			{
				border: 1px blue;
			}

			div.grid > div:active
			{
				border: 1px green;
			}
		</style>
	</head>
	<body template="window">
		<div class="grid">
			<div />
			<div />
			<div />
			<div />
			<div />
			<div />
			<div />
			<div />
			<div />
		</div>
	</body>
</rml>

For a "key pad" grid like this, the auto-spatial nav heuristic is preferring cross-axis navigation instead of axial. Visually looking at the GetNavigationHeuristic function, it fails in the case where multiple elements are touching the bounding box of the focused element. They all end up having 0, 0 for main_axis and cross_axis.

I came up with this as a quick solution:

	int GetNavigationHeuristic(const BoundingBox& source, const BoundingBox& target, NavigationSearchDirection direction)
	{
		enum Axis { Horizontal = 0, Vertical = 1 };

		auto CalculateHeuristic = [](Axis axis, const BoundingBox& a, const BoundingBox& b, const Vector2f& dir_axis) -> int {
			// The heuristic is mainly the distance from the source to the target along the specified direction. In
			// addition, the following factor determines the penalty for being outside the projected area of the element in
			// the given direction, as a multiplier of the cross-axis distance between the target and projected area.
			static constexpr int CrossAxisFactor = 10'000;

			const int main_axis = int(a.min[axis] - b.max[axis]);
			if (main_axis < 0)
				return Infinite;

			auto a_centroid = (a.min + a.max) * 0.5f;
			auto b_centroid = (b.min + b.max) * 0.5f;

			const Axis cross = Axis((axis + 1) % 2);
			const int cross_axis = Math::Max(0, int(b_centroid[cross] - a_centroid[cross])) + Math::Max(0, int(a_centroid[cross] - b_centroid[cross]));

			// Prefer elements that are touching; these always get the lowest heuristics
			// regardless of distances.
			static constexpr int TouchingFactor = 10'000;

			if (main_axis == 0 && cross_axis == 0)
			{
				auto ab_axis = (a_centroid - b_centroid).Normalise();
				auto dot = 1.0f - fabsf(dir_axis.DotProduct(ab_axis));
				return (int) abs(dot * TouchingFactor);
			}

			return TouchingFactor + (main_axis + CrossAxisFactor * cross_axis);
		};

		switch (direction)
		{
		case NavigationSearchDirection::Up: return CalculateHeuristic(Vertical, source, target, { 0.0f, -1.0f });
		case NavigationSearchDirection::Down: return CalculateHeuristic(Vertical, target, source, { 0.0f, 1.0f });
		case NavigationSearchDirection::Right: return CalculateHeuristic(Horizontal, target, source, { 1.0f, 0.0f });
		case NavigationSearchDirection::Left: return CalculateHeuristic(Horizontal, source, target, { -1.0f, 0.0f });
		}

		RMLUI_ERROR;
		return Infinite;
	}

This seems to work in my limited testing. I can file a PR for it soon (after cleaning it up a bit) and will play with it locally before I do so.

EDIT 2: updated code above; the min/max for cross axis appears to be incorrect, it seems to cause it to prefer elements to the side rather than straight. Using the centroid seems to work better.

[mikke89]

Yeah, I tested that example you give, and that is definitely not great behavior.

I did test your suggested solution. While it works much better for that sample, it doesn't really do what I'd expect in our existing cases. In particular, try it on the forms in the demo sample, as well as our navigation_01.rml, and navigation_02.rml visual tests.

Whatever solution we end up with, I think it is more important that it is predictable, rather than complicated and mostly right. I'm sure we could improve the current one without introducing much more complexity. In any case, I also think it would be useful to first discuss by words or illustrations what we are trying to optimize for, before we design new algorithms.

On a related note, I do like the suggestion with having multiple IDs as fallbacks.

[Paril]

Yeah any kind of heuristic we use is going to be wrong in some cases, but I suppose that can't be helped. I wonder if a debug view would be helpful, to see the heuristic outputs on all compatible elements with the currently focused element.

There's a good spec here for the implementation in browsers:
https://wicg.github.io/spatial-navigation/demo/
https://drafts.csswg.org/css-nav-1/#processing-model

Surprisingly, even on Chrome, the default behavior of spatial navigation right now is not great. I suspect there really is no good solution and it's best to just find something simple, and leave the developer to handle edge cases...

Would it be useful to allow developers to override heuristics (via event, perhaps)?

[mikke89]

Yeah, I've played with that demo myself, and wasn't really convinced. Even despite they are trying to be clever.

I don't think overriding the heuristic is the right approach either, that would be very expert level, and probably go unused and unmaintained. I'd rather keep the focus on good defaults, with possible user overrides.

I think we could adjust the algorithm in a couple of ways:

• Don't consider elements that are only touching the area along the projected direction. Rather, require that they have some (non-zero) overlapping area.
• Use shrink-rounding for the rectangles in case floating point precision makes an element barely overlap a projected area.

I believe this would solve the issue for the sample you posted, without negatively affecting much else. At least I can't think of a use case where the current behavior would be preferable over this.

Another thing we could consider: An option to choose a different algorithm that simple follows the document DOM in the arrow direction. (i.e. down/right is in tree order, up/left is in reverse tree order). Essentially, emulating the current tabbing-behavior, which might be more robust in certain cases. Strictly speaking, this wouldn't be spatial navigation though.

And finally, the third change I'd like is the fallback behavior with multiple IDs.

[Paril]

Okay. After reading your reasoning, makes sense to me. If developers wanted to provide their own spatial navigation they can just forego nav entirely, so fair enough.

For the fallback behavior, do you think multiple IDs is the better approach, or should it simply check the disabled object to see where it would have naturally been pointed to? For instance:

<div id="video" style="nav-up: #input; nav-down: #display;" class="item">Video</div>
<div id="display" style="nav-up: #video; nav-down: #input;" class="item not_console">Display</div>
<div id="input" style="nav-up: #display; nav-down: #video;" class="item">Input</div>

In this case, I think it's fair to assume that developers would want Video to skip straight to Input on a down press if #display is unavailable. The multiple IDs thing I mentioned was another suggestion to work around it, but I think this makes more logical sense (you're still using the nav graph, but "skipping over" missing elements).

I can't really think of a case where a developer would want the user to select nothing if they are on #video and press the down arrow. It seems like a flaw in the spec - granted the spec did mention that this fallback behavior was something that could be done to fix it.

[mikke89]

If the user explicitly states an ID, we shouldn't start selecting anything else. That would be very unexpected in my view. I am much more in favor of the fallback behavior with multiple IDs.