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 7int FDECL(get_rect_ind, (NhRect *)); 8 9static 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 20static NhRect rect[MAXRECT+1]; 21static int rect_cnt; 22 23/* 24 * Initialisation of internal structures. Should be called for every 25 * new level to be build... 26 */ 27 28void 29init_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 42int 43get_rect_ind(r) 44NhRect *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 63NhRect * 64get_rect(r) 65NhRect *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 84NhRect * 85rnd_rect() 86{ 87 return rect_cnt > 0 ? &rect[rn2(rect_cnt)] : 0; 88} 89 90/* 91 * Search intersection between two rectangles (r1 & r2). 92 * return TRUE if intersection exist and put it in r3. 93 * otherwise returns FALSE 94 */ 95 96static boolean 97intersect(r1, r2, r3) 98NhRect *r1, *r2, *r3; 99{ 100 if (r2->lx > r1->hx || r2->ly > r1->hy || 101 r2->hx < r1->lx || r2->hy < r1->ly) 102 return FALSE; 103 104 r3->lx = (r2->lx > r1->lx ? r2->lx : r1->lx); 105 r3->ly = (r2->ly > r1->ly ? r2->ly : r1->ly); 106 r3->hx = (r2->hx > r1->hx ? r1->hx : r2->hx); 107 r3->hy = (r2->hy > r1->hy ? r1->hy : r2->hy); 108 109 if (r3->lx > r3->hx || r3->ly > r3->hy) 110 return FALSE; 111 return TRUE; 112} 113 114/* 115 * Remove a rectangle from the list of free NhRect. 116 */ 117 118void 119remove_rect(r) 120NhRect *r; 121{ 122 int ind; 123 124 ind = get_rect_ind(r); 125 if ( ind >=0 ) 126 rect[ind] = rect[--rect_cnt]; 127} 128 129/* 130 * Add a NhRect to the list. 131 */ 132 133void 134add_rect(r) 135NhRect *r; 136{ 137 if (rect_cnt >= MAXRECT) { 138#ifdef WIZARD 139 if (wizard) pline("MAXRECT may be too small."); 140#endif 141 return; 142 } 143 /* Check that this NhRect is not included in another one */ 144 if (get_rect(r)) 145 return; 146 rect[rect_cnt] = *r; 147 rect_cnt++; 148} 149 150/* 151 * Okay, here we have two rectangles (r1 & r2). 152 * r1 was already in the list and r2 is included in r1. 153 * What we want is to allocate r2, that is split r1 into smaller rectangles 154 * then remove it. 155 */ 156 157void 158split_rects(r1, r2) 159NhRect *r1, *r2; 160{ 161 NhRect r, old_r; 162 int i; 163 164 old_r = *r1; 165 remove_rect(r1); 166 167 /* Walk down since rect_cnt & rect[] will change... */ 168 for (i=rect_cnt-1; i>=0; i--) 169 if (intersect(&rect[i], r2, &r)) 170 split_rects(&rect[i], &r); 171 172 if (r2->ly - old_r.ly-1 > (old_r.hy < ROWNO - 1 ? 2*YLIM : YLIM+1)+4) { 173 r = old_r; 174 r.hy = r2->ly - 2; 175 add_rect(&r); 176 } 177 if (r2->lx - old_r.lx-1 > (old_r.hx < COLNO - 1 ? 2*XLIM : XLIM+1)+4) { 178 r = old_r; 179 r.hx = r2->lx - 2; 180 add_rect(&r); 181 } 182 if (old_r.hy - r2->hy-1 > (old_r.ly > 0 ? 2*YLIM : YLIM+1)+4) { 183 r = old_r; 184 r.ly = r2->hy + 2; 185 add_rect(&r); 186 } 187 if (old_r.hx - r2->hx-1 > (old_r.lx > 0 ? 2*XLIM : XLIM+1)+4) { 188 r = old_r; 189 r.lx = r2->hx + 2; 190 add_rect(&r); 191 } 192} 193 194/*rect.c*/ 195