1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/random.c	Fri Mar 13 00:39:12 2009 -0700
     1.3 @@ -0,0 +1,253 @@
     1.4 +/* Piece randomizers for LOCKJAW, an implementation of the Soviet Mind Game
     1.5 +
     1.6 +Copyright (C) 2006-2007 Damian Yerrick <tepples+lj@spamcop.net>
     1.7 +
     1.8 +This work is free software; you can redistribute it and/or modify
     1.9 +it under the terms of the GNU General Public License as published by
    1.10 +the Free Software Foundation; either version 2 of the License, or
    1.11 +(at your option) any later version.
    1.12 +
    1.13 +This program is distributed in the hope that it will be useful,
    1.14 +but WITHOUT ANY WARRANTY; without even the implied warranty of
    1.15 +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    1.16 +GNU General Public License for more details.
    1.17 +
    1.18 +You should have received a copy of the GNU General Public License
    1.19 +along with this program; if not, write to the Free Software
    1.20 +Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    1.21 +
    1.22 +Original game concept and design by Alexey Pajitnov.
    1.23 +The Software is not sponsored or endorsed by Alexey Pajitnov, Elorg,
    1.24 +or The Tetris Company LLC.
    1.25 +
    1.26 +*/
    1.27 +
    1.28 +#include "lj.h"
    1.29 +
    1.30 +// Order matters.  The history randomizers prefer to give out the
    1.31 +// front half early in the game.  You don't want to give an S or Z
    1.32 +// first, or you force a slide. You also don't want to give an O
    1.33 +// first, or you force a slide with OS or OZ.
    1.34 +
    1.35 +static const signed char piecesNoI[] = {
    1.36 +  1, 2, 5, // front half: J L T
    1.37 +  3, 4, 6  // back half: O S Z
    1.38 +};
    1.39 +
    1.40 +static const signed char piecesTetrominoes[] = {
    1.41 +  0, 1, 2, 5, // front half: I J L T
    1.42 +  3, 4, 6 // back half: O S Z
    1.43 +};
    1.44 +
    1.45 +static const signed char piecesWithSmall[] = {
    1.46 +  0, 1, 2, 5, 9,  // front half: I J L T L3
    1.47 +  3, 7, 8, 4, 6  // back half: O I2 I3 S Z
    1.48 +  // make sure that the S and Z are in the back half
    1.49 +};
    1.50 +
    1.51 +static const signed char piecesSZ[] = {
    1.52 +  4, 6
    1.53 +};
    1.54 +
    1.55 +static const signed char piecesI[] = {
    1.56 +  0
    1.57 +};
    1.58 +
    1.59 +static const signed char piecesT[] = {
    1.60 +  5
    1.61 +};
    1.62 +
    1.63 +static const signed char *const pieceSets[] = {
    1.64 +  piecesTetrominoes,
    1.65 +  piecesNoI,
    1.66 +  piecesSZ,
    1.67 +  piecesI,
    1.68 +  piecesWithSmall,
    1.69 +  piecesT
    1.70 +};
    1.71 +
    1.72 +static const unsigned char pieceSetSizes[] = {
    1.73 +  sizeof(piecesTetrominoes),
    1.74 +  sizeof(piecesNoI),
    1.75 +  sizeof(piecesSZ),
    1.76 +  sizeof(piecesI),
    1.77 +  sizeof(piecesWithSmall),
    1.78 +  sizeof(piecesT)
    1.79 +};
    1.80 +
    1.81 +static void bagInitRandomize(LJField *p) {
    1.82 +  p->permuPhase = 0;
    1.83 +}
    1.84 +
    1.85 +static unsigned int bagRandomize(LJField *p) {
    1.86 +  unsigned int setNo = p->pieceSet;
    1.87 +  unsigned int len = pieceSetSizes[setNo];
    1.88 +  const signed char *set = pieceSets[setNo];
    1.89 +
    1.90 +  int piece;
    1.91 +
    1.92 +  // If we're out of permutation pieces, make new ones by copying
    1.93 +  // from one of the rand#Bag arrays until we hit the -1 sentinel.
    1.94 +  if (p->permuPhase == 0) {
    1.95 +    int pos;
    1.96 +  
    1.97 +    for (pos = 0; pos < len; ++pos) {
    1.98 +      p->permuPiece[pos] = set[pos];
    1.99 +      p->permuPiece[pos + len] = set[pos];
   1.100 +    }
   1.101 +    
   1.102 +    // Double bag: Add one randomly chosen piece to the bag
   1.103 +    if (p->randomizer == LJRAND_2BAG) {
   1.104 +      pos *= 2;
   1.105 +    }
   1.106 +    // 7+1 Bag (TOJ style): Add one randomly chosen piece to the bag
   1.107 +    else if (p->randomizer == LJRAND_BAGPLUS1) {
   1.108 +      p->permuPiece[pos++] = set[ljRand(p) % len];
   1.109 +    }
   1.110 +    p->permuPhase = pos;
   1.111 +  }
   1.112 +
   1.113 +  // Choose a position in the remainder of the deck
   1.114 +  int r = (p->permuPhase > 1) ? ljRand(p) % p->permuPhase : 0;
   1.115 +  
   1.116 +  // Swap the top card with the card at this position
   1.117 +  piece = p->permuPiece[r];
   1.118 +  p->permuPiece[r] = p->permuPiece[--p->permuPhase];
   1.119 +  return piece;
   1.120 +}
   1.121 +
   1.122 +static void mtbInitRandomize(LJField *p) {
   1.123 +  unsigned int setNo = p->pieceSet;
   1.124 +  unsigned int len = pieceSetSizes[setNo];
   1.125 +  const signed char *set = pieceSets[setNo];
   1.126 +
   1.127 +  // At game start, front three are I, J, L
   1.128 +  // Back four (never dealt as first tetromino) are O, S, T, Z
   1.129 +  for (int i = 0; i < len; ++i) {
   1.130 +    p->permuPiece[i] = set[i];
   1.131 +  }
   1.132 +}
   1.133 +
   1.134 +static unsigned int mtbRandomize(LJField *p) {
   1.135 +  unsigned int setNo = p->pieceSet;
   1.136 +  unsigned int len = pieceSetSizes[setNo];
   1.137 +
   1.138 +  // Choose a piece from the three in front
   1.139 +  int r = ljRand(p) % (len / 2);
   1.140 +  int piece = p->permuPiece[r];
   1.141 +  
   1.142 +  // Move it to the back
   1.143 +  for (; r < len - 1; ++r) {
   1.144 +    p->permuPiece[r] = p->permuPiece[r + 1];
   1.145 +  }
   1.146 +  p->permuPiece[len - 1] = piece;
   1.147 +  return piece;
   1.148 +}
   1.149 +
   1.150 +static void tgmInitRandomize(LJField *p) {
   1.151 +  unsigned int setNo = p->pieceSet;
   1.152 +  unsigned int len = pieceSetSizes[setNo];
   1.153 +  
   1.154 +  p->permuPiece[0] = 0;
   1.155 +  for (int i = len / 2; i < len; ++i) {
   1.156 +    p->permuPiece[i] = i & 1 ? LJP_Z : LJP_S;
   1.157 +  }
   1.158 +}
   1.159 +
   1.160 +/* State of TGM randomizer:
   1.161 + * permuPiece[3..6]: history, [3] most recent
   1.162 + * permuPiece[2]: 0 for first piece (use equal probability I, J, L, T)
   1.163 + *   or 1 for subsequent pieces
   1.164 + */
   1.165 +static unsigned int tgmRandomize(LJField *p) {
   1.166 +  unsigned int setNo = p->pieceSet;
   1.167 +  unsigned int len = pieceSetSizes[setNo];
   1.168 +  const signed char *set = pieceSets[setNo];
   1.169 +
   1.170 +  int r = ljRand(p) ^ (ljRand(p) << 15);
   1.171 +  int piece;
   1.172 +  
   1.173 +  if (p->permuPiece[0]) {
   1.174 +
   1.175 +    // Roll up to 6 times for pieces
   1.176 +    for (int rolls = 6;
   1.177 +          rolls > 0;
   1.178 +          --rolls, r /= len) {
   1.179 +      piece = set[r % len];
   1.180 +      int found = 0;
   1.181 +
   1.182 +      // If the piece is not in the history, use it now
   1.183 +      for (int histoPos = len / 2;
   1.184 +           !found && histoPos < len;
   1.185 +           ++histoPos) {
   1.186 +        if (piece == p->permuPiece[histoPos]) {
   1.187 +          found = 1;
   1.188 +        }
   1.189 +      }
   1.190 +      if (!found) {
   1.191 +        break;
   1.192 +      }
   1.193 +    }
   1.194 +  } else {
   1.195 +    p->permuPiece[0] = 1;
   1.196 +    // Generate only pieces in the first half of the list
   1.197 +    piece = set[r % ((len + 1) / 2)];
   1.198 +    if (piece == LJP_O) {
   1.199 +      piece = LJP_T;
   1.200 +    }
   1.201 +  }
   1.202 +  
   1.203 +  // Move it to the back
   1.204 +  for (r = len / 2; r < len - 1; ++r) {
   1.205 +    p->permuPiece[r] = p->permuPiece[r + 1];
   1.206 +  }
   1.207 +  p->permuPiece[len - 1] = piece;
   1.208 +  return piece;
   1.209 +}
   1.210 +
   1.211 +void initRandomize(LJField *p) {
   1.212 +  unsigned int setNo = p->pieceSet;
   1.213 +  unsigned int len = pieceSetSizes[setNo];
   1.214 +  
   1.215 +  if (len < 2) {
   1.216 +    p->randomizer = LJRAND_PURE;
   1.217 +  }
   1.218 +
   1.219 +  switch (p->randomizer) {
   1.220 +  case LJRAND_PURE:
   1.221 +    break;
   1.222 +  case LJRAND_BAG:
   1.223 +  case LJRAND_BAGPLUS1:
   1.224 +  case LJRAND_2BAG:
   1.225 +    bagInitRandomize(p);
   1.226 +    break;
   1.227 +  case LJRAND_HIST_INF:
   1.228 +    mtbInitRandomize(p);
   1.229 +    break;
   1.230 +  case LJRAND_HIST_6:
   1.231 +    tgmInitRandomize(p);
   1.232 +    break;
   1.233 +  }
   1.234 +}
   1.235 +
   1.236 +unsigned int randomize(LJField *p) {
   1.237 +  switch (p->randomizer) {
   1.238 +
   1.239 +  case LJRAND_BAG:
   1.240 +  case LJRAND_BAGPLUS1:
   1.241 +  case LJRAND_2BAG:
   1.242 +    return bagRandomize(p);
   1.243 +  case LJRAND_HIST_INF:
   1.244 +    return mtbRandomize(p);
   1.245 +  case LJRAND_HIST_6:
   1.246 +    return tgmRandomize(p);
   1.247 +  case LJRAND_PURE:
   1.248 +  default:
   1.249 +    {
   1.250 +      unsigned int setNo = p->pieceSet;
   1.251 +      unsigned int len = pieceSetSizes[setNo];
   1.252 +      const signed char *set = pieceSets[setNo];
   1.253 +      return set[ljRand(p) % len];
   1.254 +    }
   1.255 +  }
   1.256 +}