Closed Bug 67684 Opened 24 years ago Closed 18 years ago

Directional keyboard navigation needed (alt+shift+arrow?) (spatial navigation)

Categories

(Core :: DOM: UI Events & Focus Handling, enhancement, P3)

Product:
Core
Component:
DOM: UI Events & Focus Handling
Type:
enhancement

Tracking

()

Status:
RESOLVED WORKSFORME
Milestone:
Future

People

(Reporter: jesup, Assigned: dougt)

References

Details

(4 keywords, Whiteboard: [T2][wgate] parity-opera) 

This exists in a few other bugs but I thought it should have it's own entry,
since those others also involve other things.  See bug 58852 and bug 66285.

We need some form of directional navigation both for accessability and for use
in embedded products that might not have random-access pointing devices.

When used in this fashion, certain keys (probably arrow keys) would move the
highlight to the next link in the appropriate direction.  "next link" should
probably be defined as some form of cone starting at the current link.  Frames
need to be handled as well - one possibility would be to scroll so the edge of
the current frame is displayed, and if the current frame is already fully
scrolled in that direction, hop to the next frame in that direction.  If it's
the edge of the display, wrap around to the other side (either other side of the
frame, or maybe the other side of the display).

This will also need to be integrated with the widget handling, so navigation out
of a text widget is possible, etc.

I can provide some resources to work on this, but I'd like help and/or guidance
from people who are interested and know what way it can best be integrated with
mozilla.
Directional navigation should certainly straddle frames, but IMO there usually 
aren't enough frames on a Web page for directional navigation of just frames to 
be worth it.

The code for handling the navigation would follow the following outline:
*   determine minimum and maximum angles from the navigation direction (e.g.
    left == from 225 degrees to 314.99999 degrees);
*   calculate the coordinates (x2, y2) of the center of each navigable element,
    and make a set of those elements which have coordinates in the appropriate
    range of angles relative to the center of the currently focused element (x1,
    y1);
*   move focus to the element in the set for which sqrt((x2-x1)^2 + (y2-y1)^2) is
    smallest (scrolling the element into view, if necessary).

What exactly does this have to do with embedding?
Keywords: access, embed
Summary: Directional keyboard navigation needed (accessability, embedding) → Directional keyboard navigation needed
Agreed; the navigation should just hop to the next frame as appropriate.

What it has to do with embedding is that not every embedded application has a
pointer; some will only have simpler (directional) pointing devices.  Think of a
kiosk; or a WebTV; or a video game consol; or this Nokia mozilla-based thing,
etc.

There are two things I'm interested in.  One is exactly how should directional
navigation work from a UI perspective (which direction will take you to which
link under which circumstances, etc).  More important to me right now, though,
is what mechanism can be used to hook into mozilla to do this - are the hooks we
need there?  How do we get the information we're going to need?  Etc.  I can
devote some resources to getting those hooks in, but I don't know gecko/etc
objects well enough to know wheere to start.

Which direction will take you to this link is described by my algorithm above. A 
mathematician could probably prove to you that the algorithm won't leave any link 
unreachable.

As regards finding the (x,y) coordinates of the objects, ask some DOM or Layout 
people. I would be surprised if everything we need in that area doesn't already 
exist.

Actually, since you're using the centers of objects it's very easy to miss
links.  Check this example:

xxx                      xxx


            xxx



xxx                     xxx

If the angle you choose is smallish (say 30 degrees), the four corner links will
go to each other, and none of them will go to the center link.  If you choose a
very wide angle, the problem (mostly) goes away, but then it's confusing (and in
fact creates new cases where you can miss a link because you get "drawn" to the
side by a diagonal of links, etc).  Some sort of "next-link" (Tab) functionality
may give you an 'out' to get to an unnavigable link, but it's not a great
solution.

Like I said, making a fully-navigable setup is not simple, and making one that
"feels" good (and deals with imagemaps (server and client)) is much tougher.  So
I want to concentrate on the hooks first, so people can work/argue over what the
appropriate algorithms are.

