Tog on Hierarchical Menu

Khan Academy の開発者が Amazon.com の高速なメニュー切り替えを行う実装について、面白いブログを書いていたので、メモ。

BREAKING DOWN AMAZON’S MEGA DROPDOWN
http://bjk5.com/post/44698559168/breaking-down-amazons-mega-dropdown

階層メニュー

Amazon.com の department メニューや Windows のスタートメニューでお馴染みの、メインカテゴリーとサブカテゴリーというように階層になったメニューがある。Web UI 界隈では mega drop-down menu という名前が付いている模様だけど、Mac だと 80 年代から存在する。

UX 視点では

  • 上下のメインカテゴリー移動
  • メインカテゴリーからサブカテゴリーへの移動

の2つのメニュー操作が肝。

amazon-fast-2

サイト提供者としては、この操作を出来る限り直感的にスムーズに行えるようにしたい。

Evolution of Hierarchical Menu

階層メニューの先人たちの実装を振り返る

案1:ナイーブ実装

メインメニューにフォーカスがあるときだけ、ぶら下がるサブメニューを開くようにする。
問題点としては、メインからサブに移動するときに、斜め移動などでメインメニュー以外の領域にフォーカスが当たると、サブメニューが閉じてしまう。
使いにくい。

bootstrap-bug

案2:タイムラグ(Hysteresis)

いにしえの Windows では、サブメニューを開く/閉じる時に若干のタイムラグが発生するようにした。
こうすると、斜め移動しても素早く移動する限りサブメニューは開いたままになる。
一方で、メインメニューが切り替わっても、サブメニューが開くまでワンテンポある。

old

案3:Tog/Amazon.com アルゴリズム

案1の斜め移動と案2のタイムラグを解決するために、フォーカスの位置とサブメニューの上下で三角形(バッファー領域)を描く。

screen_shot_2013-03-06_at_1.17.35_am

実際のマウス操作を考えるとわかるように、フォーカスがこの三角形内を移動すれば、メインからサブに移動しているとみなせ、三角形の外に出ると、メインメニューを移動しているとみなせる。
こうすると、三角形の中を移動する限り斜め移動してもサブメニューは閉じず、上下にメインメニュー移動すると、その動きを素早く察知して、サブメニューが展開される。

この UI は有名どころでは Amazon の Department 選択で採用されている。

おどろくべきことに、この三角形のバッファー領域を使ったアルゴリズムは 1986 年には Mac で実装されていた。
惜しむらくは、Mac が NeXT を買収後、NeXT の開発者は Windows を参考に OS X のメニュー UI を実装したらしく、メニューの利便性が後退した。

Khan Academy の元ブログでは、当時 Apple でこのアイデアを考案した Bruce “Tog” Tognazzini 本人が降臨してコメントしている

Yes, I did invent it back in 1986 and it is firmly in the public domain. From what I remember, it was Jim Batson who worked out the math and coded it for the Mac OS. The OS X team later failed to copy the algorithm, so I am happy to see that amazon has resurrected it.
http://bjk5.com/post/44698559168/breaking-down-amazons-mega-dropdown#comment-826229392

Bruce “Tog” Tognazzini は自身のサイトでも、この階層メニューについて記事を書いている

Question 6 : What is the bottleneck in hierarchical menus and what techniques could make that bottleneck less of a problem?
http://www.asktog.com/columns/022DesignedToGiveFitts.html

案4:最近の Windows

手元の Windows 7 は、案2 と 案3を組み合わせている。
斜め移動に対応する一方で、サブメニューの出し入れはタイムラグがある

Tog/Amazon のアルゴリズム

フォーカスが三角形のバッファーエリア内にあると判定できるのか?

勾配を利用

Khan Academy が開発した jquery プラグインでは、フォーカスが動いた時に、移動前後でサブメニューの上下の両端との勾配を求め、両方の勾配が急になると三角形内を移動していると判定している。少なくとも片方の勾配が緩くなっていれば、メインメニューの移動と判定している。

focus_movement

単純明快で非常に良くできている。

実際のコードは以下

https://github.com/kamens/jQuery-menu-aim/blob/master/jquery.menu-aim.js#L215-L242

// We detect this by calculating the slope formed between the
// current mouse location and the upper/lower right points of
// the menu. We do the same for the previous mouse location.
// If the current mouse location's slopes are
// increasing/decreasing appropriately compared to the
// previous's, we know the user is moving toward the submenu.
//
// Note that since the y-axis increases as the cursor moves
// down the screen, we are looking for the slope between the
// cursor and the upper right corner to decrease over time, not
// increase (somewhat counterintuitively).
function slope(a, b) {
    return (b.y - a.y) / (b.x - a.x);
};

var upperSlope = slope(loc, upperRight),
    lowerSlope = slope(loc, lowerRight),
    prevUpperSlope = slope(prevLoc, upperRight),
    prevLowerSlope = slope(prevLoc, lowerRight);

if (upperSlope < prevUpperSlope &&         lowerSlope > prevLowerSlope) {
    // Mouse is moving from previous location towards the
    // currently activated submenu. Delay before activating a
    // new menu row, because user may be moving into submenu.
    lastDelayLoc = loc;
    return DELAY;
}

座標について

注意点としては、jquery は JavaScript で実装されているため、座標の入り方も JavaScript に従う。

coordinate

したがってメニューの upperRight と lowerRight は以下のようになる。

var offset = $menu.offset(),
    upperRight = {
        x: offset.left + $menu.outerWidth(),
        y: offset.top - options.tolerance
    },
    lowerRight = {
        x: offset.left + $menu.outerWidth(),
        y: offset.top + $menu.outerHeight() + options.tolerance
    },

間違っても、数学でよく見かける座標が入っているわけではない。

後者の座標で勾配を求めると、フォーカスが移動した時の大小関係が狂う。
普段 JavaScript を書かないオジサンは要注意。

クロス積を利用

元の投稿の文末によると、 Amazon の開発チームはクロス積を使って実装している。

Thanks go to Ben Alpert for helping me understand the linear algebra / cross-product magic Amazon uses to detect movement inside the “blue triangle.” I ended up going w/ a cruder slope-based approach, mostly b/c I’ve lost all intuitive understanding of linear algebra. Sad. Need to watch more KA videos.

クロス積の定義を読んで少し考えてみたけど、自分はわからなかったので、若い人のために left as an exercise にしておこうかと思う。

Further Reading

tog-on-interface

Advertisements
Tagged with: , , , ,
Posted in algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
%d bloggers like this: