1 /*
2  * Maze drawing routines.  Based on the algorithm presented in the
3  * December 1981 Byte "How to Build a Maze" by David Matuszek.
4  *
5  * maze.c	1.4		(A.I. Design)	12/14/84
6  */
7 
8 #include "rogue.h"
9 #include "curses.h"
10 extern int maxrow;
11 
12 #define MAXFRNT 100
13 
14 #define FRONTIER 'F'
15 #define NOTHING ' '
16 
17 static shint frcnt, ny, nx, topy, topx;
18 static shint maxx, maxy;
19 static shint *fr_y, *fr_x;
20 
21 draw_maze(rp)
22 struct room *rp;
23 {
24     register int y, x;
25     shint fy[MAXFRNT], fx[MAXFRNT];
26     int psgcnt;
27     coord spos;
28 
29     fr_y = fy;
30     fr_x = fx;
31     maxx = maxy = 0;
32     topy = rp->r_pos.y;
33     if (topy == 0)
34     	topy = ++rp->r_pos.y;
35     topx = rp->r_pos.x;
36     /*
37      * Choose a random spot in the maze and initialize the frontier
38      * to be the immediate neighbors of this random spot.
39      */
40     y = topy;
41     x = topx;
42     splat(y,x);
43     new_frontier(y, x);
44     /*
45      * While there are new frontiers, connect them to the path and
46      * possibly expand the frontier even more.
47      */
48     while(frcnt)
49     {
50     	con_frnt();
51     	new_frontier(ny, nx);
52     }
53     /*
54      * According to the Grand Beeking, every maze should have a loop
55      * Don't worry if you don't understand this.
56      */
57     rp->r_max.x = maxx - rp->r_pos.x + 1;
58     rp->r_max.y = maxy - rp->r_pos.y + 1;
59     do {
60     	static coord ld[4] = {
61     		-1, 0,
62     		0, 1,
63     		1, 0,
64     		0, -1
65     	};
66     	coord *cp;
67     	int sh;
68 
69     	rnd_pos(rp, &spos);
70     	for (psgcnt = 0,cp = ld,sh = 1; cp < &ld[4]; sh <<= 1,cp++) {
71     	    y = cp->y + spos.y; x = cp->x + spos.x;
72     	    if (!offmap(y, x) && chat(y, x) == PASSAGE)
73     		psgcnt += sh;
74     	}
75     } while (chat(spos.y, spos.x) == PASSAGE || psgcnt % 5);
76     splat(spos.y, spos.x);
77 }
78 
79 new_frontier(y, x)
80 int y, x;
81 {
82     add_frnt(y-2, x);
83     add_frnt(y+2, x);
84     add_frnt(y, x-2);
85     add_frnt(y, x+2);
86 }
87 
88 add_frnt(y, x)
89 int y, x;
90 {
91 #ifdef DEBUG
92     if (frcnt == MAXFRNT - 1)
93 	debug("MAZE DRAWING ERROR #3\n");
94 #endif
95     if (inrange(y, x) && chat(y, x) == NOTHING)
96     {
97     	chat(y, x) = FRONTIER;
98     	fr_y[frcnt] = y;
99     	fr_x[frcnt++] = x;
100     }
101 }
102 
103 /*
104  * Connect randomly to one of the adjacent points in the spanning tree
105  */
106 con_frnt()
107 {
108     register int n, which, ydelt = 0, xdelt = 0;
109     int choice[4];
110     int cnt = 0, y, x;
111 
112 
113     /*
114      * Choose a random frontier
115      */
116     n = rnd(frcnt);
117     ny = fr_y[n];
118     nx = fr_x[n];
119     fr_y[n] = fr_y[frcnt-1];
120     fr_x[n] = fr_x[--frcnt];
121 
122     /*
123      * Count and collect the adjacent points we can connect to
124      */
125     if (maze_at(ny-2, nx) > 0)
126     	choice[cnt++] = 0;
127     if (maze_at(ny+2, nx) > 0)
128     	choice[cnt++] = 1;
129     if (maze_at(ny, nx-2) > 0)
130     	choice[cnt++] = 2;
131     if (maze_at(ny, nx+2) > 0)
132     	choice[cnt++] = 3;
133     /*
134      * Choose one of the open places, connect to it and
135      * then the task is complete
136      */
137     which = choice[rnd(cnt)];
138     splat(ny, nx);
139     switch(which)
140     {
141     	when 0: which = 1; ydelt = -1;
142     	when 1: which = 0; ydelt = 1;
143     	when 2: which = 3; xdelt = -1;
144     	when 3: which = 2; xdelt = 1;
145     }
146     y = ny + ydelt;
147     x = nx + xdelt;
148     if (inrange(y, x))
149         splat(y, x);
150 }
151 
152 maze_at(y, x)
153 {
154     if (inrange(y, x) && chat(y, x) == PASSAGE)
155     	return 1;
156     else
157     	return 0;
158 }
159 
160 splat(y, x)
161 {
162     chat(y, x) = PASSAGE;
163     flat(y, x) = F_MAZE|F_REAL;
164     if (x > maxx)
165 	maxx = x;
166     if (y > maxy)
167 	maxy = y;
168 }
169 
170 #define MAXY (topy+((maxrow+1)/3))
171 #define MAXX (topx+COLS/3)
172 
173 inrange(y, x) 
174 int x, y;
175 {
176 	return(y >= topy && y < MAXY && x >= topx && x < MAXX);
177 }
178 ÿ