diff --git a/dealer.cpp b/dealer.cpp index 830c2ed..fcbd746 100644 --- a/dealer.cpp +++ b/dealer.cpp @@ -1,2111 +1,2111 @@ /* * Copyright (C) 1995 Paul Olav Tvete * Copyright (C) 2000-2009 Stephan Kulow * Copyright (C) 2009-2010 Parker Coates * * License of original code: * ------------------------------------------------------------------------- * Permission to use, copy, modify, and distribute this software and its * documentation for any purpose and without fee is hereby granted, * provided that the above copyright notice appear in all copies and that * both that copyright notice and this permission notice appear in * supporting documentation. * * This file is provided AS IS with no warranties of any kind. The author * shall have no liability with respect to the infringement of copyrights, * trade secrets or any patents by this file or any part thereof. In no * event will the author be liable for any lost revenue or profits or * other special, indirect and consequential damages. * ------------------------------------------------------------------------- * * License of modifications/additions made after 2009-01-01: * ------------------------------------------------------------------------- * 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, see . * ------------------------------------------------------------------------- */ #include "dealer.h" #include "dealerinfo.h" #include "kpat_debug.h" #include "messagebox.h" #include "renderer.h" #include "shuffle.h" #include "speeds.h" #include "patsolve/solverinterface.h" #include "view.h" #include "KCardTheme" #include #include #include #include #include #include #include #include #include #include namespace { const qreal wonBoxToSceneSizeRatio = 0.7; QString solverStatusMessage( int status, bool everWinnable ) { switch ( status ) { case SolverInterface::SolutionExists: return i18n("Solver: This game is winnable."); case SolverInterface::NoSolutionExists: return everWinnable ? i18n("Solver: This game is no longer winnable.") : i18n("Solver: This game cannot be won."); case SolverInterface::UnableToDetermineSolvability: return i18n("Solver: Unable to determine if this game is winnable."); case SolverInterface::SearchAborted: case SolverInterface::MemoryLimitReached: default: return QString(); } } int readIntAttribute( const QXmlStreamReader & xml, const QString & key, bool * ok = nullptr ) { QStringRef value = xml.attributes().value( key ); return QString::fromRawData( value.data(), value.length() ).toInt( ok ); } QString suitToString( int suit ) { switch ( suit ) { case KCardDeck::Clubs: return QStringLiteral("clubs"); case KCardDeck::Diamonds: return QStringLiteral("diamonds"); case KCardDeck::Hearts: return QStringLiteral("hearts"); case KCardDeck::Spades: return QStringLiteral("spades"); default: return QString(); } } QString rankToString( int rank ) { switch ( rank ) { case KCardDeck::Ace: return QStringLiteral("ace"); case KCardDeck::Two: return QStringLiteral("two"); case KCardDeck::Three: return QStringLiteral("three"); case KCardDeck::Four: return QStringLiteral("four"); case KCardDeck::Five: return QStringLiteral("five"); case KCardDeck::Six: return QStringLiteral("six"); case KCardDeck::Seven: return QStringLiteral("seven"); case KCardDeck::Eight: return QStringLiteral("eight"); case KCardDeck::Nine: return QStringLiteral("nine"); case KCardDeck::Ten: return QStringLiteral("ten"); case KCardDeck::Jack: return QStringLiteral("jack"); case KCardDeck::Queen: return QStringLiteral("queen"); case KCardDeck::King: return QStringLiteral("king"); default: return QString(); } } } class SolverThread : public QThread { Q_OBJECT public: SolverThread( SolverInterface * solver ) : m_solver( solver ) { } void run() override { SolverInterface::ExitStatus result = m_solver->patsolve(); emit finished( result ); } void abort() { m_solver->stopExecution(); wait(); } signals: void finished( int result ); private: SolverInterface * m_solver; }; int DealerScene::moveCount() const { return m_loadedMoveCount + m_undoStack.size(); } void DealerScene::saveLegacyFile( QIODevice * io ) { QXmlStreamWriter xml( io ); xml.setCodec( "UTF-8" ); xml.setAutoFormatting( true ); xml.setAutoFormattingIndent( -1 ); xml.writeStartDocument(); xml.writeDTD( QStringLiteral("") ); xml.writeStartElement( QStringLiteral("dealer") ); xml.writeAttribute( QStringLiteral("id"), QString::number( gameId() ) ); xml.writeAttribute( QStringLiteral("options"), getGameOptions() ); xml.writeAttribute( QStringLiteral("number"), QString::number( gameNumber() ) ); xml.writeAttribute( QStringLiteral("moves"), QString::number( moveCount() ) ); xml.writeAttribute( QStringLiteral("started"), QString::number( m_dealStarted ) ); xml.writeAttribute( QStringLiteral("data"), getGameState() ); foreach( const PatPile * p, patPiles() ) { xml.writeStartElement( QStringLiteral("pile") ); xml.writeAttribute( QStringLiteral("index"), QString::number( p->index() ) ); xml.writeAttribute( QStringLiteral("z"), QString::number( p->zValue() ) ); foreach( const KCard * c, p->cards() ) { xml.writeStartElement( QStringLiteral("card") ); xml.writeAttribute( QStringLiteral("suit"), QString::number( c->suit() ) ); xml.writeAttribute( QStringLiteral("value"), QString::number( c->rank() ) ); xml.writeAttribute( QStringLiteral("faceup"), QString::number( c->isFaceUp() ) ); xml.writeAttribute( QStringLiteral("z"), QString::number( c->zValue() ) ); xml.writeEndElement(); } xml.writeEndElement(); } xml.writeEndElement(); xml.writeEndDocument(); m_dealWasJustSaved = true; } bool DealerScene::loadLegacyFile( QIODevice * io ) { resetInternals(); QXmlStreamReader xml( io ); xml.readNextStartElement(); // Before KDE4.3, KPat didn't store game specific options in the save // file. This could cause crashes when loading a Spider game with a // different number of suits than the current setting. Similarly, in // Klondike the number of cards drawn from the deck was forgotten, but // this never caused crashes. Fortunately, in Spider we can count the // number of suits ourselves. For Klondike, there is no way to recover // that information. QString options = xml.attributes().value( QStringLiteral("options") ).toString(); if ( gameId() == 17 && options.isEmpty() ) { QSet suits; while ( !xml.atEnd() ) if ( xml.readNextStartElement() && xml.name() == "card" ) suits << readIntAttribute( xml, QStringLiteral("suit") ); options = QString::number( suits.size() ); // "Rewind" back to the tag. Yes, this is ugly. xml.clear(); io->reset(); xml.setDevice( io ); xml.readNextStartElement(); } setGameOptions( options ); m_dealNumber = readIntAttribute( xml, QStringLiteral("number") ); m_loadedMoveCount = readIntAttribute( xml, QStringLiteral("moves") ); m_dealStarted = readIntAttribute( xml, QStringLiteral("started") ); QString gameStateData = xml.attributes().value( QStringLiteral("data") ).toString(); QMultiHash cards; foreach ( KCard * c, deck()->cards() ) cards.insert( (c->id() & 0xffff), c ); QHash piles; foreach ( PatPile * p, patPiles() ) piles.insert( p->index(), p ); // Loop through s. while ( xml.readNextStartElement() ) { if ( xml.name() != "pile" ) { qCWarning(KPAT_LOG) << "Expected a \"pile\" tag. Found a" << xml.name() << "tag."; return false; } bool ok; int index = readIntAttribute( xml, QStringLiteral("index"), &ok ); QHash::const_iterator it = piles.constFind( index ); if ( !ok || it == piles.constEnd() ) { qCWarning(KPAT_LOG) << "Unrecognized pile index:" << xml.attributes().value( QStringLiteral("index") ); return false; } PatPile * p = it.value(); p->clear(); // Loop through s. while ( xml.readNextStartElement() ) { if ( xml.name() != "card" ) { qCWarning(KPAT_LOG) << "Expected a \"card\" tag. Found a" << xml.name() << "tag."; return false; } bool suitOk, rankOk, faceUpOk; int suit = readIntAttribute( xml, QStringLiteral("suit"), &suitOk ); int rank = readIntAttribute( xml, QStringLiteral("value"), &rankOk ); bool faceUp = readIntAttribute( xml, QStringLiteral("faceup"), &faceUpOk ); quint32 id = KCardDeck::getId( KCardDeck::Suit( suit ), KCardDeck::Rank( rank ), 0 ); KCard * card = cards.take( id ); if ( !suitOk || !rankOk || !faceUpOk || !card ) { qCWarning(KPAT_LOG) << "Unrecognized card: suit=" << xml.attributes().value(QStringLiteral("suit")) << " value=" << xml.attributes().value(QStringLiteral("value")) << " faceup=" << xml.attributes().value(QStringLiteral("faceup")); return false; } card->setFaceUp( faceUp ); p->add( card ); xml.skipCurrentElement(); } updatePileLayout( p, 0 ); } setGameState( gameStateData ); emit updateMoves( moveCount() ); takeState(); return true; } void DealerScene::saveFile( QIODevice * io ) { QXmlStreamWriter xml( io ); xml.setCodec( "UTF-8" ); xml.setAutoFormatting( true ); xml.setAutoFormattingIndent( -1 ); xml.writeStartDocument(); xml.writeStartElement( QStringLiteral("kpat-game") ); xml.writeAttribute( QStringLiteral("game-type"), m_di->baseIdString() ); if ( !getGameOptions().isEmpty() ) xml.writeAttribute( QStringLiteral("game-type-options"), getGameOptions() ); xml.writeAttribute( QStringLiteral("deal-number"), QString::number( gameNumber() ) ); if (!m_currentState) { deck()->stopAnimations(); takeState(); } QList allStates; for ( int i = 0; i < m_undoStack.size(); ++i ) allStates << m_undoStack.at( i ); allStates << m_currentState; for ( int i = m_redoStack.size() - 1; i >= 0; --i ) allStates << m_redoStack.at( i ); QString lastGameSpecificState; for ( int i = 0; i < allStates.size(); ++i ) { const GameState * state = allStates.at( i ); xml.writeStartElement( QStringLiteral("state") ); if ( state->stateData != lastGameSpecificState ) { xml.writeAttribute( QStringLiteral("game-specific-state"), state->stateData ); lastGameSpecificState = state->stateData; } if ( i == m_undoStack.size() ) xml.writeAttribute( QStringLiteral("current"), QStringLiteral("true") ); foreach ( const CardStateChange & change, state->changes ) { xml.writeStartElement( QStringLiteral("move") ); xml.writeAttribute( QStringLiteral("pile"), change.newState.pile->objectName() ); xml.writeAttribute( QStringLiteral("position"), QString::number( change.newState.index ) ); bool faceChanged = !change.oldState.pile || change.oldState.faceUp != change.newState.faceUp; foreach ( const KCard * card, change.cards ) { xml.writeStartElement( QStringLiteral("card") ); xml.writeAttribute( QStringLiteral("id"), QStringLiteral("%1").arg( card->id(), 7, 10, QChar('0') ) ); xml.writeAttribute( QStringLiteral("suit"), suitToString( card->suit() ) ); xml.writeAttribute( QStringLiteral("rank"), rankToString( card->rank() ) ); if ( faceChanged ) xml.writeAttribute( QStringLiteral("turn"), change.newState.faceUp ? "face-up" : "face-down" ); xml.writeEndElement(); } xml.writeEndElement(); } xml.writeEndElement(); } xml.writeEndElement(); xml.writeEndDocument(); m_dealWasJustSaved = true; } bool DealerScene::loadFile( QIODevice * io ) { resetInternals(); bool reenableAutoDrop = autoDropEnabled(); setAutoDropEnabled( false ); QXmlStreamReader xml( io ); xml.readNextStartElement(); if ( xml.name() != "kpat-game" ) { qCWarning(KPAT_LOG) << "First tag is not \"kpat-game\""; return false; } m_dealNumber = readIntAttribute( xml, QStringLiteral("deal-number") ); setGameOptions( xml.attributes().value( QStringLiteral("game-type-options") ).toString() ); QMultiHash cardHash; foreach ( KCard * c, deck()->cards() ) cardHash.insert( c->id(), c ); QHash pileHash; foreach ( KCardPile * p, piles() ) pileHash.insert( p->objectName(), p ); int undosToDo = -1; while( xml.readNextStartElement() ) { if ( xml.name() != "state" ) { qCWarning(KPAT_LOG) << "Expected a \"state\" tag. Found a" << xml.name() << "tag."; return false; } if ( xml.attributes().hasAttribute( QStringLiteral("game-specific-state") ) ) setGameState( xml.attributes().value( QStringLiteral("game-specific-state") ).toString() ); if ( undosToDo > -1 ) ++undosToDo; else if ( xml.attributes().value( QStringLiteral("current") ) == "true" ) undosToDo = 0; while( xml.readNextStartElement() ) { if ( xml.name() != "move" ) { qCWarning(KPAT_LOG) << "Expected a \"move\" tag. Found a" << xml.name() << "tag."; return false; } QString pileName = xml.attributes().value( QStringLiteral("pile") ).toString(); KCardPile * pile = pileHash.value( pileName ); bool indexOk; int index = readIntAttribute( xml, QStringLiteral("position"), &indexOk ); if ( !pile || !indexOk ) { qCWarning(KPAT_LOG) << "Unrecognized pile or index."; return false; } while ( xml.readNextStartElement() ) { if ( xml.name() != "card" ) { qCWarning(KPAT_LOG) << "Expected a \"card\" tag. Found a" << xml.name() << "tag."; return false; } KCard * card = cardHash.value( readIntAttribute( xml, QStringLiteral("id") ) ); if ( !card ) { qCWarning(KPAT_LOG) << "Unrecognized card."; return false; } if ( xml.attributes().value(QStringLiteral("turn")) == "face-up" ) card->setFaceUp( true ); else if ( xml.attributes().value(QStringLiteral("turn")) == "face-down" ) card->setFaceUp( false ); pile->insert( index, card ); ++index; xml.skipCurrentElement(); } } takeState(); } m_loadedMoveCount = 0; m_dealStarted = moveCount() > 0; emit updateMoves( moveCount() ); while ( undosToDo > 0 ) { undo(); --undosToDo; } foreach ( KCardPile * p, piles() ) updatePileLayout( p, 0 ); setAutoDropEnabled( reenableAutoDrop ); return true; } DealerScene::DealerScene( const DealerInfo * di ) : m_di( di ), m_solver( nullptr ), m_solverThread( nullptr ), m_peekedCard( nullptr ), m_dealNumber( 0 ), m_loadedMoveCount( 0 ), m_neededFutureMoves( 1 ), m_supportedActions( 0 ), m_autoDropEnabled( false ), m_solverEnabled( false ), m_dealStarted( false ), m_dealWasEverWinnable( false ), m_dealHasBeenWon( false ), m_dealWasJustSaved( false ), m_statisticsRecorded( false ), m_playerReceivedHelp( false ), m_toldAboutWonGame( false ), m_toldAboutLostGame( false ), m_dropSpeedFactor( 1 ), m_interruptAutoDrop( false ), m_dealInProgress( false ), m_hintInProgress( false ), m_demoInProgress( false ), m_dropInProgress( false ), m_hintQueued( false ), m_demoQueued( false ), m_dropQueued( false ), m_newCardsQueued( false ), m_takeStateQueued( false ), m_currentState( nullptr ) { setItemIndexMethod(QGraphicsScene::NoIndex); m_solverUpdateTimer.setInterval( 250 ); m_solverUpdateTimer.setSingleShot( true ); connect(&m_solverUpdateTimer, &QTimer::timeout, this, &DealerScene::stopAndRestartSolver); m_demoTimer.setSingleShot( true ); connect(&m_demoTimer, &QTimer::timeout, this, &DealerScene::demo); m_dropTimer.setSingleShot( true ); connect(&m_dropTimer, &QTimer::timeout, this, &DealerScene::drop); m_wonItem = new MessageBox(); m_wonItem->setZValue( 2000 ); m_wonItem->hide(); addItem( m_wonItem ); connect(this, &DealerScene::cardAnimationDone, this, &DealerScene::animationDone); connect(this, &DealerScene::cardDoubleClicked, this, &DealerScene::tryAutomaticMove); // Make rightClick == doubleClick. See bug #151921 connect(this, &DealerScene::cardRightClicked, this, &DealerScene::tryAutomaticMove); } DealerScene::~DealerScene() { stop(); disconnect(); if ( m_solverThread ) m_solverThread->abort(); delete m_solverThread; m_solverThread = nullptr; delete m_solver; m_solver = nullptr; qDeleteAll( m_undoStack ); delete m_currentState; qDeleteAll( m_redoStack ); delete m_wonItem; } void DealerScene::addPatPile( PatPile * pile ) { if ( !m_patPiles.contains( pile ) ) m_patPiles.append( pile ); } void DealerScene::removePatPile( PatPile * pile ) { m_patPiles.removeAll( pile ); } QList DealerScene::patPiles() const { return m_patPiles; } void DealerScene::cardsMoved( const QList & cards, KCardPile * oldPile, KCardPile * newPile ) { PatPile * newPatPile = dynamic_cast( newPile ); PatPile * oldPatPile = dynamic_cast( oldPile ); if ( oldPatPile && oldPatPile->isFoundation() && newPatPile && !newPatPile->isFoundation() ) { foreach ( KCard * c, cards ) m_cardsRemovedFromFoundations.insert( c ); } else { foreach ( KCard * c, cards ) m_cardsRemovedFromFoundations.remove( c ); } if ( !m_dropInProgress && !m_dealInProgress ) { m_dealStarted = true; takeState(); } } void DealerScene::startHint() { stopDemo(); stopDrop(); if ( isCardAnimationRunning() ) { m_hintQueued = true; return; } if ( isKeyboardModeActive() ) setKeyboardModeActive( false ); QList toHighlight; foreach ( const MoveHint & h, getHints() ) toHighlight << h.card(); if ( !m_winningMoves.isEmpty() ) { MOVE m = m_winningMoves.first(); MoveHint mh = solver()->translateMove( m ); if ( mh.isValid() ) toHighlight << mh.card(); } m_hintInProgress = !toHighlight.isEmpty(); setHighlightedItems( toHighlight ); emit hintActive( m_hintInProgress ); } void DealerScene::stopHint() { if ( m_hintInProgress ) { m_hintInProgress = false; clearHighlightedItems(); emit hintActive( false ); } } bool DealerScene::isHintActive() const { return m_hintInProgress; } QList DealerScene::getSolverHints() { QList hintList; if ( m_solverThread && m_solverThread->isRunning() ) m_solverThread->abort(); solver()->translate_layout(); solver()->patsolve( 1 ); foreach ( const MOVE & m, solver()->firstMoves() ) { MoveHint mh = solver()->translateMove( m ); hintList << mh; } return hintList; } QList DealerScene::getHints() { if ( solver() ) return getSolverHints(); QList hintList; foreach (PatPile * store, patPiles()) { if (store->isFoundation() || store->isEmpty()) continue; QList cards = store->cards(); while (cards.count() && !cards.first()->isFaceUp()) cards.erase(cards.begin()); QList::Iterator iti = cards.begin(); while (iti != cards.end()) { if (allowedToRemove(store, (*iti))) { foreach (PatPile * dest, patPiles()) { int cardIndex = store->indexOf(*iti); if (cardIndex == 0 && dest->isEmpty() && !dest->isFoundation()) continue; if (!checkAdd(dest, dest->cards(), cards)) continue; if (dest->isFoundation()) { hintList << MoveHint( *iti, dest, 127 ); } else { QList cardsBelow = cards.mid(0, cardIndex); // if it could be here as well, then it's no use if ((cardsBelow.isEmpty() && !dest->isEmpty()) || !checkAdd(store, cardsBelow, cards)) { hintList << MoveHint( *iti, dest, 0 ); } else if (checkPrefering(dest, dest->cards(), cards) && !checkPrefering(store, cardsBelow, cards)) { // if checkPrefers says so, we add it nonetheless hintList << MoveHint( *iti, dest, 10 ); } } } } cards.erase(iti); iti = cards.begin(); } } return hintList; } static bool prioSort(const MoveHint &c1, const MoveHint &c2) { return c1.priority() < c2.priority(); } MoveHint DealerScene::chooseHint() { if ( !m_winningMoves.isEmpty() ) { MOVE m = m_winningMoves.takeFirst(); MoveHint mh = solver()->translateMove( m ); -#ifndef NDEBUG +#ifndef CHOOSE_HINT_DEBUG if ( m.totype == O_Type ) fprintf( stderr, "move from %d out (at %d) Prio: %d\n", m.from, m.turn_index, m.pri ); else fprintf( stderr, "move from %d to %d (%d) Prio: %d\n", m.from, m.to, m.turn_index, m.pri ); #endif return mh; } QList hintList = getHints(); if ( hintList.isEmpty() ) { return MoveHint(); } else { // Generate a random number with an exponentional distribution averaging 1/4. qreal randomExp = qMin( -log( 1 - QRandomGenerator::global()->generateDouble() ) / 4, 1 ); int randomIndex = randomExp * ( hintList.size() - 1 ); std::sort(hintList.begin(), hintList.end(), prioSort); return hintList.at( randomIndex ); } } void DealerScene::startNew( int dealNumber ) { if ( dealNumber != -1 ) m_dealNumber = qBound( 1, dealNumber, INT_MAX ); // Only record the statistics and reset gameStarted if we're starting a // new game number or we're restarting a game we've already won. if ( dealNumber != -1 || m_dealHasBeenWon ) { recordGameStatistics(); m_statisticsRecorded = false; m_dealStarted = false; } if ( isCardAnimationRunning() ) { QTimer::singleShot( 100, this, SLOT(startNew()) ); return; } if ( m_solverThread && m_solverThread->isRunning() ) m_solverThread->abort(); resetInternals(); emit updateMoves( 0 ); foreach( KCardPile * p, piles() ) p->clear(); m_dealInProgress = true; restart( KpatShuffle::shuffled( deck()->cards(), m_dealNumber ) ); m_dealInProgress = false; takeState(); update(); } void DealerScene::resetInternals() { stop(); setKeyboardModeActive( false ); m_dealHasBeenWon = false; m_wonItem->hide(); qDeleteAll( m_undoStack ); m_undoStack.clear(); delete m_currentState; m_currentState = nullptr; qDeleteAll( m_redoStack ); m_redoStack.clear(); m_lastKnownCardStates.clear(); m_dealWasJustSaved = false; m_dealWasEverWinnable = false; m_toldAboutLostGame = false; m_toldAboutWonGame = false; m_loadedMoveCount = 0; m_playerReceivedHelp = false; m_dealInProgress = false; m_dropInProgress = false; m_dropSpeedFactor = 1; m_cardsRemovedFromFoundations.clear(); foreach (KCard * c, deck()->cards()) { c->disconnect( this ); c->stopAnimation(); } emit solverStateChanged( QString() ); emit gameInProgress( true ); } QPointF posAlongRect( qreal distOnRect, const QRectF & rect ) { if ( distOnRect < rect.width() ) return rect.topLeft() + QPointF( distOnRect, 0 ); distOnRect -= rect.width(); if ( distOnRect < rect.height() ) return rect.topRight() + QPointF( 0, distOnRect ); distOnRect -= rect.height(); if ( distOnRect < rect.width() ) return rect.bottomRight() + QPointF( -distOnRect, 0 ); distOnRect -= rect.width(); return rect.bottomLeft() + QPointF( 0, -distOnRect ); } void DealerScene::won() { if ( m_dealHasBeenWon ) return; m_dealHasBeenWon = true; m_toldAboutWonGame = true; stopDemo(); recordGameStatistics(); emit solverStateChanged( QString() ); emit newCardsPossible( false ); emit undoPossible( false ); emit redoPossible( false ); emit gameInProgress( false ); setKeyboardModeActive( false ); qreal speed = sqrt( width() * width() + height() * height() ) / ( DURATION_WON ); QRectF justOffScreen = sceneRect().adjusted( -deck()->cardWidth(), -deck()->cardHeight(), 0, 0 ); qreal spacing = 2 * ( justOffScreen.width() + justOffScreen.height() ) / deck()->cards().size(); qreal distOnRect = 0; foreach ( KCard *c, deck()->cards() ) { distOnRect += spacing; QPointF pos2 = posAlongRect( distOnRect, justOffScreen ); QPointF delta = c->pos() - pos2; qreal dist = sqrt( delta.x() * delta.x() + delta.y() * delta.y() ); c->setFaceUp( true ); c->animate( pos2, c->zValue(), 0, true, false, dist / speed ); } connect(deck(), &KAbstractCardDeck::cardAnimationDone, this, &DealerScene::showWonMessage); } void DealerScene::showWonMessage() { disconnect(deck(), &KAbstractCardDeck::cardAnimationDone, this, &DealerScene::showWonMessage); // It shouldn't be necessary to stop the demo yet again here, but we // get crashes if we don't. Will have to look into this further. stopDemo(); // Hide all cards to prevent them from showing up accidentally if the // window is resized. foreach ( KCard * c, deck()->cards() ) c->hide(); updateWonItem(); m_wonItem->show(); } void DealerScene::updateWonItem() { const qreal aspectRatio = Renderer::self()->aspectRatioOfElement(QStringLiteral("message_frame")); int boxWidth; int boxHeight; if ( width() < aspectRatio * height() ) { boxWidth = width() * wonBoxToSceneSizeRatio; boxHeight = boxWidth / aspectRatio; } else { boxHeight = height() * wonBoxToSceneSizeRatio; boxWidth = boxHeight * aspectRatio; } m_wonItem->setSize( QSize( boxWidth, boxHeight ) ); if ( m_playerReceivedHelp ) m_wonItem->setMessage( i18n( "Congratulations! We have won." ) ); else m_wonItem->setMessage( i18n( "Congratulations! You have won." ) ); m_wonItem->setPos( QPointF( (width() - boxWidth) / 2, (height() - boxHeight) / 2 ) + sceneRect().topLeft() ); } bool DealerScene::allowedToAdd( const KCardPile * pile, const QList & cards ) const { if ( !pile->isEmpty() && !pile->topCard()->isFaceUp() ) return false; const PatPile * p = dynamic_cast( pile ); return p && checkAdd( p, p->cards(), cards ); } bool DealerScene::allowedToRemove( const KCardPile * pile, const KCard * card ) const { const PatPile * p = dynamic_cast( pile ); QList cards = pile->topCardsDownTo( card ); return p && card->isFaceUp() && !cards.isEmpty() && checkRemove( p, cards ); } bool DealerScene::checkAdd( const PatPile * pile, const QList & oldCards, const QList & newCards ) const { Q_UNUSED( pile ) Q_UNUSED( oldCards ) Q_UNUSED( newCards ) return false; } bool DealerScene::checkRemove(const PatPile * pile, const QList & cards) const { Q_UNUSED( pile ) Q_UNUSED( cards ) return false; } bool DealerScene::checkPrefering( const PatPile * pile, const QList & oldCards, const QList & newCards ) const { Q_UNUSED( pile ) Q_UNUSED( oldCards ) Q_UNUSED( newCards ) return false; } void DealerScene::mousePressEvent( QGraphicsSceneMouseEvent * e ) { stop(); const QList itemsAtPoint = items( e->scenePos() ); KCard * card = qgraphicsitem_cast( itemsAtPoint.isEmpty() ? 0 : itemsAtPoint.first() ); if ( m_peekedCard ) { e->accept(); } else if ( e->button() == Qt::RightButton && card && card->pile() && card != card->pile()->topCard() && cardsBeingDragged().isEmpty() && !isCardAnimationRunning() ) { e->accept(); m_peekedCard = card; QPointF pos2( card->x() + deck()->cardWidth() / 3.0, card->y() - deck()->cardHeight() / 3.0 ); card->setZValue( card->zValue() + 0.1 ); card->animate( pos2, card->zValue(), 20, card->isFaceUp(), false, DURATION_FANCYSHOW ); } else { KCardScene::mousePressEvent( e ); if ( !cardsBeingDragged().isEmpty() ) emit cardsPickedUp(); } } void DealerScene::mouseReleaseEvent( QGraphicsSceneMouseEvent * e ) { stop(); if ( e->button() == Qt::RightButton && m_peekedCard && m_peekedCard->pile() ) { e->accept(); updatePileLayout( m_peekedCard->pile(), DURATION_FANCYSHOW ); m_peekedCard = nullptr; } else { bool hadCards = !cardsBeingDragged().isEmpty(); KCardScene::mouseReleaseEvent( e ); if ( hadCards && cardsBeingDragged().isEmpty() ) emit cardsPutDown(); } } void DealerScene::mouseDoubleClickEvent( QGraphicsSceneMouseEvent * e ) { stop(); KCardScene::mouseDoubleClickEvent( e ); } bool DealerScene::tryAutomaticMove( KCard * card ) { if ( !isCardAnimationRunning() && card && card->pile() && card == card->pile()->topCard() && card->isFaceUp() && allowedToRemove( card->pile(), card ) ) { QList cardList = QList() << card; foreach ( PatPile * p, patPiles() ) { if ( p->isFoundation() && allowedToAdd( p, cardList ) ) { moveCardToPile( card , p, DURATION_MOVE ); return true; } } } return false; } void DealerScene::undo() { undoOrRedo( true ); } void DealerScene::redo() { undoOrRedo( false ); } void DealerScene::undoOrRedo( bool undo ) { stop(); if ( isCardAnimationRunning() ) return; // The undo and redo actions are almost identical, except for where states // are pulled from and pushed to, so to keep things generic, we use // direction dependent const references throughout this code. QStack & fromStack = undo ? m_undoStack : m_redoStack; QStack & toStack = undo ? m_redoStack : m_undoStack; if ( !fromStack.isEmpty() && m_currentState ) { // If we're undoing, we use the oldStates of the changes of the current // state. If we're redoing, we use the newStates of the changes of the // nextState. const QList & changes = undo ? m_currentState->changes : fromStack.top()->changes; // Update the currentState pointer and undo/redo stacks. toStack.push( m_currentState ); m_currentState = fromStack.pop(); setGameState( m_currentState->stateData ); QSet pilesAffected; foreach ( const CardStateChange & change, changes ) { CardState sourceState = undo ? change.newState : change.oldState; CardState destState = undo ? change.oldState : change.newState; PatPile * sourcePile = dynamic_cast( sourceState.pile ); PatPile * destPile = dynamic_cast( destState.pile ); bool notDroppable = destState.takenDown || ((sourcePile && sourcePile->isFoundation()) && !(destPile && destPile->isFoundation())); pilesAffected << sourceState.pile << destState.pile; foreach ( KCard * c, change.cards ) { m_lastKnownCardStates.insert( c, destState ); c->setFaceUp( destState.faceUp ); destState.pile->insert( destState.index, c ); if ( notDroppable ) m_cardsRemovedFromFoundations.insert( c ); else m_cardsRemovedFromFoundations.remove( c ); ++sourceState.index; ++destState.index; } } // At this point all cards should be in the right piles, but not // necessarily at the right positions within those piles. So we // run through the piles involved and swap card positions until // everything is back in its place, then relayout the piles. foreach( KCardPile * p, pilesAffected ) { int i = 0; while ( i < p->count() ) { int index = m_lastKnownCardStates.value( p->at( i ) ).index; if ( i == index ) ++i; else p->swapCards( i, index ); } updatePileLayout( p, 0 ); } emit updateMoves( moveCount() ); emit undoPossible( !m_undoStack.isEmpty() ); emit redoPossible( !m_redoStack.isEmpty() ); if ( m_toldAboutLostGame ) // everything's possible again { gameInProgress( true ); m_toldAboutLostGame = false; m_toldAboutWonGame = false; } int solvability = m_currentState->solvability; m_winningMoves = m_currentState->winningMoves; emit solverStateChanged( solverStatusMessage( solvability, m_dealWasEverWinnable ) ); if ( m_solver && ( solvability == SolverInterface::SearchAborted || solvability == SolverInterface::MemoryLimitReached ) ) { startSolver(); } } } void DealerScene::takeState() { if ( isCardAnimationRunning() ) { m_takeStateQueued = true; return; } if ( !isDemoActive() ) m_winningMoves.clear(); QList changes; foreach ( KCardPile * p, piles() ) { QList currentRun; CardState oldRunState; CardState newRunState; for ( int i = 0; i < p->count(); ++i ) { KCard * c = p->at( i ); const CardState & oldState = m_lastKnownCardStates.value( c ); CardState newState( p, i, c->isFaceUp(), m_cardsRemovedFromFoundations.contains( c ) ); // The card has changed. if ( newState != oldState ) { // There's a run in progress, but this card isn't part of it. if ( !currentRun.isEmpty() && (oldState.pile != oldRunState.pile || (oldState.index != -1 && oldState.index != oldRunState.index + currentRun.size()) || oldState.faceUp != oldRunState.faceUp || newState.faceUp != newRunState.faceUp || oldState.takenDown != oldRunState.takenDown || newState.takenDown != newRunState.takenDown) ) { changes << CardStateChange( oldRunState, newRunState, currentRun ); currentRun.clear(); } // This card is the start of a new run. if ( currentRun.isEmpty() ) { oldRunState = oldState; newRunState = newState; } currentRun << c; m_lastKnownCardStates.insert( c, newState ); } } // Add the last run, if any. if ( !currentRun.isEmpty() ) { changes << CardStateChange( oldRunState, newRunState, currentRun ); } } // If nothing has changed, we're done. if ( changes.isEmpty() && m_currentState && m_currentState->stateData == getGameState() ) { return; } if ( m_currentState ) { m_undoStack.push( m_currentState ); qDeleteAll( m_redoStack ); m_redoStack.clear(); } m_currentState = new GameState( changes, getGameState() ); emit redoPossible( false ); emit undoPossible( !m_undoStack.isEmpty() ); emit updateMoves( moveCount() ); m_dealWasJustSaved = false; if ( isGameWon() ) { won(); return; } if ( !m_toldAboutWonGame && !m_toldAboutLostGame && isGameLost() ) { emit gameInProgress( false ); emit solverStateChanged( i18n( "Solver: This game is lost." ) ); m_toldAboutLostGame = true; stopDemo(); return; } if ( !isDemoActive() && !isCardAnimationRunning() && m_solver ) startSolver(); if ( autoDropEnabled() && !isDropActive() && !isDemoActive() && m_redoStack.isEmpty() ) { if ( m_interruptAutoDrop ) m_interruptAutoDrop = false; else m_dropQueued = true; } } void DealerScene::setSolverEnabled(bool a) { m_solverEnabled = a; } void DealerScene::setAutoDropEnabled( bool enabled ) { m_autoDropEnabled = enabled; } bool DealerScene::autoDropEnabled() const { return m_autoDropEnabled; } void DealerScene::startDrop() { stopHint(); stopDemo(); if ( isCardAnimationRunning() ) { m_dropQueued = true; return; } m_dropInProgress = true; m_interruptAutoDrop = false; m_dropSpeedFactor = 1; emit dropActive( true ); drop(); } void DealerScene::stopDrop() { if ( m_dropInProgress ) { m_dropTimer.stop(); m_dropInProgress = false; emit dropActive( false ); if ( autoDropEnabled() && m_takeStateQueued ) m_interruptAutoDrop = true; } } bool DealerScene::isDropActive() const { return m_dropInProgress; } bool DealerScene::drop() { foreach ( const MoveHint & mh, getHints() ) { if ( mh.pile() && mh.pile()->isFoundation() && mh.priority() > 120 && !m_cardsRemovedFromFoundations.contains( mh.card() ) ) { QList cards = mh.card()->pile()->topCardsDownTo( mh.card() ); QMap oldPositions; foreach ( KCard * c, cards ) oldPositions.insert( c, c->pos() ); moveCardsToPile( cards, mh.pile(), DURATION_MOVE ); int count = 0; foreach ( KCard * c, cards ) { c->completeAnimation(); QPointF destPos = c->pos(); c->setPos( oldPositions.value( c ) ); int duration = speedUpTime( DURATION_AUTODROP + count * DURATION_AUTODROP / 10 ); c->animate( destPos, c->zValue(), 0, c->isFaceUp(), true, duration ); ++count; } m_dropSpeedFactor *= AUTODROP_SPEEDUP_FACTOR; takeState(); return true; } } m_dropInProgress = false; emit dropActive( false ); return false; } int DealerScene::speedUpTime( int delay ) const { if ( delay < DURATION_AUTODROP_MINIMUM ) return delay; else return qMax( delay * m_dropSpeedFactor, DURATION_AUTODROP_MINIMUM ); } void DealerScene::stopAndRestartSolver() { if ( m_toldAboutLostGame || m_toldAboutWonGame ) // who cares? return; if ( m_solverThread && m_solverThread->isRunning() ) { m_solverThread->abort(); } if ( isCardAnimationRunning() ) { startSolver(); return; } slotSolverEnded(); } void DealerScene::slotSolverEnded() { if ( m_solverThread && m_solverThread->isRunning() ) return; m_solver->translate_layout(); m_winningMoves.clear(); emit solverStateChanged( i18n("Solver: Calculating...") ); if ( !m_solverThread ) { m_solverThread = new SolverThread( m_solver ); connect(m_solverThread, &SolverThread::finished, this, &DealerScene::slotSolverFinished); } m_solverThread->start( m_solverEnabled ? QThread::IdlePriority : QThread::NormalPriority ); } void DealerScene::slotSolverFinished( int result ) { if ( result == SolverInterface::SolutionExists ) { m_winningMoves = m_solver->winMoves(); m_dealWasEverWinnable = true; } emit solverStateChanged( solverStatusMessage( result, m_dealWasEverWinnable ) ); if ( m_currentState ) { m_currentState->solvability = static_cast( result ); m_currentState->winningMoves = m_winningMoves; } if ( result == SolverInterface::SearchAborted ) startSolver(); } int DealerScene::gameNumber() const { return m_dealNumber; } void DealerScene::stop() { stopHint(); stopDemo(); stopDrop(); } void DealerScene::animationDone() { Q_ASSERT( !isCardAnimationRunning() ); if ( !m_multiStepMoves.isEmpty() ) { continueMultiStepMove(); return; } if ( m_takeStateQueued ) { m_takeStateQueued = false; takeState(); } if ( m_demoInProgress ) { m_demoTimer.start( TIME_BETWEEN_MOVES ); } else if ( m_dropInProgress ) { m_dropTimer.start( speedUpTime( TIME_BETWEEN_MOVES ) ); } else if ( m_newCardsQueued ) { m_newCardsQueued = false; newCards(); } else if ( m_hintQueued ) { m_hintQueued = false; startHint(); } else if ( m_demoQueued ) { m_demoQueued = false; startDemo(); } else if ( m_dropQueued ) { m_dropQueued = false; startDrop(); } } void DealerScene::startDemo() { stopHint(); stopDrop(); if ( isCardAnimationRunning() ) { m_demoQueued = true; return; } m_demoInProgress = true; m_playerReceivedHelp = true; m_dealStarted = true; demo(); } void DealerScene::stopDemo() { if ( m_demoInProgress ) { m_demoTimer.stop(); m_demoInProgress = false; emit demoActive( false ); } } bool DealerScene::isDemoActive() const { return m_demoInProgress; } void DealerScene::demo() { if ( isCardAnimationRunning() ) { m_demoQueued = true; return; } m_demoInProgress = true; m_playerReceivedHelp = true; m_dealStarted = true; clearHighlightedItems(); m_demoTimer.stop(); MoveHint mh = chooseHint(); if ( mh.isValid() ) { KCard * card = mh.card(); Q_ASSERT( card ); KCardPile * sourcePile = mh.card()->pile(); Q_ASSERT( sourcePile ); Q_ASSERT( allowedToRemove( sourcePile, card ) ); PatPile * destPile = mh.pile(); Q_ASSERT( destPile ); Q_ASSERT( sourcePile != destPile ); QList cards = sourcePile->topCardsDownTo( card ); Q_ASSERT( allowedToAdd( destPile, cards ) ); if ( destPile->isEmpty() ) { qCDebug(KPAT_LOG) << "Moving" << card->objectName() << "from the" << sourcePile->objectName() << "pile to the" << destPile->objectName() << "pile, which is empty"; } else { qCDebug(KPAT_LOG) << "Moving" << card->objectName() << "from the" << sourcePile->objectName() << "pile to the" << destPile->objectName() << "pile, putting it on top of" << destPile->topCard()->objectName(); } moveCardsToPile( cards, destPile, DURATION_DEMO ); } else if ( !newCards() ) { if (isGameWon()) { won(); } else { stopDemo(); slotSolverEnded(); } return; } emit demoActive( true ); takeState(); } void DealerScene::drawDealRowOrRedeal() { stop(); if ( isCardAnimationRunning() ) { m_newCardsQueued = true; return; } m_newCardsQueued = false; newCards(); } bool DealerScene::newCards() { return false; } void DealerScene::setSolver( SolverInterface *s) { delete m_solver; delete m_solverThread; m_solver = s; m_solverThread = nullptr; } bool DealerScene::isGameWon() const { foreach (PatPile *p, patPiles()) { if (!p->isFoundation() && !p->isEmpty()) return false; } return true; } void DealerScene::startSolver() { if( m_solverEnabled ) m_solverUpdateTimer.start(); } bool DealerScene::isGameLost() const { if (! m_winningMoves.isEmpty()) { return false; } if ( solver() ) { if ( m_solverThread && m_solverThread->isRunning() ) m_solverThread->abort(); solver()->translate_layout(); return solver()->patsolve( neededFutureMoves() ) == SolverInterface::NoSolutionExists; } return false; } void DealerScene::recordGameStatistics() { // Don't record the game if it was never started, if it is unchanged since // it was last saved (allowing the user to close KPat after saving without // it recording a loss) or if it has already been recorded.// takeState(); // copying it again if ( m_dealStarted && !m_dealWasJustSaved && !m_statisticsRecorded ) { int id = oldId(); QString totalPlayedKey = QStringLiteral("total%1").arg( id ); QString wonKey = QStringLiteral("won%1").arg( id ); QString winStreakKey = QStringLiteral("winstreak%1").arg( id ); QString maxWinStreakKey = QStringLiteral("maxwinstreak%1").arg( id ); QString loseStreakKey = QStringLiteral("loosestreak%1").arg( id ); QString maxLoseStreakKey = QStringLiteral("maxloosestreak%1").arg( id ); QString minMovesKey = QStringLiteral("minmoves%1").arg( id ); KConfigGroup config(KSharedConfig::openConfig(), scores_group); int totalPlayed = config.readEntry( totalPlayedKey, 0 ); int won = config.readEntry( wonKey, 0 ); int winStreak = config.readEntry( winStreakKey, 0 ); int maxWinStreak = config.readEntry( maxWinStreakKey, 0 ); int loseStreak = config.readEntry( loseStreakKey, 0 ); int maxLoseStreak = config.readEntry( maxLoseStreakKey, 0 ); int minMoves = config.readEntry( minMovesKey, -1 ); ++totalPlayed; if ( m_dealHasBeenWon ) { ++won; ++winStreak; maxWinStreak = qMax( winStreak, maxWinStreak ); loseStreak = 0; if ( minMoves < 0 ) minMoves = moveCount(); else minMoves = qMin( minMoves, moveCount() ); } else { ++loseStreak; maxLoseStreak = qMax( loseStreak, maxLoseStreak ); winStreak = 0; } config.writeEntry( totalPlayedKey, totalPlayed ); config.writeEntry( wonKey, won ); config.writeEntry( winStreakKey, winStreak ); config.writeEntry( maxWinStreakKey, maxWinStreak ); config.writeEntry( loseStreakKey, loseStreak ); config.writeEntry( maxLoseStreakKey, maxLoseStreak ); config.writeEntry( minMovesKey, minMoves ); m_statisticsRecorded = true; } } void DealerScene::relayoutScene() { KCardScene::relayoutScene(); if ( m_wonItem->isVisible() ) updateWonItem(); } int DealerScene::gameId() const { return m_di->baseId(); } void DealerScene::setActions( int actions ) { m_supportedActions = actions; } int DealerScene::actions() const { return m_supportedActions; } QList DealerScene::configActions() const { return QList(); } SolverInterface * DealerScene::solver() const { return m_solver; } int DealerScene::neededFutureMoves() const { return m_neededFutureMoves; } void DealerScene::setNeededFutureMoves( int i ) { m_neededFutureMoves = i; } void DealerScene::setDeckContents( int copies, const QList & suits ) { Q_ASSERT( copies >= 1 ); Q_ASSERT( !suits.isEmpty() ); // Note that the order in which the cards are created can not be changed // without breaking the game numbering. For historical reasons, KPat // generates card by rank and then by suit, rather than the more common // suit then rank ordering. QList ids; unsigned int number = 0; for ( int i = 0; i < copies; ++i ) foreach ( const KCardDeck::Rank & r, KCardDeck::standardRanks() ) foreach ( const KCardDeck::Suit & s, suits ) ids << KCardDeck::getId( s, r, number++ ); deck()->setDeckContents( ids ); } QImage DealerScene::createDump() const { const QSize previewSize( 480, 320 ); foreach ( KCard * c, deck()->cards() ) c->completeAnimation(); QMultiMap itemsByZ; foreach ( QGraphicsItem * item, items() ) { Q_ASSERT( item->zValue() >= 0 ); itemsByZ.insert( item->zValue(), item ); } QImage img( contentArea().size().toSize(), QImage::Format_ARGB32 ); img.fill( Qt::transparent ); QPainter p( &img ); foreach ( QGraphicsItem * item, itemsByZ ) { if ( item->isVisible() ) { p.save(); p.setTransform( item->deviceTransform( p.worldTransform() ), false ); item->paint( &p, nullptr ); p.restore(); } } p.end(); img = img.scaled( previewSize, Qt::KeepAspectRatio, Qt::SmoothTransformation ); QImage img2( previewSize, QImage::Format_ARGB32 ); img2.fill( Qt::transparent ); QPainter p2( &img2 ); p2.drawImage( (img2.width() - img.width()) / 2, (img2.height() - img.height()) / 2, img ); p2.end(); return img2; } void DealerScene::mapOldId( int id ) { Q_UNUSED( id ); } int DealerScene::oldId() const { return gameId(); } QString DealerScene::getGameState() const { return QString(); } void DealerScene::setGameState( const QString & state ) { Q_UNUSED( state ); } QString DealerScene::getGameOptions() const { return QString(); } void DealerScene::setGameOptions( const QString & options ) { Q_UNUSED( options ); } bool DealerScene::allowedToStartNewGame() { // Check if the user is already running a game, and if she is, // then ask if she wants to abort it. return !m_dealStarted || m_dealWasJustSaved || m_toldAboutWonGame || m_toldAboutLostGame || KMessageBox::warningContinueCancel(nullptr, i18n("A new game has been requested, but there is already a game in progress.\n\n" "A loss will be recorded in the statistics if the current game is abandoned."), i18n("Abandon Current Game?"), KGuiItem(i18n("Abandon Current Game")), KStandardGuiItem::cancel(), QStringLiteral("careaboutstats") ) == KMessageBox::Continue; } void DealerScene::addCardForDeal( KCardPile * pile, KCard * card, bool faceUp, QPointF startPos ) { Q_ASSERT( card ); Q_ASSERT( pile ); card->setFaceUp( faceUp ); pile->add( card ); m_initDealPositions.insert( card, startPos ); } void DealerScene::startDealAnimation() { qreal speed = sqrt( width() * width() + height() * height() ) / ( DURATION_DEAL ); foreach ( PatPile * p, patPiles() ) { updatePileLayout( p, 0 ); foreach ( KCard * c, p->cards() ) { if ( !m_initDealPositions.contains( c ) ) continue; QPointF pos2 = c->pos(); c->setPos( m_initDealPositions.value( c ) ); QPointF delta = c->pos() - pos2; qreal dist = sqrt( delta.x() * delta.x() + delta.y() * delta.y() ); int duration = qRound( dist / speed ); c->animate( pos2, c->zValue(), 0, c->isFaceUp(), false, duration ); } } m_initDealPositions.clear(); } void DealerScene::multiStepMove( const QList & cards, KCardPile * pile, const QList & freePiles, const QList & freeCells, int duration ) { Q_ASSERT( cards.size() == 1 || !freePiles.isEmpty() || !freeCells.isEmpty() ); m_multiStepMoves.clear(); m_multiStepDuration = duration; multiStepSubMove( cards, pile, freePiles, freeCells ); continueMultiStepMove(); } void DealerScene::multiStepSubMove( QList cards, KCardPile * pile, QList freePiles, const QList & freeCells ) { // Note that cards and freePiles are passed by value, as we need to make a // local copy anyway. // Using n free cells, we can move a run of n+1 cards. If we want to move // more than that, we have to recursively move some of our cards to one of // the free piles temporarily. const int freeCellsPlusOne = freeCells.size() + 1; int cardsToSubMove = cards.size() - freeCellsPlusOne; QList > > tempMoves; while ( cardsToSubMove > 0 ) { int tempMoveSize; if ( cardsToSubMove <= freePiles.size() * freeCellsPlusOne ) { // If the cards that have to be submoved can be spread across the // the free piles without putting more than freeCellsPlusOne cards // on each one, we do so. This means that none of our submoves will // need further submoves, which keeps the total move count down. We // Just to a simple rounding up integer division. tempMoveSize = (cardsToSubMove + freePiles.size() - 1) / freePiles.size(); } else { // Otherwise, we use the space optimal method that gets the cards // moved using a minimal number of piles, but uses more submoves. tempMoveSize = freeCellsPlusOne; while ( tempMoveSize * 2 < cardsToSubMove ) tempMoveSize *= 2; } QList subCards; for ( int i = 0; i < tempMoveSize; ++i ) subCards.prepend( cards.takeLast() ); Q_ASSERT( !freePiles.isEmpty() ); KCardPile * nextPile = freePiles.takeFirst(); tempMoves << qMakePair( nextPile, subCards ); multiStepSubMove( subCards, nextPile, freePiles, freeCells ); cardsToSubMove -= tempMoveSize; } // Move cards to free cells. for ( int i = 0; i < cards.size() - 1; ++i ) { KCard * c = cards.at( cards.size() - 1 - i ); m_multiStepMoves << qMakePair( c, freeCells[i] ); } // Move bottom card to destination pile. m_multiStepMoves << qMakePair( cards.first(), pile ); // Move cards from free cells to destination pile. for ( int i = 1; i < cards.size(); ++i ) m_multiStepMoves << qMakePair( cards.at( i ), pile ); // If we just moved the bottomost card of the source pile, it must now be // empty and we won't need it any more. So we return it to the list of free // piles. KCardPile * sourcePile = cards.first()->pile(); if ( sourcePile->at( 0 ) == cards.first() ) freePiles << sourcePile; // If we had to do any submoves, we now move those cards from their // temporary pile to the destination pile and free up their temporary pile. while ( !tempMoves.isEmpty() ) { QPair > m = tempMoves.takeLast(); multiStepSubMove( m.second, pile, freePiles, freeCells ); freePiles << m.first; } } void DealerScene::continueMultiStepMove() { Q_ASSERT( !m_multiStepMoves.isEmpty() ); Q_ASSERT( !isCardAnimationRunning() ); QPair m = m_multiStepMoves.takeFirst(); KCard * card = m.first; KCardPile * dest = m.second; KCardPile * source = card->pile(); Q_ASSERT( card == source->topCard() ); Q_ASSERT( allowedToAdd( dest, QList() << card ) ); m_multiStepDuration = qMax( m_multiStepDuration * 0.9, 50 ); dest->add( card ); card->raise(); updatePileLayout( dest, m_multiStepDuration ); updatePileLayout( source, m_multiStepDuration ); if ( m_multiStepMoves.isEmpty() ) takeState(); } #include "dealer.moc" #include "moc_dealer.cpp" diff --git a/patsolve/patsolve.cpp b/patsolve/patsolve.cpp index 9435f92..b2ca58e 100644 --- a/patsolve/patsolve.cpp +++ b/patsolve/patsolve.cpp @@ -1,992 +1,992 @@ /* * Copyright (C) 1998-2002 Tom Holroyd * Copyright (C) 2006-2009 Stephan Kulow * * 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, see . */ #include "patsolve.h" #include "../patpile.h" #include "../kpat_debug.h" #include #include #include #include #include #include #include #ifdef ERR #undef ERR #endif long all_moves = 0; /* This is a 32 bit FNV hash. For more information, see http://www.isthe.com/chongo/tech/comp/fnv/index.html */ namespace { constexpr qint32 FNV_32_PRIME = 0x01000193; // FIXME: move into fnv_hash once we depend on C++14 constexpr qint32 fnv_hash(qint32 x, qint32 hash) {return (hash * FNV_32_PRIME) ^ x;} /* Hash a 0 terminated string. */ quint32 fnv_hash_str(const quint8 *s) { constexpr qint32 FNV1_32_INIT = 0x811C9DC5; quint32 h; h = FNV1_32_INIT; while (*s) { h = fnv_hash(*s++, h); } return h; } } /* Hash a pile. */ template void Solver::hashpile(int w) { W[w][Wlen[w]] = 0; Whash[w] = fnv_hash_str(W[w]); /* Invalidate this pile's id. We'll calculate it later. */ Wpilenum[w] = -1; } /* Generate an array of the moves we can make from this position. */ template MOVE *Solver::get_moves(int *nmoves) { int i, n, alln, a = 0, numout = 0; MOVE *mp, *mp0; /* Fill in the Possible array. */ alln = n = get_possible_moves(&a, &numout); -#ifndef NDEBUG +#ifdef GET_MOVES_DEBUG { print_layout(); fprintf( stderr, "moves %d\n", n ); for (int j = 0; j < n; j++) { fprintf( stderr, " " ); if ( Possible[j].totype == O_Type ) fprintf( stderr, "move from %d out (at %d) Prio: %d\n", Possible[j].from, Possible[j].turn_index, Possible[j].pri ); else fprintf( stderr, "move %d from %d to %d (%d) Prio: %d\n", Possible[j].card_index, Possible[j].from, Possible[j].to, Possible[j].turn_index, Possible[j].pri ); } } #endif /* No moves? Maybe we won. */ if (n == 0) { /* No more moves - won or lost */ //print_layout(); return nullptr; } /* Prioritize these moves. Automoves don't get queued, so they don't need a priority. */ if (!a) { prioritize(Possible, alln); } /* Now copy to safe storage and return. Non-auto moves out get put at the end. Queueing them isn't a good idea because they are still good moves, even if they didn't pass the automove test. So we still do the recursive solve() on them, but only after queueing the other moves. */ mp = mp0 = mm_new_array(n); if (mp == nullptr) { return nullptr; } *nmoves = n; i = 0; if (a || numout == 0) { for (i = 0; i < alln; ++i) { if (Possible[i].card_index != -1) { *mp = Possible[i]; /* struct copy */ mp++; } } } else { for (i = numout; i < alln; ++i) { if (Possible[i].card_index != -1) { *mp = Possible[i]; /* struct copy */ mp++; } } for (i = 0; i < numout; ++i) { if (Possible[i].card_index != -1) { *mp = Possible[i]; /* struct copy */ mp++; } } } return mp0; } /* Test the current position to see if it's new (or better). If it is, save it, along with the pointer to its parent and the move we used to get here. */ int Posbytes; template void Solver::pilesort(void) { /* Make sure all the piles have id numbers. */ for (size_t w = 0; w < NumberPiles; w++) { if (Wpilenum[w] < 0) { Wpilenum[w] = get_pilenum(w); if (Wpilenum[w] < 0) { return; } } //fprintf( stderr, "%d ", Wpilenum[w] ); } //fprintf( stderr, "\n" ); } #define NBUCKETS 65521 /* the largest 16 bit prime */ #define NPILES 65536 /* a 16 bit code */ typedef struct bucketlist { quint8 *pile; /* 0 terminated copy of the pile */ quint32 hash; /* the pile's hash code */ int pilenum; /* the unique id for this pile */ struct bucketlist *next; } BUCKETLIST; BUCKETLIST *Bucketlist[NBUCKETS]; int Pilenum; /* the next pile number to be assigned */ BUCKETLIST *Pilebucket[NPILES]; /* reverse lookup for unpack to get the bucket from the pile */ /* Compact position representation. The position is stored as an array with the following format: pile0# pile1# ... pileN# (N = Nwpiles) where each pile number is packed into 16 bits (so a pile take 2 bytes). Positions in this format are unique can be compared with memcmp(). The O cells are encoded as a cluster number: no two positions with different cluster numbers can ever be the same, so we store different clusters in different trees. */ int Treebytes; template TREE *Solver::pack_position(void) { int j; quint8 *p; TREE *node; /* Allocate space and store the pile numbers. The tree node will get filled in later, by insert_node(). */ p = mm->new_from_block(Treebytes); if (p == nullptr) { Status = UnableToDetermineSolvability; return nullptr; } node = (TREE *)p; p += sizeof(TREE); /* Pack the pile numers j into bytes p. j j +--------+----:----+--------+ |76543210|7654:3210|76543210| +--------+----:----+--------+ p p p */ quint16 *p2 = ( quint16* ) p; for (size_t w = 0; w < NumberPiles; ++w) { j = Wpilenum[w]; if ( j < 0 ) { mm->give_back_block( p ); return nullptr; } *p2++ = j; } return node; } /* Like strcpy() but return the length of the string. */ static inline int strecpy(unsigned char *d, unsigned char *s) { int i; i = 0; while ((*d++ = *s++) != '\0') { i++; } return i; } /* Unpack a compact position rep. T cells must be restored from the array following the POSITION struct. */ template void Solver::unpack_position(POSITION *pos) { int i = 0; BUCKETLIST *l; unpack_cluster(pos->cluster); /* Unpack bytes p into pile numbers j. p p p +--------+----:----+--------+ |76543210|7654:3210|76543210| +--------+----:----+--------+ j j */ size_t w = 0; quint16 *p2 = ( quint16* )( (quint8 *)(pos->node) + sizeof(TREE) ); while (w < NumberPiles) { i = *p2++; Wpilenum[w] = i; l = Pilebucket[i]; i = strecpy(W[w], l->pile); Wp[w] = &W[w][i - 1]; Wlen[w] = i; Whash[w] = l->hash; w++; } } template void Solver::printcard(card_t card, FILE *outfile) { static char Rank[] = " A23456789TJQK"; static char Suit[] = "DCHS"; if (RANK(card) == NONE) { fprintf(outfile, " "); } else { if ( DOWN(card ) ) fprintf(outfile, "|%c%c ", Rank[RANK(card)], Suit[SUIT(card)]); else fprintf(outfile, "%c%c ", Rank[RANK(card)], Suit[SUIT(card)]); } } /* Win. Print out the move stack. */ template void Solver::win(POSITION *pos) { int i, nmoves; POSITION *p; MOVE **mpp, **mpp0; /* Go back up the chain of parents and store the moves in reverse order. */ i = 0; for (p = pos; p->parent; p = p->parent) { i++; } nmoves = i; //printf("Winning in %d moves.\n", nmoves); mpp0 = mm_new_array(nmoves); if (mpp0 == nullptr) { Status = UnableToDetermineSolvability; return; /* how sad, so close... */ } mpp = mpp0 + nmoves - 1; for (p = pos; p->parent; p = p->parent) { *mpp-- = &p->move; } for (i = 0, mpp = mpp0; i < nmoves; ++i, ++mpp) m_winMoves.append( **mpp ); MemoryManager::free_array(mpp0, nmoves); } /* Initialize the hash buckets. */ template void Solver::init_buckets(void) { int i; /* Packed positions need 3 bytes for every 2 piles. */ i = ( NumberPiles ) * sizeof( quint16 ); i += ( NumberPiles ) & 0x1; mm->Pilebytes = i; memset(Bucketlist, 0, sizeof(Bucketlist)); Pilenum = 0; Treebytes = sizeof(TREE) + mm->Pilebytes; /* In order to keep the TREE structure aligned, we need to add up to 7 bytes on Alpha or 3 bytes on Intel -- but this is still better than storing the TREE nodes and keys separately, as that requires a pointer. On Intel for -f Treebytes winds up being a multiple of 8 currently anyway so it doesn't matter. */ #define ALIGN_BITS 0x7 if (Treebytes & ALIGN_BITS) { Treebytes |= ALIGN_BITS; Treebytes++; } Posbytes = sizeof(POSITION); if (Posbytes & ALIGN_BITS) { Posbytes |= ALIGN_BITS; Posbytes++; } } /* For each pile, return a unique identifier. Although there are a large number of possible piles, generally fewer than 1000 different piles appear in any given game. We'll use the pile's hash to find a hash bucket that contains a short list of piles, along with their identifiers. */ template int Solver::get_pilenum(int w) { int bucket, pilenum; BUCKETLIST *l, *last; /* For a given pile, get its unique pile id. If it doesn't have one, add it to the appropriate list and give it one. First, get the hash bucket. */ bucket = Whash[w] % NBUCKETS; /* Look for the pile in this bucket. */ last = nullptr; for (l = Bucketlist[bucket]; l; l = l->next) { if (l->hash == Whash[w] && strncmp((char*)l->pile, (char*)W[w], Wlen[w]) == 0) { break; } last = l; } /* If we didn't find it, make a new one and add it to the list. */ if (l == nullptr) { if (Pilenum >= NPILES ) { Status = UnableToDetermineSolvability; //qCDebug(KPAT_LOG) << "out of piles"; return -1; } l = mm_allocate(); if (l == nullptr) { Status = UnableToDetermineSolvability; //qCDebug(KPAT_LOG) << "out of buckets"; return -1; } l->pile = mm_new_array(Wlen[w] + 1); if (l->pile == nullptr) { Status = UnableToDetermineSolvability; MemoryManager::free_ptr(l); //qCDebug(KPAT_LOG) << "out of memory"; return -1; } /* Store the new pile along with its hash. Maintain a reverse mapping so we can unpack the piles swiftly. */ strncpy((char*)l->pile, (char*)W[w], Wlen[w] + 1); l->hash = Whash[w]; l->pilenum = pilenum = Pilenum++; l->next = nullptr; if (last == nullptr) { Bucketlist[bucket] = l; } else { last->next = l; } Pilebucket[pilenum] = l; } #if 0 if (w < 4) { fprintf( stderr, "get_pile_num %d ", l->pilenum ); for (int i = 0; i < Wlen[w]; ++i) { printcard(W[w][i], stderr); } fprintf( stderr, "\n" ); } #endif return l->pilenum; } template void Solver::free_buckets(void) { int i, j; BUCKETLIST *l, *n; for (i = 0; i < NBUCKETS; i++) { l = Bucketlist[i]; while (l) { n = l->next; j = strlen((char*)l->pile); /* @@@ use block? */ MemoryManager::free_array(l->pile, j + 1); MemoryManager::free_ptr(l); l = n; } } } /* Solve patience games. Prioritized breadth-first search. Simple breadth- first uses exponential memory. Here the work queue is kept sorted to give priority to positions with more cards out, so the solution found is not guaranteed to be the shortest, but it'll be better than with a depth-first search. */ template void Solver::doit() { int i, q; POSITION *pos; MOVE m; /* Init the queues. */ for (i = 0; i < NQUEUES; ++i) { Qhead[i] = nullptr; } Maxq = 0; /* Queue the initial position to get started. */ hash_layout(); pilesort(); m.card_index = -1; m.turn_index = -1; pos = new_position(nullptr, &m); if ( pos == nullptr ) { Status = UnableToDetermineSolvability; return; } queue_position(pos, 0); /* Solve it. */ while ((pos = dequeue_position()) != nullptr) { q = solve(pos); if (!q) { free_position(pos, true); } } } /* Generate all the successors to a position and either queue them or recursively solve them. Return whether any of the child nodes, or their descendents, were queued or not (if not, the position can be freed). */ template bool Solver::solve(POSITION *parent) { int i, nmoves, qq; MOVE *mp, *mp0; POSITION *pos; bool q; all_moves++; /* If we've won already (or failed), we just go through the motions but always return false from any position. This enables the cleanup of the move stack and eventual destruction of the position store. */ if (Status != NoSolutionExists) { return false; } if ( m_shouldEnd.load() ) { Status = SearchAborted; return false; } if ( max_positions != -1 && Total_positions > ( unsigned long )max_positions ) { Status = MemoryLimitReached; return false; } /* Generate an array of all the moves we can make. */ if ((mp0 = get_moves(&nmoves)) == nullptr) { if ( isWon() ) { Status = SolutionExists; win( parent ); } return false; } if ( parent->depth == 0 ) { Q_ASSERT( m_firstMoves.isEmpty() ); for (int j = 0; j < nmoves; ++j) m_firstMoves.append( Possible[j] ); } parent->nchild = nmoves; /* Make each move and either solve or queue the result. */ q = false; for (i = 0, mp = mp0; i < nmoves; ++i, ++mp) { make_move(mp); /* Calculate indices for the new piles. */ pilesort(); /* See if this is a new position. */ if ((pos = new_position(parent, mp)) == nullptr) { undo_move(mp); parent->nchild--; continue; } /* If this position is in a new cluster, a card went out. Don't queue it, just keep going. A larger cutoff can also force a recursive call, which can help speed things up (but reduces the quality of solutions). Otherwise, save it for later. */ if (pos->cluster != parent->cluster || !nmoves) { qq = solve(pos); undo_move(mp); if (!qq) { free_position(pos, false); } q |= (bool)qq; } else { queue_position(pos, mp->pri); undo_move(mp); q = true; } } MemoryManager::free_array(mp0, nmoves); /* Return true if this position needs to be kept around. */ return q; } /* We can't free the stored piles in the trees, but we can free some of the POSITION structs. We have to be careful, though, because there are many threads running through the game tree starting from the queued positions. The nchild element keeps track of descendents, and when there are none left in the parent we can free it too after solve() returns and we get called recursively (rec == true). */ template void Solver::free_position(POSITION *pos, int rec) { /* We don't really free anything here, we just push it onto a freelist (using the queue member), so we can use it again later. */ if (!rec) { pos->queue = Freepos; Freepos = pos; pos->parent->nchild--; } else { do { pos->queue = Freepos; Freepos = pos; pos = pos->parent; if (pos == nullptr) { return; } pos->nchild--; } while (pos->nchild == 0); } } /* Save positions for consideration later. pri is the priority of the move that got us here. The work queue is kept sorted by priority (simply by having separate queues). */ template void Solver::queue_position(POSITION *pos, int pri) { /* In addition to the priority of a move, a position gets an additional priority depending on the number of cards out. We use a "queue squashing function" to map nout to priority. */ int nout = getOuts(); static qreal Yparam[] = { 0.0032, 0.32, -3.0 }; qreal x = (Yparam[0] * nout + Yparam[1]) * nout + Yparam[2]; pri += (int)floor(x + .5); if (pri < 0) { pri = 0; } else if (pri >= NQUEUES) { pri = NQUEUES - 1; } if (pri > Maxq) { Maxq = pri; } /* We always dequeue from the head. Here we either stick the move at the head or tail of the queue, depending on whether we're pretending it's a stack or a queue. */ pos->queue = nullptr; if (Qhead[pri] == nullptr) { Qhead[pri] = pos; } else { pos->queue = Qhead[pri]; Qhead[pri] = pos; } } /* Return the position on the head of the queue, or NULL if there isn't one. */ template POSITION *Solver::dequeue_position() { int last; POSITION *pos; static int qpos = 0; static int minpos = 0; /* This is a kind of prioritized round robin. We make sweeps through the queues, starting at the highest priority and working downwards; each time through the sweeps get longer. That way the highest priority queues get serviced the most, but we still get lots of low priority action (instead of ignoring it completely). */ last = false; do { qpos--; if (qpos < minpos) { if (last) { return nullptr; } qpos = Maxq; minpos--; if (minpos < 0) { minpos = Maxq; } if (minpos == 0) { last = true; } } } while (Qhead[qpos] == nullptr); pos = Qhead[qpos]; Qhead[qpos] = pos->queue; /* Decrease Maxq if that queue emptied. */ while (Qhead[qpos] == nullptr && qpos == Maxq && Maxq > 0) { Maxq--; qpos--; if (qpos < minpos) { minpos = qpos; } } /* Unpack the position into the work arrays. */ unpack_position(pos); return pos; } template Solver::Solver() : mm(new MemoryManager) { /* Initialize work arrays. */ for (auto& workspace: W) { workspace = new card_t[84]; memset( workspace, 0, sizeof( card_t ) * 84 ); } } template Solver::~Solver() { for ( size_t i = 0; i < NumberPiles; ++i ) { delete [] W[i]; } } template void Solver::init() { m_shouldEnd.store(false); init_buckets(); mm->init_clusters(); m_winMoves.clear(); m_firstMoves.clear(); /* Reset stats. */ Status = NoSolutionExists; Total_positions = 0; Total_generated = 0; depth_sum = 0; } template void Solver::free() { free_buckets(); mm->free_clusters(); mm->free_blocks(); Freepos = nullptr; } template SolverInterface::ExitStatus Solver::patsolve( int _max_positions ) { max_positions = _max_positions; /* Initialize the suitable() macro variables. */ init(); /* Go to it. */ doit(); if ( Status == SearchAborted ) // thread quit { m_firstMoves.clear(); m_winMoves.clear(); } #if 0 printf("%ld positions generated (%f).\n", Total_generated, depth_sum / Total_positions); printf("%ld unique positions.\n", Total_positions); printf("Mem_remain = %ld\n", ( long int )mm->Mem_remain); #endif free(); return Status; } template void Solver::stopExecution() { m_shouldEnd.store(true); } template QList Solver::winMoves() const { return m_winMoves; } template QList Solver::firstMoves() const { return m_firstMoves; } template void Solver::print_layout() { } template int Solver::translateSuit( int s ) { int suit = s * 0x10; if ( suit == PS_DIAMOND ) return PS_CLUB; else if ( suit == PS_CLUB ) return PS_DIAMOND; return suit; } template int Solver::translate_pile(const KCardPile *pile, card_t *w, int size) { Q_UNUSED( size ); Q_ASSERT( pile->count() <= size ); for ( int i = 0; i < pile->count(); ++i ) { KCard *c = pile->at( i ); *w = + translateSuit( c->suit() ) + c->rank(); if ( !c->isFaceUp() ) *w += 1 << 7; w++; } return pile->count(); } /* Insert key into the tree unless it's already there. Return true if it was new. */ template MemoryManager::inscode Solver::insert(unsigned int *cluster, int d, TREE **node) { /* Get the cluster number from the Out cell contents. */ unsigned int k = getClusterNumber(); *cluster = k; /* Get the tree for this cluster. */ TREELIST *tl = mm->cluster_tree(k); if (tl == nullptr) { return MemoryManager::ERR; } /* Create a compact position representation. */ TREE *newtree = pack_position(); if (newtree == nullptr) { return MemoryManager::ERR; } Total_generated++; MemoryManager::inscode i2 = mm->insert_node(newtree, d, &tl->tree, node); if (i2 != MemoryManager::NEW) { mm->give_back_block((quint8 *)newtree); } return i2; } template POSITION *Solver::new_position(POSITION *parent, MOVE *m) { unsigned int depth, cluster; quint8 *p; POSITION *pos; TREE *node; /* Search the list of stored positions. If this position is found, then ignore it and return (unless this position is better). */ if (parent == nullptr) { depth = 0; } else { depth = parent->depth + 1; } MemoryManager::inscode i = insert(&cluster, depth, &node); if (i == MemoryManager::NEW) { Total_positions++; depth_sum += depth; } else return nullptr; /* A new or better position. insert() already stashed it in the tree, we just have to wrap a POSITION struct around it, and link it into the move stack. Store the temp cells after the POSITION. */ if (Freepos) { p = (quint8 *)Freepos; Freepos = Freepos->queue; } else { p = mm->new_from_block(Posbytes); if (p == nullptr) { Status = UnableToDetermineSolvability; return nullptr; } } pos = (POSITION *)p; pos->queue = nullptr; pos->parent = parent; pos->node = node; pos->move = *m; /* struct copy */ pos->cluster = cluster; pos->depth = depth; pos->nchild = 0; #if 0 QString dummy; quint16 *t = ( quint16* )( ( char* )node + sizeof( TREE ) ); for ( int i = 0; i < NumberPiles; ++i ) { QString s = " " + QString( "%1" ).arg( ( int )t[i] ); dummy += s.right( 5 ); } if ( Total_positions % 1000 == 1000 ) print_layout(); //qCDebug(KPAT_LOG) << "new" << dummy; #endif p += sizeof(POSITION); return pos; } /* Hash the whole layout. This is called once, at the start. */ template void Solver::hash_layout(void) { for (size_t w = 0; w < NumberPiles; w++) { hashpile(w); } } template void Solver::prioritize(MOVE *, int ) { } constexpr auto Nwpiles = 8; constexpr auto Ntpiles = 4; template class Solver<9>; template class Solver<10>; template class Solver<7 * 3 + 1>; template class Solver<8 + 1 + 8>; template class Solver<6>; template class Solver<34>; template class Solver<15>; template class Solver<7>; template class Solver;