paulo@0: /* Piece randomizers for LOCKJAW, an implementation of the Soviet Mind Game
paulo@0: 
paulo@0: Copyright (C) 2006-2007 Damian Yerrick <tepples+lj@spamcop.net>
paulo@0: 
paulo@0: This work is free software; you can redistribute it and/or modify
paulo@0: it under the terms of the GNU General Public License as published by
paulo@0: the Free Software Foundation; either version 2 of the License, or
paulo@0: (at your option) any later version.
paulo@0: 
paulo@0: This program is distributed in the hope that it will be useful,
paulo@0: but WITHOUT ANY WARRANTY; without even the implied warranty of
paulo@0: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
paulo@0: GNU General Public License for more details.
paulo@0: 
paulo@0: You should have received a copy of the GNU General Public License
paulo@0: along with this program; if not, write to the Free Software
paulo@0: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
paulo@0: 
paulo@0: Original game concept and design by Alexey Pajitnov.
paulo@0: The Software is not sponsored or endorsed by Alexey Pajitnov, Elorg,
paulo@0: or The Tetris Company LLC.
paulo@0: 
paulo@0: */
paulo@0: 
paulo@0: #include "lj.h"
paulo@0: 
paulo@0: // Order matters.  The history randomizers prefer to give out the
paulo@0: // front half early in the game.  You don't want to give an S or Z
paulo@0: // first, or you force a slide. You also don't want to give an O
paulo@0: // first, or you force a slide with OS or OZ.
paulo@0: 
paulo@0: static const signed char piecesNoI[] = {
paulo@0:   1, 2, 5, // front half: J L T
paulo@0:   3, 4, 6  // back half: O S Z
paulo@0: };
paulo@0: 
paulo@0: static const signed char piecesTetrominoes[] = {
paulo@0:   0, 1, 2, 5, // front half: I J L T
paulo@0:   3, 4, 6 // back half: O S Z
paulo@0: };
paulo@0: 
paulo@0: static const signed char piecesWithSmall[] = {
paulo@0:   0, 1, 2, 5, 9,  // front half: I J L T L3
paulo@0:   3, 7, 8, 4, 6  // back half: O I2 I3 S Z
paulo@0:   // make sure that the S and Z are in the back half
paulo@0: };
paulo@0: 
paulo@0: static const signed char piecesSZ[] = {
paulo@0:   4, 6
paulo@0: };
paulo@0: 
paulo@0: static const signed char piecesI[] = {
paulo@0:   0
paulo@0: };
paulo@0: 
paulo@0: static const signed char piecesT[] = {
paulo@0:   5
paulo@0: };
paulo@0: 
paulo@0: static const signed char *const pieceSets[] = {
paulo@0:   piecesTetrominoes,
paulo@0:   piecesNoI,
paulo@0:   piecesSZ,
paulo@0:   piecesI,
paulo@0:   piecesWithSmall,
paulo@0:   piecesT
paulo@0: };
paulo@0: 
paulo@0: static const unsigned char pieceSetSizes[] = {
paulo@0:   sizeof(piecesTetrominoes),
paulo@0:   sizeof(piecesNoI),
paulo@0:   sizeof(piecesSZ),
paulo@0:   sizeof(piecesI),
paulo@0:   sizeof(piecesWithSmall),
paulo@0:   sizeof(piecesT)
paulo@0: };
paulo@0: 
paulo@0: static void bagInitRandomize(LJField *p) {
paulo@0:   p->permuPhase = 0;
paulo@0: }
paulo@0: 
paulo@0: static unsigned int bagRandomize(LJField *p) {
paulo@0:   unsigned int setNo = p->pieceSet;
paulo@0:   unsigned int len = pieceSetSizes[setNo];
paulo@0:   const signed char *set = pieceSets[setNo];
paulo@0: 
paulo@0:   int piece;
paulo@0: 
paulo@0:   // If we're out of permutation pieces, make new ones by copying
paulo@0:   // from one of the rand#Bag arrays until we hit the -1 sentinel.
paulo@0:   if (p->permuPhase == 0) {
paulo@0:     int pos;
paulo@0:   
paulo@0:     for (pos = 0; pos < len; ++pos) {
paulo@0:       p->permuPiece[pos] = set[pos];
paulo@0:       p->permuPiece[pos + len] = set[pos];
paulo@0:     }
paulo@0:     
paulo@0:     // Double bag: Add one randomly chosen piece to the bag
paulo@0:     if (p->randomizer == LJRAND_2BAG) {
paulo@0:       pos *= 2;
paulo@0:     }
paulo@0:     // 7+1 Bag (TOJ style): Add one randomly chosen piece to the bag
paulo@0:     else if (p->randomizer == LJRAND_BAGPLUS1) {
paulo@0:       p->permuPiece[pos++] = set[ljRand(p) % len];
paulo@0:     }
paulo@0:     p->permuPhase = pos;
paulo@0:   }
paulo@0: 
paulo@0:   // Choose a position in the remainder of the deck
paulo@0:   int r = (p->permuPhase > 1) ? ljRand(p) % p->permuPhase : 0;
paulo@0:   
paulo@0:   // Swap the top card with the card at this position
paulo@0:   piece = p->permuPiece[r];
paulo@0:   p->permuPiece[r] = p->permuPiece[--p->permuPhase];
paulo@0:   return piece;
paulo@0: }
paulo@0: 
paulo@0: static void mtbInitRandomize(LJField *p) {
paulo@0:   unsigned int setNo = p->pieceSet;
paulo@0:   unsigned int len = pieceSetSizes[setNo];
paulo@0:   const signed char *set = pieceSets[setNo];
paulo@0: 
paulo@0:   // At game start, front three are I, J, L
paulo@0:   // Back four (never dealt as first tetromino) are O, S, T, Z
paulo@0:   for (int i = 0; i < len; ++i) {
paulo@0:     p->permuPiece[i] = set[i];
paulo@0:   }
paulo@0: }
paulo@0: 
paulo@0: static unsigned int mtbRandomize(LJField *p) {
paulo@0:   unsigned int setNo = p->pieceSet;
paulo@0:   unsigned int len = pieceSetSizes[setNo];
paulo@0: 
paulo@0:   // Choose a piece from the three in front
paulo@0:   int r = ljRand(p) % (len / 2);
paulo@0:   int piece = p->permuPiece[r];
paulo@0:   
paulo@0:   // Move it to the back
paulo@0:   for (; r < len - 1; ++r) {
paulo@0:     p->permuPiece[r] = p->permuPiece[r + 1];
paulo@0:   }
paulo@0:   p->permuPiece[len - 1] = piece;
paulo@0:   return piece;
paulo@0: }
paulo@0: 
paulo@0: static void tgmInitRandomize(LJField *p) {
paulo@0:   unsigned int setNo = p->pieceSet;
paulo@0:   unsigned int len = pieceSetSizes[setNo];
paulo@0:   
paulo@0:   p->permuPiece[0] = 0;
paulo@0:   for (int i = len / 2; i < len; ++i) {
paulo@0:     p->permuPiece[i] = i & 1 ? LJP_Z : LJP_S;
paulo@0:   }
paulo@0: }
paulo@0: 
paulo@0: /* State of TGM randomizer:
paulo@0:  * permuPiece[3..6]: history, [3] most recent
paulo@0:  * permuPiece[2]: 0 for first piece (use equal probability I, J, L, T)
paulo@0:  *   or 1 for subsequent pieces
paulo@0:  */
paulo@0: static unsigned int tgmRandomize(LJField *p) {
paulo@0:   unsigned int setNo = p->pieceSet;
paulo@0:   unsigned int len = pieceSetSizes[setNo];
paulo@0:   const signed char *set = pieceSets[setNo];
paulo@0: 
paulo@0:   int r = ljRand(p) ^ (ljRand(p) << 15);
paulo@0:   int piece;
paulo@0:   
paulo@0:   if (p->permuPiece[0]) {
paulo@0: 
paulo@0:     // Roll up to 6 times for pieces
paulo@0:     for (int rolls = 6;
paulo@0:           rolls > 0;
paulo@0:           --rolls, r /= len) {
paulo@0:       piece = set[r % len];
paulo@0:       int found = 0;
paulo@0: 
paulo@0:       // If the piece is not in the history, use it now
paulo@0:       for (int histoPos = len / 2;
paulo@0:            !found && histoPos < len;
paulo@0:            ++histoPos) {
paulo@0:         if (piece == p->permuPiece[histoPos]) {
paulo@0:           found = 1;
paulo@0:         }
paulo@0:       }
paulo@0:       if (!found) {
paulo@0:         break;
paulo@0:       }
paulo@0:     }
paulo@0:   } else {
paulo@0:     p->permuPiece[0] = 1;
paulo@0:     // Generate only pieces in the first half of the list
paulo@0:     piece = set[r % ((len + 1) / 2)];
paulo@0:     if (piece == LJP_O) {
paulo@0:       piece = LJP_T;
paulo@0:     }
paulo@0:   }
paulo@0:   
paulo@0:   // Move it to the back
paulo@0:   for (r = len / 2; r < len - 1; ++r) {
paulo@0:     p->permuPiece[r] = p->permuPiece[r + 1];
paulo@0:   }
paulo@0:   p->permuPiece[len - 1] = piece;
paulo@0:   return piece;
paulo@0: }
paulo@0: 
paulo@0: void initRandomize(LJField *p) {
paulo@0:   unsigned int setNo = p->pieceSet;
paulo@0:   unsigned int len = pieceSetSizes[setNo];
paulo@0:   
paulo@0:   if (len < 2) {
paulo@0:     p->randomizer = LJRAND_PURE;
paulo@0:   }
paulo@0: 
paulo@0:   switch (p->randomizer) {
paulo@0:   case LJRAND_PURE:
paulo@0:     break;
paulo@0:   case LJRAND_BAG:
paulo@0:   case LJRAND_BAGPLUS1:
paulo@0:   case LJRAND_2BAG:
paulo@0:     bagInitRandomize(p);
paulo@0:     break;
paulo@0:   case LJRAND_HIST_INF:
paulo@0:     mtbInitRandomize(p);
paulo@0:     break;
paulo@0:   case LJRAND_HIST_6:
paulo@0:     tgmInitRandomize(p);
paulo@0:     break;
paulo@0:   }
paulo@0: }
paulo@0: 
paulo@0: unsigned int randomize(LJField *p) {
paulo@0:   switch (p->randomizer) {
paulo@0: 
paulo@0:   case LJRAND_BAG:
paulo@0:   case LJRAND_BAGPLUS1:
paulo@0:   case LJRAND_2BAG:
paulo@0:     return bagRandomize(p);
paulo@0:   case LJRAND_HIST_INF:
paulo@0:     return mtbRandomize(p);
paulo@0:   case LJRAND_HIST_6:
paulo@0:     return tgmRandomize(p);
paulo@0:   case LJRAND_PURE:
paulo@0:   default:
paulo@0:     {
paulo@0:       unsigned int setNo = p->pieceSet;
paulo@0:       unsigned int len = pieceSetSizes[setNo];
paulo@0:       const signed char *set = pieceSets[setNo];
paulo@0:       return set[ljRand(p) % len];
paulo@0:     }
paulo@0:   }
paulo@0: }