Any DOM/layout people want to comment?
Keywords: helpwanted
Randell, see my 2001-02-05 comment. Each arrow key would look for the nearest 
item in a 90-degree sector around the cardinal compass point. With that, there 
would never be a link you couldn't get to.
Ok, for very wide angles (in addition to being very confusing to users), you
have this problem:

ccc
   xxx
      xxx
         xxx
            xxx
aaa            bbb

Node aaa cannot be reached.  Down from ccc goes to an xxx link.  Left from bbb
goes to an xxx link.  Etc.

None of this means you can't make a reasonable algorithm for directional
navigation - many people have done so, including me.  It's just not that simple.

yikes, I don't have time for this, but anyone else is welcome to take this.
Status: NEW → ASSIGNED
Priority: -- → P3
Target Milestone: --- → Future
Randell, please provide the x and y coordinates of the simplest collection of 
links you can think of where directional navigation to one of the links would not 
be possible with my algorithm. (E-mail me, if you don't want to clutter this bug 
with them.) Otherwise, I think you are mistaken.

mpt: <img usemap=#pixMap> where <area name=pixMap> includes the required pixels 
given by Randell Jesup 2001-02-08 08:40.
No, that example works fine with my algorithm. aaa is at a compass angle of 180* 
with respect to ccc, and (the top-left-most) xxx is at a compass angle of 
approximately 109.4* with respect to ccc. So Alt+Shift+Down from ccc would go to 
aaa, as expected, since 135* <= 180* < 225*; it would not go to xxx, since 135* 
!<= 109.4*. And Alt+Shift+Right from ccc would go to xxx, as expected, since 45* 
<= 109.4* < 135*; it would not go to aaa, since 180* !< 135*.

You forgot the part of your algorithm that says "move to the node with the
smallest distance from the current node".  The first xxx is FAR closer.  This is
assuming a large angle on each side such that xxx is included.  I can always
contruct a case where this is a problem for any given angle (though it's far
more of a problem for large angles, say 45* or more to each side).  For narrow
angles, you have the problem I first mentioned, where a node is always jumped
past.

There are solutions to these problems, though they get more "fun".  You could
calculate a mesh and require (force) all nodes to have links, warping the mesh
if needed.  You could minimize the problem by using more than one angle
depending on distance.  You could  side-step the problem by assuming they can
also use the "next link" and "previous link" keys (Tab/shift-Tab or whatever). 
Etc.

Once again, if someone gives me some ideas where/how the hooks for this can be
added, I can devote some resources to getting the hooks in that would allow
people to actually try these things out.

reassigning to nobody@mozilla.org because I am never going to implement this and
the amount of bug traffic this is generating is wasting my time.
Assignee: alecf → nobody
Status: ASSIGNED → NEW
Well, since Alec doesn't want this bug, I'll take it.
Assignee: nobody → rjesup
Status: NEW → ASSIGNED
> You forgot the part of your algorithm that says "move to the node with the
> smallest distance from the current node".  The first xxx is FAR closer.

I didn't forget anything. How close or far xxx is is completely irrelevant, 
because it's outside the 90-degree sector (as described in my 2001-02-05 comment) 
for the down direction. You appear to have ignored that part of the algorithm 
(I'm sure you didn't do it on purpose).

> I can always contruct a case where this is a problem for any given angle

Go ahead, I'm still waiting. :-) By the way, if you want help from DOM or layout 
people to tell you where the hooks are, then e-mail them. They're not going to 
magically appear in this bug.

Ok.

 aaa

   xxx

     xxx

       xxx

         xxx

           xxx

             xxx

               xxx

                 xxx
                  xxx
                   xxx
                      xxx

                          xxx

bbb                            ccc


