src/rect.c

   1 /* NetHack 3.7  rect.c  $NHDT-Date: 1596498203 2020/08/03 23:43:23 $  $NHDT-Branch: NetHack-3.7 $:$NHDT-Revision: 1.14 $ */
   2 /* Copyright (c) 1990 by Jean-Christophe Collet                   */
   3 /* NetHack may be freely redistributed.  See license for details. */
   4
   5 #include "hack.h"
   6
   7 int get_rect_ind(NhRect *);
   8
   9 staticfn boolean intersect(NhRect *, NhRect *, NhRect *);
  10
  11 /*
  12  * In this file, we will handle the various rectangle functions we
  13  * need for room generation.
  14  */
  15
  16 #define XLIM 4
  17 #define YLIM 3
  18
  19 static NhRect *rect = (NhRect *) 0;
  20 static int n_rects = 0;
  21 static int rect_cnt;
  22
  23 /*
  24  * Initialization of internal structures. Should be called for every
  25  * new level to be build...
  26  */
  27
  28 void
  29 init_rect(void)
  30 {
  31     if (!rect) {
  32         n_rects = (COLNO * ROWNO) / 30;
  33         rect = (NhRect *) alloc(sizeof(NhRect) * n_rects);
  34         if (!rect)
  35             panic("Could not alloc rect");
  36     }
  37
  38     rect_cnt = 1;
  39     rect[0].lx = rect[0].ly = 0;
  40     rect[0].hx = COLNO - 1;
  41     rect[0].hy = ROWNO - 1;
  42 }
  43
  44 void
  45 free_rect(void)
  46 {
  47     if (rect)
  48         free(rect);
  49     rect = 0;
  50     n_rects = rect_cnt = 0;
  51 }
  52
  53
  54 /*
  55  * Search Index of one precise NhRect.
  56  *
  57  */
  58
  59 int
  60 get_rect_ind(NhRect *r)
  61 {
  62     NhRect *rectp;
  63     int lx, ly, hx, hy;
  64     int i;
  65
  66     lx = r->lx;
  67     ly = r->ly;
  68     hx = r->hx;
  69     hy = r->hy;
  70     for (i = 0, rectp = &rect[0]; i < rect_cnt; i++, rectp++)
  71         if (lx == rectp->lx && ly == rectp->ly && hx == rectp->hx
  72             && hy == rectp->hy)
  73             return i;
  74     return -1;
  75 }
  76
  77 /*
  78  * Search a free rectangle that include the one given in arg
  79  */
  80
  81 NhRect *
  82 get_rect(NhRect *r)
  83 {
  84     NhRect *rectp;
  85     int lx, ly, hx, hy;
  86     int i;
  87
  88     lx = r->lx;
  89     ly = r->ly;
  90     hx = r->hx;
  91     hy = r->hy;
  92     for (i = 0, rectp = &rect[0]; i < rect_cnt; i++, rectp++)
  93         if (lx >= rectp->lx && ly >= rectp->ly && hx <= rectp->hx
  94             && hy <= rectp->hy)
  95             return rectp;
  96     return 0;
  97 }
  98
  99 /*
 100  * Get some random NhRect from the list.
 101  */
 102
 103 NhRect *
 104 rnd_rect(void)
 105 {
 106     return rect_cnt > 0 ? &rect[rn2(rect_cnt)] : 0;
 107 }
 108
 109 /*
 110  * Search intersection between two rectangles (r1 & r2).
 111  * return TRUE if intersection exist and put it in r3.
 112  * otherwise returns FALSE
 113  */
 114
 115 staticfn boolean
 116 intersect(NhRect *r1, NhRect *r2, NhRect *r3)
 117 {
 118     if (r2->lx > r1->hx || r2->ly > r1->hy || r2->hx < r1->lx
 119         || r2->hy < r1->ly)
 120         return FALSE;
 121
 122     r3->lx = (r2->lx > r1->lx ? r2->lx : r1->lx);
 123     r3->ly = (r2->ly > r1->ly ? r2->ly : r1->ly);
 124     r3->hx = (r2->hx > r1->hx ? r1->hx : r2->hx);
 125     r3->hy = (r2->hy > r1->hy ? r1->hy : r2->hy);
 126
 127     if (r3->lx > r3->hx || r3->ly > r3->hy)
 128         return FALSE;
 129     return TRUE;
 130 }
 131
 132 /* Put the rectangle containing both r1 and r2 into r3 */
 133 void
 134 rect_bounds(NhRect r1, NhRect r2, NhRect *r3)
 135 {
 136     r3->lx = min(r1.lx, r2.lx);
 137     r3->ly = min(r1.ly, r2.ly);
 138     r3->hx = max(r1.hx, r2.hx);
 139     r3->hy = max(r1.hy, r2.hy);
 140 }
 141
 142 /*
 143  * Remove a rectangle from the list of free NhRect.
 144  */
 145
 146 void
 147 remove_rect(NhRect *r)
 148 {
 149     int ind;
 150
 151     ind = get_rect_ind(r);
 152     if (ind >= 0)
 153         rect[ind] = rect[--rect_cnt];
 154 }
 155
 156 /*
 157  * Add a NhRect to the list.
 158  */
 159
 160 void
 161 add_rect(NhRect *r)
 162 {
 163     if (rect_cnt >= n_rects) {
 164         impossible("n_rects may be too small.");
 165         return;
 166     }
 167     /* Check that this NhRect is not included in another one */
 168     if (get_rect(r))
 169         return;
 170     rect[rect_cnt] = *r;
 171     rect_cnt++;
 172 }
 173
 174 /*
 175  * Okay, here we have two rectangles (r1 & r2).
 176  * r1 was already in the list and r2 is included in r1.
 177  * What we want is to allocate r2, that is split r1 into smaller rectangles
 178  * then remove it.
 179  */
 180
 181 void
 182 split_rects(NhRect *r1, NhRect *r2)
 183 {
 184     NhRect r, old_r;
 185     int i;
 186
 187     old_r = *r1;
 188     remove_rect(r1);
 189
 190     /* Walk down since rect_cnt & rect[] will change... */
 191     for (i = rect_cnt - 1; i >= 0; i--)
 192         if (intersect(&rect[i], r2, &r))
 193             split_rects(&rect[i], &r);
 194
 195     if (r2->ly - old_r.ly - 1
 196         > (old_r.hy < ROWNO - 1 ? 2 * YLIM : YLIM + 1) + 4) {
 197         r = old_r;
 198         r.hy = r2->ly - 2;
 199         add_rect(&r);
 200     }
 201     if (r2->lx - old_r.lx - 1
 202         > (old_r.hx < COLNO - 1 ? 2 * XLIM : XLIM + 1) + 4) {
 203         r = old_r;
 204         r.hx = r2->lx - 2;
 205         add_rect(&r);
 206     }
 207     if (old_r.hy - r2->hy - 1 > (old_r.ly > 0 ? 2 * YLIM : YLIM + 1) + 4) {
 208         r = old_r;
 209         r.ly = r2->hy + 2;
 210         add_rect(&r);
 211     }
 212     if (old_r.hx - r2->hx - 1 > (old_r.lx > 0 ? 2 * XLIM : XLIM + 1) + 4) {
 213         r = old_r;
 214         r.lx = r2->hx + 2;
 215         add_rect(&r);
 216     }
 217 }
 218
 219 /*rect.c*/