Re: [AD] new GUI focus selection algorithm

[Eric Botcazou <ebotcazou@xxxxxxxxxx>]

> Ok, improved patch attached.

Thanks.  I think the algorithm is now good enough.  I've made some 
modifications, the result is attached.

> I also put in the exclusion of D_HIDDEN and D_DISABLED objects, since with 
> qsort's O(n^2) worst case that should give a huge performance boost :)

Fine.

-- 
Eric Botcazou

--- /home/eric/cvs/allegro/src/gui.c	Sat Nov 29 08:25:22 2003
+++ allegro/src/gui.c	Sat Nov 29 20:07:13 2003
@@ -18,6 +18,8 @@
  *
  *      Eric Botcazou added the support for non-blocking menus.
  *
+ *      Elias Pschernig and Sven Sandberg improved the focus algorithm.
+ *
  *      See readme.txt for copyright information.
  */
 
@@ -505,6 +507,12 @@
    int diff;
 } OBJ_LIST;
 
+/* Weight ratio between the orthogonal direction and the main direction
+   when calculating the distance for the focus algorithm. */
+#define DISTANCE_RATIO  8
+
+enum axis { X_AXIS, Y_AXIS };
+
 
 
 /* obj_list_cmp:
@@ -547,14 +555,62 @@
 
 
 
+/* min_dist:
+ *  Returns the minimum distance between two dialogs.
+ */
+static int min_dist(AL_CONST DIALOG *d1, AL_CONST DIALOG *d2, enum axis main_axis)
+{
+   int x_left = d1->x - d2->x - d2->w + 1;
+   int x_right = d2->x - d1->x - d1->w + 1;
+   int y_top = d1->y - d2->y - d2->h + 1;
+   int y_bottom = d2->y - d1->y - d1->h + 1;
+
+   if (main_axis == X_AXIS) {
+      y_top *= DISTANCE_RATIO;
+      y_bottom *= DISTANCE_RATIO;
+   }
+   else {
+      x_left *= DISTANCE_RATIO;
+      x_right *= DISTANCE_RATIO;
+   }
+
+   if (x_left > 0) { /* d2 is left of d1 */
+      if (y_top > 0)  /* d2 is above d1 */
+         return x_left + y_top;
+      else if (y_bottom > 0)  /* d2 is below d1 */
+         return x_left + y_bottom;
+      else  /* vertically overlapping */
+         return x_left;
+   }
+   else if (x_right > 0) { /* d2 is right of d1 */
+      if (y_top > 0)  /* d2 is above d1 */
+         return x_right + y_top;
+      else if (y_bottom > 0)  /* d2 is below d1 */
+         return x_right + y_bottom;
+      else  /* vertically overlapping */
+         return x_right;
+   }
+   /* horizontally overlapping */
+   else if (y_top > 0)  /* d2 is above d1 */
+      return y_top;
+   else if (y_bottom > 0)  /* d2 is below d1 */
+      return y_bottom;
+   else  /* overlapping */
+      return 0;
+}
+
+
+
 /* cmp_right:
  *  Comparison function for right arrow key movement.
  */
 static int cmp_right(AL_CONST DIALOG *d1, AL_CONST DIALOG *d2)
 {
-   int ret = (d2->x - d1->x) + ABS(d1->y - d2->y) * 8;
+   int ret = min_dist(d1, d2, X_AXIS);
 
-   if (d1->x >= d2->x)
+   /* Penalize if d2 is not fully contained in the half-plan delimited
+      by d1's right edge and not containing d1. */
+   if (d2->x < d1->x + d1->w)
       ret += 0x10000;
 
    return ret;
@@ -567,9 +623,11 @@
  */
 static int cmp_left(AL_CONST DIALOG *d1, AL_CONST DIALOG *d2)
 {
-   int ret = (d1->x - d2->x) + ABS(d1->y - d2->y) * 8;
+   int ret = min_dist(d1, d2, X_AXIS);
 
-   if (d1->x <= d2->x)
+   /* Penalize if d2 is not fully contained in the half-plan delimited
+      by d1's left edge and not containing d1. */
+   if (d2->x + d2->w > d1->x)
       ret += 0x10000;
 
    return ret;
@@ -582,9 +640,11 @@
  */
 static int cmp_down(AL_CONST DIALOG *d1, AL_CONST DIALOG *d2)
 {
-   int ret = (d2->y - d1->y) + ABS(d1->x - d2->x) * 8;
+   int ret = min_dist(d1, d2, Y_AXIS);
 
-   if (d1->y >= d2->y)
+   /* Penalize if d2 is not fully contained in the half-plan delimited
+      by d1's bottom edge and not containing d1. */
+   if (d2->y < d1->y + d1->h)
       ret += 0x10000;
 
    return ret;
@@ -597,9 +657,11 @@
  */
 static int cmp_up(AL_CONST DIALOG *d1, AL_CONST DIALOG *d2)
 {
-   int ret = (d1->y - d2->y) + ABS(d1->x - d2->x) * 8;
+   int ret = min_dist(d1, d2, Y_AXIS);
 
-   if (d1->y <= d2->y)
+   /* Penalize if d2 is not fully contained in the half-plan delimited
+      by d1's top edge and not containing d1. */
+   if (d2->y + d2->h > d1->y)
       ret += 0x10000;
 
    return ret;
@@ -631,7 +693,8 @@
 
    /* fill temporary table */
    for (c=0; d[c].proc; c++) {
-      if ((*focus_obj < 0) || (c != *focus_obj)) {
+      if (((*focus_obj < 0) || (c != *focus_obj))
+	  && !(d[c].flags & (D_DISABLED | D_HIDDEN))) {
 	 obj[obj_count].index = c;
 	 if (*focus_obj >= 0)
 	    obj[obj_count].diff = cmp(d+*focus_obj, d+c);