src/rect.c

   1 /* NetHack 3.6  rect.c  $NHDT-Date: 1432512774 2015/05/25 00:12:54 $  $NHDT-Branch: master $:$NHDT-Revision: 1.11 $ */
   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 FDECL(get_rect_ind, (NhRect *));
   8
   9 STATIC_DCL boolean FDECL(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 50
  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;
  51     ly = r->ly;
  52     hx = r->hx;
  53     hy = r->hy;
  54     for (i = 0, rectp = &rect[0]; i < rect_cnt; i++, rectp++)
  55         if (lx == rectp->lx && ly == rectp->ly && hx == rectp->hx
  56             && hy == rectp->hy)
  57             return i;
  58     return -1;
  59 }
  60
  61 /*
  62  * Search a free rectangle that include the one given in arg
  63  */
  64
  65 NhRect *
  66 get_rect(r)
  67 NhRect *r;
  68 {
  69     register NhRect *rectp;
  70     register int lx, ly, hx, hy;
  71     register int i;
  72
  73     lx = r->lx;
  74     ly = r->ly;
  75     hx = r->hx;
  76     hy = r->hy;
  77     for (i = 0, rectp = &rect[0]; i < rect_cnt; i++, rectp++)
  78         if (lx >= rectp->lx && ly >= rectp->ly && hx <= rectp->hx
  79             && hy <= rectp->hy)
  80             return rectp;
  81     return 0;
  82 }
  83
  84 /*
  85  * Get some random NhRect from the list.
  86  */
  87
  88 NhRect *
  89 rnd_rect()
  90 {
  91     return rect_cnt > 0 ? &rect[rn2(rect_cnt)] : 0;
  92 }
  93
  94 /*
  95  * Search intersection between two rectangles (r1 & r2).
  96  * return TRUE if intersection exist and put it in r3.
  97  * otherwise returns FALSE
  98  */
  99
 100 STATIC_OVL boolean
 101 intersect(r1, r2, r3)
 102 NhRect *r1, *r2, *r3;
 103 {
 104     if (r2->lx > r1->hx || r2->ly > r1->hy || r2->hx < r1->lx
 105         || r2->hy < r1->ly)
 106         return FALSE;
 107
 108     r3->lx = (r2->lx > r1->lx ? r2->lx : r1->lx);
 109     r3->ly = (r2->ly > r1->ly ? r2->ly : r1->ly);
 110     r3->hx = (r2->hx > r1->hx ? r1->hx : r2->hx);
 111     r3->hy = (r2->hy > r1->hy ? r1->hy : r2->hy);
 112
 113     if (r3->lx > r3->hx || r3->ly > r3->hy)
 114         return FALSE;
 115     return TRUE;
 116 }
 117
 118 /*
 119  * Remove a rectangle from the list of free NhRect.
 120  */
 121
 122 void
 123 remove_rect(r)
 124 NhRect *r;
 125 {
 126     int ind;
 127
 128     ind = get_rect_ind(r);
 129     if (ind >= 0)
 130         rect[ind] = rect[--rect_cnt];
 131 }
 132
 133 /*
 134  * Add a NhRect to the list.
 135  */
 136
 137 void
 138 add_rect(r)
 139 NhRect *r;
 140 {
 141     if (rect_cnt >= MAXRECT) {
 142         if (wizard)
 143             pline("MAXRECT may be too small.");
 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
 176         > (old_r.hy < ROWNO - 1 ? 2 * YLIM : YLIM + 1) + 4) {
 177         r = old_r;
 178         r.hy = r2->ly - 2;
 179         add_rect(&r);
 180     }
 181     if (r2->lx - old_r.lx - 1
 182         > (old_r.hx < COLNO - 1 ? 2 * XLIM : XLIM + 1) + 4) {
 183         r = old_r;
 184         r.hx = r2->lx - 2;
 185         add_rect(&r);
 186     }
 187     if (old_r.hy - r2->hy - 1 > (old_r.ly > 0 ? 2 * YLIM : YLIM + 1) + 4) {
 188         r = old_r;
 189         r.ly = r2->hy + 2;
 190         add_rect(&r);
 191     }
 192     if (old_r.hx - r2->hx - 1 > (old_r.lx > 0 ? 2 * XLIM : XLIM + 1) + 4) {
 193         r = old_r;
 194         r.lx = r2->hx + 2;
 195         add_rect(&r);
 196     }
 197 }
 198
 199 /*rect.c*/