diff --git a/dealer.h b/dealer.h index beba47f..6cbe8bb 100644 --- a/dealer.h +++ b/dealer.h @@ -1,290 +1,289 @@ /* * 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 . * ------------------------------------------------------------------------- */ #ifndef DEALER_H #define DEALER_H class DealerInfo; #include "gamestate.h" class MessageBox; class MoveHint; #include "patpile.h" class Solver; class SolverThread; #include "speeds.h" #include "view.h" -#include "patsolve/patsolve.h" #include "KCardDeck" #include "KCardScene" class QAction; #include #include #include class DealerScene : public KCardScene { Q_OBJECT public: enum { None = 0, Hint = 1, Demo = 2, Draw = 4, Deal = 8, Redeal = 16 } Actions; explicit DealerScene( const DealerInfo * di ); ~DealerScene(); virtual void initialize() = 0; void relayoutScene() Q_DECL_OVERRIDE; void updateWonItem(); void addPatPile( PatPile * pile ); void removePatPile( PatPile * pile ); QList patPiles() const; void setAutoDropEnabled( bool enabled ); bool autoDropEnabled() const; int gameNumber() const; int gameId() const; void setActions( int actions ); int actions() const; virtual QList configActions() const; void startHint(); void stopHint(); bool isHintActive() const; void startDrop(); void stopDrop(); bool isDropActive() const; void startDemo(); void stopDemo(); bool isDemoActive() const; void setSolverEnabled( bool enabled ); Solver * solver() const; void startSolver(); virtual bool isGameLost() const; virtual bool isGameWon() const; bool allowedToStartNewGame(); int moveCount() const; void saveFile( QIODevice * io ); bool loadFile( QIODevice * io ); void saveLegacyFile( QIODevice * io ); bool loadLegacyFile( QIODevice * io ); virtual void mapOldId(int id); virtual int oldId() const; void recordGameStatistics(); QImage createDump() const; signals: void undoPossible(bool poss); void redoPossible(bool poss); void newCardsPossible(bool poss); void gameInProgress(bool inProgress); void demoActive(bool active); void hintActive(bool active); void dropActive(bool active); void updateMoves(int moves); void solverStateChanged(QString text); void cardsPickedUp(); void cardsPutDown(); public slots: void startNew( int dealNumber = -1 ); void undo(); void redo(); void stop(); void drawDealRowOrRedeal(); virtual bool tryAutomaticMove( KCard * card ); protected: bool allowedToAdd(const KCardPile * pile, const QList & cards) const Q_DECL_OVERRIDE; bool allowedToRemove(const KCardPile * pile, const KCard * card) const Q_DECL_OVERRIDE; virtual bool checkAdd( const PatPile * pile, const QList & oldCards, const QList & newCards ) const; virtual bool checkRemove( const PatPile * pile, const QList & cards ) const; virtual bool checkPrefering( const PatPile * pile, const QList & oldCards, const QList & newCards ) const; void cardsMoved( const QList & cards, KCardPile * oldPile, KCardPile * newPile ) Q_DECL_OVERRIDE; void mouseDoubleClickEvent( QGraphicsSceneMouseEvent * mouseEvent ) Q_DECL_OVERRIDE; void mousePressEvent( QGraphicsSceneMouseEvent * mouseEvent ) Q_DECL_OVERRIDE; void mouseReleaseEvent( QGraphicsSceneMouseEvent * mouseEvent ) Q_DECL_OVERRIDE; virtual void restart( const QList & cards ) = 0; void setSolver( Solver * solver ); virtual QList getHints(); // reimplement these to store and load game-specific information in the state structure virtual QString getGameState() const; virtual void setGameState( const QString & state ); // reimplement these to store and load game-specific options in the saved game file virtual QString getGameOptions() const; virtual void setGameOptions( const QString & options ); void addCardForDeal( KCardPile * pile, KCard * card, bool faceUp, QPointF startPos ); void startDealAnimation(); void setNeededFutureMoves( int moves ); int neededFutureMoves() const; void setDeckContents( int copies = 1, const QList & suits = KCardDeck::standardSuits() ); void multiStepMove( const QList & cards, KCardPile * pile, const QList & freePiles, const QList & freeCells, int duration ); QList getSolverHints(); protected slots: void takeState(); virtual void animationDone(); virtual bool newCards(); virtual bool drop(); private slots: void stopAndRestartSolver(); void slotSolverEnded(); void slotSolverFinished( int result ); void demo(); void showWonMessage(); private: void undoOrRedo( bool undo ); void resetInternals(); MoveHint chooseHint(); void won(); int speedUpTime( int delay ) const; void multiStepSubMove( QList cards, KCardPile * pile, QList freePiles, const QList & freeCells ); void continueMultiStepMove(); const DealerInfo * const m_di; Solver * m_solver; SolverThread * m_solverThread; QList m_winningMoves; KCard * m_peekedCard; MessageBox * m_wonItem; QTimer m_solverUpdateTimer; QTimer m_demoTimer; QTimer m_dropTimer; int m_dealNumber; int m_loadedMoveCount; int m_neededFutureMoves; int m_supportedActions; bool m_autoDropEnabled; bool m_solverEnabled; bool m_dealStarted; bool m_dealWasEverWinnable; bool m_dealHasBeenWon; bool m_dealWasJustSaved; bool m_statisticsRecorded; bool m_playerReceivedHelp; // We need a flag to avoid telling someone the game is lost // just because the winning animation moved the cards away bool m_toldAboutWonGame; bool m_toldAboutLostGame; QSet m_cardsRemovedFromFoundations; qreal m_dropSpeedFactor; bool m_interruptAutoDrop; bool m_dealInProgress; bool m_hintInProgress; bool m_demoInProgress; bool m_dropInProgress; bool m_hintQueued; bool m_demoQueued; bool m_dropQueued; bool m_newCardsQueued; bool m_takeStateQueued; QStack m_undoStack; GameState * m_currentState; QStack m_redoStack; QHash m_lastKnownCardStates; QList > m_multiStepMoves; int m_multiStepDuration; QList m_patPiles; QMap m_initDealPositions; }; #endif diff --git a/libkcardgame/kcardscene.cpp b/libkcardgame/kcardscene.cpp index f2ea3a4..9291af4 100644 --- a/libkcardgame/kcardscene.cpp +++ b/libkcardgame/kcardscene.cpp @@ -1,1280 +1,1252 @@ /* * 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 "kcardscene.h" #include "kabstractcarddeck.h" #include "kcardpile.h" #include #include #include #include #include -#define DEBUG_LAYOUT 0 - - namespace { const int cardMoveDuration = 230; void setItemHighlight( QGraphicsItem * item, bool highlight ) { KCard * card = qgraphicsitem_cast( item ); if ( card ) { card->setHighlighted( highlight ); return; } KCardPile * pile = qgraphicsitem_cast( item ); if ( pile ) { pile->setHighlighted( highlight ); return; } } QGraphicsItem * toGraphicsItem( QObject * object ) { if ( KCard * card = qobject_cast( object ) ) return card; if ( KCardPile * pile = qobject_cast( object ) ) return pile; Q_ASSERT( !object ); return nullptr; } } class KCardScenePrivate : public QObject { public: KCardScenePrivate( KCardScene * p ); KCardPile * bestDestinationPileUnderCards(); void sendCardsToPile( KCardPile * pile, QList cards, qreal rate, bool isSpeed, bool flip ); void changeFocus( int pileChange, int cardChange ); void updateKeyboardFocus(); KCardScene * const q; KAbstractCardDeck * deck; QList piles; QHash pileAreas; QSet highlightedItems; QList cardsBeingDragged; QPointF startOfDrag; bool dragStarted; KCardScene::SceneAlignment alignment; qreal layoutMargin; qreal layoutSpacing; QSizeF contentSize; bool keyboardMode; int keyboardPileIndex; int keyboardCardIndex; QPointer keyboardFocusItem; bool sizeHasBeenSet; }; KCardScenePrivate::KCardScenePrivate( KCardScene * p ) : QObject( p ), q( p ) { dragStarted = false; } KCardPile * KCardScenePrivate::bestDestinationPileUnderCards() { QSet targets; foreach ( QGraphicsItem * item, q->collidingItems( cardsBeingDragged.first(), Qt::IntersectsItemBoundingRect ) ) { KCardPile * p = qgraphicsitem_cast( item ); if ( !p ) { KCard * c = qgraphicsitem_cast( item ); if ( c ) p = c->pile(); } if ( p ) targets << p; } KCardPile * bestTarget = nullptr; qreal bestArea = 1; foreach ( KCardPile * p, targets ) { if ( p != cardsBeingDragged.first()->pile() && q->allowedToAdd( p, cardsBeingDragged ) ) { QRectF targetRect = p->sceneBoundingRect(); foreach ( KCard *c, p->cards() ) targetRect |= c->sceneBoundingRect(); QRectF intersection = targetRect & cardsBeingDragged.first()->sceneBoundingRect(); qreal area = intersection.width() * intersection.height(); if ( area > bestArea ) { bestTarget = p; bestArea = area; } } } return bestTarget; } void KCardScenePrivate::sendCardsToPile( KCardPile * pile, QList newCards, qreal rate, bool isSpeed, bool flip ) { if ( pile->isEmpty() && newCards.isEmpty() ) return; int oldCardCount = pile->count(); for ( int i = 0; i < newCards.size(); ++i ) { // If we're flipping the cards, we have to add them to the pile in // reverse order. KCard * c = newCards[ flip ? newCards.size() - 1 - i : i ]; // The layout of the card within the pile may depend on whether it is // face up or down. Therefore, we must flip the card, add it to the // pile, calculate its position, flip it back, then start the animation // which will flip it one more time. if ( flip ) c->setFaceUp( !c->isFaceUp() ); pile->add( c ); } const QSize cardSize = deck->cardSize(); const qreal cardUnit = (deck->cardWidth() + deck->cardHeight()) / 2.0; const QList cards = pile->cards(); const QList positions = pile->cardPositions(); qreal minX = 0; qreal maxX = 0; qreal minY = 0; qreal maxY = 0; foreach ( const QPointF & pos, positions ) { minX = qMin( minX, pos.x() ); maxX = qMax( maxX, pos.x() ); minY = qMin( minY, pos.y() ); maxY = qMax( maxY, pos.y() ); } QPointF absLayoutPos = pile->layoutPos(); if ( absLayoutPos.x() < 0 ) absLayoutPos.rx() += contentSize.width() / cardSize.width() - 1; if ( absLayoutPos.y() < 0 ) absLayoutPos.ry() += contentSize.height() / cardSize.height() - 1; QRectF available = pileAreas.value( pile, QRectF() ); qreal availableTop = absLayoutPos.y() - available.top(); qreal availableBottom = available.bottom() - (absLayoutPos.y() + 1); qreal availableLeft = absLayoutPos.x() - available.left(); qreal availableRight = available.right() - (absLayoutPos.x() + 1); qreal scaleTop = (minY >= 0) ? 1 : qMin( availableTop / -minY, 1 ); qreal scaleBottom = (maxY <= 0) ? 1 : qMin( availableBottom / maxY, 1 ); qreal scaleY = qMin( scaleTop, scaleBottom ); qreal scaleLeft = (minX >= 0) ? 1 : qMin( availableLeft / -minX, 1 ); qreal scaleRight = (maxX <= 0) ? 1 : qMin( availableRight / maxX, 1 ); qreal scaleX = qMin( scaleLeft, scaleRight ); QList realPositions; QList distances; qreal maxDistance = 0; for ( int i = 0; i < cards.size(); ++i ) { QPointF pos( pile->x() + positions[i].x() * scaleX * cardSize.width(), pile->y() + positions[i].y() * scaleY * cardSize.height() ); realPositions << pos; qreal distance = 0; if ( isSpeed && i >= oldCardCount ) { QPointF delta = pos - cards[i]->pos(); distance = sqrt( delta.x() * delta.x() + delta.y() * delta.y() ) / cardUnit; if ( distance > maxDistance ) maxDistance = distance; } distances << distance; } qreal z = pile->zValue(); int layoutDuration = isSpeed ? qMin( cardMoveDuration, maxDistance / rate * 1000 ) : rate; for ( int i = 0; i < cards.size(); ++i ) { bool isNewCard = i >= oldCardCount; int duration = (isNewCard && isSpeed) ? distances[i] / rate * 1000 : layoutDuration; // Honour the pile's autoTurnTop property. bool face = cards[i]->isFaceUp() || (cards[i] == pile->topCard() && pile->autoTurnTop()); if ( isNewCard && flip ) { // The card will be flipped as part of the animation, so we return // it to its original face up/down position before starting the // animation. cards[i]->setFaceUp( !cards[i]->isFaceUp() ); } // Each card has a Z value 1 greater than the card below it. ++z; cards[i]->animate( realPositions[i], z, 0, face, isNewCard, duration ); } } void KCardScenePrivate::changeFocus( int pileChange, int cardChange ) { if ( !keyboardMode ) { q->setKeyboardModeActive( true ); return; } if ( pileChange ) { KCardPile * pile; KCardPile::KeyboardFocusHint hint; do { keyboardPileIndex += pileChange; if ( keyboardPileIndex < 0 ) keyboardPileIndex = piles.size() - 1; else if ( keyboardPileIndex >= piles.size() ) keyboardPileIndex = 0; pile = piles.at( keyboardPileIndex ); hint = cardsBeingDragged.isEmpty() ? pile->keyboardSelectHint() : pile->keyboardDropHint(); } while ( hint == KCardPile::NeverFocus ); if ( !pile->isEmpty() ) { if ( hint == KCardPile::AutoFocusTop || hint == KCardPile::ForceFocusTop ) { keyboardCardIndex = pile->count() - 1; } else if ( hint == KCardPile::AutoFocusDeepestRemovable ) { keyboardCardIndex = pile->count() - 1; while ( keyboardCardIndex > 0 && q->allowedToRemove( pile, pile->at( keyboardCardIndex - 1 ) ) ) --keyboardCardIndex; } else if ( hint == KCardPile::AutoFocusDeepestFaceUp ) { keyboardCardIndex = pile->count() - 1; while ( keyboardCardIndex > 0 && pile->at( keyboardCardIndex - 1 )->isFaceUp() ) --keyboardCardIndex; } else if ( hint == KCardPile::AutoFocusBottom ) { keyboardCardIndex = 0; } } } if ( cardChange ) { KCardPile * pile = piles.at( keyboardPileIndex ); if ( cardChange < 0 && keyboardCardIndex >= pile->count() ) { keyboardCardIndex = qMax( 0, pile->count() - 2 ); } else { keyboardCardIndex += cardChange; if ( keyboardCardIndex < 0 ) keyboardCardIndex = pile->count() - 1; else if ( keyboardCardIndex >= pile->count() ) keyboardCardIndex = 0; } } updateKeyboardFocus(); } void KCardScenePrivate::updateKeyboardFocus() { setItemHighlight( toGraphicsItem( keyboardFocusItem ), false ); if ( !keyboardMode ) { keyboardFocusItem.clear(); keyboardPileIndex = 0; keyboardCardIndex = 0; return; } KCardPile * pile = piles.at( keyboardPileIndex ); KCardPile::KeyboardFocusHint hint = cardsBeingDragged.isEmpty() ? pile->keyboardSelectHint() : pile->keyboardDropHint(); if ( !cardsBeingDragged.isEmpty() && cardsBeingDragged.first()->pile() == pile ) { int index = pile->indexOf( cardsBeingDragged.first() ); if ( index == 0 ) keyboardFocusItem = pile; else keyboardFocusItem = pile->at( index - 1 ); } else if ( pile->isEmpty() ) { keyboardFocusItem = pile; } else if ( keyboardCardIndex >= pile->count() || hint == KCardPile::ForceFocusTop ) { keyboardFocusItem = pile->topCard(); } else { keyboardFocusItem = pile->at( keyboardCardIndex ); } QGraphicsItem * focusItem = toGraphicsItem( keyboardFocusItem ); Q_ASSERT( focusItem ); setItemHighlight( focusItem, true ); QPointF delta = focusItem->pos() - startOfDrag; startOfDrag = focusItem->pos(); foreach ( KCard * c, cardsBeingDragged ) c->setPos( c->pos() + delta ); } KCardScene::KCardScene( QObject * parent ) : QGraphicsScene( parent ), d( new KCardScenePrivate( this ) ) { d->deck = nullptr; d->alignment = AlignHCenter | AlignHSpread; d->layoutMargin = 0.15; d->layoutSpacing = 0.15; d->keyboardMode = false; d->keyboardPileIndex = 0; d->keyboardCardIndex = 0; d->keyboardFocusItem.clear(); d->sizeHasBeenSet = false; } KCardScene::~KCardScene() { foreach ( KCardPile * p, d->piles ) { removePile( p ); delete p; } d->piles.clear(); } void KCardScene::setDeck( KAbstractCardDeck * deck ) { if ( d->deck ) disconnect( d->deck, &KAbstractCardDeck::cardAnimationDone, this, &KCardScene::cardAnimationDone ); d->deck = deck; if ( d->deck ) connect( d->deck, &KAbstractCardDeck::cardAnimationDone, this, &KCardScene::cardAnimationDone ); } KAbstractCardDeck * KCardScene::deck() const { return d->deck; } bool KCardScene::isCardAnimationRunning() const { return d->deck && d->deck->hasAnimatedCards(); } QList KCardScene::cardsBeingDragged() const { return d->cardsBeingDragged; } void KCardScene::addPile( KCardPile * pile ) { KCardScene * origScene = dynamic_cast( pile->scene() ); if ( origScene ) origScene->removePile( pile ); addItem( pile ); foreach ( KCard * c, pile->cards() ) addItem( c ); d->piles.append( pile ); } void KCardScene::removePile( KCardPile * pile ) { foreach ( KCard * c, pile->cards() ) removeItem( c ); removeItem( pile ); d->piles.removeAll( pile ); } QList KCardScene::piles() const { return d->piles; } void KCardScene::setSceneAlignment( KCardScene::SceneAlignment alignment ) { if ( alignment != d->alignment ) { d->alignment = alignment; relayoutScene(); } } KCardScene::SceneAlignment KCardScene::sceneAlignment() const { return d->alignment; } void KCardScene::setLayoutMargin( qreal margin ) { if ( margin != d->layoutMargin ) { d->layoutMargin = margin; relayoutScene(); } } qreal KCardScene::layoutMargin() const { return d->layoutMargin; } void KCardScene::setLayoutSpacing( qreal spacing ) { if ( spacing != d->layoutSpacing ) { d->layoutSpacing = spacing; relayoutScene(); } } qreal KCardScene::layoutSpacing() const { return d->layoutSpacing; } QRectF KCardScene::contentArea() const { return QRectF( QPoint( 0, 0 ), d->contentSize ); } void KCardScene::resizeScene( const QSize & size ) { d->sizeHasBeenSet = true; setSceneRect( QRectF( sceneRect().topLeft(), size ) ); relayoutScene(); } void KCardScene::relayoutScene() { if ( !d->sizeHasBeenSet || !d->deck ) return; qreal usedWidth = 1; qreal usedHeight = 1; qreal extraWidth = 0; qreal extraHeight = 0; foreach ( const KCardPile * p, piles() ) { if ( p->layoutPos().x() >= 0 ) usedWidth = qMax( usedWidth, p->layoutPos().x() + 1 + p->rightPadding() ); else extraWidth = qMax( extraWidth, p->leftPadding() + 1 + p->rightPadding() ); if ( p->layoutPos().y() >= 0 ) usedHeight = qMax( usedHeight, p->layoutPos().y() + 1 + p->bottomPadding() ); else extraHeight = qMax( extraHeight, p->topPadding() + 1 + p->bottomPadding() ); } if ( extraWidth ) { qreal hSpacing = d->layoutSpacing * (1 + d->deck->cardHeight() / d->deck->cardWidth()) / 2; usedWidth += hSpacing + extraWidth; } if ( extraHeight ) { qreal vSpacing = d->layoutSpacing * (1 + d->deck->cardWidth() / d->deck->cardHeight()) / 2; usedHeight += vSpacing + extraHeight; } // Add the border to the size of the contents QSizeF sizeToFit( usedWidth + 2 * d->layoutMargin, usedHeight+ 2 * d->layoutMargin ); qreal scaleX = width() / ( d->deck->cardWidth() * sizeToFit.width() ); qreal scaleY = height() / ( d->deck->cardHeight() * sizeToFit.height() ); qreal n_scaleFactor = qMin( scaleX, scaleY ); d->deck->setCardWidth( n_scaleFactor * d->deck->cardWidth() ); int usedPixelWidth = usedWidth * d->deck->cardWidth(); int usedPixelHeight = usedHeight * d->deck->cardHeight(); int pixelHMargin = d->layoutMargin * d->deck->cardWidth(); int pixelVMargin = d->layoutMargin * d->deck->cardHeight(); int contentWidth; int xOffset; if ( d->alignment & AlignLeft ) { contentWidth = usedPixelWidth; xOffset = pixelHMargin; } else if ( d->alignment & AlignRight ) { contentWidth = usedPixelWidth; xOffset = width() - contentWidth - pixelHMargin; } else if ( d->alignment & AlignHCenter ) { contentWidth = usedPixelWidth; xOffset = ( width() - contentWidth ) / 2; } else { contentWidth = width() - 2 * d->layoutMargin * d->deck->cardWidth(); xOffset = pixelHMargin; } int contentHeight; int yOffset; if ( d->alignment & AlignTop ) { contentHeight = usedPixelHeight; yOffset = pixelVMargin; } else if ( d->alignment & AlignBottom ) { contentHeight = usedPixelHeight; yOffset = height() - contentHeight - pixelVMargin; } else if ( d->alignment & AlignVCenter ) { contentHeight = usedPixelHeight; yOffset = ( height() - contentHeight ) / 2; } else { contentHeight = height() - 2 * d->layoutMargin * d->deck->cardHeight(); yOffset = pixelVMargin; } d->contentSize = QSizeF( contentWidth, contentHeight ); setSceneRect( -xOffset, -yOffset, width(), height() ); recalculatePileLayouts(); foreach ( KCardPile * p, piles() ) updatePileLayout( p, 0 ); } void KCardScene::recalculatePileLayouts() { if ( !d->sizeHasBeenSet || !d->deck ) return; QSize cardSize = d->deck->cardSize(); const qreal contentWidth = d->contentSize.width() / cardSize.width(); const qreal contentHeight = d->contentSize.height() / cardSize.height(); const qreal spacing = d->layoutSpacing; QList visiblePiles; QHash reserve; QHash & areas = d->pileAreas; areas.clear(); foreach ( KCardPile * p, piles() ) { QPointF layoutPos = p->layoutPos(); if ( layoutPos.x() < 0 ) layoutPos.rx() += contentWidth - 1; if ( layoutPos.y() < 0 ) layoutPos.ry() += contentHeight - 1; p->setPos( layoutPos.x() * cardSize.width(), layoutPos.y() * cardSize.height() ); p->setGraphicSize( cardSize ); if ( p->isVisible() ) { visiblePiles << p; reserve[p] = QRectF( layoutPos, QSize( 1, 1 ) ).adjusted( -p->leftPadding(), -p->topPadding(), p->rightPadding(), p->bottomPadding() ); areas[p] = reserve[p]; } } // Grow piles down foreach ( KCardPile * p1, visiblePiles ) { if ( p1->heightPolicy() == KCardPile::GrowDown ) { areas[p1].setBottom( contentHeight ); foreach ( KCardPile * p2, visiblePiles ) { if ( p2 != p1 && areas[p1].intersects( areas[p2] ) ) { if ( p2->heightPolicy() == KCardPile::GrowUp ) areas[p1].setBottom( (reserve[p1].bottom() + reserve[p2].top() - spacing) / 2 ); else areas[p1].setBottom( reserve[p2].top() - spacing ); } } } } // Grow piles up foreach ( KCardPile * p1, visiblePiles ) { if ( p1->heightPolicy() == KCardPile::GrowUp ) { areas[p1].setTop( 0 ); foreach ( KCardPile * p2, visiblePiles ) { if ( p2 != p1 && areas[p1].intersects( areas[p2] ) ) { if ( p2->heightPolicy() == KCardPile::GrowDown ) areas[p1].setTop( (reserve[p1].top() + reserve[p2].bottom() + spacing) / 2 ); else areas[p1].setTop( reserve[p2].bottom() + spacing ); } } } } // Grow piles right foreach ( KCardPile * p1, visiblePiles ) { if ( p1->widthPolicy() == KCardPile::GrowRight ) { areas[p1].setRight( contentWidth ); foreach ( KCardPile * p2, visiblePiles ) { if ( p2 != p1 && areas[p1].intersects( areas[p2] ) ) { if ( p2->widthPolicy() == KCardPile::GrowLeft ) areas[p1].setRight( (reserve[p1].right() + reserve[p2].left() - spacing) / 2 ); else areas[p1].setRight( reserve[p2].left() - spacing ); } } } } // Grow piles left foreach ( KCardPile * p1, visiblePiles ) { if ( p1->widthPolicy() == KCardPile::GrowLeft ) { areas[p1].setLeft( 0 ); foreach ( KCardPile * p2, visiblePiles ) { if ( p2 != p1 && areas[p1].intersects( areas[p2] ) ) { if ( p2->widthPolicy() == KCardPile::GrowRight ) areas[p1].setLeft( (reserve[p1].left() + reserve[p2].right() + spacing) / 2 ); else areas[p1].setLeft( reserve[p2].right() + spacing ); } } } } } void KCardScene::setHighlightedItems( QList items ) { QSet s = QSet::fromList( items ); foreach ( QGraphicsItem * i, d->highlightedItems.subtract( s ) ) setItemHighlight( i, false ); foreach ( QGraphicsItem * i, s ) setItemHighlight( i, true ); d->highlightedItems = s; } void KCardScene::clearHighlightedItems() { foreach ( QGraphicsItem * i, d->highlightedItems ) setItemHighlight( i, false ); d->highlightedItems.clear(); } QList KCardScene::highlightedItems() const { return d->highlightedItems.toList(); } void KCardScene::moveCardsToPile( const QList & cards, KCardPile * pile, int duration ) { if ( cards.isEmpty() ) return; KCardPile * source = cards.first()->pile(); d->sendCardsToPile( pile, cards, duration, false, false ); if ( source ) d->sendCardsToPile( source, QList(), duration, false, false ); cardsMoved( cards, source, pile ); } void KCardScene::moveCardToPile( KCard * card, KCardPile * pile, int duration ) { moveCardsToPile( QList() << card, pile, duration ); } void KCardScene::moveCardsToPileAtSpeed( const QList & cards, KCardPile * pile, qreal velocity ) { if ( cards.isEmpty() ) return; KCardPile * source = cards.first()->pile(); d->sendCardsToPile( pile, cards, velocity, true, false ); if ( source ) d->sendCardsToPile( source, QList(), cardMoveDuration, false, false ); cardsMoved( cards, source, pile ); } void KCardScene::moveCardToPileAtSpeed( KCard * card, KCardPile * pile, qreal velocity ) { moveCardsToPileAtSpeed( QList() << card, pile, velocity ); } void KCardScene::flipCardsToPile( const QList & cards, KCardPile * pile, int duration ) { if ( cards.isEmpty() ) return; KCardPile * source = cards.first()->pile(); d->sendCardsToPile( pile, cards, duration, false, true ); if ( source ) d->sendCardsToPile( source, QList(), duration, false, false ); cardsMoved( cards, source, pile ); } void KCardScene::flipCardToPile( KCard * card, KCardPile * pile, int duration ) { flipCardsToPile( QList() << card, pile, duration ); } void KCardScene::flipCardsToPileAtSpeed( const QList & cards, KCardPile * pile, qreal velocity ) { if ( cards.isEmpty() ) return; KCardPile * source = cards.first()->pile(); d->sendCardsToPile( pile, cards, velocity, true, true ); if ( source ) d->sendCardsToPile( source, QList(), cardMoveDuration, false, false ); cardsMoved( cards, source, pile ); } void KCardScene::flipCardToPileAtSpeed( KCard * card, KCardPile * pile, qreal velocity ) { flipCardsToPileAtSpeed( QList() << card, pile, velocity ); } void KCardScene::keyboardFocusLeft() { d->changeFocus( -1, 0 ); } void KCardScene::keyboardFocusRight() { d->changeFocus( +1, 0 ); } void KCardScene::keyboardFocusUp() { d->changeFocus( 0, -1 ); } void KCardScene::keyboardFocusDown() { d->changeFocus( 0, +1 ); } void KCardScene::keyboardFocusCancel() { setKeyboardModeActive( false ); } void KCardScene::keyboardFocusSelect() { if ( !isKeyboardModeActive() ) { setKeyboardModeActive( true ); return; } if ( d->cardsBeingDragged.isEmpty() ) { KCardPile * pile = d->piles.at( d->keyboardPileIndex ); if ( pile->isEmpty() ) return; if ( d->keyboardCardIndex >= pile->count() ) d->keyboardCardIndex = pile->count() - 1; KCard * card = pile->at( d->keyboardCardIndex ); d->cardsBeingDragged = card->pile()->topCardsDownTo( card ); if ( allowedToRemove( card->pile(), d->cardsBeingDragged.first() ) ) { d->startOfDrag = d->keyboardCardIndex > 0 ? pile->at( d->keyboardCardIndex - 1 )->pos() : pile->pos(); QPointF offset = d->startOfDrag - card->pos() + QPointF( d->deck->cardWidth(), d->deck->cardHeight() ) / 10.0; foreach ( KCard * c, d->cardsBeingDragged ) { c->stopAnimation(); c->raise(); c->setPos( c->pos() + offset ); } d->dragStarted = true; d->updateKeyboardFocus(); } else { d->cardsBeingDragged.clear(); } } else { KCardPile * destination = d->bestDestinationPileUnderCards(); if ( destination ) cardsDroppedOnPile( d->cardsBeingDragged, destination ); else updatePileLayout( d->cardsBeingDragged.first()->pile(), cardMoveDuration ); QGraphicsItem * toFocus = d->cardsBeingDragged.first(); d->cardsBeingDragged.clear(); d->dragStarted = false; setKeyboardFocus( toFocus ); } } void KCardScene::setKeyboardFocus( QGraphicsItem * item ) { KCard * c = qgraphicsitem_cast( item ); if ( c && c->pile() ) { KCardPile * p = c->pile(); d->keyboardPileIndex = d->piles.indexOf( p ); d->keyboardCardIndex = p->indexOf( c ); } else { KCardPile * p = qgraphicsitem_cast( item ); if ( p ) { d->keyboardPileIndex = d->piles.indexOf( p ); d->keyboardCardIndex = 0; } } d->updateKeyboardFocus(); } void KCardScene::setKeyboardModeActive( bool keyboardMode ) { if ( !d->keyboardMode && keyboardMode ) { clearHighlightedItems(); d->keyboardMode = true; d->updateKeyboardFocus(); } else if ( d->keyboardMode && !keyboardMode ) { if ( !d->cardsBeingDragged.isEmpty() ) updatePileLayout( d->cardsBeingDragged.first()->pile(), cardMoveDuration ); d->cardsBeingDragged.clear(); d->keyboardMode = false; d->updateKeyboardFocus(); } } bool KCardScene::isKeyboardModeActive() const { return d->keyboardMode; } void KCardScene::updatePileLayout( KCardPile * pile, int duration ) { d->sendCardsToPile( pile, QList(), duration, false, false ); } bool KCardScene::allowedToAdd( const KCardPile * pile, const QList & cards ) const { Q_UNUSED( pile ) Q_UNUSED( cards ) return true; } bool KCardScene::allowedToRemove( const KCardPile * pile, const KCard * card ) const { Q_UNUSED( pile ) Q_UNUSED( card ) return true; } void KCardScene::cardsDroppedOnPile( const QList & cards, KCardPile * pile ) { moveCardsToPile( cards, pile, cardMoveDuration ); } void KCardScene::cardsMoved( const QList & cards, KCardPile * oldPile, KCardPile * newPile ) { Q_UNUSED( cards ); Q_UNUSED( oldPile ); Q_UNUSED( newPile ); } void KCardScene::mousePressEvent( QGraphicsSceneMouseEvent * e ) { if ( isKeyboardModeActive() ) setKeyboardModeActive( false ); const QList itemsAtPoint = items( e->scenePos() ); QGraphicsItem * item = itemsAtPoint.isEmpty() ? 0 : itemsAtPoint.first(); KCard * card = qgraphicsitem_cast( item ); KCardPile * pile = qgraphicsitem_cast( item ); if ( e->button() == Qt::LeftButton && ( card || pile ) ) { e->accept(); if ( card && !isCardAnimationRunning() && !d->cardsBeingDragged.contains( card ) ) { QList cards = card->pile()->topCardsDownTo( card ); if ( allowedToRemove( card->pile(), cards.first() ) ) { d->cardsBeingDragged = cards; foreach ( KCard * c, d->cardsBeingDragged ) { c->stopAnimation(); c->raise(); } } d->dragStarted = false; d->startOfDrag = e->scenePos(); } } else { QGraphicsScene::mousePressEvent( e ); } } void KCardScene::mouseMoveEvent( QGraphicsSceneMouseEvent * e ) { if ( !d->cardsBeingDragged.isEmpty() ) { e->accept(); if ( !d->dragStarted ) { bool overCard = d->cardsBeingDragged.first()->sceneBoundingRect().contains( e->scenePos() ); QPointF delta = e->scenePos() - d->startOfDrag; qreal distanceSquared = delta.x() * delta.x() + delta.y() * delta.y(); // Ignore the move event until we've moved at least 4 pixels or the // cursor leaves the card. if ( distanceSquared > 16.0 || !overCard ) { d->dragStarted = true; // If the cursor hasn't left the card, then continue the drag from // the current position, which makes it look smoother. if ( overCard ) d->startOfDrag = e->scenePos(); } } if ( d->dragStarted ) { foreach ( KCard * card, d->cardsBeingDragged ) card->setPos( card->pos() + e->scenePos() - d->startOfDrag ); d->startOfDrag = e->scenePos(); QList toHighlight; KCardPile * dropPile = d->bestDestinationPileUnderCards(); if ( dropPile ) { if ( dropPile->isEmpty() ) toHighlight << dropPile; else toHighlight << dropPile->topCard(); } setHighlightedItems( toHighlight ); } } else { QGraphicsScene::mouseMoveEvent( e ); } } void KCardScene::mouseReleaseEvent( QGraphicsSceneMouseEvent * e ) { const QList itemsAtPoint = items( e->scenePos() ); QGraphicsItem * topItem = itemsAtPoint.isEmpty() ? 0 : itemsAtPoint.first(); KCard * card = qgraphicsitem_cast( topItem ); KCardPile * pile = qgraphicsitem_cast( topItem ); if ( e->button() == Qt::LeftButton && !d->dragStarted && !d->cardsBeingDragged.isEmpty() ) { updatePileLayout( d->cardsBeingDragged.first()->pile(), cardMoveDuration ); d->cardsBeingDragged.clear(); } if ( e->button() == Qt::LeftButton && !d->cardsBeingDragged.isEmpty() ) { e->accept(); KCardPile * destination = d->bestDestinationPileUnderCards(); if ( destination ) cardsDroppedOnPile( d->cardsBeingDragged, destination ); else updatePileLayout( d->cardsBeingDragged.first()->pile(), cardMoveDuration ); d->cardsBeingDragged.clear(); d->dragStarted = false; clearHighlightedItems(); } else if ( card && !isCardAnimationRunning() ) { e->accept(); if ( e->button() == Qt::LeftButton ) { emit cardClicked( card ); if ( card->pile() ) emit card->pile()->clicked( card ); } else if ( e->button() == Qt::RightButton ) { emit cardRightClicked( card ); if ( card->pile() ) emit card->pile()->rightClicked( card ); } } else if ( pile && !isCardAnimationRunning() ) { e->accept(); if ( e->button() == Qt::LeftButton ) { emit pileClicked( pile ); emit pile->clicked( nullptr ); } else if ( e->button() == Qt::RightButton ) { emit pileRightClicked( pile ); emit pile->rightClicked( nullptr ); } } else { QGraphicsScene::mouseReleaseEvent( e ); } } void KCardScene::mouseDoubleClickEvent( QGraphicsSceneMouseEvent * e ) { const QList itemsAtPoint = items( e->scenePos() ); QGraphicsItem * topItem = itemsAtPoint.isEmpty() ? 0 : itemsAtPoint.first(); KCard * card = qgraphicsitem_cast( topItem ); KCardPile * pile = qgraphicsitem_cast( topItem ); if ( !d->cardsBeingDragged.isEmpty() ) { updatePileLayout( d->cardsBeingDragged.first()->pile(), cardMoveDuration ); d->cardsBeingDragged.clear(); } if ( card && e->button() == Qt::LeftButton && !isCardAnimationRunning() ) { e->accept(); emit cardDoubleClicked( card ); if ( card->pile() ) emit card->pile()->doubleClicked( card ); } else if ( pile && e->button() == Qt::LeftButton && !isCardAnimationRunning() ) { e->accept(); emit pileDoubleClicked( pile ); emit pile->doubleClicked( nullptr ); } else { QGraphicsScene::mouseDoubleClickEvent( e ); } } void KCardScene::wheelEvent( QGraphicsSceneWheelEvent * e ) { if ( d->deck && e->modifiers() & Qt::ControlModifier ) { e->accept(); qreal scaleFactor = pow( 2, e->delta() / qreal(10 * 120) ); int newWidth = d->deck->cardWidth() * scaleFactor; d->deck->setCardWidth( newWidth ); recalculatePileLayouts(); foreach ( KCardPile * p, piles() ) updatePileLayout( p, 0 ); } else { QGraphicsScene::wheelEvent( e ); } } void KCardScene::drawForeground ( QPainter * painter, const QRectF & rect ) { Q_UNUSED( painter ) Q_UNUSED( rect ) - -#if DEBUG_LAYOUT - if ( !d->sizeHasBeenSet || !d->deck ) - return; - - painter->setPen( Qt::yellow ); - painter->drawRect( 0, 0, d->contentSize.width(), d->contentSize.height() ); - - foreach ( const KCardPile * p, piles() ) - { - if ( !p->isVisible() ) - continue; - - QRectF availableRect = multRectSize( d->pileAreas.value( p, QRectF() ), d->deck->cardSize() ); - - QRectF reservedRect( -p->leftPadding(), -p->topPadding(), 1 + p->rightPadding(), 1 + p->bottomPadding() ); - reservedRect = multRectSize( reservedRect, d->deck->cardSize() ); - reservedRect.translate( p->pos() ); - - painter->setPen( Qt::cyan ); - painter->drawRect( availableRect ); - painter->setPen( QPen( Qt::red, 1, Qt::DotLine, Qt::FlatCap ) ); - painter->drawRect( reservedRect ); - } -#endif } diff --git a/patsolve/fortyeightsolver.cpp b/patsolve/fortyeightsolver.cpp index ca3f43b..37e4e27 100644 --- a/patsolve/fortyeightsolver.cpp +++ b/patsolve/fortyeightsolver.cpp @@ -1,686 +1,688 @@ /* * 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 "fortyeightsolver.h" #include "../fortyeight.h" #include -#define NUM_PILE 8 -#define NUM_DECK 9 +namespace { +constexpr auto NUM_PILE = 8; +constexpr auto NUM_DECK = 9; +} #define PRINT 0 class FortyeightSolverState { public: bool empty[8]; bool linedup[8]; int highestbreak[8]; int firstempty; int freestores; int fromscore[8]; }; void FortyeightSolver::checkState(FortyeightSolverState &d) { d.firstempty = -1; d.freestores = 0; for ( int w = 0; w < 8; w++ ) { d.empty[w] = (Wlen[w] == 0); d.linedup[w] = true; if ( !Wlen[w] ) { d.freestores++; if (d.firstempty < 0) d.firstempty = w; } d.highestbreak[w] = 0; for (int i = 1; i < Wlen[w]; i++) { card_t card1 = W[w][Wlen[w]-i-1]; card_t card2 = W[w][Wlen[w]-i]; if ( SUIT( card1 ) != SUIT( card2 ) || RANK( card1 ) != RANK( card2 ) + 1 ) { d.highestbreak[w] = i - 1; d.linedup[w] = false; break; } } d.fromscore[w] = 0; for (int i = d.highestbreak[w] + 1; i < Wlen[w]; i++) { card_t card = W[w][Wlen[w]-i-1]; if ( RANK(card) < 5 || RANK(card) == PS_ACE) { d.fromscore[w] += (13 - RANK(card)) * 20; } } if (Wlen[w]) d.fromscore[w] /= Wlen[w]; } } void FortyeightSolver::make_move(MOVE *m) { #if PRINT if ( m->totype == O_Type ) fprintf( stderr, "\nmake move %d from %d to %d out (at %d)\n\n", m->card_index, m->from, m->to, m->turn_index ); else fprintf( stderr, "\nmake move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index ); print_layout(); #endif int from = m->from; int to = m->to; // move to pile if ( from == NUM_DECK && to == NUM_PILE ) { card_t card = *Wp[NUM_DECK]; Wp[NUM_DECK]--; Wlen[NUM_DECK]--; card = ( SUIT( card ) << 4 ) + RANK( card ); Wp[NUM_PILE]++; *Wp[NUM_PILE] = card; Wlen[NUM_PILE]++; hashpile( NUM_DECK ); hashpile( NUM_PILE ); #if PRINT print_layout(); #endif return; } // move to deck if ( from == NUM_PILE && to == NUM_DECK ) { while ( Wlen[NUM_PILE] > 1 ) { Wlen[NUM_DECK]++; Wp[NUM_DECK]++; card_t card = *Wp[NUM_PILE] + ( 1 << 7 ); *Wp[NUM_DECK] = card; Wlen[NUM_PILE]--; Wp[NUM_PILE]--; } hashpile( NUM_DECK ); hashpile( NUM_PILE ); lastdeal = true; #if PRINT print_layout(); #endif return; } for ( int i = m->card_index + 1; i > 0; --i ) { card_t card = W[from][Wlen[from]-i]; Wp[from]--; if ( m->totype == O_Type ) { O[to]++; } else { Wp[to]++; *Wp[to] = card; Wlen[to]++; } } Wlen[from] -= m->card_index+1; hashpile(from); if ( m->totype != O_Type ) hashpile(to); #if PRINT print_layout(); #endif } void FortyeightSolver::undo_move(MOVE *m) { #if PRINT if ( m->totype == O_Type ) fprintf( stderr, "\nundo move %d from %d to %d out (at %d)\n\n", m->card_index, m->from, m->to, m->turn_index ); else fprintf( stderr, "\nundo move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index ); print_layout(); #endif int from = m->from; int to = m->to; // move to pile if ( from == NUM_DECK && to == NUM_PILE ) { card_t card = *Wp[NUM_PILE]; Wp[NUM_PILE]--; Wlen[NUM_PILE]--; card = ( SUIT( card ) << 4 ) + RANK( card ) + ( 1 << 7 ); Wp[NUM_DECK]++; *Wp[NUM_DECK] = card; Wlen[NUM_DECK]++; hashpile( NUM_DECK ); hashpile( NUM_PILE ); #if PRINT print_layout(); #endif return; } // move to deck if ( from == NUM_PILE && to == NUM_DECK ) { while ( Wlen[NUM_DECK] ) { Wlen[NUM_PILE]++; Wp[NUM_PILE]++; *Wp[NUM_PILE] = ( SUIT( *Wp[NUM_DECK] ) << 4 ) + RANK( *Wp[NUM_DECK] ); Wlen[NUM_DECK]--; Wp[NUM_DECK]--; } hashpile( NUM_DECK ); hashpile( NUM_PILE ); lastdeal = false; #if PRINT print_layout(); #endif return; } for ( int i = m->card_index + 1; i > 0; --i ) { card_t card; if ( m->totype != O_Type ) { card = W[to][Wlen[to]-i]; Wp[to]--; } else { card = Osuit[to] + O[to]; O[to]--; } Wp[from]++; *Wp[from] = card; Wlen[from]++; } hashpile(from); if ( m->totype != O_Type ) { Wlen[to] -= m->card_index+1; hashpile(to); } #if PRINT print_layout(); #endif } bool FortyeightSolver::checkMoveOut( int from, MOVE *mp, int *dropped) { if ( !Wlen[from] ) return false; card_t card = *Wp[from]; int suit = SUIT( card ); int target = suit * 2; // aces need to fit on empty if ( RANK(card) == PS_ACE ) { if (O[target++] != NONE) target--; else if ( O[target] != NONE) return false; } else { if ( RANK(card) == O[target++] + 1 ) target--; else if ( RANK(card) != O[target] + 1 ) return false; } dropped[target]++; mp->card_index = 0; mp->from = from; mp->to = target; mp->totype = O_Type; mp->pri = 127; mp->turn_index = -1; return true; } /* Get the possible moves from a position, and store them in Possible[]. */ bool FortyeightSolver::checkMove( int from, int to, MOVE *mp ) { if ( !Wlen[from] ) return false; card_t card = *Wp[from]; Q_ASSERT( to < 8 ); if ( Wlen[to] ) { card_t top = *Wp[to]; if ( SUIT( top ) != SUIT( card ) || RANK( top ) != RANK( card ) + 1 ) return false; } mp->card_index = 0; mp->from = from; mp->to = to; mp->totype = W_Type; mp->pri = 70; mp->turn_index = -1; return true; } int FortyeightSolver::get_possible_moves(int *a, int *numout) { int n = 0; MOVE *mp = Possible; *a = false; FortyeightSolverState d; checkState(d); //print_layout(); // if a specific target got two possible drops, we don't make it auto drop int dropped[8] = { 0, 0, 0, 0, 0, 0, 0, 0}; // off for ( int w = 0; w < 8; w++ ) { if ( checkMoveOut( w, mp, dropped ) ) { n++; mp++; break; } } if ( checkMoveOut( NUM_PILE, mp, dropped ) ) { n++; mp++; } for ( int i = 0; i < 8; i++ ) { if ( dropped[i] > 1 ) { for ( int j = 0; j < n; j++ ) if ( Possible[j].to == i ) Possible[j].pri = qBound( 121, 110 + Wlen[Possible[j].from], 126 ); } if ( dropped[i] == 1 ) { // good automove if (n != 1) { for ( int j = 0; j < n; j++ ) { if ( Possible[j].to == i ) { Possible[0] = Possible[j]; Possible[0].pri = 127; break; } } } *a = true; *numout = 1; return 1; } } //fprintf(stderr, "\n"); *numout = n; for (int w = 0; w < 8; w++) { for ( int j = 0; j < 8; j++ ) { if ( j == w ) continue; if ( checkMove( w, j, mp ) ) { if ( !Wlen[j] ) { if (d.linedup[w]) continue; // ignore it if ( j != d.firstempty ) // one is enough continue; if ( d.highestbreak[w] >= 1) continue; mp->pri = qMin( 115, 11 + d.fromscore[w]); } else { if (d.linedup[w] && Wlen[w] > 1) continue; if (d.linedup[j] && Wlen[j] > 1) mp->pri = 110 + Wlen[j]; else { if (d.fromscore[w] < d.fromscore[j]) mp->pri = 2; else mp->pri = qMin(115, 20 + d.highestbreak[w] + RANK(*Wp[w]) + d.fromscore[w]); } } n++; mp++; } } if ( checkMove( NUM_PILE, w, mp ) && (!d.empty[w] || w == d.firstempty)) { if (d.empty[w]) mp->pri = 15; else { if (d.linedup[w]) mp->pri = 100; else mp->pri = qMax(50 - d.fromscore[w], 0); } n++; mp++; } if ( Wlen[w] > 1 && d.freestores ) { if ( SUIT( *Wp[w] ) == SUIT( W[w][Wlen[w]-2] ) ) { //print_layout(); for ( int to = 0; to < 8; to++ ) { if ( to == w ) continue; if ( Wlen[to] && SUIT( *Wp[to] ) != SUIT( *Wp[w] ) ) continue; if ( d.empty[to] && to != d.firstempty ) continue; int moves = 1 << d.freestores; if ( !Wlen[to] ) moves = 1 << ( d.freestores - 1 ); if ( moves >= Wlen[w] ) moves = Wlen[w]; bool switched = false; for ( int i = 2; i < moves; ++i ) { /* printcard( W[w][Wlen[w]-i-1], stderr ); printcard( *Wp[w], stderr ); fprintf( stderr, " switch? %d\n", i ); */ if ( SUIT( W[w][Wlen[w]-i-1] ) != SUIT( *Wp[w] ) || RANK ( W[w][Wlen[w]-i-1] ) != RANK ( W[w][Wlen[w]-i] ) + 1) { switched = true; moves = i; break; } } if ( !Wlen[to] ) { if ( moves < 2 || moves == Wlen[w] || !switched) continue; //print_layout(); mp->card_index = moves-1; mp->from = w; mp->to = to; mp->totype = W_Type; mp->pri = 60; mp->turn_index = -1; n++; mp++; continue; } if (d.linedup[w] && moves < Wlen[w]) continue; card_t top = *Wp[to]; for ( int i = 2; i <= moves && i <= Wlen[w]; i++ ) { card_t cur = W[w][Wlen[w]-i]; /* printcard( top, stderr ); printcard( cur, stderr ); fprintf( stderr, " %d\n", i ); */ Q_ASSERT( SUIT( top ) == SUIT( cur ) ); if ( RANK( top ) == RANK( cur ) + 1 ) { mp->card_index = i-1; mp->from = w; mp->to = to; mp->totype = W_Type; mp->pri = 80; mp->turn_index = -1; n++; mp++; } } } } } } /* check for deck->pile */ if ( Wlen[NUM_DECK] ) { mp->card_index = 1; mp->from = NUM_DECK; mp->to = NUM_PILE; mp->totype = W_Type; mp->pri = 19; mp->turn_index = 0; n++; mp++; } else if ( !lastdeal ) { mp->card_index = 1; mp->from = NUM_PILE; mp->to = NUM_DECK; mp->totype = W_Type; mp->pri = 19; mp->turn_index = 0; n++; mp++; } return n; } void FortyeightSolver::unpack_cluster( unsigned int k ) { O[0] = k & 0xF; k >>= 4; O[1] = k & 0xF; k >>= 4; O[2] = k & 0xF; k >>= 4; O[3] = k & 0xF; k >>= 4; O[4] = k & 0xF; k >>= 4; O[5] = k & 0xF; k >>= 4; O[6] = k & 0xF; k >>= 4; O[7] = k & 0xF; } bool FortyeightSolver::isWon() { for ( int i = 0; i < 8; ++i ) if ( O[i] != PS_KING ) return false; //qDebug() << "isWon" << getOuts(); return true; } int FortyeightSolver::getOuts() { int total = 0; for ( int i = 0; i < 8; ++i ) total += O[i]; return total; } FortyeightSolver::FortyeightSolver(const Fortyeight *dealer) : Solver() { setNumberPiles( 10 ); deal = dealer; } void FortyeightSolver::translate_layout() { /* Read the workspace. */ int total = 0; for ( int w = 0; w < 8; ++w ) { int i = translate_pile(deal->stack[w], W[w], 52); Wp[w] = &W[w][i - 1]; Wlen[w] = i; total += i; } /* Output piles, if any. */ for (int i = 0; i < 8; ++i) { O[i] = NONE; } Osuit[0] = PS_DIAMOND; Osuit[1] = PS_DIAMOND; Osuit[2] = PS_CLUB; Osuit[3] = PS_CLUB; Osuit[4] = PS_HEART; Osuit[5] = PS_HEART; Osuit[6] = PS_SPADE; Osuit[7] = PS_SPADE; for (int i = 0; i < 8; ++i) { KCard *c = deal->target[i]->topCard(); if (c) { int suit = translateSuit( c->suit() ) >> 4; if (O[suit * 2] == NONE) O[suit * 2] = c->rank(); else { if (O[suit * 2] < c->rank()) { O[suit * 2 + 1] = O[suit * 2]; O[suit * 2] = c->rank(); } else { O[suit * 2 + 1] = c->rank(); } } total += c->rank(); } } int i = translate_pile( deal->pile, W[NUM_PILE], 80 ); Wp[NUM_PILE] = &W[NUM_PILE][i-1]; Wlen[NUM_PILE] = i; total += i; i = translate_pile( deal->talon, W[NUM_DECK], 80 ); Wp[NUM_DECK] = &W[NUM_DECK][i-1]; Wlen[NUM_DECK] = i; total += i; lastdeal = deal->lastdeal; Q_ASSERT( total == 104 ); } unsigned int FortyeightSolver::getClusterNumber() { unsigned int i = O[0] + (O[1] << 4); unsigned int k = i; i = O[2] + (O[3] << 4); k |= i << 8; i = O[4] + (O[5] << 4); k |= i << 16; i = O[6] + (O[7] << 4); k |= i << 24; return k; } MoveHint FortyeightSolver::translateMove( const MOVE &m ) { if ( m.from == NUM_DECK || m.to == NUM_DECK ) return MoveHint(); PatPile *frompile = nullptr; if ( m.from < 8 ) frompile = deal->stack[m.from]; else frompile = deal->pile; Q_ASSERT( frompile ); KCard *card = frompile->at( frompile->count() - m.card_index - 1); Q_ASSERT( card ); Q_ASSERT( m.to < NUM_PILE ); if ( m.totype == W_Type) return MoveHint( card, deal->stack[m.to], m.pri ); for (int i = 0; i < 8; i++) { KCard *top = deal->target[i]->topCard(); if (top) { if (top->suit() == card->suit() && top->rank() + 1 == card->rank()) return MoveHint( card, deal->target[i], m.pri ); } else { if (card->rank() == PS_ACE) return MoveHint( card, deal->target[i], m.pri ); } } Q_ASSERT( false); return MoveHint(); } void FortyeightSolver::print_layout() { FortyeightSolverState d; checkState(d); fprintf(stderr, "print-layout-begin\n"); for (int w = 0; w < 10; w++) { if ( w == NUM_DECK ) fprintf( stderr, "Deck(9): " ); else if ( w == 8 ) fprintf( stderr, "Pile(8): " ); else if ( w < 8 ) fprintf( stderr, "Play%d: ", w ); for (int i = 0; i < Wlen[w]; i++) { printcard(W[w][i], stderr); } fputc('\n', stderr); } fprintf( stderr, "Off: " ); for (int o = 0; o < 8; ++o) { printcard(O[o] + Osuit[o], stderr); } fprintf( stderr, "\nLast-Deal: %d\n", lastdeal ); #if 1 fprintf( stderr, "FE: %d FS: %d\n", d.firstempty, d.freestores); for (int o = 0; o < 8; ++o) { fprintf( stderr, "Pile%d: empty:%d linedup:%d highestbreak:%d fromscore:%d\n", o, d.empty[o], d.linedup[o], d.highestbreak[o], d.fromscore[o]); } #endif fprintf(stderr, "print-layout-end\n"); } diff --git a/patsolve/freecellsolver.cpp b/patsolve/freecellsolver.cpp index 8007c74..7784e97 100644 --- a/patsolve/freecellsolver.cpp +++ b/patsolve/freecellsolver.cpp @@ -1,519 +1,523 @@ /* * 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 "freecellsolver.h" #include "../freecell.h" /* Some macros used in get_possible_moves(). */ -/* The following macro implements +/* The following function implements (Same_suit ? (suit(a) == suit(b)) : (color(a) != color(b))) */ -#define suitable(a, b) ((((a) ^ (b)) & PS_COLOR) == PS_COLOR) +namespace { + constexpr bool suitable(const card_t a, const card_t b) {return ((a ^ b) & PS_COLOR) == PS_COLOR; } +} /* Statistics. */ int FreecellSolver::Xparam[] = { 4, 1, 8, -1, 7, 11, 4, 2, 2, 1, 2 }; /* These two routines make and unmake moves. */ void FreecellSolver::make_move(MOVE *m) { int from, to; card_t card; from = m->from; to = m->to; /* Remove from pile. */ card = *Wp[from]--; Wlen[from]--; hashpile(from); /* Add to pile. */ if (m->totype == O_Type) { O[to]++; } else { *++Wp[to] = card; Wlen[to]++; hashpile(to); } } void FreecellSolver::undo_move(MOVE *m) { int from, to; card_t card; from = m->from; to = m->to; /* Remove from 'to' pile. */ if (m->totype == O_Type) { card = O[to] + Osuit[to]; O[to]--; } else { card = *Wp[to]--; Wlen[to]--; hashpile(to); } /* Add to 'from' pile. */ *++Wp[from] = card; Wlen[from]++; hashpile(from); } /* Move prioritization. Given legal, pruned moves, there are still some that are a waste of time, especially in the endgame where there are lots of possible moves, but few productive ones. Note that we also prioritize positions when they are added to the queue. */ -#define NNEED 8 +namespace { + constexpr auto NNEED = 8; +} void FreecellSolver::prioritize(MOVE *mp0, int n) { int i, j, s, w, pile[NNEED], npile; card_t card, need[4]; MOVE *mp; /* There are 4 cards that we "need": the next cards to go out. We give higher priority to the moves that remove cards from the piles containing these cards. */ for (i = 0; i < NNEED; ++i) { pile[i] = -1; } npile = 0; for (s = 0; s < 4; ++s) { need[s] = NONE; if (O[s] == NONE) { need[s] = Osuit[s] + PS_ACE; } else if (O[s] != PS_KING) { need[s] = Osuit[s] + O[s] + 1; } } /* Locate the needed cards. There's room for optimization here, like maybe an array that keeps track of every card; if maintaining such an array is not too expensive. */ for (w = 0; w < Nwpiles; ++w) { j = Wlen[w]; for (i = 0; i < j; ++i) { card = W[w][i]; s = SUIT(card); /* Save the locations of the piles containing not only the card we need next, but the card after that as well. */ if (need[s] != NONE && (card == need[s] || card == need[s] + 1)) { pile[npile++] = w; if (npile == NNEED) { break; } } } if (npile == NNEED) { break; } } /* Now if any of the moves remove a card from any of the piles listed in pile[], bump their priority. Likewise, if a move covers a card we need, decrease its priority. These priority increments and decrements were determined empirically. */ for (i = 0, mp = mp0; i < n; ++i, ++mp) { if (mp->card_index != -1) { w = mp->from; for (j = 0; j < npile; ++j) { if (w == pile[j]) { mp->pri += Xparam[0]; } } if (Wlen[w] > 1) { card = W[w][Wlen[w] - 2]; for (s = 0; s < 4; ++s) { if (card == need[s]) { mp->pri += Xparam[1]; break; } } } if (mp->totype == W_Type) { for (j = 0; j < npile; ++j) { if (mp->to == pile[j]) { mp->pri -= Xparam[2]; } } } } } } /* Automove logic. Freecell games must avoid certain types of automoves. */ int FreecellSolver::good_automove(int o, int r) { int i; if (r <= 2) { return true; } /* Check the Out piles of opposite color. */ for (i = 1 - (o & 1); i < 4; i += 2) { if (O[i] < r - 1) { #if 1 /* Raymond's Rule */ /* Not all the N-1's of opposite color are out yet. We can still make an automove if either both N-2's are out or the other same color N-3 is out (Raymond's rule). Note the re-use of the loop variable i. We return here and never make it back to the outer loop. */ for (i = 1 - (o & 1); i < 4; i += 2) { if (O[i] < r - 2) { return false; } } if (O[(o + 2) & 3] < r - 3) { return false; } return true; #else /* Horne's Rule */ return false; #endif } } return true; } /* Get the possible moves from a position, and store them in Possible[]. */ int FreecellSolver::get_possible_moves(int *a, int *numout) { int i, n, t, w, o, empty, emptyw; card_t card; MOVE *mp; /* Check for moves from W to O. */ n = 0; mp = Possible; for (w = 0; w < Nwpiles + Ntpiles; ++w) { if (Wlen[w] > 0) { card = *Wp[w]; o = SUIT(card); empty = (O[o] == NONE); if ((empty && (RANK(card) == PS_ACE)) || (!empty && (RANK(card) == O[o] + 1))) { mp->card_index = 0; mp->from = w; mp->to = o; mp->totype = O_Type; mp->turn_index = -1; mp->pri = 0; /* unused */ n++; mp++; /* If it's an automove, just do it. */ if (good_automove(o, RANK(card))) { *a = true; mp[-1].pri = 127; if (n != 1) { Possible[0] = mp[-1]; return 1; } return n; } } } } /* No more automoves, but remember if there were any moves out. */ *a = false; *numout = n; /* Check for moves from non-singleton W cells to one of any empty W cells. */ emptyw = -1; for (w = 0; w < Nwpiles; ++w) { if (Wlen[w] == 0) { emptyw = w; break; } } if (emptyw >= 0) { for (i = 0; i < Nwpiles + Ntpiles; ++i) { if (i == emptyw || Wlen[i] == 0) { continue; } bool allowed = false; if ( i < Nwpiles) allowed = true; if ( i >= Nwpiles ) allowed = true; if ( allowed ) { card = *Wp[i]; mp->card_index = 0; mp->from = i; mp->to = emptyw; mp->totype = W_Type; mp->turn_index = -1; if ( i >= Nwpiles ) mp->pri = Xparam[6]; else mp->pri = Xparam[3]; n++; mp++; } } } /* Check for moves from W to non-empty W cells. */ for (i = 0; i < Nwpiles + Ntpiles; ++i) { if (Wlen[i] > 0) { card = *Wp[i]; for (w = 0; w < Nwpiles; ++w) { if (i == w) { continue; } if (Wlen[w] > 0 && (RANK(card) == RANK(*Wp[w]) - 1 && suitable(card, *Wp[w]))) { mp->card_index = 0; mp->from = i; mp->to = w; mp->totype = W_Type; mp->turn_index = -1; if ( i >= Nwpiles ) mp->pri = Xparam[5]; else mp->pri = Xparam[4]; n++; mp++; } } } } /* Check for moves from W to one of any empty T cells. */ for (t = 0; t < Ntpiles; ++t) { if (!Wlen[t+Nwpiles]) { break; } } if (t < Ntpiles) { for (w = 0; w < Nwpiles; ++w) { if (Wlen[w] > 0) { card = *Wp[w]; mp->card_index = 0; mp->from = w; mp->turn_index = -1; mp->to = t+Nwpiles; mp->totype = W_Type; mp->pri = Xparam[7]; n++; mp++; } } } return n; } void FreecellSolver::unpack_cluster( unsigned int k ) { /* Get the Out cells from the cluster number. */ O[0] = k & 0xF; k >>= 4; O[1] = k & 0xF; k >>= 4; O[2] = k & 0xF; k >>= 4; O[3] = k & 0xF; } bool FreecellSolver::isWon() { // maybe won? for (int o = 0; o < 4; ++o) { if (O[o] != PS_KING) { return false; } } return true; } int FreecellSolver::getOuts() { return O[0] + O[1] + O[2] + O[3]; } FreecellSolver::FreecellSolver(const Freecell *dealer) : Solver() { Osuit[0] = PS_DIAMOND; Osuit[1] = PS_CLUB; Osuit[2] = PS_HEART; Osuit[3] = PS_SPADE; Nwpiles = 8; Ntpiles = 4; setNumberPiles( Nwpiles + Ntpiles ); deal = dealer; } /* Read a layout file. Format is one pile per line, bottom to top (visible card). Temp cells and Out on the last two lines, if any. */ void FreecellSolver::translate_layout() { /* Read the workspace. */ int total = 0; for ( int w = 0; w < 8; ++w ) { int i = translate_pile(deal->store[w], W[w], 52); Wp[w] = &W[w][i - 1]; Wlen[w] = i; total += i; if (w == Nwpiles) { break; } } /* Temp cells may have some cards too. */ for (int w = 0; w < Ntpiles; ++w) { int i = translate_pile( deal->freecell[w], W[w+Nwpiles], 52 ); Wp[w+Nwpiles] = &W[w+Nwpiles][i-1]; Wlen[w+Nwpiles] = i; total += i; } /* Output piles, if any. */ for (int i = 0; i < 4; ++i) { O[i] = NONE; } if (total != 52) { for (int i = 0; i < 4; ++i) { KCard *c = deal->target[i]->topCard(); if (c) { O[translateSuit( c->suit() ) >> 4] = c->rank(); total += c->rank(); } } } } MoveHint FreecellSolver::translateMove( const MOVE &m ) { // this is tricky as we need to want to build the "meta moves" PatPile *frompile = nullptr; if ( m.from < 8 ) frompile = deal->store[m.from]; else frompile = deal->freecell[m.from-8]; KCard *card = frompile->at( frompile->count() - m.card_index - 1); if ( m.totype == O_Type ) { PatPile *target = nullptr; PatPile *empty = nullptr; for (int i = 0; i < 4; ++i) { KCard *c = deal->target[i]->topCard(); if (c) { if ( c->suit() == card->suit() ) { target = deal->target[i]; break; } } else if ( !empty ) empty = deal->target[i]; } if ( !target ) target = empty; return MoveHint( card, target, m.pri ); } else { PatPile *target = nullptr; if ( m.to < 8 ) target = deal->store[m.to]; else target = deal->freecell[m.to-8]; return MoveHint( card, target, m.pri ); } } unsigned int FreecellSolver::getClusterNumber() { int i = O[0] + (O[1] << 4); unsigned int k = i; i = O[2] + (O[3] << 4); k |= i << 8; return k; } void FreecellSolver::print_layout() { int i, t, w, o; fprintf(stderr, "print-layout-begin\n"); for (w = 0; w < Nwpiles; ++w) { fprintf(stderr, "W-Pile%d: ", w); for (i = 0; i < Wlen[w]; ++i) { printcard(W[w][i], stderr); } fputc('\n', stderr); } for (t = 0; t < Ntpiles; ++t) { fprintf(stderr, "T-Pile%d: ", t+Nwpiles); printcard(W[t+Nwpiles][Wlen[t+Nwpiles]], stderr); } fprintf( stderr, "\n" ); for (o = 0; o < 4; ++o) { printcard(O[o] + Osuit[o], stderr); } fprintf(stderr, "\nprint-layout-end\n"); } diff --git a/patsolve/idiotsolver.cpp b/patsolve/idiotsolver.cpp index adb56f1..4ff0ce9 100644 --- a/patsolve/idiotsolver.cpp +++ b/patsolve/idiotsolver.cpp @@ -1,304 +1,304 @@ /* * 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 "idiotsolver.h" #include "../idiot.h" #include #define PRINT 0 /* These two routines make and unmake moves. */ void IdiotSolver::make_move(MOVE *m) { #if PRINT if ( m->totype == O_Type ) fprintf( stderr, "\nmake move %d from %d out (at %d)\n\n", m->card_index, m->from, m->turn_index ); else fprintf( stderr, "\nmake move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index ); print_layout(); #else //print_layout(); #endif int from, to; card_t card = NONE; from = m->from; to = m->to; if ( from == 4 ) { Q_ASSERT( Wlen[from] >= 4 ); for ( int i = 0; i < 4; ++i ) { Wp[i]++; card = *Wp[from]; *Wp[i] = ( SUIT( card ) << 4 ) + RANK( card ); Wp[from]--; Wlen[from]--; Wlen[i]++; hashpile( i ); } hashpile( from ); } else { card = *Wp[from]; Wp[from]--; Wlen[from]--; Wp[to]++; *Wp[to] = card; Wlen[to]++; hashpile( to ); hashpile(from); } #if PRINT print_layout(); #endif } void IdiotSolver::undo_move(MOVE *m) { #if PRINT if ( m->totype == O_Type ) fprintf( stderr, "\nundo move %d from %d out (at %d)\n\n", m->card_index, m->from, m->turn_index ); else fprintf( stderr, "\nundo move %d from %d to %d (%d)\n\n", m->card_index, m->from, m->to, m->turn_index ); print_layout(); #endif int from, to; card_t card; from = m->from; to = m->to; if ( from == 4 ) { for ( int i = 3; i >= 0; --i ) { card = *Wp[i]; Wp[i]--; Wlen[i]--; Wp[from]++; *Wp[from] = ( SUIT( card ) << 4 ) + RANK( card ) + ( 1 << 7 ); Wlen[from]++; hashpile( i ); } hashpile( from ); } else { card = *Wp[to]; Wp[to]--; Wlen[to]--; Wp[from]++; *Wp[from] = card; Wlen[from]++; hashpile( to ); hashpile(from); } #if PRINT print_layout(); #endif } /* Get the possible moves from a position, and store them in Possible[]. */ int IdiotSolver::get_possible_moves(int *a, int *numout) { MOVE *mp = Possible; int n = 0; *a = false; *numout = n; for ( int i = 0; i < 4; ++i ) if ( Wlen[i] && canMoveAway( i ) ) { mp->card_index = 0; mp->from = i; mp->to = 5; mp->totype = W_Type; mp->turn_index = -1; mp->pri = 30; n++; mp++; return 1; } if ( Wlen[4] ) { mp->card_index = 0; mp->from = 4; mp->to = 0; mp->totype = W_Type; mp->turn_index = 0; mp->pri = 2; n++; mp++; } // now let's try to be a bit clever with the empty piles for( int i = 0; i < 4; ++i ) { if (Wlen[i] == 0) { // Find a card to move there for( int j = 0; j < 4; ++j ) { if ( i != j && Wlen[j]>0 ) { mp->card_index = 0; mp->from = j; mp->to = i; mp->totype = W_Type; mp->turn_index = 0; mp->pri = 2; n++; mp++; } } } } return n; } bool IdiotSolver::isWon() { // maybe won? return Wlen[5] == 48; } int IdiotSolver::getOuts() { return Wlen[5]; } IdiotSolver::IdiotSolver(const Idiot *dealer) : Solver() { setNumberPiles( 6 ); deal = dealer; } /* Read a layout file. Format is one pile per line, bottom to top (visible card). Temp cells and Out on the last two lines, if any. */ void IdiotSolver::translate_layout() { /* Read the workspace. */ int total = 0; for ( int w = 0; w < 4; ++w ) { int i = translate_pile(deal->m_play[w], W[w], 52); Wp[w] = &W[w][i - 1]; Wlen[w] = i; total += i; } int i = translate_pile( deal->talon, W[4], 52 ); Wp[4] = &W[4][i-1]; Wlen[4] = i; total += i; i = translate_pile( deal->m_away, W[5], 52 ); Wp[5] = &W[5][i-1]; Wlen[5] = i; total += i; Q_ASSERT( total == 52 ); } MoveHint IdiotSolver::translateMove( const MOVE &m ) { if ( m.from >=4 ) return MoveHint(); PatPile *frompile = deal->m_play[m.from]; KCard *card = frompile->at( frompile->count() - m.card_index - 1); Q_ASSERT( card ); PatPile *target = nullptr; if ( m.to == 5 ) target = deal->m_away; else target = deal->m_play[m.to]; return MoveHint( card, target, m.pri ); } void IdiotSolver::print_layout() { int i, w; fprintf(stderr, "print-layout-begin\n"); for (w = 0; w < 6; ++w) { if ( w == 4 ) fprintf( stderr, "Deck: " ); else if ( w == 5 ) fprintf( stderr, "Away: " ); else fprintf( stderr, "Play%d: ", w ); for (i = 0; i < Wlen[w]; ++i) { printcard(W[w][i], stderr); } fputc('\n', stderr); } fprintf(stderr, "\nprint-layout-end\n"); } inline bool higher( const card_t &c1, const card_t &c2) { // Sanity check. if (c1 == c2) return false; // Must be same suit. if ( SUIT( c1 ) != SUIT( c2 ) ) return false; // Aces form a special case. if (RANK( c2 ) == PS_ACE) return true; if (RANK( c1 ) == PS_ACE) return false; return (RANK( c1 ) < RANK( c2 )); } bool IdiotSolver::canMoveAway(int pile ) const { Q_ASSERT( pile < 4 ); if ( Wlen[pile] == 0 ) return false; for ( int i = 0; i < 4; ++i ) - Q_ASSERT( Wp[i] = &W[i][Wlen[i] - 1] ); + Q_ASSERT( Wp[i] == &W[i][Wlen[i] - 1] ); return ( ( Wlen[0] && higher( *Wp[pile], *Wp[0] ) ) || ( Wlen[1] && higher( *Wp[pile], *Wp[1] ) ) || ( Wlen[2] && higher( *Wp[pile], *Wp[2] ) ) || ( Wlen[3] && higher( *Wp[pile], *Wp[3] ) ) ); } diff --git a/patsolve/memory.cpp b/patsolve/memory.cpp index fb9682e..63a36a8 100644 --- a/patsolve/memory.cpp +++ b/patsolve/memory.cpp @@ -1,241 +1,241 @@ /* * 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 "memory.h" #include #include #include #include #include #define BLOCKSIZE (32 * 4096) /* Add it to the binary tree for this cluster. The piles are stored following the TREE structure. */ size_t MemoryManager::Mem_remain = 30 * 1000 * 1000; MemoryManager::inscode MemoryManager::insert_node(TREE *n, int d, TREE **tree, TREE **node) { int c; quint8 *key, *tkey; TREE *t; key = (quint8 *)n + sizeof(TREE); n->depth = d; n->left = n->right = nullptr; *node = n; t = *tree; if (t == nullptr) { *tree = n; return NEW; } while (true) { tkey = (quint8 *)t + sizeof(TREE); c = memcmp(key, tkey, Pilebytes); if (c == 0) { break; } if (c < 0) { if (t->left == nullptr) { t->left = n; return NEW; } t = t->left; } else { if (t->right == nullptr) { t->right = n; return NEW; } t = t->right; } } /* We get here if it's already in the tree. Don't add it again. If the new path to this position was shorter, record the new depth so we can prune the original path. */ return FOUND; } /* Given a cluster number, return a tree. There are 14^4 possible clusters, but we'll only use a few hundred of them at most. Hash on the cluster number, then locate its tree, creating it if necessary. */ #define TBUCKETS 499 /* a prime */ TREELIST *Treelist[TBUCKETS]; /* Clusters are also stored in a hashed array. */ void MemoryManager::init_clusters(void) { memset(Treelist, 0, sizeof(Treelist)); Block = new_block(); /* @@@ */ } TREELIST *MemoryManager::cluster_tree(unsigned int cluster) { int bucket; TREELIST *tl, *last; /* Pick a bucket, any bucket. */ bucket = cluster % TBUCKETS; /* Find the tree in this bucket with that cluster number. */ last = nullptr; for (tl = Treelist[bucket]; tl; tl = tl->next) { if (tl->cluster == cluster) { break; } last = tl; } /* If we didn't find it, make a new one and add it to the list. */ if (tl == nullptr) { - tl = mm_allocate(TREELIST); + tl = mm_allocate(); if (tl == nullptr) { return nullptr; } tl->tree = nullptr; tl->cluster = cluster; tl->next = nullptr; if (last == nullptr) { Treelist[bucket] = tl; } else { last->next = tl; } } return tl; } /* Block storage. Reduces overhead, and can be freed quickly. */ BLOCK *MemoryManager::new_block(void) { BLOCK *b; - b = mm_allocate(BLOCK); + b = mm_allocate(); if (b == nullptr) { return nullptr; } - b->block = new_array(quint8, BLOCKSIZE); + b->block = mm_new_array(BLOCKSIZE); if (b->block == nullptr) { MemoryManager::free_ptr(b); return nullptr; } b->ptr = b->block; b->remain = BLOCKSIZE; b->next = nullptr; return b; } /* Like new(), only from the current block. Make a new block if necessary. */ quint8 *MemoryManager::new_from_block(size_t s) { quint8 *p; BLOCK *b; b = Block; if (s > b->remain) { b = new_block(); if (b == nullptr) { return nullptr; } b->next = Block; Block = b; } p = b->ptr; b->remain -= s; b->ptr += s; return p; } /* Return the previous result of new_from_block() to the block. This can ONLY be called once, immediately after the call to new_from_block(). That is, no other calls to new_from_block() are allowed. */ void MemoryManager::give_back_block(quint8 *p) { size_t s; BLOCK *b; b = Block; s = b->ptr - p; b->ptr -= s; b->remain += s; } void MemoryManager::free_blocks(void) { BLOCK *b, *next; b = Block; while (b) { next = b->next; MemoryManager::free_array(b->block, BLOCKSIZE); MemoryManager::free_ptr(b); b = next; } } void MemoryManager::free_clusters(void) { int i; TREELIST *l, *n; for (i = 0; i < TBUCKETS; i++) { l = Treelist[i]; while (l) { n = l->next; MemoryManager::free_ptr(l); l = n; } } } /* Allocate some space and return a pointer to it. See new() in util.h. */ void *MemoryManager::allocate_memory(size_t s) { void *x; if (s > Mem_remain) { return nullptr; } // use calloc to ensure that the memory is zeroed if ((x = calloc(1, s)) == nullptr) { return nullptr; } Mem_remain -= s; return x; } diff --git a/patsolve/memory.h b/patsolve/memory.h index a1978cb..d28aa5c 100644 --- a/patsolve/memory.h +++ b/patsolve/memory.h @@ -1,98 +1,103 @@ /* * 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 . */ #ifndef MEMORY_H #define MEMORY_H #include #include struct TREE; /* Memory. */ struct BLOCK; struct BLOCK { unsigned char *block; unsigned char *ptr; size_t remain; BLOCK *next; }; struct TREELIST; struct TREELIST { TREE *tree; unsigned int cluster; TREELIST *next; }; /* Position information. We store a compact representation of the position; Temp cells are stored separately since they don't have to be compared. We also store the move that led to this position from the parent, as well as a pointers back to the parent, and the btree of all positions examined so far. */ struct TREE { TREE *left; TREE *right; short depth; }; #ifdef ERR #undef ERR #endif class MemoryManager { public: enum inscode { NEW, FOUND, ERR }; unsigned char *new_from_block(size_t s); void init_clusters(void); void free_blocks(void); void free_clusters(void); TREELIST *cluster_tree(unsigned int cluster); inscode insert_node(TREE *n, int d, TREE **tree, TREE **node); void give_back_block(unsigned char *p); BLOCK *new_block(void); template static void free_ptr(T *ptr) { free(ptr); Mem_remain += sizeof(T); } template static void free_array(T *ptr, size_t size) { free(ptr); Mem_remain += size * sizeof(T); } static void *allocate_memory(size_t s); // ugly hack int Pilebytes; static size_t Mem_remain; private: BLOCK *Block; }; -#define new_array( type, size ) ( type* )MemoryManager::allocate_memory( ( size )*sizeof( type ) ); -#define mm_allocate( type ) ( type* )MemoryManager::allocate_memory( sizeof( type ) ); +template +T* mm_new_array(const size_t size) { + return static_cast(MemoryManager::allocate_memory(size * sizeof(T))); +} + +template +T* mm_allocate() {return static_cast(MemoryManager::allocate_memory(sizeof(T)));} #endif // MEMORY_H diff --git a/patsolve/patsolve.cpp b/patsolve/patsolve.cpp index cdf96e6..d65c4da 100644 --- a/patsolve/patsolve.cpp +++ b/patsolve/patsolve.cpp @@ -1,1123 +1,976 @@ /* * 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 "KCardDeck" #include #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 */ -#define FNV1_32_INIT 0x811C9DC5 -#define FNV_32_PRIME 0x01000193 - -#define fnv_hash(x, hash) (((hash) * FNV_32_PRIME) ^ (x)) - -/* Hash a buffer. */ - -static inline quint32 fnv_hash_buf(quint8 *s, int len) -{ - int i; - quint32 h; - - h = FNV1_32_INIT; - for (i = 0; i < len; i++) { - h = fnv_hash(*s++, h); - } - - return h; -} +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. */ -static inline quint32 fnv_hash_str(quint8 *s) +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. */ 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; } -#define MAXDEPTH 400 - -bool Solver::recursive(POSITION *parent) -{ - int i, alln, a, numout = 0; - - if ( parent == nullptr ) { - init(); - recu_pos.clear(); - delete Stack; - Stack = new POSITION[MAXDEPTH]; - memset( Stack, 0, sizeof( POSITION ) * MAXDEPTH ); - } - - /* Fill in the Possible array. */ - - alln = get_possible_moves(&a, &numout); - assert(alln < MAXMOVES); - - if (alln == 0) { - if ( isWon() ) { - Status = SolutionExists; - Q_ASSERT(parent); // it just is never called with a won game - win(parent); - return true; - } - return false; - } - - /* 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. */ - - if ( parent && parent->depth >= MAXDEPTH - 2 ) - return false; - - MOVE *mp0 = new_array(MOVE, alln+1); - if (mp0 == nullptr) { - return false; - } - MOVE *mp = mp0; - for (i = 0; i < alln; ++i) { - if (Possible[i].card_index != -1) { - *mp = Possible[i]; /* struct copy */ - mp++; - } - } - mp->card_index = -1; - ++alln; - - bool fit = false; - for (mp = mp0; mp->card_index != -1; ++mp) { - - int depth = 0; - if (parent != nullptr) - depth = parent->depth + 1; - - make_move(mp); - - /* Calculate indices for the new piles. */ - pilesort(); - - /* See if this is a new position. */ - - Total_generated++; - POSITION *pos = &Stack[depth]; - pos->queue = nullptr; - pos->parent = parent; - pos->node = pack_position(); - quint8 *key = (quint8 *)pos->node + sizeof(TREE); -#if 0 - qint32 hash = fnv_hash_buf(key, mm->Pilebytes); - if ( recu_pos.contains( hash ) ) - { - undo_move( mp ); - mm->give_back_block( (quint8 *)pos->node ); - continue; - } - recu_pos[hash] = true; -#else - for ( int i = 0; i < depth; ++i ) - { - quint8 *tkey = (quint8 *)Stack[i].node + sizeof(TREE); - if ( !memcmp( key, tkey, mm->Pilebytes ) ) - { - key = nullptr; - break; - } - } - if ( !key ) - { - undo_move( mp ); - mm->give_back_block( (quint8 *)pos->node ); - continue; - } -#endif - Total_positions++; - if ( Total_positions % 10000 == 0 ) { - //qDebug() << "positions" << Total_positions; - } - - pos->move = *mp; /* struct copy */ - pos->cluster = 0; - pos->depth = depth; - pos->nchild = 0; - - bool ret = recursive(pos); - fit |= ret; - undo_move(mp); - mm->give_back_block( (quint8 *)pos->node ); - if ( ret ) - break; - } - - MemoryManager::free_array(mp0, alln); - - if ( parent == nullptr ) { - printf( "Total %ld\n", Total_generated ); - delete [] Stack; - Stack = nullptr; - } - return fit; -} - - /* Generate an array of the moves we can make from this position. */ 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); if (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 ); } } /* 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 = new_array(MOVE, n); + 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; void Solver::pilesort(void) { /* Make sure all the piles have id numbers. */ for (int w = 0; w < m_number_piles; 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; TREE *Solver::pack_position(void) { int j, w; 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 (w = 0; w < m_number_piles; ++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. */ void Solver::unpack_position(POSITION *pos) { int i, w; BUCKETLIST *l; unpack_cluster(pos->cluster); /* Unpack bytes p into pile numbers j. p p p +--------+----:----+--------+ |76543210|7654:3210|76543210| +--------+----:----+--------+ j j */ w = i = 0; quint16 *p2 = ( quint16* )( (quint8 *)(pos->node) + sizeof(TREE) ); while (w < m_number_piles) { 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++; } } 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. */ 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 = new_array(MOVE *, 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) winMoves.append( **mpp ); MemoryManager::free_array(mpp0, nmoves); } /* Initialize the hash buckets. */ void Solver::init_buckets(void) { int i; /* Packed positions need 3 bytes for every 2 piles. */ i = ( m_number_piles ) * sizeof( quint16 ); i += ( m_number_piles ) & 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. */ 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; //qDebug() << "out of piles"; return -1; } - l = mm_allocate(BUCKETLIST); + l = mm_allocate(); if (l == nullptr) { Status = UnableToDetermineSolvability; //qDebug() << "out of buckets"; return -1; } - l->pile = new_array(quint8, Wlen[w] + 1); + l->pile = mm_new_array(Wlen[w] + 1); if (l->pile == nullptr) { Status = UnableToDetermineSolvability; MemoryManager::free_ptr(l); //qDebug() << "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; } 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. */ void Solver::doit() { int i, q; POSITION *pos; MOVE m; memset( &m, 0, sizeof( MOVE ) ); /* 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). */ 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; } { QMutexLocker lock( &endMutex ); if ( m_shouldEnd ) { 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( firstMoves.count() == 0 ); for (int j = 0; j < nmoves; ++j) 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). */ 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). */ 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. */ 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; } Solver::Solver() { mm = new MemoryManager(); Freepos = nullptr; /* Work arrays. */ W = nullptr; Wp = nullptr; Wlen = nullptr; Whash = nullptr; Wpilenum = nullptr; Stack = nullptr; } Solver::~Solver() { delete mm; for ( int i = 0; i < m_number_piles; ++i ) { delete [] W[i]; } delete [] W; delete [] Wp; delete [] Wlen; delete [] Whash; delete [] Wpilenum; } void Solver::init() { m_shouldEnd = false; init_buckets(); mm->init_clusters(); winMoves.clear(); firstMoves.clear(); /* Reset stats. */ Status = NoSolutionExists; Total_positions = 0; Total_generated = 0; depth_sum = 0; } void Solver::free() { free_buckets(); mm->free_clusters(); mm->free_blocks(); Freepos = nullptr; } Solver::ExitStatus Solver::patsolve( int _max_positions, bool _debug ) { max_positions = _max_positions; debug = _debug; /* Initialize the suitable() macro variables. */ init(); /* Go to it. */ doit(); if ( Status == SearchAborted ) // thread quit { firstMoves.clear(); 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; } void Solver::print_layout() { } void Solver::setNumberPiles( int p ) { m_number_piles = p; /* Work arrays. */ W = new card_t*[m_number_piles]; for ( int i = 0; i < m_number_piles; ++i ) { W[i] = new card_t[84]; memset( W[i], 0, sizeof( card_t ) * 84 ); } Wp = new card_t*[m_number_piles]; Wlen = new int[m_number_piles]; Whash = new quint32[m_number_piles]; Wpilenum = new int[m_number_piles]; memset( Wpilenum, 0, sizeof( int ) * m_number_piles ); } 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; } 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. */ 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; } 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 < m_number_piles; ++i ) { QString s = " " + QString( "%1" ).arg( ( int )t[i] ); dummy += s.right( 5 ); } if ( Total_positions % 1000 == 1000 ) print_layout(); //qDebug() << "new" << dummy; #endif p += sizeof(POSITION); return pos; } /* Hash the whole layout. This is called once, at the start. */ void Solver::hash_layout(void) { int w; for (w = 0; w < m_number_piles; w++) { hashpile(w); } } void Solver::prioritize(MOVE *, int ) { } diff --git a/patsolve/patsolve.h b/patsolve/patsolve.h index 4cef465..082edee 100644 --- a/patsolve/patsolve.h +++ b/patsolve/patsolve.h @@ -1,185 +1,185 @@ /* * 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 . */ #ifndef PATSOLVE_H #define PATSOLVE_H #include "../hint.h" #include "memory.h" #include "KCardPile" #include #include #include /* A card is represented as ( down << 6 ) + (suit << 4) + rank. */ typedef quint8 card_t; /* Represent a move. */ enum PileType { O_Type = 1, W_Type }; class MOVE { public: int card_index; /* the card we're moving (0 is the top)*/ quint8 from; /* from pile number */ quint8 to; /* to pile number */ PileType totype; signed char pri; /* move priority (low priority == low value) */ int turn_index; /* turn the card index */ bool operator<( const MOVE &m) const { return pri < m.pri; } }; struct POSITION { POSITION *queue; /* next position in the queue */ POSITION *parent; /* point back up the move stack */ TREE *node; /* compact position rep.'s tree node */ MOVE move; /* move that got us here from the parent */ quint32 cluster; /* the cluster this node is in */ short depth; /* number of moves so far */ quint8 nchild; /* number of child nodes left */ }; class MemoryManager; class Solver { public: enum ExitStatus { MemoryLimitReached = -3, SearchAborted = -2, UnableToDetermineSolvability = -1, NoSolutionExists = 0, SolutionExists = 1 }; Solver(); virtual ~Solver(); ExitStatus patsolve( int max_positions = -1, bool debug = false); - bool recursive(POSITION *pos = nullptr); virtual void translate_layout() = 0; bool m_shouldEnd; QMutex endMutex; virtual MoveHint translateMove(const MOVE &m ) = 0; QList firstMoves; QList winMoves; protected: MOVE *get_moves(int *nmoves); bool solve(POSITION *parent); void doit(); void win(POSITION *pos); virtual int get_possible_moves(int *a, int *numout) = 0; int translateSuit( int s ); void queue_position(POSITION *pos, int pri); void free_position(POSITION *pos, int); POSITION *dequeue_position(); void hashpile(int w); POSITION *new_position(POSITION *parent, MOVE *m); TREE *pack_position(void); void unpack_position(POSITION *pos); void init_buckets(void); int get_pilenum(int w); MemoryManager::inscode insert(unsigned int *cluster, int d, TREE **node); void free_buckets(void); void printcard(card_t card, FILE *outfile); int translate_pile(const KCardPile *pile, card_t *w, int size); virtual void print_layout(); void pilesort(void); void hash_layout( void ); virtual void make_move(MOVE *m) = 0; virtual void undo_move(MOVE *m) = 0; virtual void prioritize(MOVE *mp0, int n); virtual bool isWon() = 0; virtual int getOuts() = 0; virtual unsigned int getClusterNumber() { return 0; } virtual void unpack_cluster( unsigned int ) {} void setNumberPiles( int i ); int m_number_piles; void init(); void free(); /* Work arrays. */ card_t **W; /* the workspace */ card_t **Wp; /* point to the top card of each work pile */ int *Wlen; /* the number of cards in each pile */ /* Every different pile has a hash and a unique id. */ quint32 *Whash; int *Wpilenum; /* Position freelist. */ POSITION *Freepos; -#define MAXMOVES 64 /* > max # moves from any position */ + static constexpr auto MAXMOVES = 64; /* > max # moves from any position */ MOVE Possible[MAXMOVES]; MemoryManager *mm; ExitStatus Status; /* win, lose, or fail */ -#define NQUEUES 127 + static constexpr auto NQUEUES = 127; POSITION *Qhead[NQUEUES]; /* separate queue for each priority */ int Maxq; unsigned long Total_generated, Total_positions; qreal depth_sum; POSITION *Stack; QMap recu_pos; int max_positions; bool debug; }; /* Misc. */ -#define PS_DIAMOND 0x00 /* red */ -#define PS_CLUB 0x10 /* black */ -#define PS_HEART 0x20 /* red */ -#define PS_SPADE 0x30 /* black */ -#define PS_BLACK 0x10 -#define PS_COLOR 0x10 /* black if set */ -#define PS_SUIT 0x30 /* mask both suit bits */ - -#define NONE 0 -#define PS_ACE 1 -#define PS_KING 13 - -#define RANK(card) ((card) & 0xF) -#define SUIT(card) (( (card) >> 4 ) & 3) -#define COLOR(card) ((card) & PS_COLOR) -#define DOWN(card) ((card) & ( 1 << 7 ) ) +constexpr card_t PS_DIAMOND = 0x00; /* red */ +constexpr card_t PS_CLUB = 0x10; /* black */ +constexpr card_t PS_HEART = 0x20; /* red */ +constexpr card_t PS_SPADE = 0x30; /* black */ +constexpr card_t PS_BLACK = 0x10; +constexpr card_t PS_COLOR = 0x10; /* black if set */ +constexpr card_t PS_SUIT = 0x30; /* mask both suit bits */ + +constexpr card_t NONE = 0; +constexpr card_t PS_ACE = 1; +constexpr card_t PS_KING = 13; + +constexpr card_t RANK(card_t card) {return card & 0xF;} +constexpr card_t SUIT(card_t card) {return (card >> 4 ) & 3;} + +constexpr card_t COLOR(card_t card) {return card & PS_COLOR;} +constexpr card_t DOWN(card_t card) {return (card) & ( 1 << 7 );} extern long all_moves; #endif // PATSOLVE_H