So, from aaa or ccc (or any xxx), how do you get to bbb with a 90* angle? 
Admittedly, for 90* it's hard to have a problem - but they can exist.  And
perhaps the best solution is to ignore that there's an edge case, and instead
assume directional arrows plus a next-link ability to deal with unlikely cases.

If you widen the 90*, the problem above gets worse.  If you narrow it, you have
the first problem:

xxx                  xxx



          xxx




xxx                  xxx

On top of that, links aren't all the same size, so using centers can be very
confusing.  For example:

   aaa




           bbb
cccccccccccccc

Going up from 'c', people would probably assume it'd go to 'b', but it would
actually go to 'a'.  You could get to 'b', but only by going _right_ from 'c' -
very non-intuitive.  A better algorithm might be to take a link as a rectangle,
and then fan out from the two appropriate ends.  (That still leads to some
confusion in the case above - down from 'a' goes to 'c' - but at least up from
'c' goes to 'b'.)

As for contacting DOM/layout people, I will.  I had been hoping that the person
in charge of keyboard navigation (Alec) would give me a starting point.
> So, from aaa or ccc (or any xxx), how do you get to bbb with a 90* angle?

From the xxx which is third from the bottom in the set of xxxes, pressing
Alt+Shift+Left goes to bbb, since 225* <= 255.3* < 315*. (It does not go to the 
xxx above it, since 315* !< 315*; the xxx above it is instead reached by
Alt+Shift+Up, since 315* <= 315* < 405*.)

I admit that it isn't the most intuitive algorithm, but it is the simplest to 
implement (you may even be able to rearrange the Bresenham line-drawing algorithm 
somehow to get rid of the trigonometry), and I'm pretty sure it always works -- 
your example is the worst case I could think of when I first proposed it (and you 
have to admit it's a pretty unlikely case), but it still worked. Constructing a 
mesh would, as you say, probably give more intuitive results, but the amount of 
processor time and memory time involved might well mean that it was too slow to 
be usable.

> If you widen the 90*, the problem above gets worse.  If you narrow it

I do neither.

Hmmmm....  I'd been thinking of +-45 as inclusive, not exclusive.  Exclusive
does leave a theoretical hole for the node-in-the-middle case (if it's exactly
45 degrees from all of the 4 nodes around it) but that's not an important hole.

Hmmm.  If you're using exclusive, what about this?

x
 x
  x
   x

(Where the angles between nodes are all 45 degrees.)  Neither up nor left nor
right nor down would get you from any of those nodes to another.

> Hmmm.  If you're using exclusive

I'm not. I'm sorry to have to say this, but ... Read my 2001-02-05 comment again, 
particularly the numbers given in the first bullet point.

In your latest example, Alt+Shift+Down would take you from the first x to the 
second (and so on down the line), since 135* <= 135* < 225*. (Alt+Shift+Right 
would not have the same effect, since 45* <= 135* !< 135*.) Similarly,
Alt+Shift+Up would take you from the second x to the first, since 315* <= 315* < 
405*. (Alt+Shift+Left would not, since 225* !<= 315* !< 315*.)

Aha.  Sorry, I misunderstood your algorithm (or rather didn't read it carefully
enough).

Ok.  I'm going to concentrate on the other issues involved (i.e. the hooks). 
Also, hooks will probably be needed in the editor (and other) widgets as well I
believe, depending on how we want to "escape" a text widget.

Thanks for pointing out my mistake.  Your algorithm will guarantee navigability
I believe, though as we said it may produce some "surprising" linkages to the
user.  I do think considering links as rectangles instead of points has
advantages from a user-expectation point-of-view, though I haven't given any
thought to how it would interact with your algorithm.

In any case, those issue can wait until we have something that works and can be
used as a testbed.
Summary: Directional keyboard navigation needed → Directional keyboard navigation needed (alt+shift+arrow?)
Here's a page where directional navigation would be useful:
http://www.gwydir.demon.co.uk/giles/javalife.htm
Directional navigation would be very tough on that page - it's Java.  The
problem with Java is that we don't know what spots are hot, what it does with
keypresses or mouse/etc movements, highlighting really can't be done, etc.  Java
browser applets simply assume you're using a mouse or equivalent.
Actually, that page is just HTML and JavaScript :)  The board tiles are images 
in links, so they can be focused, and pressing enter with a tile focused 
toggles whether the tile is alive.  The problem is that to get from the top of 
the board to the bottom requires hitting tab more than a hundred times.
Sorry - I saw the "javalife" and assumed it was actually java.
You're right - directional navigation is great for this.
One way to hook it up:

