Command Pattern - Undo

[mtgrares]

This is directed toward nantuko84 but other people might be interested also.

The command pattern can be used to implement an undo/redo system. The "trick" is that everything in your program has to generate a Command object. Generally the Command object is just an abstract interface with a single method. To implement undo you just make each Command action reversible.

In my opinion generating a Command object for every action is a bit of a pain. So if a player draws 3 cards, undo() would put those cards back on top of the library in the correct order. With Magic and state effects like the "legendary rule", I presume each state effect would also generate a Command object. So if a player played a 2nd legendary creature, that would generate one Command and then state effects would be checked and it would generate a second Command. And as always the devil is in the details, especially when considering combat and EOT effects.

There are a ton of tiny, detailed stuff you could to in order to make undo better for the user. You could combine "minor" Commands together to make a "major" Command, like minor Commands would be tapping individual cards and the major Command would be paying for a card.

And if you implement the Command pattern you should be able to write each Command to the hard drive and be able to replay the game, which would really help debugging.

This is how I understand things and I hope this helps.

Code: Select all

public interface Command
{
  public void execute();
}

Code: Select all

public interface UndoCommand
{
  public void execute();
  public void undo();
}

[silly freak]

This is how I understand things and I hope this helps.

Code: Select all

public interface Command
{
  public void execute();
}

Code: Select all

public interface UndoCommand extends Command
{
  public void execute();
  public void undo();
}

Actually more like this: An UndoCommamd IS-A Command. Everywhere you need a command, you can use on that can be undone.

I'm about to write a post on that matter on my blog (see signature). check back in a few days

[frwololo]

Interesting topic.

someone on my forums suggested an other approach that sounds much more easier (avoids to code undos for everything):
Save the state of the game at every beginning of turn.

