1 /* NetWalk game code
2 * Ben Lynn
3 */
4 /*
5 Copyright (C) 2004 Benjamin Lynn (blynn@cs.stanford.edu)
6
7 This program is free software; you can redistribute it and/or
8 modify it under the terms of the GNU General Public License
9 as published by the Free Software Foundation; either version 2
10 of the License, or (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 */
21 #include <stdlib.h>
22 #include <string.h>
23 #include "game.h"
24
25 //tile = integer
26 //bits 0...3 specify which directions lead out
27 //bit 4 = connected
28 //bit 5 = server
29 int boardw = 10, boardh = 9;
30 int board[boardmaxw][boardmaxh];
31 int neighbourcount[boardmaxw][boardmaxh];
32 int flags[boardmaxw][boardmaxh];
33 int sourcex, sourceytop, sourceybottom;
34
35 int wrap_flag = 0;
36 int no_fourway = 0;
37 int game_won = 0;
38
39 static int par;
40
41 coord_s dir[4] = {
42 {0, -1},
43 {1, 0},
44 {0, 1},
45 {-1, 0},
46 };
47 // 0 = up, 1 = right, 2 = down, 3 = left
48 // 0
49 // |
50 // 3--+--1
51 // |
52 // 2
53
add_dir(int * x,int * y,int x1,int y1,int d)54 void add_dir(int *x, int *y, int x1, int y1, int d)
55 {
56 *x = x1 + dir[d].x;
57 *y = y1 + dir[d].y;
58
59 if (wrap_flag) {
60 if (*x < 0) *x = boardw - 1;
61 if (*x >= boardw) *x = 0;
62 if (*y < 0) *y = boardh - 1;
63 if (*y >= boardh) *y = 0;
64 }
65 }
66
clear_flags()67 void clear_flags()
68 {
69 int i;
70 for(i = 0;i < boardw;i++)
71 {
72 int j;
73 for(j = 0;j < boardh;j++)
74 flags[i][j] = 0;
75 }
76 }
77
generate_maze()78 void generate_maze()
79 {
80 coord_s opentile[boardmaxw * boardmaxh];
81 int n;
82 int i, j;
83 int x, y;
84 int x1, y1;
85
86 n = 2;
87 opentile[0].x = sourcex;
88 opentile[1].x = sourcex;
89 opentile[0].y = sourceytop;
90 opentile[1].y = sourceybottom;
91
92 for (i=0; i<boardw; i++) {
93 for (j=0; j<boardh; j++) {
94 board[i][j] = 0;
95 neighbourcount[i][j] = 0;
96 }
97 }
98 board[sourcex][sourceytop] = 32;
99 board[sourcex][sourceybottom] = 32;
100
101 while (n) {
102 int flag;
103
104 i = rand() % n;
105 x = opentile[i].x;
106 y = opentile[i].y;
107
108 //check if surrounded
109 flag = 1;
110
111 //special case for top of server
112 if (x == sourcex && y == sourceytop) {
113 if (!board[x][y-1]) {
114 flag = 0;
115 }
116 //don't need special case for bottom of server
117 //top is blocked by top server
118 } else {
119 for (j=0; j<4; j++) {
120 add_dir(&x1, &y1, x, y, j);
121 if (x1 < 0 || x1 >= boardw
122 || y1 < 0 || y1 >= boardh) {
123 continue;
124 }
125
126 if (!board[x1][y1]) {
127 flag = 0;
128 break;
129 }
130 }
131 }
132
133 //if so, remove from list
134 if (flag) {
135 n--;
136 memmove(&opentile[i], &opentile[i+1], sizeof(coord_s) * (n - i));
137 continue;
138 }
139
140 j = rand() % 4;
141
142 //not allowed left or right from top of server
143 if (x == sourcex && y == sourceytop) {
144 if (j % 2) continue;
145 }
146
147 add_dir(&x1, &y1, x, y, j);
148
149 if (x1 < 0 || x1 >= boardw
150 || y1 < 0 || y1 >= boardh) continue;
151 if (board[x1][y1]) continue;
152 if (no_fourway && neighbourcount[x][y] >= 3) continue;
153 neighbourcount[x][y]++;
154 neighbourcount[x1][y1]++;
155
156 board[x][y] |= (1 << j);
157 board[x1][y1] |= (1 << ((j + 2) % 4));
158
159 opentile[n].x = x1;
160 opentile[n].y = y1;
161 n++;
162 }
163 }
164
rotatecw(int d,int n)165 int rotatecw(int d, int n)
166 {
167 int i;
168 int d1;
169
170 d1 = d;
171 for (i=0; i<n; i++) {
172 d1 = (d1 << 1);
173 if (d1 >= 16) d1 -= 15;
174 }
175 return d1;
176 }
177
scramble()178 void scramble()
179 {
180 int i, j;
181 int d, d1;
182
183 par = 0;
184
185 game_won = 0;
186
187 //handle server by temporarily merging the two blocks into one
188
189 board[sourcex][sourceybottom] |= board[sourcex][sourceytop] & 1;
190
191 for (i=0; i<boardw; i++) {
192 for (j=0; j<boardh; j++) {
193 if (i == sourcex && j == sourceytop) continue;
194 if (board[i][j]) {
195 d = board[i][j] & 15;
196 switch (rand() % 4) {
197 case 1:
198 d1 = rotatecw(d, 1);
199 if (d != d1) par++;
200 break;
201 case 2:
202 d1 = rotatecw(d, 2);
203 if (d != d1) par+=2;
204 break;
205 case 3:
206 d1 = rotatecw(d, 3);
207 if (d != d1) par++;
208 break;
209 default:
210 d1 = d;
211 break;
212 }
213
214 board[i][j] &= ~15;
215 board[i][j] += d1;
216 }
217 }
218 }
219
220 board[sourcex][sourceytop] &= ~1;
221 board[sourcex][sourceytop] |= board[sourcex][sourceybottom] & 1;
222 board[sourcex][sourceybottom] &= ~1;
223 }
224
check_live()225 void check_live()
226 {
227 coord_s opentile[boardmaxw * boardmaxh];
228 int n;
229 int i, j;
230 int x, y;
231 int x1, y1;
232 int tilecount = 0;
233 int livecount;
234
235 n = 2;
236 opentile[0].x = sourcex;
237 opentile[1].x = sourcex;
238 opentile[0].y = sourceytop;
239 opentile[1].y = sourceybottom;
240
241 for (i=0; i<boardw; i++) {
242 for (j=0; j<boardh; j++) {
243 if (board[i][j]) tilecount++;
244 board[i][j] &= ~16;
245 }
246 }
247 board[sourcex][sourceytop] |= 16;
248 board[sourcex][sourceybottom] |= 16;
249 livecount = 2;
250
251 while (n) {
252 n--;
253 x = opentile[n].x;
254 y = opentile[n].y;
255
256 for (j=0; j<4; j++) {
257 if (board[x][y] & (1 << j)) {
258 add_dir(&x1, &y1, x, y, j);
259 if (x1 < 0 || x1 >= boardw
260 || y1 < 0 || y1 >= boardh) {
261 continue;
262 }
263
264 i = board[x1][y1];
265 if (i & (1 << ((j + 2) % 4))) {
266 if (!(i & 16)) {
267 board[x1][y1] |= 16;
268 livecount++;
269 opentile[n].x = x1;
270 opentile[n].y = y1;
271 n++;
272 }
273 }
274 }
275 }
276 }
277 if (livecount == tilecount) {
278 game_won = 1;
279 }
280 }
281