The xpfe/browser/resources/content/nsBrowserStatusHandler.js file in the chrome
contains a web progress listener. In the onStateChange function one could add
code for initializing the directional navigation when a page has loaded, and
code for clean up when a page is left.

Directional navigation will be way too slow to do in JS, so the code should be
implemented in C++ (an simple XPCOM object will do). As for getting the key
events, it can be done by extending the key/broadcaster-set in the chrome.

The XPCOM interface could look like this:

InitNavigation(nsIDOMWindowInternal win);
FreeNavigation();
GoLeft();
GoRight();
GoUp();
GoDown();

where the JS window object is passed down to the C++ code where becomes a
nsIDOMWindowInternal. From that window the DOM may be traversed.

The web progress listening stuff can surely be done from C++, but how do one get
the events in that case?

added myself to cc list

Just a note: Alt+Shift as well as Ctrl+Shift are key combinations that Windows
uses to switch between keyboard layouts on machines with multiple input locales.
So using these combinations can break Mozilla's internationalisation on Windows.
Alexey,

I was not aware of that. Can you be be specific?

Alt+Shift+arrow, Ctrl+Shift+arrow?
Or Alt+shift/Ctrl+shift by themselves without another key?
{left-alt}-shift.
or
ctrl-shift.

also either of above + any digit, ~ or `

basically forget this =).
Alt+Shift+arrow are default keybindings if you are using the enlightenment WM.
It allows you to cycle around virtual desktops. 

Seems Ctl+arrow might be a good choice, it doesn't seem to bind to anything on
unix, win or mac.

--pete

Ok, i hooked up the Ctl+arrow key bindings.

So if you hit Ctl->Left or Ctl->Right you move back and forth respectively.
Same w/ Ctl->Up and Ctl->Down.

Right now i am just using ShiftFocus() until i write an implementation for the
actual navigation.

--pete
Different WM's hijack different variations on the modifier-plus-arrow keys. 
fvwm95 snags control-arrow by default.  My configuration of Sawfish (with Gnome)
is also set for control-arrow because I'm used to it.  I imagine ANY sequence we
pick will cause problems for someone or some platform or some WM.  That said, a
default of control-arrow might not be bad, so long as it can be changed (a
UI/pref would be nice, but that can come afterwards).
Okay, ctrl+arrow is cool for this.

Ctrl+left/right in textfields/textareas, as well as in caret browse mode, is
should move the caret by one word -- make sure that still works.
It sounds like that leaves us with...

Tab and Shift+tab                   Move between form elements in structural order
Ctrl+arrow and Alt+Shift+arrow      Move between links as positioned on screen
F8                                  Leave form element

Will there still be a way to move between links in the structural order?
Is this directional keyboard navigation supposed to include form elements?

If so, Ctrl+left/right arrow won't work very well when the are editable fields
in what the user is navigating.

I'm tempted to say we should use the numeric keypad.

Argh, and this would be such a great feature with the right keybindings.
To be honest, hooking in the keys is the easy part.  ;-)

Ctl+arrow seems to work ideally for me on my test page across links and various
form elements.

The only thing i noticed is when using it in the editor, Ctl+ left | right will
increment the cursor.

As far as the keys go, it is just a matter of finding the right combination w/
the arrow keys. You do need to use the arrow keys, because they are the most
intuitive and universal across different types of input devices.

--pete
One thing to realize is that "directional" navigation tends to be a different
mode of interaction from "normal" interaction.  This might affect some of our
decisions.

In particular, when within a edit field (line or textarea), you may need to
either override the normal behavior of the sequence, OR modify the behavior to
extend the edit behavior.  For example, if ctrl-arrow is word left/right (what
are up/down?), then you might override the behavior when it hits the boundaries.

In particular, for people who have problems with fine motor control, etc, it
would be HIGHLY advantageous to have link navigation on the plain
up/down/left/right arrow keys.  To make this work, you'd need to handle edit
boxes by having arrows move you out of the edit field when you hit an edge,
perhaps combined with some behavior to not go "into" an edit box unless you
select it while navigating links and form elements.

i.e. navigating around.  nagivate to a text area.  If you hit
left/right/up/down, it goes to whatever is left/right/up/down from the text box.
 If you type a character, or select (enter), focus goes into the text area and
now arrows work within the text area to move the caret.  If you hit the edge of
the text area and continue to move in that direction, it moves focus out of the
text area to the next link in that direction.

Think "How would I use a browser if I could only use l/r/u/d, a select button,
and some form of popup keyboard or speech recognition or ... to type" - and no
modifiers (no holding one key while pressing another).
If we implemented it so that hitting Ctrl+left, Ctrl+right, left or right past
the end of a text field focused the next item, that would be bad for
accessibility, especially for blind users.

I agree that we will need a one handed keyboard mode sometime in the future, but
that's in a different bug.

I think we might be stuck with Alt+shift+arrow. We might get away with using
just shift+arrow, even though that normally is used for selection.

Anyway, as Pete says - the hardest part is getting it working at all. We'll
figure out the best keybindings for it at some point.

No Aaron, the way it is now, it will focus the text item not skip over it. 

Picute tabbed navigation using the arrow keys. I don't think that behavior
should change.

Randell, yes, i understand exactly what you are saying. 
I think there are two issues here. 

One is a specific key binding.
The other is the implementation for omnidirectional tabbed navigation.

If you want omnidirectional tabbed navigation for a PC, you bind X-modifier w/
the arrow keys.
If you want omnidirectional tabbed navigation for a different input device, you
bind to different keys (eg: arrow only).

The point is the implementation is there for whatever key binding one needs.

Perhaps as suggested a default binding set can be established. Then a pref for
alternative bindings (eg: arrows only).

--pete
Pete: exactly.  I suspect that trying to have every variation active at the same
time will be a Bad Thing UI-wise; the best solution will probably be to specify
(via a pref) what sort of interface you'd like (i.e. what keybindings).

This does spill over into things like form controls if you want to be able to do
things like overload arrow keys (no-modifiers-mode).  We can open subsidary bugs
for that as needed.

The tricky parts are things like how to handle frames, iframes, imagemaps,
server-side imagemaps, java/etc objects, etc.
Right, i think abstracting bindings into prefs needs to be a different bug.

This bug can track progress for implementing directional keyboard navigation.

--pete


general reminder, not all keyboards have numeric keypads, and on some accessing 
the numeric keys is a royal pain.
I have implemented this in mozilla for a commercial company during a set top box
project under a two year period. I can't share the code, but if anyone would
like to ask questions concerning my experiences in this area, feel free to
e-mail me about it.

Yes, I do have some questions about your implementation. What files/methods did
you patch. Was it mostly in Javascript or C++? What were the hardest parts?
Another question for you Martin : do you think there is any chance that you can
convince your management team to open the navigation code on which you have worked ?
The whole Mozilla community could have great benefits from having this feature
available, especially disabled people for which Mozilla-the-browser seems to be
the only solution for surfing the Web (see accessibility project).
Code opening could also have strong benefits for your company : peer-review,
extended bug hunting, algorithm optimizations ... All this things could really
enhance the quality of your product and have direct consequences on sales.
Just for the record, picking a single point for each focussable element is going
to give you headaches, since focussable elements can have multiple rectangles
(and often do).

e.g.: Some worst case scenarios:

                        [bbb
                [aaa]
         bbb]

...or even:

        456]
              [ccc]
                     [123

...where the links are [aaa], [bbbbbb], [123456], and [ccc] in document order.
Right, you don't use a single center point alone, instead you use the entire
rect as your target. You record hits while traversing the frame tree pushing the
closest target into a `nextFocus' variable. When finished, the target w/ the
shortest distance is left 

