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