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?

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?

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.

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.

Well, since Alec doesn't want this bug, I'll take it.

> 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.

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

aaron: is this related to something you have fixed recently?

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.

Bulk adding topembed keyword. Gecko/embedding needed.

topembed-, aaron, please renominate if this is important

Corfirming topembed- [T2] per EDT triage.

You have to consider a link with split content like: [123 456] two be two focusable nodes (frames) for the purposes of directional navigation.

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. ***

I guess I should take this.

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.

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.