win/gem/gr_rect.c

   1 /* NetHack 3.6  gr_rect.c       $NHDT-Date: 1432512810 2015/05/25 00:13:30 $  $NHDT-Branch: master $:$NHDT-Revision: 1.7 $ */
   2  */
   3 /* Copyright (c) Christian Bressler, 2001 */
   4 /* NetHack may be freely redistributed.  See license for details. */
   5 /* This is an almost exact copy of qt_clust.cpp */
   6 /* gr_rect.c */
   7 #include <stdlib.h>
   8 #include <stdio.h>
   9 #include <limits.h>
  10 #include "gr_rect.h"
  11 dirty_rect *
  12 new_dirty_rect(int size)
  13 {
  14     dirty_rect *new = NULL;
  15     if (size > 0) {
  16         new = (dirty_rect *) calloc(1L, sizeof(dirty_rect));
  17         if (new) {
  18             new->rects = (GRECT *) calloc((long) size, sizeof(GRECT));
  19             if (new->rects == NULL) {
  20                 free(new);
  21                 return (NULL);
  22             }
  23             new->max = size;
  24         }
  25     }
  26     return (new);
  27 }
  28 void
  29 delete_dirty_rect(dirty_rect *this)
  30 {
  31     if (this == NULL)
  32         return;
  33     if (this->rects)
  34         free(this->rects);
  35     /* In case the Pointer is reused wrongly */
  36     this->rects = NULL;
  37     this->max = 0;
  38     this->used = 0;
  39     free(this);
  40 }
  41 static int gc_inside(GRECT *frame, GRECT *test);
  42 static int gc_touch(GRECT *frame, GRECT *test);
  43 static void gc_combine(GRECT *frame, GRECT *test);
  44 static long gc_area(GRECT *area);
  45 int
  46 add_dirty_rect(dirty_rect *dr, GRECT *area)
  47 {
  48     int cursor;
  49     long lowestcost = 9999999L;
  50     int cheapest = -1;
  51     int cheapestmerge1 = -1;
  52     int cheapestmerge2 = -1;
  53     int merge1;
  54     int merge2;
  55     for (cursor = 0; cursor < dr->used; cursor++) {
  56         if (gc_inside(&dr->rects[cursor], area)) {
  57             /* Wholly contained already. */
  58             return (TRUE);
  59         }
  60     }
  61     for (cursor = 0; cursor < dr->used; cursor++) {
  62         if (gc_touch(&dr->rects[cursor], area)) {
  63             GRECT larger = dr->rects[cursor];
  64             long cost;
  65             gc_combine(&larger, area);
  66             cost = gc_area(&larger) - gc_area(&dr->rects[cursor]);
  67             if (cost < lowestcost) {
  68                 int bad = FALSE, c;
  69                 for (c = 0; c < dr->used && !bad; c++) {
  70                     bad = gc_touch(&dr->rects[c], &larger) && c != cursor;
  71                 }
  72                 if (!bad) {
  73                     cheapest = cursor;
  74                     lowestcost = cost;
  75                 }
  76             }
  77         }
  78     }
  79     if (cheapest >= 0) {
  80         gc_combine(&dr->rects[cheapest], area);
  81         return (TRUE);
  82     }
  83     if (dr->used < dr->max) {
  84         dr->rects[dr->used++] = *area;
  85         return (TRUE);
  86     }
  87     // Do cheapest of:
  88     //  add to closest cluster
  89     //  do cheapest cluster merge, add to new cluster
  90     lowestcost = 9999999L;
  91     cheapest = -1;
  92     for (cursor = 0; cursor < dr->used; cursor++) {
  93         GRECT larger = dr->rects[cursor];
  94         long cost;
  95         gc_combine(&larger, area);
  96         cost = gc_area(&larger) - gc_area(&dr->rects[cursor]);
  97         if (cost < lowestcost) {
  98             int bad = FALSE, c;
  99             for (c = 0; c < dr->used && !bad; c++) {
 100                 bad = gc_touch(&dr->rects[c], &larger) && c != cursor;
 101             }
 102             if (!bad) {
 103                 cheapest = cursor;
 104                 lowestcost = cost;
 105             }
 106         }
 107     }
 108     // XXX could make an heuristic guess as to whether we
 109     // XXX need to bother looking for a cheap merge.
 110     for (merge1 = 0; merge1 < dr->used; merge1++) {
 111         for (merge2 = 0; merge2 < dr->used; merge2++) {
 112             if (merge1 != merge2) {
 113                 GRECT larger = dr->rects[merge1];
 114                 long cost;
 115                 gc_combine(&larger, &dr->rects[merge2]);
 116                 cost = gc_area(&larger) - gc_area(&dr->rects[merge1])
 117                        - gc_area(&dr->rects[merge2]);
 118                 if (cost < lowestcost) {
 119                     int bad = FALSE, c;
 120                     for (c = 0; c < dr->used && !bad; c++) {
 121                         bad = gc_touch(&dr->rects[c], &larger) && c != cursor;
 122                     }
 123                     if (!bad) {
 124                         cheapestmerge1 = merge1;
 125                         cheapestmerge2 = merge2;
 126                         lowestcost = cost;
 127                     }
 128                 }
 129             }
 130         }
 131     }
 132     if (cheapestmerge1 >= 0) {
 133         gc_combine(&dr->rects[cheapestmerge1], &dr->rects[cheapestmerge2]);
 134         dr->rects[cheapestmerge2] = dr->rects[dr->used - 1];
 135         dr->rects[dr->used - 1] = *area;
 136     } else {
 137         gc_combine(&dr->rects[cheapest], area);
 138     }
 139     // NB: clusters do not intersect (or intersection will
 140     //   overwrite).  This is a result of the above algorithm,
 141     //   given the assumption that (x,y) are ordered topleft
 142     //   to bottomright.
 143     return (TRUE);
 144 }
 145 int
 146 get_dirty_rect(dirty_rect *dr, GRECT *area)
 147 {
 148     if (dr == NULL || area == NULL || dr->rects == NULL || dr->used <= 0
 149         || dr->max <= 0)
 150         return (FALSE);
 151     *area = dr->rects[--dr->used];
 152     return (TRUE);
 153 }
 154 int
 155 clear_dirty_rect(dirty_rect *dr)
 156 {
 157     if (dr)
 158         dr->used = 0;
 159     return (TRUE);
 160 }
 161 int
 162 resize_dirty_rect(dirty_rect *dr, int new_size)
 163 {
 164     return (FALSE);
 165 }
 166 static int
 167 gc_inside(GRECT *frame, GRECT *test)
 168 {
 169     if (frame && test && frame->g_x <= test->g_x && frame->g_y <= test->g_y
 170         && frame->g_x + frame->g_w >= test->g_x + test->g_w
 171         && frame->g_y + frame->g_h >= test->g_y + test->g_h)
 172         return (TRUE);
 173     return (FALSE);
 174 }
 175 static int
 176 gc_touch(GRECT *frame, GRECT *test)
 177 {
 178     GRECT tmp = { test->g_x - 1, test->g_y - 1, test->g_w + 2,
 179                   test->g_h + 2 };
 180     return (rc_intersect(frame, &tmp));
 181 }
 182 static void
 183 gc_combine(GRECT *frame, GRECT *test)
 184 {
 185     if (!frame || !test)
 186         return;
 187     if (frame->g_x > test->g_x) {
 188         frame->g_w += frame->g_x - test->g_x;
 189         frame->g_x = test->g_x;
 190     }
 191     if (frame->g_y > test->g_y) {
 192         frame->g_h += frame->g_y - test->g_y;
 193         frame->g_y = test->g_y;
 194     }
 195     if (frame->g_x + frame->g_w < test->g_x + test->g_w)
 196         frame->g_w = test->g_x + test->g_w - frame->g_x;
 197     if (frame->g_y + frame->g_h < test->g_y + test->g_h)
 198         frame->g_h = test->g_y + test->g_h - frame->g_y;
 199 }
 200 static long
 201 gc_area(GRECT *area)
 202 {
 203     return ((long) area->g_h * (long) area->g_w);
 204 }