From 3f6159a968fcf7fc850b8b0873c32239b668f819 Mon Sep 17 00:00:00 2001 From: Eugene Sandulenko Date: Mon, 20 Jul 2009 22:15:37 +0000 Subject: Proper implementation of microscope puzzle. svn-id: r42634 --- engines/groovie/cell.cpp | 818 +++++++++++++++++++++++++++++++++++++++------ engines/groovie/cell.h | 48 ++- engines/groovie/script.cpp | 36 +- engines/groovie/script.h | 3 + 4 files changed, 773 insertions(+), 132 deletions(-) (limited to 'engines/groovie') diff --git a/engines/groovie/cell.cpp b/engines/groovie/cell.cpp index 3bc8650aa6..e6d8d48759 100644 --- a/engines/groovie/cell.cpp +++ b/engines/groovie/cell.cpp @@ -27,156 +27,772 @@ namespace Groovie { -CellGame::CellGame(byte *board) : - _board(board) { +CellGame::CellGame() { _startX = _startY = _endX = _endY = 255; -} -int8 CellGame::calcMove(byte *origboard, uint8 color, uint8 depth) { - uint8 i, j; - int8 di, dj; - uint8 bestStartX, bestStartY, bestEndX, bestEndY; - int8 bestDiff = -100; - int8 origBoardCount = countBoard(origboard, color); - int8 currDiff = -100; - byte *newboard; - uint8 boardmemsize = sizeof(byte) * BOARDSIZE * BOARDSIZE; - uint8 oppColor = 3 - color; + _stack_index = _boardStackPtr = 0; + _flag4 = false; + _flag2 = false; + _coeff3 = 0; - bestStartX = bestStartY = bestEndX = bestEndY = 255; - newboard = (byte*) malloc(boardmemsize); - memcpy(newboard, origboard, boardmemsize); + _moveCount = 0; +} - if (0 == depth) { +byte CellGame::getStartX() { + if (_startX > BOARDSIZE) { + warning ("CellGame::getStartX: not calculated yet (%d)!", _startX); return 0; + } else { + return _startX; + } +} + +byte CellGame::getStartY() { + if (_startY > BOARDSIZE) { + warning ("CellGame::getStartY: not calculated yet (%d)!", _startY); + return 6; + } else { + return _startY; + } +} + +byte CellGame::getEndX() { + if (_endX > BOARDSIZE) { + warning ("CellGame::getEndX: not calculated yet (%d)!", _endX); + return 1; + } else { + return _endX; + } +} + +byte CellGame::getEndY() { + if (_endY > BOARDSIZE) { + warning ("CellGame::getEndY: not calculated yet (%d)!", _endY); + return 6; + } else { + return _endY; + } +} + +CellGame::~CellGame() { +} + +const int8 possibleMoves[][9] = { + { 1, 7, 8, -1 }, + { 0, 2, 7, 8, 9, -1 }, + { 1, 3, 8, 9, 10, -1 }, + { 2, 4, 9, 10, 11, -1 }, + { 3, 5, 10, 11, 12, -1 }, + { 4, 6, 11, 12, 13, -1 }, // 5 + { 5, 12, 13, -1 }, + { 0, 1, 8, 14, 15, -1 }, + { 0, 1, 2, 7, 9, 14, 15, 16, -1 }, + { 1, 2, 3, 8, 10, 15, 16, 17, -1 }, + { 2, 3, 4, 9, 11, 16, 17, 18, -1 }, // 10 + { 3, 4, 5, 10, 12, 17, 18, 19, -1 }, + { 4, 5, 6, 11, 13, 18, 19, 20, -1 }, + { 5, 6, 12, 19, 20, -1 }, + { 7, 8, 15, 21, 22, -1 }, + { 7, 8, 9, 14, 16, 21, 22, 23, -1 }, // 15 + { 8, 9, 10, 15, 17, 22, 23, 24, -1 }, + { 9, 10, 11, 16, 18, 23, 24, 25, -1 }, + { 10, 11, 12, 17, 19, 24, 25, 26, -1 }, + { 11, 12, 13, 18, 20, 25, 26, 27, -1 }, + { 12, 13, 19, 26, 27, -1 }, // 20 + { 14, 15, 22, 28, 29, -1 }, + { 14, 15, 16, 21, 23, 28, 29, 30, -1 }, + { 15, 16, 17, 22, 24, 29, 30, 31, -1 }, + { 16, 17, 18, 23, 25, 30, 31, 32, -1 }, + { 17, 18, 19, 24, 26, 31, 32, 33, -1 }, // 25 + { 18, 19, 20, 25, 27, 32, 33, 34, -1 }, + { 19, 20, 26, 33, 34, -1 }, + { 21, 22, 29, 35, 36, -1 }, + { 21, 22, 23, 28, 30, 35, 36, 37, -1 }, + { 22, 23, 24, 29, 31, 36, 37, 38, -1 }, // 30 + { 23, 24, 25, 30, 32, 37, 38, 39, -1 }, + { 24, 25, 26, 31, 33, 38, 39, 40, -1 }, + { 25, 26, 27, 32, 34, 39, 40, 41, -1 }, + { 26, 27, 33, 40, 41, -1 }, + { 28, 29, 36, 42, 43, -1 }, // 35 + { 28, 29, 30, 35, 37, 42, 43, 44, -1 }, + { 29, 30, 31, 36, 38, 43, 44, 45, -1 }, + { 30, 31, 32, 37, 39, 44, 45, 46, -1 }, + { 31, 32, 33, 38, 40, 45, 46, 47, -1 }, + { 32, 33, 34, 39, 41, 46, 47, 48, -1 }, // 40 + { 33, 34, 40, 47, 48, -1 }, + { 35, 36, 43, -1 }, + { 35, 36, 37, 42, 44, -1 }, + { 36, 37, 38, 43, 45, -1 }, + { 37, 38, 39, 44, 46, -1 }, // 45 + { 38, 39, 40, 45, 47, -1 }, + { 39, 40, 41, 46, 48, -1 }, + { 40, 41, 47, -1 } +}; + + +const int8 strategy2[][17] = { + { 2, 9, 14, 15, 16, -1 }, + { 3, 10, 14, 15, 16, 17, -1 }, + { 0, 4, 7, 11, 14, 15, 16, 17, 18, -1 }, + { 1, 5, 8, 12, 15, 16, 17, 18, 19, -1 }, + { 2, 6, 9, 13, 16, 17, 18, 19, 20, -1 }, + { 3, 10, 17, 18, 19, 20, -1 }, // 5 + { 4, 11, 18, 19, 20, -1 }, + { 2, 9, 16, 21, 22, 23, -1 }, + { 3, 10, 17, 21, 22, 23, 24, -1 }, + { 0, 4, 7, 11, 14, 18, 21, 22, 23, 24, 25, -1 }, + { 1, 5, 8, 12, 15, 19, 22, 23, 24, 25, 26, -1 }, // 10 + { 2, 6, 9, 13, 16, 20, 23, 24, 25, 26, 27, -1 }, + { 3, 10, 17, 24, 25, 26, 27, -1 }, + { 4, 11, 18, 25, 26, 27, -1 }, + { 0, 1, 2, 9, 16, 23, 28, 29, 30, -1 }, + { 0, 1, 2, 3, 10, 17, 24, 28, 29, 30, 31, -1 }, // 15 + { 0, 1, 2, 3, 4, 7, 11, 14, 18, 21, 25, 28, 29, 30, 31, 32, -1 }, + { 1, 2, 3, 4, 5, 8, 12, 15, 19, 22, 26, 29, 30, 31, 32, 33, -1 }, + { 2, 3, 4, 5, 6, 9, 13, 16, 20, 23, 27, 30, 31, 32, 33, 34, -1 }, + { 3, 4, 5, 6, 10, 17, 24, 31, 32, 33, 34, -1 }, + { 4, 5, 6, 11, 18, 25, 32, 33, 34, -1 }, // 20 + { 7, 8, 9, 16, 23, 30, 35, 36, 37, -1 }, + { 7, 8, 9, 10, 17, 24, 31, 35, 36, 37, 38, -1 }, + { 7, 8, 9, 10, 11, 14, 18, 21, 25, 28, 32, 35, 36, 37, 38, 39, -1 }, + { 8, 9, 10, 11, 12, 15, 19, 22, 26, 29, 33, 36, 37, 38, 39, 40, -1 }, + { 9, 10, 11, 12, 13, 16, 20, 23, 27, 30, 34, 37, 38, 39, 40, 41, -1 }, // 25 + { 10, 11, 12, 13, 17, 24, 31, 38, 39, 40, 41, -1 }, + { 11, 12, 13, 18, 25, 32, 39, 40, 41, -1 }, + { 14, 15, 16, 23, 30, 37, 42, 43, 44, -1 }, + { 14, 15, 16, 17, 24, 31, 38, 42, 43, 44, 45, -1 }, + { 14, 15, 16, 17, 18, 21, 25, 28, 32, 35, 39, 42, 43, 44, 45, 46, -1 }, // 30 + { 15, 16, 17, 18, 19, 22, 26, 29, 33, 36, 40, 43, 44, 45, 46, 47, -1 }, + { 16, 17, 18, 19, 20, 23, 27, 30, 34, 37, 41, 44, 45, 46, 47, 48, -1 }, + { 17, 18, 19, 20, 24, 31, 38, 45, 46, 47, 48, -1 }, + { 18, 19, 20, 25, 32, 39, 46, 47, 48, -1 }, + { 21, 22, 23, 30, 37, 44, -1 }, // 35 + { 21, 22, 23, 24, 31, 38, 45, -1 }, + { 21, 22, 23, 24, 25, 28, 32, 35, 39, 42, 46, -1 }, + { 22, 23, 24, 25, 26, 29, 33, 36, 40, 43, 47, -1 }, + { 23, 24, 25, 26, 27, 30, 34, 37, 41, 44, 48, -1 }, + { 24, 25, 26, 27, 31, 38, 45, -1 }, // 40 + { 25, 26, 27, 32, 39, 46, -1 }, + { 28, 29, 30, 37, 44, -1 }, + { 28, 29, 30, 31, 38, 45, -1 }, + { 28, 29, 30, 31, 32, 35, 39, 42, 46, -1 }, + { 29, 30, 31, 32, 33, 36, 40, 43, 47, -1 }, // 45 + { 30, 31, 32, 33, 34, 37, 41, 44, 48, -1 }, + { 31, 32, 33, 34, 38, 45, -1 }, + { 32, 33, 34, 39, 46, -1 } +}; + +void CellGame::copyToTempBoard() { + for (int i = 0; i < 53; ++i) { + _tempBoard[i] = _board[i]; + } +} + +void CellGame::copyFromTempBoard() { + for (int i = 0; i < 53; ++i) { + _board[i] = _tempBoard[i]; } +} + +void CellGame::copyToShadowBoard() { + _board[53] = 0; + _board[55] = 1; + _board[56] = 0; + + for (int i = 0; i < 49; ++i) { + _shadowBoard[i] = _board[i]; + } +} + +void CellGame::pushBoard() { + assert(_boardStackPtr < 57 * 9); - for (i = 0; BOARDSIZE > i; i++) { // For every square on the board - for (j = 0; BOARDSIZE > j; j++) { // - if (color == *(origboard + i + (BOARDSIZE * j))) { // If the square is the desired colour - for (di = -2; 2 >= di; di++) { // Check every square two or less in every direction - for (dj = -2; 2 >= dj; dj++) { // - if (di != 0 || dj != 0) { // Don't allow a move onto itself - debugC(7, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Testing move %d, %d-> %d, %d", depth, i, j, i+di, j+dj); - if (validMove(origboard, color, i+di, j+dj)) { - int8 nextlevel; - debugC(5, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Valid move %d, %d-> %d, %d", depth, i, j, i+di, j+dj); - execMove (newboard, color, i, j, i+di, j+dj); - - nextlevel = calcMove (newboard, oppColor, depth - 1); - debugC(5, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Next level down returned %d", depth, nextlevel); - currDiff = countBoard(newboard, color) - origBoardCount - nextlevel; - if (currDiff > bestDiff) { - debugC(4, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Found new best move (diff of %d): %d, %d-> %d, %d", depth, currDiff, i, j, i+di, j+dj); - bestDiff = currDiff; - bestStartX = i; - bestStartY = j; - bestEndX = i+di; - bestEndY = j+dj; - - } - // TODO: ideal would be to revert the move, rather than copy the board again. I think. - memcpy(newboard, origboard, boardmemsize); - } - } + for (int i = 0; i < 57; ++i) + _boardStack[_boardStackPtr + i] = _board[i]; + _boardStackPtr += 57; +} + +void CellGame::popBoard() { + assert(_boardStackPtr > 0); + + _boardStackPtr -= 57; + for (int i = 0; i < 57; ++i) { + _board[i] = _boardStack[_boardStackPtr + i]; + } +} + +void CellGame::pushShadowBoard() { + assert(_boardStackPtr < 57 * 9); + + for (int i = 0; i < 57; ++i) + _boardStack[_boardStackPtr + i] = _shadowBoard[i]; + + _boardStackPtr += 57; +} + +void CellGame::popShadowBoard() { + assert(_boardStackPtr > 0); + + _boardStackPtr -= 57; + + for (int i = 0; i < 57; ++i) { + _shadowBoard[i] = _boardStack[_boardStackPtr + i]; + } +} + +void CellGame::clearMoves() { + _stack_startXY[0] = _board[53]; + _stack_endXY[0] = _board[54]; + _stack_pass[0] = _board[55]; + + _stack_index = 1; +} + +void CellGame::pushMove() { + _stack_startXY[_stack_index] = _board[53]; + _stack_endXY[_stack_index] = _board[54]; + _stack_pass[_stack_index] = _board[55]; + + _stack_index++; +} + +void CellGame::resetMove() { + _board[53] = 0; + _board[54] = 0; + _board[55] = 0; +} + +void CellGame::takeCells(uint16 whereTo, int8 color) { + int cellN; + const int8 *str; + + str = possibleMoves[whereTo]; + while (1) { + cellN = *str++; + if (cellN < 0) + break; + if (_tempBoard[cellN] > 0) { + --_tempBoard[_tempBoard[cellN] + 48]; + _tempBoard[cellN] = color; + ++_tempBoard[color + 48]; + } + } +} + +void CellGame::countAllCells() { + _board[49] = 0; + _board[50] = 0; + _board[51] = 0; + _board[52] = 0; + + for (int i = 0; i < 49; i++) { + switch (_board[i]) { + case 1: // CELL_BLUE + _board[49]++; + break; + case 2: // CELL_GREEN + _board[50]++; + break; + case 3: + _board[51]++; + break; + case 4: + _board[52]++; + break; + } + } +} + +int CellGame::countCellsOnTempBoard(int8 color) { + const int8 *str; + int res = 0; + int i; + + for (i = 0; i < 49; i++) + _boardSum[i] = 0; + + for (i = 0; i < 49; i++) { + if (_tempBoard[i] == color) { + for (str = possibleMoves[i]; *str > 0; str++) { + if (!_tempBoard[*str]) + ++_boardSum[*str]; + } + } + } + + for (i = 0; i < 49; i++) + res += _boardSum[i]; + + return res; +} + +bool CellGame::canMoveFunc1(int8 color) { + const int8 *str; + + if (_board[55] == 1) { + for (; _board[53] < 49; _board[53]++) { + if (_shadowBoard[_board[53]] == color) { + str = &possibleMoves[_board[53]][_board[56]]; + for (;_board[56] < 8; _board[56]++) { + _board[54] = *str++; + if (_board[54] < 0) + break; + if (!_shadowBoard[_board[54]]) { + _shadowBoard[_board[54]] = -1; + ++_board[56]; + return true; } } + _board[56] = 0; + } + } + _board[53] = 0; + _board[55] = 2; + _board[56] = 0; + } + if (_board[55] == 2) { + for (; _board[53] < 49; _board[53]++) { + if (_shadowBoard[_board[53]] == color) { + str = &strategy2[_board[53]][_board[56]]; + for (;_board[56] < 16; _board[56]++) { + _board[54] = *str++; + if (_board[54] < 0) + break; + if (!_board[_board[54]]) { + ++_board[56]; + return true; + } + } + _board[56] = 0; } } } - _startX = bestStartX; - _startY = bestStartY; - _endX = bestEndX; - _endY = bestEndY; - - debugC(2, kGroovieDebugCell | kGroovieDebugAll, "Depth: %d: Best move is (diff of %d): %d, %d-> %d, %d", depth, bestDiff, _startX, _startY, _endX, _endY); - free(newboard); - debugC(5, kGroovieDebugCell | kGroovieDebugAll, "Freed newboard"); - return bestDiff; + return false; } -void CellGame::execMove(byte *board, uint8 color, int8 startX, int8 startY, int8 endX, int8 endY) { - int8 i, j; - uint8 colorToEat = 3 - color; // The opposite of the colour passed: 2 -> 1, 1 -> 2 +bool CellGame::canMoveFunc3(int8 color) { + const int8 *str; + + if (_board[55] == 1) { + for (; _board[53] < 49; _board[53]++) { + if (_shadowBoard[_board[53]] == color) { + str = &possibleMoves[_board[53]][_board[56]]; + for (;_board[56] < 8; _board[56]++) { + _board[54] = *str++; + if (_board[54] < 0) + break; + if (!_shadowBoard[_board[54]]) { + _shadowBoard[_board[54]] = -1; + ++_board[56]; + return true; + } + } + _board[56] = 0; + } + } - if (abs(endX - startX) == 2 || abs(endY - startY) == 2) { - *(board + startX + BOARDSIZE * startY) = 0; + _board[53] = 0; + _board[55] = 2; + _board[56] = 0; + for (int i = 0; i < 49; ++i) + _shadowBoard[i] = _board[i]; + } + if (_board[55] == 2) { + for (; _board[53] < 49; _board[53]++) { + if (_shadowBoard[_board[53]] == color) { + str = &strategy2[_board[53]][_board[56]]; + for (;_board[56] < 16; _board[56]++) { + _board[54] = *str++; + if (_board[54] < 0) + break; + if (!_shadowBoard[_board[54]]) { + _shadowBoard[_board[54]] = -1; + ++_board[56]; + return true; + } + } + _board[56] = 0; + } + } } - *(board + endX + BOARDSIZE * endY) = color; + return false; +} + +bool CellGame::canMoveFunc2(int8 color) { + const int8 *str; - for (i = (endX - 1); endX + 1 >= i; i++) { - for (j = (endY - 1); endY + 1 >= j; j++) { - if (BOARDSIZE > i && BOARDSIZE > j && 0 <= i && 0 <= j) { // Don't wrap around the board edges! - uint8 offset = i + BOARDSIZE * j; - if (colorToEat == *(board + offset)) { - *(board + offset) = color; + while (1) { + while (_board[_board[54]]) { + ++_board[54]; + if (_board[54] >= 49) + return false; + } + if (!_board[55]) { + str = possibleMoves[_board[54]]; + while (1) { + _board[53] = *str++; + if (_board[53] < 0) + break; + if (_board[_board[53]] == color) { + _board[55] = 1; + return true; + } + } + _board[55] = 1; + } + if (_board[55] == 1) { + _board[55] = 2; + _board[56] = 0; + } + if (_board[55] == 2) { + str = &strategy2[_board[54]][_board[56]]; + for (; _board[56] < 16; _board[56]++) { + _board[53] = *str++; + if (_board[53] < 0) + break; + if (_board[_board[53]] == color) { + ++_board[56]; + return true; } } + ++_board[54]; + _board[55] = 0; + if (_board[54] >= 49) + break; } } + return false; } -bool CellGame::validMove(byte *board, uint8 color, int8 endX, int8 endY) { - if (0 > endX || 0 > endY || BOARDSIZE <= endX || BOARDSIZE <= endY) { // Move is out of bounds - return false; +void CellGame::makeMove(int8 color) { + copyToTempBoard(); + _tempBoard[_board[54]] = color; + ++_tempBoard[color + 48]; + if (_board[55] == 2) { + _tempBoard[_board[53]] = 0; + --_tempBoard[color + 48]; } - if (0 == *(board + endX + (BOARDSIZE * endY))) { - return true; + takeCells(_board[54], color); +} + +int CellGame::getBoardWeight(int8 color1, int8 color2) { + int8 celln; + const int8 *str; + byte cellCnt[8]; + + str = possibleMoves[_board[54]]; + cellCnt[1] = _board[49]; + cellCnt[2] = _board[50]; + cellCnt[3] = _board[51]; + cellCnt[4] = _board[52]; + if (_board[55] != 2) + ++cellCnt[color2]; + celln = *str++; + + celln = _board[celln]; + if (celln > 0) { + --cellCnt[celln]; + ++cellCnt[color2]; } - return false; + celln = *str++; + + celln = _board[celln]; + if (celln > 0) { + --cellCnt[celln]; + ++cellCnt[color2]; + } + celln = *str++; + + celln = _board[celln]; + if (celln > 0) { + --cellCnt[celln]; + ++cellCnt[color2]; + } + while (1) { + celln = *str++; + if (celln < 0) + break; + celln = _board[celln]; + if (celln > 0) { + --cellCnt[celln]; + ++cellCnt[color2]; + } + } + return _coeff3 + 2 * (2 * cellCnt[color1] - cellCnt[1] - cellCnt[2] - cellCnt[3] - cellCnt[4]); } -uint8 CellGame::countBoard(byte *board, uint8 color) { - uint8 total = 0; - for (uint8 i = 0; BOARDSIZE > i; i++) { - for (uint8 j = 0; BOARDSIZE > j; j++) { - if (color == *(board + i + (BOARDSIZE * j))) { - total++; +void CellGame::chooseBestMove(int8 color) { + int moveIndex = 0; + int curWeight; + int bestWeight; + + if (_flag2) { + bestWeight = 32767; + for (int i = 0; i < _stack_index; ++i) { + _board[53] = _stack_startXY[i]; + _board[54] = _stack_endXY[i]; + _board[55] = _stack_pass[i]; + makeMove(color); + curWeight = countCellsOnTempBoard(color); + if (curWeight <= bestWeight) { + if (curWeight < bestWeight) + moveIndex = 0; + bestWeight = curWeight; + _stack_startXY[moveIndex] = _board[53]; + _stack_endXY[moveIndex] = _board[54]; + _stack_pass[moveIndex++] = _board[55]; } } + _stack_index = moveIndex; } - return total; + + _startX = _stack_startXY[0] % 7; + _startY = _stack_startXY[0] / 7; + _endX = _stack_endXY[0] % 7; + _endY = _stack_endXY[0] / 7; } -byte CellGame::getStartX() { - if (_startX > BOARDSIZE) { - warning ("CellGame::getStartX: not calculated yet!"); - return 0; +int8 CellGame::calcBestWeight(int8 color1, int8 color2, uint16 depth, int bestWeight) { + int8 res; + int8 curColor; + bool canMove; + int type; + uint16 i; + int8 currBoardWeight; + int8 weight; + + pushBoard(); + copyFromTempBoard(); + curColor = color2; + for (i = 0;; ++i) { + if (i >= 4) { + res = _coeff3 + 2 * (2 * _board[color1 + 48] - _board[49] - _board[50] - _board[51] - _board[52]); + popBoard(); + return res; + } + ++curColor; + if (curColor > 4) + curColor = 1; + + if (_board[curColor + 48]) { + if (_board[curColor + 48] >= 49 - _board[49] - _board[50] - _board[51] - _board[52]) { + resetMove(); + canMove = canMoveFunc2(curColor); + type = 1; + } else { + copyToShadowBoard(); + if (depth == 1) { + canMove = canMoveFunc3(curColor); + type = 3; + } else { + canMove = canMoveFunc1(curColor); + type = 2; + } + } + if (canMove) + break; + } + } + if (_flag1) { + popBoard(); + return bestWeight + 1; + } + + depth -= 1; + if (depth) { + makeMove(curColor); + if (type == 1) { + res = calcBestWeight(color1, curColor, depth, bestWeight); + } else { + pushShadowBoard(); + res = calcBestWeight(color1, curColor, depth, bestWeight); + popShadowBoard(); + } } else { - return _startX; + res = getBoardWeight(color1, curColor); + } + if (res < bestWeight && color1 != curColor || _flag4) { + popBoard(); + return res; + } + + currBoardWeight = _coeff3 + 2 * (2 * _board[color1 + 48] - _board[49] - _board[50] - _board[51] - _board[52]); + while (1) { + if (type == 1) { + canMove = canMoveFunc2(curColor); + } else if (type == 2) { + canMove = canMoveFunc1(curColor); + } else { + canMove = canMoveFunc3(curColor); + } + + if (!canMove) + break; + if (_flag1) { + popBoard(); + return bestWeight + 1; + } + if (_board[55] == 2) { + if (getBoardWeight(color1, curColor) == currBoardWeight) + continue; + } + if (!depth) { + weight = getBoardWeight(color1, curColor); + if (type == 1) { + if (_board[55] == 2) + _board[56] = 16; + } + } else { + makeMove(curColor); + if (type != 1) { + pushShadowBoard(); + weight = calcBestWeight(color1, curColor, depth, bestWeight); + popShadowBoard(); + } else { + weight = calcBestWeight(color1, curColor, depth, bestWeight); + } + } + if ((weight < res && color1 != curColor) || (weight > res && color1 == curColor)) + res = weight; + + if ((res < bestWeight && color1 != curColor) || _flag4) + break; } + popBoard(); + + return res; } -byte CellGame::getStartY() { - if (_startY > BOARDSIZE) { - warning ("CellGame::getStartY: not calculated yet!"); - return 6; +int16 CellGame::doGame(int8 color, int depth) { + bool canMove; + int type; + int8 currBoardWeight; + int8 w1; + int8 w2; + + countAllCells(); + if (_board[color + 48] >= 49 - _board[49] - _board[50] - _board[51] - _board[52]) { + resetMove(); + canMove = canMoveFunc2(color); + type = true; } else { - return _startY; + copyToShadowBoard(); + canMove = canMoveFunc1(color); + type = false; } -} -byte CellGame::getEndX() { - if (_endX > BOARDSIZE) { - warning ("CellGame::getEndX: not calculated yet!"); + if (canMove) { + if (_board[color + 48] - _board[49] - _board[50] - _board[51] - _board[52] == 0) + depth = 0; + _coeff3 = 0; + if (_board[55] == 1) + _coeff3 = 1; + clearMoves(); + if (depth) { + makeMove(color); + _flag4 = false; + if (type) { + w2 = calcBestWeight(color, color, depth, -127); + } else { + pushShadowBoard(); + w2 = calcBestWeight(color, color, depth, -127); + popShadowBoard(); + } + } else { + w2 = getBoardWeight(color, color); + } + currBoardWeight = 2 * (2 * _board[color + 48] - _board[49] - _board[50] - _board[51] - _board[52]); + while (1) { + if (type) + canMove = canMoveFunc2(color); + else + canMove = canMoveFunc1(color); + + if (!canMove) + break; + if (_flag1) + break; + _coeff3 = 0; + if (_board[55] == 2) { + if (getBoardWeight(color, color) == currBoardWeight) + continue; + } + if (_board[55] == 1) + _coeff3 = 1; + if (depth) { + makeMove(color); + _flag4 = false; + if (type) { + w1 = calcBestWeight(color, color, depth, w2); + } else { + pushShadowBoard(); + w1 = calcBestWeight(color, color, depth, w2); + popShadowBoard(); + } + } else { + w1 = getBoardWeight(color, color); + } + if (w1 == w2) + pushMove(); + + if (w1 > w2) { + clearMoves(); + w2 = w1; + } + } + chooseBestMove(color); return 1; - } else { - return _endX; } + + return 0; } -byte CellGame::getEndY() { - if (_endY > BOARDSIZE) { - warning ("CellGame::getEndY: not calculated yet!"); - return 6; +const int8 depths[] = { 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 3, 3 }; + +int16 CellGame::calcMove(int8 color, uint16 depth) { + int result; + + _flag1 = false; + ++_moveCount; + if (depth) { + if (depth == 1) { + _flag2 = true; + result = doGame(color, 0); + } else { + int newDepth; + + newDepth = depths[3 * (depth - 2) + _moveCount % 3]; + _flag2 = true; + if (newDepth >= 20) { + assert(0); // This branch is not implemented + } else { + result = doGame(color, newDepth); + } + } } else { - return _endY; + _flag2 = false; + result = doGame(color, depth); } + return result; } -CellGame::~CellGame() { +int CellGame::playStauf(byte color, uint16 depth, byte *scriptBoard) { + int i; + + for (i = 0; i < 49; i++, scriptBoard++) { + _board[i] = 0; + if (*scriptBoard == 50) + _board[i] = 1; + if (*scriptBoard == 66) + _board[i] = 2; + } + for (i = 49; i < 57; i++) + _board[i] = 0; + + return calcMove(color, depth); } + } // End of Groovie namespace diff --git a/engines/groovie/cell.h b/engines/groovie/cell.h index 70e135b62d..39ee529beb 100644 --- a/engines/groovie/cell.h +++ b/engines/groovie/cell.h @@ -29,6 +29,7 @@ #include "common/file.h" #include "common/util.h" +#include "groovie/cell.h" #include "groovie/groovie.h" #define BOARDSIZE 7 @@ -43,24 +44,59 @@ class Script; class CellGame { public: - CellGame(byte *board); + CellGame(); ~CellGame(); - int8 calcMove(byte *origboard, uint8 color, uint8 depth); byte getStartX(); byte getStartY(); byte getEndX(); byte getEndY(); + int playStauf(byte color, uint16 depth, byte *scriptBoard); private: - bool validMove(byte *board, uint8 color, int8 endX, int8 endY); - void execMove(byte *board, uint8 color, int8 startX, int8 startY, int8 endX, int8 endY); - uint8 countBoard(byte* board, uint8 color); - byte *_board; + void copyToTempBoard(); + void copyFromTempBoard(); + void copyToShadowBoard(); + void pushBoard(); + void popBoard(); + void pushShadowBoard(); + void popShadowBoard(); + void clearMoves(); + void pushMove(); + void resetMove(); + bool canMoveFunc1(int8 color); + bool canMoveFunc2(int8 color); + bool canMoveFunc3(int8 color); + void takeCells(uint16 whereTo, int8 color); + void countAllCells(); + int countCellsOnTempBoard(int8 color); + void makeMove(int8 color); + int getBoardWeight(int8 color1, int8 color2); + void chooseBestMove(int8 color); + int8 calcBestWeight(int8 color1, int8 color2, uint16 depth, int bestWeight); + int16 doGame(int8 color, int depth); + int16 calcMove(int8 color, uint16 depth); byte _startX; byte _startY; byte _endX; byte _endY; + + int8 _board[57]; + int8 _tempBoard[58]; + int8 _shadowBoard[64]; + int8 _boardStack[570]; + int _boardStackPtr; + + int8 _boardSum[58]; + + int8 _stack_startXY[128]; + int8 _stack_endXY[128]; + int8 _stack_pass[128]; + int _stack_index; + + int _coeff3; + bool _flag1, _flag2, _flag4; + int _moveCount; }; } // End of Groovie namespace diff --git a/engines/groovie/script.cpp b/engines/groovie/script.cpp index eb53842b91..6c4f38c270 100644 --- a/engines/groovie/script.cpp +++ b/engines/groovie/script.cpp @@ -61,7 +61,7 @@ static void debugScript(int level, bool nl, const char *s, ...) { Script::Script(GroovieEngine *vm, EngineVersion version) : _code(NULL), _savedCode(NULL), _stacktop(0), _debugger(NULL), _vm(vm), - _videoFile(NULL), _videoRef(0), _font(NULL) { + _videoFile(NULL), _videoRef(0), _font(NULL), _staufsMove(NULL) { // Initialize the opcode set depending on the engine version switch (version) { case kGroovieT7G: @@ -1376,33 +1376,21 @@ void Script::o_sub() { } void Script::o_cellmove() { - uint16 arg = readScript8bits(); + uint16 depth = readScript8bits(); byte *scriptBoard = &_variables[0x19]; - byte *board = (byte*) malloc (BOARDSIZE * BOARDSIZE * sizeof(byte)); byte startX, startY, endX, endY; - debugScript(1, true, "CELL MOVE var[0x%02X]", arg); - - // Arguments used by the original implementation: (2, arg, scriptBoard) - for (int y = 0; y < 7; y++) { - for (int x = 0; x < 7; x++) { - uint8 offset = x + BOARDSIZE * y; - *(board + offset) = 0; - if (*scriptBoard == 0x32) *(board + offset) = CELL_BLUE; - if (*scriptBoard == 0x42) *(board + offset) = CELL_GREEN; - scriptBoard++; - debugScript(1, false, "%d", *(board + offset)); - } - debugScript(1, false, "\n"); - } + debugScript(1, true, "CELL MOVE var[0x%02X]", depth); - CellGame staufsMove((byte*) board); - staufsMove.calcMove((byte*) board, CELL_GREEN, 2); - startX = staufsMove.getStartX(); - startY = staufsMove.getStartY(); - endX = staufsMove.getEndX(); - endY = staufsMove.getEndY(); + if (!_staufsMove) + _staufsMove = new CellGame; + _staufsMove->playStauf(2, depth, scriptBoard); + + startX = _staufsMove->getStartX(); + startY = _staufsMove->getStartY(); + endX = _staufsMove->getEndX(); + endY = _staufsMove->getEndY(); // Set the movement origin setVariable(0, startY); // y @@ -1410,8 +1398,6 @@ void Script::o_cellmove() { // Set the movement destination setVariable(2, endY); setVariable(3, endX); - - free (board); } void Script::o_returnscript() { diff --git a/engines/groovie/script.h b/engines/groovie/script.h index 664cac82d8..71c26835aa 100644 --- a/engines/groovie/script.h +++ b/engines/groovie/script.h @@ -40,6 +40,7 @@ enum EngineVersion { }; class GroovieEngine; +class CellGame; class Script { friend class Debugger; @@ -120,6 +121,8 @@ private: Common::String _debugString; uint16 _oldInstruction; + CellGame *_staufsMove; + // Helper functions uint8 getCodeByte(uint16 address); uint8 readScript8bits(); -- cgit v1.2.3