This way, "undo" goes back one turn. It pretty much does what the players expect (come back in time when they did a stupid mistake), while being much more easier to code (save a list of the cards in each zone, and maybe the current value of the random seed, and that's it)

With undoing each single action in MTG, you run the risk of forgetting one of them, completely messing up the state of the game.
what if you "undraw" 3 cards, which in return stupidly triggers an effect "whenever a card leaves your hand"... so you'd have to somehow "deactivate" triggers and state effects when the undo is being processed.
sounds like a pain to take all cases into account, while saving the game state at regular intervals is pretty straightforward.

[nantuko84]

mtgrares> thanks a lot for creating such topic, this is one I've been thinking over a lot last time

silly freak> good point, undo is the same command
and I found your blog rather interesting!

[nantuko84]

frwololo> you are totally right

Half a year ago my inet suffered from bad connections, so when I played with my friend, games in MagicWars became broken saying "connection refused" that was very very annoying. What I could do that time is to implement saving the whole game state on harddrive every turn: it was easy, as all games objects and actions are in GameManager, so I just serialized it.
Later when playing with undo, I rewrote it a little and made MWState that handles game state, but not sure about performance (for AI I will need to store a lot of states).

I also tried what you said about triggeres - I turned on "silent" mode, it works more or less, but I thought the same as you saying that it's pain to take all cases into account and it may become the reason of many bugs in future.

Why I came back to Undo command idea is Duels of the Planeswalkers game and article written by architect (does anybody have its source code? )
I believe they thought ten times before using it, so probably it's much more effective than saving game state.

[silly freak]

thanks a lot! i'm glad there's someone reading it^^

undo as back one turn and redo is an option, but I think as soon as you want an AI that does and undoes moves to find the best, this might get hard.
If you do actions right, there shouldn't be a problem. the result of an action that triggers something is another action, and undo should be independent from triggering anything. I admit that I haven't fully figured that out yet

and indeed, my inspiration for undo was Duels of the Planeswalkers. I wouldn't have found that without forge mentioning it ^^

[nantuko84]

oh, I remembered that I had another that "silent mode idea" for undo command

let's say we have "whenever a card leaves your hand"
the main idea that all such triggers are handled by GameManager (or RulesEngine in Forge 2), and cards can play with objects in game only using these classed. Undo function will return back only the consequences and will do it directly.

let me bring example:
we had 7 cards in hand, 0 in grave, 1 on battlefield, 0 in exile
we played cycling (do discard and draw), then it triggered removing creature
here we can see that we have other 7 cards in hand, 1 in grave, 0 on battlefield, 1 in exile
so we just create undo action that will inject directly (not using GameManager) 1 card from grave to hand, 1 from exile to battlefield - it's just working with array lists not calling moveToZone() methods

1. no triggers for undo
2. we just compare lists for every zone (that is limited and constant) so probably no bugs in future

what do you think?

updated: hm, not only zones, but permanents properties (type, power, toughness, color, counters, name) but it's also limited I believe

[silly freak]

my idea is to go very deep - timestamps, priority, ... - whenever any value in the game is changed, this is an action. actions are grouped together to things that happen atomically (like state-bases actions before a player gets priority).
Every component creates actions itself and makes sure that every change is included. then the component that caused the sub-action collects it and stuffs it together with the other actions it caused.
In the end, the top-level component reports the action (containing sub-actions in a tree) to the game, which finally executes it... or something like that. I'm working to make it easier and more transparent

[Arch]

An alternative way of doing undo is to use immutable data. Since the data would be guarantueed never to change you can take a snapshot at any time and use that as an undo-point. Like; undoPoint = myCurrentGameState;. Restoring it would be just as easy.

Immutable data structures for the JVM is becoming commonplace these days. I think the most powerful one are the Clojure ones. They implement the Java interfaces and could probably be used straight up. Another one is Functional Java - haven't tried this one myself but seems decent.

It may not be a viable strategy for many projects on here though. A lot of code would have to be rewritten in order to handle the new data structures correctly, possibly the entire thing.

[telengard]

Interesting topic.

someone on my forums suggested an other approach that sounds much more easier (avoids to code undos for everything):
Save the state of the game at every beginning of turn.

This way, "undo" goes back one turn. It pretty much does what the players expect (come back in time when they did a stupid mistake), while being much more easier to code (save a list of the cards in each zone, and maybe the current value of the random seed, and that's it)

With undoing each single action in MTG, you run the risk of forgetting one of them, completely messing up the state of the game.
what if you "undraw" 3 cards, which in return stupidly triggers an effect "whenever a card leaves your hand"... so you'd have to somehow "deactivate" triggers and state effects when the undo is being processed.
sounds like a pain to take all cases into account, while saving the game state at regular intervals is pretty straightforward.

Given the amount of data in the game state (for Magic etc) this way is very difficult. I did it this way and it was pure pain (was also hoping to leverage it for a thread AI). I now have change_state objects which can be done/undone and it works great.

The way I get back to the exact state after an action is executed (and other things happen) is back up to that particular id. Every action has a numerical id (which is incremented for each new one allocated) so I can back up to prior to that id.

~telengard

[nantuko84]

telengard>
could you please give any example of change_state objects with done\undone. may be describing some real game state and actions occured with saying what was saved and how it was returned to initial state using numerical id.

[telengard]

telengard>
could you please give any example of change_state objects with done\undone. may be describing some real game state and actions occured with saying what was saved and how it was returned to initial state using numerical id.

No problem

Core undo code

http://pastebin.com/f398fca4d

Key bit not shown in this particular code, is that after any action is executed (everything derives from action: effects, abilities, etc), handle_undo_stack is called.

The above code also has one of the many change_state_* routines. I've removed a lot of my debugging info and have undo commented out (should probably re-enable that hehe). The undo framework is mostly for the AI, but it also can be used by a human player to undo the last choice he/she made.

The class for changing an int is here, pretty simple stuff:

http://pastebin.com/f8fd889c

The AI use of the undo engine is below:

http://pastebin.com/f2384c2b8

As you can see it calls pop_state()

Hope this helps a little bit

~telengard