When content has two nsIFrame's, the coords of the first frame  in most cases is
usually sufficient since you are traversing frames in the direction you are
going. But this situation needs specific handling.

There is no single algorithm to solve this problem. It is a layered process of
elimination using a combination of different techniques.

--pete


http://www.mindflow.dk/keynav/ has an add-on for IE that adds this feature.  I
haven't tried it.
batch: adding topembed per Gecko2 document
http://rocknroll.mcom.com/users/marek/publish/Gecko/Gecko2Tasks.html
Keywords: topembed
aaron: is this related to something you have fixed recently?
Keywords: topembed
No, I did type/search for links in bug 30088, but this is for up/down/left/right
access. This would be useful for browsing with a keypad or remote control.
Blocks: grouper
Bulk adding topembed keyword.  Gecko/embedding needed.
Keywords: topembed
topembed-, aaron, please renominate if this is important
Keywords: topembed → topembed-
Corfirming topembed- [T2] per EDT triage.
Whiteboard: [T2]
You have to consider a link with split content like:

         [123

456]

two be two focusable nodes (frames) for the purposes of directional navigation.
Whiteboard: [T2] → [T2][wgate]
Opera 7 for Windows has this feature and calls it "spatial navigation". 
Shift+Arrow keys move between links and form elements in a way similar to the
one described here.  Shift+Left and Shift+Right don't move out of form elements,
but Shift+Up and Shift+Down do.  Opera 7 still has the Ctrl+Up/Down shortcuts to
move between links (and only links) in the document order.
A Firefox extension "CrossFire" has implemented the similar concept.
http://tkm.s31.xrea.com/xul/crossfire.shtml
I've noticed, that adding a memory to cursor, is very helpful. For example
consider such link configuration:

