Re: [AD] new GUI focus selection algorithm

[Elias Pschernig <elias@xxxxxxxxxx>]

On Mon, 2003-11-17 at 10:57, Eric Botcazou wrote:

> Two remarks:
> - I think that using the Euclidean distance is too costly in terms of ratio 
> benefit/overhead. After all, all distances are (mathematically) equivalent 
> and we don't care if our circles look like squares :-)
> - You should introduce a compile-time parameter in the distance formula so 
> that we can tweak the relative weight of the two axes.
> 

Ok, improved patch 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 :)

-- 
Elias Pschernig <elias@xxxxxxxxxx>

Index: src/gui.c
===================================================================
RCS file: /cvsroot/alleg/allegro/src/gui.c,v
retrieving revision 1.65
diff -u -r1.65 gui.c
--- src/gui.c	17 Oct 2003 08:49:18 -0000	1.65
+++ src/gui.c	27 Nov 2003 13:38:10 -0000
@@ -505,6 +505,12 @@
    int diff;
 } OBJ_LIST;
 
+/* When selecting the next focus object with the cursor keys, this sets
+ * the ratio of the cursor key direction to its orthogonal direction
+ * in the distance formula to 8:1.
+ */
+#define DISTANCE_RATIO 8
+
 
 
 /* obj_list_cmp:
@@ -547,17 +553,59 @@
 
 
 
+/* min_dist:
+ *  Get the minimum distance from a dialog to a rectangle.
+ */
+static int min_dist(AL_CONST DIALOG *d1, int d2x, int d2y, int d2w, int d2h,
+   int x_weight, int y_weight)
+{
+   int x_left = d1->x - d2x - d2w + 1;
+   int x_right = d2x - d1->x - d1->w + 1;
+   int y_top = d1->y - d2y - d2h + 1;
+   int y_bottom = d2y - d1->y - d1->h + 1;
+
+   if (x_left > 0) { /* d2 is left of d1 */
+       if (y_top > 0) { /* d2 is above d1 */
+           return x_left * x_weight + y_top * y_weight;
+       }
+       if (y_bottom > 0) { /* d2 is below d1 */
+           return x_left * x_weight + y_bottom * y_weight;
+       }
+       /* vertically overlapping */
+       return x_left;
+   }
+   if (x_right > 0) { /* d2 is right of d1 */
+       if (y_top > 0) { /* d2 is above d1 */
+           return x_right * x_weight + y_top * y_weight;
+       }
+       if (y_bottom > 0) { /* d2 is below d1 */
+           return x_right * x_weight + y_bottom * y_weight;
+       }
+       /* vertically overlapping */
+       return x_right;
+   }
+   /* horizontally overlapping */
+   if (y_top > 0) { /* d2 is above d1 */
+       return y_top;
+   }
+   if (y_bottom > 0) { /* d2 is below d1 */
+       return y_bottom;
+   }
+   /* 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;
-
-   if (d1->x >= d2->x)
-      ret += 0x10000;
-
-   return ret;
+   if (d1->x + d1->w > d2->x)
+       return min_dist(d1, 0x10000 + d2->x, d2->y, d2->w, d2->h, DISTANCE_RATIO, 1);
+   else
+       return  min_dist(d1, d2->x, d2->y, d2->w, d2->h, DISTANCE_RATIO, 1);
 }
 
 
@@ -567,12 +615,10 @@
  */
 static int cmp_left(AL_CONST DIALOG *d1, AL_CONST DIALOG *d2)
 {
-   int ret = (d1->x - d2->x) + ABS(d1->y - d2->y) * 8;
-
-   if (d1->x <= d2->x)
-      ret += 0x10000;
-
-   return ret;
+   if (d1->x < d2->x + d2->w)
+      return  min_dist(d1, d2->x - 0x10000, d2->y, d2->w, d2->h, DISTANCE_RATIO, 1); 
+   else
+      return  min_dist(d1, d2->x, d2->y, d2->w, d2->h, DISTANCE_RATIO, 1); 
 }
 
 
@@ -582,12 +628,10 @@
  */
 static int cmp_down(AL_CONST DIALOG *d1, AL_CONST DIALOG *d2)
 {
-   int ret = (d2->y - d1->y) + ABS(d1->x - d2->x) * 8;
-
-   if (d1->y >= d2->y)
-      ret += 0x10000;
-
-   return ret;
+   if (d1->y + d1->h > d2->y)
+       return min_dist(d1, d2->x, 0x10000 + d2->y, d2->w, d2->h, 1, DISTANCE_RATIO);
+   else
+       return  min_dist(d1, d2->x, d2->y, d2->w, d2->h, 1, DISTANCE_RATIO);
 }
 
 
@@ -597,12 +641,10 @@
  */
 static int cmp_up(AL_CONST DIALOG *d1, AL_CONST DIALOG *d2)
 {
-   int ret = (d1->y - d2->y) + ABS(d1->x - d2->x) * 8;
-
-   if (d1->y <= d2->y)
-      ret += 0x10000;
-
-   return ret;
+   if (d1->y < d2->y + d2->h)
+       return min_dist(d1, d2->x, d2->y - 0x10000, d2->w, d2->h, 1, DISTANCE_RATIO);
+   else
+       return  min_dist(d1, d2->x, d2->y, d2->w, d2->h, 1, DISTANCE_RATIO); 
 }
 
 
@@ -631,7 +673,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);