game.c

   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 sourcex, sourceytop, sourceybottom;
  33
  34 int wrap_flag = 0;
  35 int no_fourway = 0;
  36 int game_won = 0;
  37
  38 static int par;
  39
  40 coord_s dir[4] = {
  41     {0, -1},
  42     {1, 0},
  43     {0, 1},
  44     {-1, 0},
  45 };
  46 // 0 = up, 1 = right, 2 = down, 3 = left
  47 //    0
  48 //    |
  49 // 3--+--1
  50 //    |
  51 //    2
  52
  53 void add_dir(int *x, int *y, int x1, int y1, int d)
  54 {
  55     *x = x1 + dir[d].x;
  56     *y = y1 + dir[d].y;
  57
  58     if (wrap_flag) {
  59         if (*x < 0) *x = boardw - 1;
  60         if (*x >= boardw) *x = 0;
  61         if (*y < 0) *y = boardh - 1;
  62         if (*y >= boardh) *y = 0;
  63     }
  64 }
  65
  66 void generate_maze()
  67 {
  68     coord_s opentile[boardmaxw * boardmaxh];
  69     int n;
  70     int i, j;
  71     int x, y;
  72     int x1, y1;
  73
  74     n = 2;
  75     opentile[0].x = sourcex;
  76     opentile[1].x = sourcex;
  77     opentile[0].y = sourceytop;
  78     opentile[1].y = sourceybottom;
  79
  80     for (i=0; i<boardw; i++) {
  81         for (j=0; j<boardh; j++) {
  82             board[i][j] = 0;
  83             neighbourcount[i][j] = 0;
  84         }
  85     }
  86     board[sourcex][sourceytop] = 32;
  87     board[sourcex][sourceybottom] = 32;
  88
  89     while (n) {
  90         int flag;
  91
  92         i = rand() % n;
  93         x = opentile[i].x;
  94         y = opentile[i].y;
  95
  96         //check if surrounded
  97         flag = 1;
  98
  99         //special case for top of server
 100         if (x == sourcex && y == sourceytop) {
 101             if (!board[x][y-1]) {
 102                 flag = 0;
 103             }
 104             //don't need special case for bottom of server
 105             //top is blocked by top server
 106         } else {
 107             for (j=0; j<4; j++) {
 108                 add_dir(&x1, &y1, x, y, j);
 109                 if (x1 < 0 || x1 >= boardw
 110                         || y1 < 0 || y1 >= boardh) {
 111                     continue;
 112                 }
 113
 114                 if (!board[x1][y1]) {
 115                     flag = 0;
 116                     break;
 117                 }
 118             }
 119         }
 120
 121         //if so, remove from list
 122         if (flag) {
 123             n--;
 124             memmove(&opentile[i], &opentile[i+1], sizeof(coord_s) * (n - i));
 125             continue;
 126         }
 127
 128         j = rand() % 4;
 129
 130         //not allowed left or right from top of server
 131         if (x == sourcex && y == sourceytop) {
 132             if (j % 2) continue;
 133         }
 134
 135         add_dir(&x1, &y1, x, y, j);
 136
 137         if (x1 < 0 || x1 >= boardw
 138                 || y1 < 0 || y1 >= boardh) continue;
 139         if (board[x1][y1]) continue;
 140         if (no_fourway && neighbourcount[x][y] >= 3) continue;
 141         neighbourcount[x][y]++;
 142         neighbourcount[x1][y1]++;
 143
 144         board[x][y] |= (1 << j);
 145         board[x1][y1] |= (1 << ((j + 2) % 4));
 146
 147         opentile[n].x = x1;
 148         opentile[n].y = y1;
 149         n++;
 150     }
 151 }
 152
 153 int rotatecw(int d, int n)
 154 {
 155     int i;
 156     int d1;
 157
 158     d1 = d;
 159     for (i=0; i<n; i++) {
 160         d1 = (d1 << 1);
 161         if (d1 >= 16) d1 -= 15;
 162     }
 163     return d1;
 164 }
 165
 166 void scramble()
 167 {
 168     int i, j;
 169     int d, d1;
 170
 171     par = 0;
 172
 173     game_won = 0;
 174
 175     //handle server by temporarily merging the two blocks into one
 176
 177     board[sourcex][sourceybottom] |= board[sourcex][sourceytop] & 1;
 178
 179     for (i=0; i<boardw; i++) {
 180         for (j=0; j<boardh; j++) {
 181             if (i == sourcex && j == sourceytop) continue;
 182             if (board[i][j]) {
 183                 d = board[i][j] & 15;
 184                 switch (rand() % 4) {
 185                     case 1:
 186                         d1 = rotatecw(d, 1);
 187                         if (d != d1) par++;
 188                         break;
 189                     case 2:
 190                         d1 = rotatecw(d, 2);
 191                         if (d != d1) par+=2;
 192                         break;
 193                     case 3:
 194                         d1 = rotatecw(d, 3);
 195                         if (d != d1) par++;
 196                         break;
 197                     default:
 198                         d1 = d;
 199                         break;
 200                 }
 201
 202                 board[i][j] &= ~15;
 203                 board[i][j] += d1;
 204             }
 205         }
 206     }
 207
 208     board[sourcex][sourceytop] &= ~1;
 209     board[sourcex][sourceytop] |= board[sourcex][sourceybottom] & 1;
 210     board[sourcex][sourceybottom] &= ~1;
 211 }
 212
 213 void check_live()
 214 {
 215     coord_s opentile[boardmaxw * boardmaxh];
 216     int n;
 217     int i, j;
 218     int x, y;
 219     int x1, y1;
 220     int tilecount = 0;
 221     int livecount;
 222
 223     n = 2;
 224     opentile[0].x = sourcex;
 225     opentile[1].x = sourcex;
 226     opentile[0].y = sourceytop;
 227     opentile[1].y = sourceybottom;
 228
 229     for (i=0; i<boardw; i++) {
 230         for (j=0; j<boardh; j++) {
 231             if (board[i][j]) tilecount++;
 232             board[i][j] &= ~16;
 233         }
 234     }
 235     board[sourcex][sourceytop] |= 16;
 236     board[sourcex][sourceybottom] |= 16;
 237     livecount = 2;
 238
 239     while (n) {
 240         n--;
 241         x = opentile[n].x;
 242         y = opentile[n].y;
 243
 244         for (j=0; j<4; j++) {
 245             if (board[x][y] & (1 << j)) {
 246                 add_dir(&x1, &y1, x, y, j);
 247                 if (x1 < 0 || x1 >= boardw
 248                         || y1 < 0 || y1 >= boardh) {
 249                     continue;
 250                 }
 251
 252                 i = board[x1][y1];
 253                 if (i & (1 << ((j + 2) % 4))) {
 254                     if (!(i & 16)) {
 255                         board[x1][y1] |= 16;
 256                         livecount++;
 257                         opentile[n].x = x1;
 258                         opentile[n].y = y1;
 259                         n++;
 260                     }
 261                 }
 262             }
 263         }
 264     }
 265     if (livecount == tilecount) {
 266         game_won = 1;
 267     }
 268 }