1 | /* SCCS Id: @(#)rect.c 3.3 90/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 FDECL(get_rect_ind, (NhRect *));
8 |
9 | static 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; 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 | 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 |
96 | static boolean
97 | intersect(r1, r2, r3)
98 | NhRect *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 |
118 | void
119 | remove_rect(r)
120 | NhRect *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 |
133 | void
134 | add_rect(r)
135 | NhRect *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 |
157 | void
158 | split_rects(r1, r2)
159 | NhRect *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*/