src/rect.c

   1 /*      SCCS Id: @(#)rect.c     3.4     1990/02/22      */
   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 static 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 MAXRECT 1000
  17 #define XLIM    4
  18 #define YLIM    3
  19
  20 static NhRect rect[MAXRECT+1];
  21 static int rect_cnt;
  22
  23 /*
  24  * Initialisation of internal structures. Should be called for every
  25  * new level to be build...
  26  */
  27
  28 void
  29 init_rect()
  30 {
  31         rect_cnt = 1;
  32         rect[0].lx = rect[0].ly = 0;
  33         rect[0].hx = COLNO - 1;
  34         rect[0].hy = ROWNO - 1;
  35 }
  36
  37 /*
  38  * Search Index of one precise NhRect.
  39  *
  40  */
  41
  42 int
  43 get_rect_ind(r)
  44 NhRect *r;
  45 {
  46         register NhRect *rectp;
  47         register int lx, ly, hx, hy;
  48         register int i;
  49
  50         lx = r->lx; ly = r->ly;
  51         hx = r->hx; hy = r->hy;
  52         for (i=0,rectp = &rect[0];i<rect_cnt;i++,rectp++)
  53             if ( lx == rectp->lx && ly == rectp->ly &&
  54                  hx == rectp->hx && hy == rectp->hy)
  55                 return i;
  56         return -1;
  57 }
  58
  59 /*
  60  * Search a free rectangle that include the one given in arg
  61  */
  62
  63 NhRect *
  64 get_rect(r)
  65 NhRect *r;
  66 {
  67         register NhRect *rectp;
  68         register int lx, ly, hx, hy;
  69         register int i;
  70
  71         lx = r->lx; ly = r->ly;
  72         hx = r->hx; hy = r->hy;
  73         for (i=0,rectp = &rect[0];i<rect_cnt;i++,rectp++)
  74             if ( lx >= rectp->lx && ly >= rectp->ly &&
  75                  hx <= rectp->hx && hy <= rectp->hy)
  76                 return rectp;
  77         return 0;
  78 }
  79
  80 /*
  81  * Get some random NhRect from the list.
  82  */
  83
  84 NhRect *
  85 rnd_rect()
  86 {
  87
  88                 /*if (wizard && rect_cnt == 0) pline("rect_cnt = 0");*/
  89
  90             return rect_cnt > 0 ? &rect[rn2(rect_cnt)] : 0;
  91 }
  92
  93 /*
  94  * Search intersection between two rectangles (r1 & r2).
  95  * return TRUE if intersection exist and put it in r3.
  96  * otherwise returns FALSE
  97  */
  98
  99 static boolean
 100 intersect(r1, r2, r3)
 101 NhRect *r1, *r2, *r3;
 102 {
 103         if (r2->lx > r1->hx || r2->ly > r1->hy ||
 104             r2->hx < r1->lx || r2->hy < r1->ly)
 105             return FALSE;
 106
 107         r3->lx = (r2->lx > r1->lx ? r2->lx : r1->lx);
 108         r3->ly = (r2->ly > r1->ly ? r2->ly : r1->ly);
 109         r3->hx = (r2->hx > r1->hx ? r1->hx : r2->hx);
 110         r3->hy = (r2->hy > r1->hy ? r1->hy : r2->hy);
 111
 112         if (r3->lx > r3->hx || r3->ly > r3->hy)
 113             return FALSE;
 114         return TRUE;
 115 }
 116
 117 /*
 118  * Remove a rectangle from the list of free NhRect.
 119  */
 120
 121 void
 122 remove_rect(r)
 123 NhRect *r;
 124 {
 125         int ind;
 126
 127         ind = get_rect_ind(r);
 128         if ( ind >=0 )
 129             rect[ind] = rect[--rect_cnt];
 130 }
 131
 132 /*
 133  * Add a NhRect to the list.
 134  */
 135
 136 void
 137 add_rect(r)
 138 NhRect *r;
 139 {
 140         if (rect_cnt >= MAXRECT) {
 141 #ifdef WIZARD
 142                 if (wizard) pline("MAXRECT may be too small.");
 143 #endif
 144                 return;
 145         }
 146         /* Check that this NhRect is not included in another one */
 147         if (get_rect(r))
 148             return;
 149         rect[rect_cnt] = *r;
 150         rect_cnt++;
 151 }
 152
 153 /*
 154  * Okay, here we have two rectangles (r1 & r2).
 155  * r1 was already in the list and r2 is included in r1.
 156  * What we want is to allocate r2, that is split r1 into smaller rectangles
 157  * then remove it.
 158  */
 159
 160 void
 161 split_rects(r1, r2)
 162 NhRect *r1, *r2;
 163 {
 164         NhRect r, old_r;
 165         int i;
 166
 167         old_r = *r1;
 168         remove_rect(r1);
 169
 170         /* Walk down since rect_cnt & rect[] will change... */
 171         for (i=rect_cnt-1; i>=0; i--)
 172             if (intersect(&rect[i], r2, &r))
 173                 split_rects(&rect[i], &r);
 174
 175         if (r2->ly - old_r.ly-1 > (old_r.hy < ROWNO - 1 ? 2*YLIM : YLIM+1)+4) {
 176                 r = old_r;
 177                 r.hy = r2->ly - 2;
 178                 add_rect(&r);
 179         }
 180         if (r2->lx - old_r.lx-1 > (old_r.hx < COLNO - 1 ? 2*XLIM : XLIM+1)+4) {
 181                 r = old_r;
 182                 r.hx = r2->lx - 2;
 183                 add_rect(&r);
 184         }
 185         if (old_r.hy - r2->hy-1 > (old_r.ly > 0 ? 2*YLIM : YLIM+1)+4) {
 186                 r = old_r;
 187                 r.ly = r2->hy + 2;
 188                 add_rect(&r);
 189         }
 190         if (old_r.hx - r2->hx-1 > (old_r.lx > 0 ? 2*XLIM : XLIM+1)+4) {
 191                 r = old_r;
 192                 r.lx = r2->hx + 2;
 193                 add_rect(&r);
 194         }
 195 }
 196
 197 /*rect.c*/