[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Eliot-dev] Changes to eliot/game/board_search.cpp [antoine-1]
From: |
eliot-dev |
Subject: |
[Eliot-dev] Changes to eliot/game/board_search.cpp [antoine-1] |
Date: |
Sun, 23 Oct 2005 13:16:28 -0400 |
Index: eliot/game/board_search.cpp
diff -u /dev/null eliot/game/board_search.cpp:1.4.2.1
--- /dev/null Sun Oct 23 17:16:28 2005
+++ eliot/game/board_search.cpp Sun Oct 23 17:16:23 2005
@@ -0,0 +1,290 @@
+/*****************************************************************************
+ * Copyright (C) 1999-2005 Eliot
+ * Authors: Antoine Fraboulet <address@hidden>
+ * Olivier Teuliere <address@hidden>
+ *
+ * $Id: board_search.cpp,v 1.4.2.1 2005/10/23 17:16:23 afrab Exp $
+ *
+ * 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 2 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, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *****************************************************************************/
+
+#include <dic.h>
+#include "tile.h"
+#include "rack.h"
+#include "round.h"
+#include "results.h"
+#include "board.h"
+
+#include "debug.h"
+
+/*
+ * computes the score of a word, coordinates may be changed to reflect
+ * the real direction of the word
+ */
+static void BoardSearchEvalMove(const Board &iBoard,
+ Matrix<Tile> &iTilesMx,
+ Matrix<int> &iPointsMx,
+ Matrix<bool> &iJokerMx,
+ Results &iResults, Round &iWord)
+{
+ int i, pts, ptscross;
+ int l, t, fromrack;
+ int len, row, col, wordmul;
+
+ fromrack = 0;
+ pts = 0;
+ ptscross = 0;
+ wordmul = 1;
+
+ len = iWord.getWordLen();
+ row = iWord.getRow();
+ col = iWord.getCol();
+
+ for (i = 0; i < len; i++)
+ {
+ if (!iTilesMx[row][col+i].isEmpty())
+ {
+ if (!iJokerMx[row][col+i])
+ pts += iWord.getTile(i).getPoints();
+ }
+ else
+ {
+ if (!iWord.isJoker(i))
+ l = iWord.getTile(i).getPoints() *
+ iBoard.getLetterMultiplier(row, col + i);
+ else
+ l = 0;
+ pts += l;
+ wordmul *= iBoard.getWordMultiplier(row, col + i);
+
+ t = iPointsMx[row][col+i];
+ if (t >= 0)
+ ptscross += (t + l) * iBoard.getWordMultiplier(row, col + i);
+ fromrack++;
+ }
+ }
+ pts = ptscross + pts * wordmul + 50 * (fromrack == 7);
+ iWord.setBonus(fromrack == 7);
+ iWord.setPoints(pts);
+
+ if (iWord.getDir() == VERTICAL)
+ {
+ iWord.setRow(col);
+ iWord.setCol(row);
+ }
+ iResults.add(iWord);
+ if (iWord.getDir() == VERTICAL)
+ {
+ iWord.setRow(row);
+ iWord.setCol(col);
+ }
+}
+
+
+static void ExtendRight(const Board &iBoard,
+ const Dictionary iDic,
+ Matrix<Tile> &iTilesMx,
+ Matrix<Cross> &iCrossMx,
+ Matrix<int> &iPointsMx,
+ Matrix<bool> &iJokerMx,
+ Rack &iRack, Round &partialword,
+ Results &iResults, unsigned int iNode,
+ int iRow, int iCol, int anchor)
+{
+ Tile l;
+ unsigned int succ;
+
+ if (iTilesMx[iRow][iCol].isEmpty())
+ {
+ if (Dic_word(iDic, iNode) && iCol > anchor)
+ BoardSearchEvalMove(iBoard, iTilesMx, iPointsMx, iJokerMx,
+ iResults, partialword);
+
+ for (succ = Dic_succ(iDic, iNode); succ; succ = Dic_next(iDic, succ))
+ {
+ l = Tile('A' - 1 + Dic_chr(iDic, succ));
+ if (iCrossMx[iRow][iCol].check(l))
+ {
+ if (iRack.in(l))
+ {
+ iRack.remove(l);
+ partialword.addRightFromRack(l, 0);
+ ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
+ iJokerMx, iRack, partialword, iResults,
+ succ, iRow, iCol + 1, anchor);
+ partialword.removeRightToRack(l, 0);
+ iRack.add(l);
+ }
+ if (iRack.in(Tile::Joker()))
+ {
+ iRack.remove(Tile::Joker());
+ partialword.addRightFromRack(l, 1);
+ ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
+ iJokerMx, iRack, partialword, iResults,
+ succ, iRow, iCol + 1, anchor);
+ partialword.removeRightToRack(l, 1);
+ iRack.add(Tile::Joker());
+ }
+ }
+ }
+ }
+ else
+ {
+ l = iTilesMx[iRow][iCol];
+ for (succ = Dic_succ(iDic, iNode); succ ; succ = Dic_next(iDic, succ))
+ {
+ if (Tile('A' - 1 + Dic_chr(iDic, succ)) == l)
+ {
+ partialword.addRightFromBoard(l);
+ ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
+ iJokerMx, iRack, partialword,
+ iResults, succ, iRow, iCol + 1, anchor);
+ partialword.removeRightToBoard(l);
+ }
+ }
+ }
+}
+
+
+static void LeftPart(const Board &iBoard,
+ const Dictionary &iDic,
+ Matrix<Tile> &iTilesMx,
+ Matrix<Cross> &iCrossMx,
+ Matrix<int> &iPointsMx,
+ Matrix<bool> &iJokerMx,
+ Rack &iRack, Round &iPartialWord,
+ Results &iResults, int n, int iRow, int anchor, int limit)
+{
+ Tile l;
+ int succ;
+
+ ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx, iJokerMx, iRack,
+ iPartialWord, iResults, n, iRow, anchor, anchor);
+
+ if (limit > 0)
+ {
+ for (succ = Dic_succ(iDic, n); succ; succ = Dic_next(iDic, succ))
+ {
+ l = Tile('A' - 1 + Dic_chr(iDic, succ));
+ if (iRack.in(l))
+ {
+ iRack.remove(l);
+ iPartialWord.addRightFromRack(l, 0);
+ iPartialWord.setCol(iPartialWord.getCol() - 1);
+ LeftPart(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
+ iJokerMx, iRack, iPartialWord, iResults,
+ succ, iRow, anchor, limit - 1);
+ iPartialWord.setCol(iPartialWord.getCol() + 1);
+ iPartialWord.removeRightToRack(l, 0);
+ iRack.add(l);
+ }
+ if (iRack.in(Tile::Joker()))
+ {
+ iRack.remove(Tile::Joker());
+ iPartialWord.addRightFromRack(l, 1);
+ iPartialWord.setCol(iPartialWord.getCol() - 1);
+ LeftPart(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
+ iJokerMx, iRack, iPartialWord, iResults,
+ succ, iRow, anchor, limit - 1);
+ iPartialWord.setCol(iPartialWord.getCol() + 1);
+ iPartialWord.removeRightToRack(l, 1);
+ iRack.add(Tile::Joker());
+ }
+ }
+ }
+}
+
+
+static void BoardSearchAux(const Board &iBoard,
+ const Dictionary &iDic,
+ Matrix<Tile> &iTilesMx,
+ Matrix<Cross> &iCrossMx,
+ Matrix<int> &iPointsMx,
+ Matrix<bool> &iJokerMx,
+ Rack &iRack, Results &iResults, Direction iDir)
+{
+ int row, col, lastanchor;
+ Round partialword;
+ for (row = 1; row <= BOARD_DIM; row++)
+ {
+ partialword.init();
+ partialword.setDir(iDir);
+ partialword.setRow(row);
+ lastanchor = 0;
+ for (col = 1; col <= BOARD_DIM; col++)
+ {
+ if (iTilesMx[row][col].isEmpty() &&
+ (!iTilesMx[row][col - 1].isEmpty() ||
+ !iTilesMx[row][col + 1].isEmpty() ||
+ !iTilesMx[row - 1][col].isEmpty() ||
+ !iTilesMx[row + 1][col].isEmpty()))
+ {
+ if (!iTilesMx[row][col - 1].isEmpty())
+ {
+ partialword.setCol(lastanchor + 1);
+ ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
+ iJokerMx, iRack, partialword, iResults,
+ Dic_root(iDic), row, lastanchor + 1, col);
+ }
+ else
+ {
+ partialword.setCol(col);
+ LeftPart(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
+ iJokerMx, iRack, partialword, iResults,
+ Dic_root(iDic), row, col, col -
+ lastanchor - 1);
+ }
+ lastanchor = col;
+ }
+ }
+ }
+}
+
+
+void Board::search(const Dictionary iDic,
+ const Rack &iRack,
+ Results &oResults)
+{
+ // Create a copy of the rack to avoid modifying the given one
+ Rack copyRack = iRack;
+
+ BoardSearchAux(*this, iDic, m_tilesRow, m_crossRow,
+ m_pointRow, m_jokerRow,
+ copyRack, oResults, HORIZONTAL);
+
+ BoardSearchAux(*this, iDic, m_tilesCol, m_crossCol,
+ m_pointCol, m_jokerCol,
+ copyRack, oResults, VERTICAL);
+}
+
+
+void Board::searchFirst(const Dictionary iDic,
+ const Rack &iRack,
+ Results &oResults)
+{
+ Round partialword;
+ int row = 8, col = 8;
+
+ // Create a copy of the rack to avoid modifying the given one
+ Rack copyRack = iRack;
+
+ partialword.setRow(row);
+ partialword.setCol(col);
+ partialword.setDir(HORIZONTAL);
+ LeftPart(*this, iDic, m_tilesRow, m_crossRow,
+ m_pointRow, m_jokerRow,
+ copyRack, partialword, oResults, Dic_root(iDic), row, col,
+ copyRack.nTiles() - 1);
+}
- [Eliot-dev] Changes to eliot/game/board_search.cpp [antoine-1],
eliot-dev <=