aaa bbb ccc
ddddddddddd
eee fff ggg

if cursor stays on 'eee' and user press 'up', 'dddd' link will get activated, if
up will be pressed once again, it is natural to highlight 'aaa', but if we
started from 'fff', result should be to 'bbb', etc. Remembering single x/y
coordinates for cursor (updating x on left/right movement and y on up/down
movement) and moving to nearest x/y will result in such behaviour.
*** Bug 254260 has been marked as a duplicate of this bug. ***
Whiteboard: [T2][wgate] → [T2][wgate] parity-opera
I guess I should take this.
Assignee: rjesup → dougt
Status: ASSIGNED → NEW
Summary: Directional keyboard navigation needed (alt+shift+arrow?) → Directional keyboard navigation needed (alt+shift+arrow?) (spatial navigation)
Doug, you have an old-style extension in mozilla/extensions that fixes this right? Can't we resolve it now?
Yes.

mozilla/extensions/spatial-navigation.

marking fixed.  If you have specific complaints about how this extension works given certain conditions, please open new bugs.
Status: NEW → RESOLVED
Closed: 18 years ago
Resolution: --- → FIXED
Bugs should never be marked FIXED because of an extension that does what you want.  It should either be WONTFIX (for addition to core code) or, perhaps, WORKSFORME - assuming that the original reporter doesn't have a problem with that.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Status: REOPENED → RESOLVED
Closed: 18 years ago → 18 years ago
Resolution: --- → WORKSFORME
Component: Keyboard: Navigation → User events and focus handling
You need to log in before you can comment on or make changes to this bug.