[openbox] Direction focus algorithm

[Tore Anderson]

* Clay Barnes

> I haven't use the most recent build of OB3 yet, so this may have
> changed, but I've noticed a few strange focus patterns with
> DireectionFocus(N|S|E|W), including that if you focus across a couple
> apps in one direction, but try to go back the other direction, they
> don't always traverse the same windows.  Don't get me wrong, it does
> very well most of the time, I'm just trying to figure out what's
> causing the issue.
> 
> Example of case where the issue arises:
> .---------.---------.
> |        2|        3|
> |         |         |
> |         |         |
>> --.      |         |
> | 1|      |         |
> '--"------'---------'
> Select goes west from 3 to 2 to 1, but when going east goes straight
> from 1 to 3.
> 
> My question is, is window selection based on the center of the window
> or the edges?  I suspect it's center-based, because then I can imagine
> that 2's center is too "diagonal" to get hit from 1.  However, it
> seems like there might be a slightly less quirky way to design this.
> (Going east/west, the next center (considering only the X ordinate)
> would always be the next selected, and if several are the same X (+/-
> some % of the screen to keep 1-pixel shifts from dictating the order),
> the one with the closest Y ordinate would be selected, for example.
> Or something that considers edges, etc.)

   It is based on center-to-center.  The algorithm is from FVWM2, and I
  don't think I changed it much (might have been modified since OB3.0 but
  to me it feels unchanged).  If it's the same, it counts the distance
  in pixels from the centre of the currently focused window to the centre
  of all other windows.  The distance is calculated by adding the catheti
  together, the absolute distance isn't used (unless the length of one of
  catheti is 0, of course).

   The window that has the lowest distance wins and are focused.  Some
  windows are disqualified, such as windows that are found in the
  opposite direction and iconified windows.  Also if a window is more
  than 45° off the requested direction (ie. the length of the cathetus
  crossing the requested direction is longer than the cathetus parallel
  to the direction), it is penalized by having a lot added to the length
  (but not disqualified).

   This I assume is the reason for the behaviour you find strange, when
  going east from window 1, the centre of window two is more than 45°
  off, penalised, and therefore window 3 wins (if you instead had
  requested north, window 2 would've won).  When going in the opposite
  direction, 3->2 is easy to see why is happening, and 2->1 happens even
  though the centre's more than 45° off, because there's no other window
  in the westbound direction anyway.

   The reason for using centres is to be able to go between window even
  though they're slightly overlapping.  For instance, using the edges
  would make it impossible to go east/west between two windows arranged
  like this:

          +-----+
     +-----+    |
     |     |    |
     |     |----+
     +-----+

   ...even though it would appear logical expect it to work.  At least I
  do.

> I'll think about algorithms in case you decide to change anything.  I
> know it's a low priority, though, since it's already good and changes
> might have a lot of unexpected consequences.

   Well, the directional focus kept me returing to fvwm although I hated
  almost everything else about it, so OB3 was a nice opportunity for me
  to finally do something about it as it had something very rare; a code
  base so nice a mediocre programmer like me I could understand and hack
  on so I ported the directional focus and added the grow/movetoedge
  actions also.  Since then I've been very happy with how it has worked
  so I'm not really interested in diving into it again, but if you too
  have an itch to scratch I'm sure we'll all gain from that.  Look into
  openbox/client.c, the function is called client_find_directional() if
  I remember correctly.

   I think maybe the first thing I'd do if I were you was to try out
  modifying it so that the absolute distance is used instead of adding
  the catheti, using the hypotenuse instead.  Possibly the windows with
  offset from the direction should still be penalised, but the 45° limit
  is arbitrary and too sudden.  Maybe adding distance according to some
  formula, increasing penalty logarithmically depending on how many
  degrees the window is off.  Hmm.  Also there's the problem of big
  windows next to a small window will be penalised needlessly, ie. in a
  situation like

       +-+ +--+ +-+
       |A| |B | |C|
       +-+ |  | +-+
           |  |
           |  |
           |  |
           |  |
           |  |
           +--+

   you might end up not being able to end up at C by going east from A or
  west from C, that you instead have to go south from both which feels a
  bit odd.  Not sure how to best deal with that though.  I guess an
  algorithm that always ends up doing what you mean/expect to happen is
  the optimal, but probably tricky to implement completely.  Good luck
  though!  ;-)

Regards
-- 
Tore Anderson