Iggy focus handling

iggy_focus.cpp

enum FocusDir
{
   DIR_W,
   DIR_E,
   DIR_N,
   DIR_S
};

static FocusDir get_quadrant(float dx, float dy)
{
   if (fabsf(dx) > fabsf(dy))
      return (dx > 0.0f) ? DIR_E : DIR_W;
   else
      return (dy > 0.0f) ? DIR_S : DIR_N;
}

static float dist_interval(float a0, float a1, float b0, float b1)
{
   if (a1 < b0)
      return a1 - b0;
   else if (b1 < a0)
      return a0 - b1;
   else
      return 0.0f;
}

static void move_focus(Iggy *f, FocusDir dir, int wrap)
{
   S32 num_obj;
   const int max_objects = 256;
   IggyFocusableObject objs[max_objects], *old_obj;
   IggyFocusHandle old, best = NULL;
   F32 width = (F32) cur_width; // need this when wrap!=0
   F32 height = (F32) cur_height; // dto

   IggyPlayerGetFocusableObjects(f, &old, objs, max_objects, &num_obj);

   if (!old) // no object on the stage currently has focus, just give focus to the first object we encounter.
      best = objs ? objs[0].object : IGGY_FOCUS_NULL;
   else {
      F32 best_dist_axial = FLT_MAX, best_dist_box = FLT_MAX, best_dist_center = FLT_MAX;
      int i;

      for (i=0; i < num_obj; ++i)
         if (objs[i].object == old)
            break;

      if (i == num_obj) {
         // should be unreachable: the currently focused object wasn't on the focus list.
         // treat the same as no object has focus
         best = objs ? objs[0].object : IGGY_FOCUS_NULL;
         goto done;
      }
      old_obj = &objs[i];

      // go through all bboxes to find the best neighbor
      for (i=0; i < num_obj; ++i) {

         // don't move to this button again
         IggyFocusableObject *current = &objs[i];
         if (current->object == old)
            continue;

         float dax=0, day=0, dist_axial=0;
         float dbx, dby, dist_box;
         float dcx, dcy, dist_center;
         FocusDir quadrant;
         
         // compute distance between centers
         // this is off by a factor of 2, but we only compare center distances with each other so it doesn't matter
         dcx = (current->x0 + current->x1) - (old_obj->x0 + old_obj->x1);
         dcy = (current->y0 + current->y1) - (old_obj->y0 + old_obj->y1);
         dist_center = fabsf(dcx) + fabsf(dcy); // L1 metric (need this for our connectedness guarantee)

         // compute distance between boxes
         dbx = dist_interval(current->x0, current->x1, old_obj->x0, old_obj->x1);
         dby = dist_interval(current->y0, current->y1, old_obj->y0, old_obj->y1);
         dist_box = fabsf(dbx) + fabsf(dby);

         // determine which quadrant of bi bj lies in based on distance
         if (dbx || dby) { // for non-overlapping boxes, use distance between boxes
            dax = dbx;
            day = dby;
            dist_axial = dist_box;
            quadrant = get_quadrant(dbx, dby);
         } else if (dcx || dcy) { // for overlapping boxes with different centers, use distance between centers
            dax = dcx;
            day = dcy;
            dist_axial = dist_center;
            quadrant = get_quadrant(dcx, dcy);
         } else // degenerate case: two overlapping buttons with same center, break ties using order
            quadrant = (current->object < old) ? DIR_W : DIR_E;

         // is it in the quadrant we're interesting in moving to?
         if (quadrant == dir) {
            // does it beat the current best candidate?
            if (dist_box < best_dist_box) {
               best_dist_box = dist_box;
               best_dist_center = dist_center;
               best = current->object;
            } else if (dist_box == best_dist_box) {
               // try using distance between center points to break ties
               if (dist_center < best_dist_center) {
                  best_dist_center = dist_center;
                  best = current->object;
               } else if (dist_center == best_dist_center) {
                  // still tied! we need to be extra-careful to make sure everything gets linked properly.
                  // we consistently break ties by symbolically moving "later" buttons
                  // (with higher index) to the right/downwards by an infinitesimal amount
                  // since we saw the current "best" button already (so it must have a lower index),
                  // this is fairly easy. this rule ensures that all buttons with dx==dy==0 will end
                  // up being linked in order of appearance along the x axis.
                  if ((dir >= DIR_N ? dby : dbx) < 0.0f) // moving bj to the right/down decreases distance
                     best = current->object;
               }
            }
         }

         // axial check: if bi has no link at all in some direction and bj lies roughly in that
         // direction, add a tentative link. this will only be kept if no "real" matches are found,
         // so it only augments the graph produced by the above method using extra links. (important,
         // since it doesn't guarantee strong connectedness)
         //
         // this is just to avoid buttons having no links in a particular direction when there's
         // a suitable neighbor. you get good graphs without this too.
         if (best_dist_box == FLT_MAX) {
            // check axial match
            if (dist_axial < best_dist_axial && 
               ((dir == DIR_W && dax < 0.0f) || (dir == DIR_E && dax > 0.0f) || (dir == DIR_N && day < 0.0f) || (dir == DIR_S && day > 0.0f)))
               best_dist_axial = dist_axial, best = current->object;

            // check wraparound
            if ((wrap & 1) && ((dir == DIR_W && dax > 0.0f) || (dir == DIR_E && dax < 0.0f))) {
               float t = width * (dax < 0.0f ? 2.0f : -2.0f); // *2 to make it worse than any real axial match
               float d = fabsf(dist_interval(t + current->x0, t + current->x1, old_obj->x0, old_obj->x1)) + fabsf(dby);
               if (d < best_dist_axial)
                  best_dist_axial = d, best = current->object;
            }

            if ((wrap & 2) && ((dir == DIR_N && day > 0.0f) || (dir == DIR_S && day < 0.0f))) {
               float t = height * (day < 0.0f ? 2.0f : -2.0f); // *2 to make it worse than any real axial match
               float d = fabsf(dist_interval(t + current->y0, t + current->y1, old_obj->y0, old_obj->y1)) + fabsf(dbx);
               if (d < best_dist_axial)
                  best_dist_axial = d, best = current->object;
            }
         }
      }
   }

done:
   if (best) {
      char msg[256];
      sprintf(msg, "moving focus to %p\n", best);
      OutputDebugStringA(msg);

      IggyPlayerSetFocusRS(f, best, '\t');
   } else
      OutputDebugStringA("not moving focus!\n");
}