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 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
  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
  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
  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
 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
 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
 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 }