[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-commits
Subject: KDE/kdegames/kpat
From: Parker Coates <parker.coates () kdemail ! net>
Date: 2012-02-15 4:44:50
Message-ID: 20120215044450.2EBB2AC894 () svn ! kde ! org
[Download RAW message or body]
SVN commit 1280161 by coates:
Rewrite the state saving and restoring code to be diff based.
Previously, KPat stored the state of every single card for every state
in its undo/redo history. Since the vast majority of moves involve less
than 10 cards and a decent percentage involve only one, this approach
is obviously quite inefficient.
As of this commit, KPat now stores only the old and new states of each
card that has been altered since the last move. This is both more
processor and memory friendly, which is great, but it also opens the
door to creating a new saved game format that stores the entire game
history.
DIGEST:
M +93 -76 dealer.cpp
M +4 -6 dealer.h
M +24 -18 gamestate.h
--- trunk/KDE/kdegames/kpat/dealer.cpp #1280160:1280161
@@ -183,6 +183,7 @@
QStack<GameState*> undoStack;
GameState * currentState;
QStack<GameState*> redoStack;
+ QHash<KCard*,CardState> cardStates;
QList<PatPile*> patPiles;
QSet<KCard*> cardsNotToDrop;
@@ -661,6 +662,7 @@
d->currentState = 0;
qDeleteAll( d->redoStack );
d->redoStack.clear();
+ d->cardStates.clear();
d->gameWasJustSaved = false;
d->gameWasEverWinnable = false;
@@ -935,15 +937,74 @@
if ( isCardAnimationRunning() )
return;
- QStack<GameState*> & from = undo ? d->undoStack : d->redoStack;
- QStack<GameState*> & to = undo ? d->redoStack : d->undoStack;
+ // The undo and redo actions are almost identical, except for where states
+ // are pulled from and pushed to, so to keep things generic, we use
+ // direction dependent const references throughout this code.
+ QStack<GameState*> & fromStack = undo ? d->undoStack : d->redoStack;
+ QStack<GameState*> & toStack = undo ? d->redoStack : d->undoStack;
- if ( !from.isEmpty() && d->currentState )
+ if ( !fromStack.isEmpty() && d->currentState )
{
- to.push( d->currentState );
- d->currentState = from.pop();
- setState( d->currentState );
+ // If we're undoing, we use the oldStates of the diffs of the current
+ // state. If we're redoing, we use the newStates of the diffs of the
+ // nextState.
+ const QHash<KCard*,CardDiff> & diffs = undo ? d->currentState->diffs
+ : fromStack.top()->diffs;
+ // Update the currentState pointer and undo/redo stacks.
+ toStack.push( d->currentState );
+ d->currentState = fromStack.pop();
+ setGameState( d->currentState->stateData );
+
+ QSet<KCardPile*> pilesAffected;
+ QHash<KCard*,CardDiff>::const_iterator it = diffs.constBegin();
+ QHash<KCard*,CardDiff>::const_iterator end = diffs.constEnd();
+ for ( ; it != end; ++it )
+ {
+ KCard * c = it.key();
+ const CardDiff & diff = it.value();
+ const CardState & sourceState = undo ? diff.newState : diff.oldState;
+ const CardState & destState = undo ? diff.oldState : diff.newState;
+
+ d->cardStates.insert( c, destState );
+ pilesAffected << sourceState.pile << destState.pile;
+
+ c->setFaceUp( destState.faceUp );
+ destState.pile->add( c );
+
+ PatPile * sourcePile = dynamic_cast<PatPile*>( sourceState.pile );
+ PatPile * destPile = dynamic_cast<PatPile*>( destState.pile );
+ if ( destState.takenDown
+ || ((sourcePile && sourcePile->isFoundation())
+ && !(destPile && destPile->isFoundation())) )
+ {
+ d->cardsNotToDrop.insert( c );
+ }
+ else
+ {
+ d->cardsNotToDrop.remove( c );
+ }
+ }
+
+ // At this point all cards should be in the right piles, but not
+ // necessarily at the right positions within those piles. So we
+ // run through the piles involved and swap card positions until
+ // everything is back in its place, then relayout the piles.
+ foreach( KCardPile * p, pilesAffected )
+ {
+ int i = 0;
+ while ( i < p->count() )
+ {
+ int index = d->cardStates.value( p->at( i ) ).index;
+ if ( i != index )
+ p->swapCards( i, index );
+ else
+ ++i;
+ }
+
+ updatePileLayout( p, 0 );
+ }
+
emit updateMoves( moveCount() );
emit undoPossible( !d->undoStack.isEmpty() );
emit redoPossible( !d->redoStack.isEmpty() );
@@ -994,11 +1055,33 @@
if ( !isDemoActive() )
d->winMoves.clear();
- GameState * newState = getState();
+ QHash<KCard*,CardDiff> cardDiffs;
+ foreach ( KCardPile * p, piles() )
+ {
+ for ( int i = 0; i < p->count(); ++i )
+ {
+ KCard * c = p->at( i );
- if ( d->currentState && *newState == *(d->currentState) )
+ CardState s;
+ s.pile = p;
+ s.index = i;
+ s.faceUp = c->isFaceUp();
+ s.takenDown = d->cardsNotToDrop.contains( c );
+
+ const CardState & oldState = d->cardStates.value( c );
+ if ( s != oldState )
{
- delete newState;
+ cardDiffs.insert( c, CardDiff( oldState, s ) );
+ d->cardStates.insert( c, s );
+ }
+ }
+ }
+
+ // If nothing has changed, we're done.
+ if ( cardDiffs.isEmpty()
+ && d->currentState
+ && d->currentState->stateData == getGameState() )
+ {
return;
}
@@ -1008,7 +1091,7 @@
qDeleteAll( d->redoStack );
d->redoStack.clear();
}
- d->currentState = newState;
+ d->currentState = new GameState( cardDiffs, getGameState() );
emit redoPossible( false );
emit undoPossible( !d->undoStack.isEmpty() );
@@ -1043,72 +1126,6 @@
}
-GameState *DealerScene::getState()
-{
- QSet<CardState> cardStates;
- cardStates.reserve( deck()->cards().size() );
- foreach (PatPile * p, patPiles())
- {
- foreach (KCard * c, p->cards())
- {
- CardState s;
- s.card = c;
- s.pile = c->pile();
- if (!s.pile) {
- kDebug() << c->objectName() << "has no valid parent.";
- Q_ASSERT(false);
- continue;
- }
- s.cardIndex = s.pile->indexOf( c );
- s.faceUp = c->isFaceUp();
- s.takenDown = d->cardsNotToDrop.contains( c );
- cardStates << s;
- }
- }
-
- return new GameState( cardStates, getGameState() );
-}
-
-
-void DealerScene::setState( GameState * state )
-{
- d->cardsNotToDrop.clear();
-
- QSet<KCard*> cardsFromFoundations;
- foreach (PatPile *p, patPiles())
- {
- if ( p->isFoundation() )
- foreach (KCard *c, p->cards())
- cardsFromFoundations.insert( c );
- p->clear();
- }
-
- QMap<KCard*,int> cardIndices;
- foreach ( const CardState & s, state->cards )
- {
- KCard *c = s.card;
- c->setFaceUp( s.faceUp );
- s.pile->add( c );
- cardIndices.insert( c, s.cardIndex );
-
- PatPile * p = dynamic_cast<PatPile*>(c->pile());
- if ( s.takenDown || (cardsFromFoundations.contains( c ) && !(p && p->isFoundation())) )
- d->cardsNotToDrop.insert( c );
- }
-
- foreach( PatPile * p, patPiles() )
- {
- foreach ( KCard * c, p->cards() )
- p->swapCards( p->indexOf( c ), cardIndices.value( c ) );
-
- updatePileLayout( p, 0 );
- }
-
- // restore game-specific information
- setGameState( state->gameData );
-}
-
-
void DealerScene::setSolverEnabled(bool a)
{
d->solverEnabled = a;
--- trunk/KDE/kdegames/kpat/dealer.h #1280160:1280161
@@ -39,6 +39,7 @@
#define DEALER_H
class DealerScene;
+class CardDiff;
class GameState;
class MoveHint;
#include "patpile.h"
@@ -185,6 +186,7 @@
const QList<KCardPile*> & freeCells,
int duration );
+ QList<MoveHint> getSolverHints();
protected slots:
void takeState();
@@ -193,12 +195,6 @@
virtual bool drop();
virtual bool tryAutomaticMove( KCard * card );
- void undoOrRedo( bool undo );
- GameState * getState();
- void setState( GameState * state );
-
- QList<MoveHint> getSolverHints();
-
private slots:
void stopAndRestartSolver();
void slotSolverEnded();
@@ -209,6 +205,8 @@
void showWonMessage();
private:
+ void undoOrRedo( bool undo );
+
void resetInternals();
MoveHint chooseHint();
--- trunk/KDE/kdegames/kpat/gamestate.h #1280160:1280161
@@ -49,48 +49,54 @@
class CardState
{
public:
- KCard * card;
KCardPile * pile;
+ int index;
bool faceUp;
bool takenDown;
- int cardIndex;
bool operator==( const CardState & rhs ) const
{
- return card == rhs.card
- && pile == rhs.pile
+ return pile == rhs.pile
+ && index == rhs.index
&& faceUp == rhs.faceUp
- && cardIndex == rhs.cardIndex
&& takenDown == rhs.takenDown;
}
+
+ bool operator!=( const CardState & rhs ) const
+ {
+ return !operator==( rhs );
+ }
};
-uint qHash( const CardState & state )
+class CardDiff
{
- return qHash( state.card );
-}
+public:
+ CardState oldState;
+ CardState newState;
+ CardDiff( CardState o, CardState n )
+ : oldState( o ),
+ newState( n )
+ {
+ };
+};
+
class GameState
{
public:
- QSet<CardState> cards;
- QString gameData;
+ QHash<KCard*,CardDiff> diffs;
+ QString stateData;
Solver::ExitStatus solvability;
QList<MOVE> winningMoves;
- GameState( QSet<CardState> cardStates, QString gameData )
- : cards( cardStates ),
- gameData( gameData ),
+ GameState( QHash<KCard*,CardDiff> diffs, QString stateData )
+ : diffs( diffs ),
+ stateData( stateData ),
solvability( Solver::SearchAborted )
{
}
-
- bool operator==( const GameState & rhs ) const
- {
- return cards == rhs.cards && gameData == rhs.gameData;
- }
};
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic