Original author: Pierre Sarrazin. Preserve upstream GPLv3-or-later and file-specific notices. Source: http://sarrazip.com/dev/coco-letters-0.1.0.tar.gz Archive SHA-256: ad7c7771845e1a35014644fb562634a558abee632e1d7738683db6e9e9e46b94
598 lines
18 KiB
C
598 lines
18 KiB
C
/* GameState.c
|
|
Copyright (C) 2026 Pierre Sarrazin <http://sarrazip.com/>
|
|
|
|
This program is free software: you can redistribute it and/or modify
|
|
it under the terms of the GNU General Public License as published by
|
|
the Free Software Foundation, either version 3 of the License, or
|
|
(at your option) any later version.
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
#include "GameState.h"
|
|
|
|
#include "dict.h"
|
|
|
|
|
|
// Represents a tile.
|
|
//
|
|
typedef struct LetterSpec
|
|
{
|
|
byte numTiles; // number of tiles of this letter
|
|
byte numPoints; // points scored when playing this letter
|
|
} LetterSpec;
|
|
|
|
|
|
// Tile numbers:
|
|
// 0 = blank;
|
|
// 1..26 = A..Z.
|
|
//
|
|
static const LetterSpec letterSpecs[NUM_TILE_TYPES] =
|
|
{
|
|
{ NUM_BLANK_TILES, 0 },
|
|
{ 9, 1 }, // A
|
|
{ 2, 3 }, // B
|
|
{ 2, 3 }, // C
|
|
{ 4, 2 }, // D
|
|
{ 12, 1 }, // E
|
|
{ 2, 4 }, // F
|
|
{ 3, 2 }, // G
|
|
{ 2, 4 }, // H
|
|
{ 9, 1 }, // I
|
|
{ 1, 8 }, // J
|
|
{ 1, 5 }, // K
|
|
{ 4, 1 }, // L
|
|
{ 2, 3 }, // M
|
|
{ 6, 1 }, // N
|
|
{ 8, 1 }, // O
|
|
{ 2, 3 }, // P
|
|
{ 1, 10 }, // Q
|
|
{ 6, 1 }, // R
|
|
{ 4, 1 }, // S
|
|
{ 6, 1 }, // T
|
|
{ 4, 1 }, // U
|
|
{ 2, 4 }, // V
|
|
{ 2, 4 }, // W
|
|
{ 1, 8 }, // X
|
|
{ 2, 4 }, // Y
|
|
{ 1, 10 }, // Z
|
|
};
|
|
|
|
|
|
#define _ SQ_EMPTY,
|
|
#define S SQ_START,
|
|
#define T SQ_TRIPLE_WORD,
|
|
#define D SQ_DOUBLE_WORD,
|
|
#define t SQ_TRIPLE_LETTER,
|
|
#define d SQ_DOUBLE_LETTER,
|
|
#define EOL }, {
|
|
#define EOB }
|
|
|
|
const byte GameState_boardSquareTypes[BOARD_SIZE][BOARD_SIZE] =
|
|
{
|
|
{
|
|
#include "board.h"
|
|
}
|
|
};
|
|
|
|
#undef _
|
|
#undef S
|
|
#undef T
|
|
#undef D
|
|
#undef t
|
|
#undef d
|
|
#undef EOL
|
|
#undef EOB
|
|
|
|
|
|
void
|
|
GameState_init(GameState *gs)
|
|
{
|
|
for (byte i = 0; i < NUM_TILE_TYPES; ++i)
|
|
gs->numTiles[i] = letterSpecs[i].numTiles;
|
|
memset(gs->boardTiles, (char) TILE_TYPE_NONE, BOARD_SIZE * (size_t) BOARD_SIZE);
|
|
gs->isBoardEmpty = TRUE;
|
|
gs->numPlayedBlankTiles = 0;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_getNumTilesOfType(const GameState *gs, byte tileType)
|
|
{
|
|
if (tileType > 26) // if TILE_TYPE_NONE or invalid
|
|
return 0;
|
|
return letterSpecs[tileType].numTiles;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_getTileValue(const GameState *gs, byte tileType)
|
|
{
|
|
if (tileType > 26) // if TILE_TYPE_NONE or invalid
|
|
return 0;
|
|
return letterSpecs[tileType].numPoints;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_getBlankTileLetter(const GameState *gs, byte row, byte col)
|
|
{
|
|
for (byte i = gs->numPlayedBlankTiles; i--; )
|
|
{
|
|
const PlayedBlankTile *p = &gs->playedBlankTiles[i];
|
|
if (p->row == row && p->col == col)
|
|
return p->letterTileType;
|
|
}
|
|
return TILE_TYPE_NONE;
|
|
}
|
|
|
|
|
|
void
|
|
GameState_setTile(GameState *gs, byte row, byte col,
|
|
byte tileType, byte letterTileTypeIfBlank)
|
|
{
|
|
// If tileType is TILE_TYPE_BLANK, then letterTileTypeIfBlank must be A..Z.
|
|
// Otherwise, letterTileTypeIfBlank is not used and should be TILE_TYPE_NONE.
|
|
//
|
|
assert(tileType != TILE_TYPE_BLANK || letterTileTypeIfBlank >= 1 && letterTileTypeIfBlank <= 26);
|
|
assert(tileType == TILE_TYPE_BLANK || letterTileTypeIfBlank == TILE_TYPE_NONE);
|
|
|
|
gs->boardTiles[row][col] = tileType;
|
|
gs->isBoardEmpty = FALSE;
|
|
if (tileType == TILE_TYPE_BLANK && gs->numPlayedBlankTiles < NUM_BLANK_TILES)
|
|
{
|
|
PlayedBlankTile *p = &gs->playedBlankTiles[gs->numPlayedBlankTiles];
|
|
p->row = row;
|
|
p->col = col;
|
|
p->letterTileType = letterTileTypeIfBlank;
|
|
++gs->numPlayedBlankTiles;
|
|
}
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_countTilesInBag(const GameState *gs)
|
|
{
|
|
//printf("GameState_countTilesInBag:");
|
|
byte total = 0;
|
|
for (byte i = 0; i < NUM_TILE_TYPES; ++i)
|
|
{
|
|
//printf(" %u=%u", i, gs->numTiles[i]);
|
|
total += gs->numTiles[i];
|
|
}
|
|
//printf("; total=%u\n", total);
|
|
return total;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_pickRandomLetter(GameState *gs)
|
|
{
|
|
byte numTiles = GameState_countTilesInBag(gs);
|
|
if (numTiles == 0)
|
|
return TILE_TYPE_NONE;
|
|
byte chosenTileIndex = (byte) (rand() % numTiles); // index among all tiles in bag
|
|
//printf("GameState_pickRandomLetter: chosenTileIndex=%u\n", chosenTileIndex);
|
|
for (byte i = 0; i < NUM_TILE_TYPES; ++i)
|
|
{
|
|
byte *numTilesOfTypeI = &gs->numTiles[i];
|
|
if (chosenTileIndex < *numTilesOfTypeI)
|
|
{
|
|
--*numTilesOfTypeI;
|
|
//printf("GameState_pickRandomLetter: return %u\n", i);
|
|
return i;
|
|
}
|
|
chosenTileIndex -= *numTilesOfTypeI;
|
|
}
|
|
return TILE_TYPE_NONE;
|
|
}
|
|
|
|
|
|
void
|
|
GameState_fillRackEmptySlots(GameState *gs, byte rack[RACK_SIZE])
|
|
{
|
|
for (byte i = 0; i < RACK_SIZE; ++i)
|
|
if (rack[i] == TILE_TYPE_NONE)
|
|
rack[i] = GameState_pickRandomLetter(gs);
|
|
}
|
|
|
|
|
|
// Returns TRUE if the required free space exists.
|
|
//
|
|
static BOOL
|
|
GameState_checkFreeSpaceLeft(const GameState *gs,
|
|
byte row, byte col,
|
|
byte numFreeSquaresNeededForNewWord)
|
|
{
|
|
if (col < numFreeSquaresNeededForNewWord) // not enough columns at left of (row, col)
|
|
return FALSE;
|
|
for ( ; numFreeSquaresNeededForNewWord > 0; --numFreeSquaresNeededForNewWord)
|
|
{
|
|
--col;
|
|
if (gs->boardTiles[row][col] != TILE_TYPE_NONE)
|
|
return FALSE;
|
|
}
|
|
if (col == 0)
|
|
return TRUE;
|
|
// One more free space is needed to keep the new word from touching an existing word.
|
|
return gs->boardTiles[row][col - 1] == TILE_TYPE_NONE;
|
|
}
|
|
|
|
|
|
// Returns TRUE if the required free space exists.
|
|
//
|
|
static BOOL
|
|
GameState_checkFreeSpaceRight(const GameState *gs,
|
|
byte row, byte col,
|
|
byte numFreeSquaresNeededForNewWord)
|
|
{
|
|
if (col + numFreeSquaresNeededForNewWord >= BOARD_SIZE) // not enough rows at right of (row, col)
|
|
return FALSE;
|
|
for ( ; numFreeSquaresNeededForNewWord > 0; --numFreeSquaresNeededForNewWord)
|
|
{
|
|
++col;
|
|
if (gs->boardTiles[row][col] != TILE_TYPE_NONE)
|
|
return FALSE;
|
|
}
|
|
if (col == BOARD_SIZE - 1)
|
|
return TRUE;
|
|
// One more free space is needed to keep the new word from touching an existing word.
|
|
return gs->boardTiles[row][col + 1] == TILE_TYPE_NONE;
|
|
}
|
|
|
|
|
|
// Returns TRUE if the required free space exists.
|
|
//
|
|
static BOOL
|
|
GameState_checkFreeSpaceUp(const GameState *gs,
|
|
byte row, byte col,
|
|
byte numFreeSquaresNeededForNewWord)
|
|
{
|
|
if (row < numFreeSquaresNeededForNewWord) // not enough rows above (row, col)
|
|
return FALSE;
|
|
for ( ; numFreeSquaresNeededForNewWord > 0; --numFreeSquaresNeededForNewWord)
|
|
{
|
|
--row;
|
|
if (gs->boardTiles[row][col] != TILE_TYPE_NONE)
|
|
return FALSE;
|
|
}
|
|
if (row == 0)
|
|
return TRUE;
|
|
// One more free space is needed to keep the new word from touching an existing word.
|
|
return gs->boardTiles[row - 1][col] == TILE_TYPE_NONE;
|
|
}
|
|
|
|
|
|
// Returns TRUE if the required free space exists.
|
|
//
|
|
static BOOL
|
|
GameState_checkFreeSpaceDown(const GameState *gs,
|
|
byte row, byte col,
|
|
byte numFreeSquaresNeededForNewWord)
|
|
{
|
|
if (row + numFreeSquaresNeededForNewWord >= BOARD_SIZE) // not enough rows below (row, col)
|
|
return FALSE;
|
|
for ( ; numFreeSquaresNeededForNewWord > 0; --numFreeSquaresNeededForNewWord)
|
|
{
|
|
++row;
|
|
if (gs->boardTiles[row][col] != TILE_TYPE_NONE)
|
|
return FALSE;
|
|
}
|
|
if (row == BOARD_SIZE - 1)
|
|
return TRUE;
|
|
// One more free space is needed to keep the new word from touching an existing word.
|
|
return gs->boardTiles[row + 1][col] == TILE_TYPE_NONE;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_detectHorizontalPrefix(const GameState *gs, byte row, byte col)
|
|
{
|
|
if (row >= BOARD_SIZE || col >= BOARD_SIZE)
|
|
return 0; // out of bounds
|
|
byte before;
|
|
for (before = 1; before <= col; ++before)
|
|
if (gs->boardTiles[row][col - before] == TILE_TYPE_NONE)
|
|
break;
|
|
return before - 1;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_detectHorizontalSuffix(const GameState *gs, byte row, byte col)
|
|
{
|
|
if (row >= BOARD_SIZE || col >= BOARD_SIZE)
|
|
return 0; // out of bounds
|
|
byte after;
|
|
for (after = 1; col + after < BOARD_SIZE; ++after)
|
|
if (gs->boardTiles[row][col + after] == TILE_TYPE_NONE)
|
|
break;
|
|
return after - 1;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_detectHorizontalWordLimits(const GameState *gs,
|
|
byte row, byte col,
|
|
byte *startCol)
|
|
{
|
|
byte before = GameState_detectHorizontalPrefix(gs, row, col);
|
|
byte after = GameState_detectHorizontalSuffix(gs, row, col);
|
|
byte length = after + before + 1;
|
|
if (length == 1)
|
|
return 0; // no word found
|
|
*startCol = col - before;
|
|
return length;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_detectVerticalPrefix(const GameState *gs, byte row, byte col)
|
|
{
|
|
if (row >= BOARD_SIZE || col >= BOARD_SIZE)
|
|
return 0; // out of bounds
|
|
byte before;
|
|
for (before = 1; before <= row; ++before)
|
|
if (gs->boardTiles[row - before][col] == TILE_TYPE_NONE)
|
|
break;
|
|
return before - 1;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_detectVerticalSuffix(const GameState *gs, byte row, byte col)
|
|
{
|
|
if (row >= BOARD_SIZE || col >= BOARD_SIZE)
|
|
return 0; // out of bounds
|
|
byte after;
|
|
for (after = 1; row + after < BOARD_SIZE; ++after)
|
|
if (gs->boardTiles[row + after][col] == TILE_TYPE_NONE)
|
|
break;
|
|
return after - 1;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_detectVerticalWordLimits(const GameState *gs,
|
|
byte row, byte col,
|
|
byte *startRow)
|
|
{
|
|
byte before = GameState_detectVerticalPrefix(gs, row, col);
|
|
byte after = GameState_detectVerticalSuffix(gs, row, col);
|
|
byte length = after + before + 1;
|
|
if (length == 1)
|
|
return 0; // no word found
|
|
*startRow = row - before;
|
|
return length;
|
|
}
|
|
|
|
|
|
char
|
|
GameState_getTileTypeChar(byte tileType)
|
|
{
|
|
switch (tileType)
|
|
{
|
|
case TILE_TYPE_BLANK: return 127; // DEL character rendered as filled rectangle in 4x8 font
|
|
case TILE_TYPE_NONE: return ' ';
|
|
default: return '@' + (char) tileType; // 'A'..'Z'
|
|
}
|
|
}
|
|
|
|
|
|
// Fills destWord[] with the word found at position (row, col) and
|
|
// going in the direction given by 'horizontally'.
|
|
// row, col: Position of the first letter of the word.
|
|
// letterInEmptySquare: Tile value that is used if a board position has no tile.
|
|
//
|
|
static void
|
|
GameState_readWordFromBoard(const GameState *gs,
|
|
char destWord[MAX_WORD_LEN + 1],
|
|
BOOL horizontally,
|
|
byte row,
|
|
byte col,
|
|
byte length,
|
|
char letterInEmptySquare)
|
|
{
|
|
for (byte i = 0; i < length; ++i)
|
|
{
|
|
byte tileType = gs->boardTiles[row][col];
|
|
if (tileType == TILE_TYPE_BLANK)
|
|
tileType = GameState_getBlankTileLetter(gs, row, col);
|
|
destWord[i] = (tileType == TILE_TYPE_NONE
|
|
? letterInEmptySquare
|
|
: GameState_getTileTypeChar(tileType));
|
|
if (horizontally)
|
|
++col;
|
|
else
|
|
++row;
|
|
}
|
|
destWord[length] = '\0';
|
|
}
|
|
|
|
|
|
// horizontally: Orientation in which the candidate word is positioned.
|
|
// hangLetterOffset: Offset in candidateWord[] of the letter that uses a tile
|
|
// already on the board. (Example, if candidateWord is "FOOBAR"
|
|
// and hangLetterOffset is 3, then we are trying to place "FOO"
|
|
// and "AR" around a "B" tile already on the board.
|
|
//
|
|
BOOL
|
|
GameState_checkAdjacentWords(const GameState *gs,
|
|
BOOL horizontally,
|
|
byte row,
|
|
byte col,
|
|
byte hangLetterOffset,
|
|
const char *candidateWord,
|
|
byte candidateWordLength)
|
|
{
|
|
// (dRow, dCol) is the couple to add to (row, col) to go forward in reading direction.
|
|
sbyte dRow = !horizontally;
|
|
sbyte dCol = horizontally;
|
|
|
|
for (byte i = 0; i < candidateWordLength; ++i, row += dRow, col += dCol)
|
|
if (i != hangLetterOffset)
|
|
{
|
|
// Does candidateWord[i] at (row, col) form a word with the letters adjacent to it?
|
|
byte detectedRow, detectedCol, detectedLength;
|
|
if (!horizontally)
|
|
{
|
|
detectedLength = GameState_detectHorizontalWordLimits(gs, row, col, &detectedCol);
|
|
detectedRow = row;
|
|
}
|
|
else
|
|
{
|
|
detectedLength = GameState_detectVerticalWordLimits(gs, row, col, &detectedRow);
|
|
detectedCol = col;
|
|
}
|
|
if (detectedLength > 0)
|
|
{
|
|
char detectedWord[MAX_WORD_LEN + 1];
|
|
GameState_readWordFromBoard(gs, detectedWord, !horizontally,
|
|
detectedRow, detectedCol, detectedLength,
|
|
candidateWord[i]);
|
|
BOOL isInDict = isWordInDictionary(detectedWord);
|
|
if (!isInDict)
|
|
return FALSE; // reject because adjacent word not in dictionary
|
|
}
|
|
}
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
|
|
BOOL
|
|
GameState_tryHangWord(const GameState *gs,
|
|
const char *candidateWord, byte candidateWordLength,
|
|
char boardLetterToHangTo,
|
|
byte freeSquaresNeededBeforeForNewWord,
|
|
byte freeSquaresNeededAfterForNewWord,
|
|
BOOL *outHorizontally, byte *outRow, byte *outCol)
|
|
{
|
|
//printf("TRYHANGWORD: %c %u %u\n",
|
|
// boardLetterToHangTo, freeSquaresNeededBeforeForNewWord, freeSquaresNeededAfterForNewWord);
|
|
byte tileTypeToHangTo = boardLetterToHangTo - '@'; // 1..26
|
|
for (byte row = 0; row < BOARD_SIZE; ++row)
|
|
{
|
|
for (byte col = 0; col < BOARD_SIZE; ++col)
|
|
{
|
|
if (gs->boardTiles[row][col] == tileTypeToHangTo)
|
|
{
|
|
// N.B.: This version always tries the vertical first and always accepts it if it works.
|
|
// This is not an optimal strategy.
|
|
if (GameState_checkFreeSpaceUp(gs, row, col, freeSquaresNeededBeforeForNewWord)
|
|
&& GameState_checkFreeSpaceDown(gs, row, col, freeSquaresNeededAfterForNewWord)
|
|
&& GameState_checkAdjacentWords(gs, FALSE,
|
|
row - freeSquaresNeededBeforeForNewWord, col,
|
|
freeSquaresNeededBeforeForNewWord,
|
|
candidateWord, candidateWordLength))
|
|
{
|
|
//printf("HANG TO %c VERT. AT (%u, %u)\n", boardLetterToHangTo, row, col);
|
|
*outHorizontally = FALSE;
|
|
*outRow = row - freeSquaresNeededBeforeForNewWord;
|
|
*outCol = col;
|
|
return TRUE;
|
|
}
|
|
if (GameState_checkFreeSpaceLeft(gs, row, col, freeSquaresNeededBeforeForNewWord)
|
|
&& GameState_checkFreeSpaceRight(gs, row, col, freeSquaresNeededAfterForNewWord)
|
|
&& GameState_checkAdjacentWords(gs, TRUE,
|
|
row, col - freeSquaresNeededBeforeForNewWord,
|
|
freeSquaresNeededBeforeForNewWord,
|
|
candidateWord, candidateWordLength))
|
|
{
|
|
//printf("HANG TO %c HORIZ. AT (%u, %u)\n", boardLetterToHangTo, row, col);
|
|
*outHorizontally = TRUE;
|
|
*outRow = row;
|
|
*outCol = col - freeSquaresNeededBeforeForNewWord;
|
|
return TRUE;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
//printf("FAIL TO HANG TO %c\n", boardLetterToHangTo);
|
|
return FALSE;
|
|
}
|
|
|
|
|
|
byte
|
|
GameState_getTileWithBoundsChecking(const GameState *self, byte row, byte col)
|
|
{
|
|
if (row >= BOARD_SIZE) // if 255 (-1) or below last row
|
|
return TILE_TYPE_NONE;
|
|
if (col >= BOARD_SIZE) // if 255 (-1) or at right of last column
|
|
return TILE_TYPE_NONE;
|
|
return GameState_getTile(self, row, col);
|
|
}
|
|
|
|
|
|
BOOL
|
|
GameState_detectCrossingWord(const GameState *gs,
|
|
byte initRow,
|
|
byte initCol,
|
|
byte rowInc,
|
|
byte colInc,
|
|
byte *foundWordRow,
|
|
byte *foundWordCol,
|
|
byte *indexOfTileToPlace,
|
|
byte *foundWordLen)
|
|
{
|
|
// First go backward to find the start of the word, if any.
|
|
// Backward means left if the caller is processing a vertical word,
|
|
// or up if it's a horizontal word.
|
|
//
|
|
*foundWordRow = initRow;
|
|
*foundWordCol = initCol;
|
|
*foundWordLen = 0;
|
|
for (;;)
|
|
{
|
|
*foundWordRow -= rowInc;
|
|
*foundWordCol -= colInc;
|
|
|
|
if (*foundWordRow >= BOARD_SIZE || *foundWordCol >= BOARD_SIZE)
|
|
break; // now to the left of the board, or above it, so stop
|
|
|
|
if (GameState_getTile(gs, *foundWordRow, *foundWordCol) == TILE_TYPE_NONE)
|
|
break; // reached an empty tile, so stop
|
|
|
|
++*foundWordLen;
|
|
}
|
|
|
|
*indexOfTileToPlace = *foundWordLen;
|
|
|
|
// Get back to the last non-empty tile seen.
|
|
//
|
|
*foundWordRow += rowInc;
|
|
*foundWordCol += colInc;
|
|
|
|
// Go forward (i.e., right or down) to find the end of the word, if any.
|
|
//
|
|
byte wordEndRow = initRow, wordEndCol = initCol;
|
|
for (;;)
|
|
{
|
|
wordEndRow += rowInc;
|
|
wordEndCol += colInc;
|
|
|
|
if (wordEndRow >= BOARD_SIZE || wordEndCol >= BOARD_SIZE)
|
|
break; // now to the left of the board, or above it, so stop
|
|
|
|
if (GameState_getTile(gs, wordEndRow, wordEndCol) == TILE_TYPE_NONE)
|
|
break; // reached an empty tile, so stop
|
|
|
|
++*foundWordLen;
|
|
}
|
|
|
|
// (wordEndRow, wordEndCol) is now one PAST the last letter.
|
|
|
|
++*foundWordLen; // count the tile to place
|
|
|
|
//printf("\t""detectCrossingWord: (%u, %u) -> (%u, %u), %u.\n",
|
|
// *foundWordRow, *foundWordCol, wordEndRow, wordEndCol, *foundWordLen);
|
|
|
|
return *foundWordLen > 1;
|
|
}
|