Object Serialization for Undo/Redo Functionality Java

Question

I have been trying to implement and undo/redo system in a game I am coding in Java. I am taking the approach of serializing the state of the game after each move. I there a way of saving the serialized objects on a stack and accessing them for undo/redo?

Answer 1

Java provides a javax.swing.undo.UndoManagerthat is essentially a stack of UndoableEdit's (i.e. commands). If you save the before and after state in an UndoableEdit, then whenever you issue an undo, or a redo, it's simply a matter of restoring that state on undo or redo.

If you can't use the swing class above, you can use a basic stack or list as long as you make sure to perform the correct operations when different edits/commands are performed. For example, if you were to undo a few operations, and then make a different edit, the previously undone commands would be lost.

Answer 2

Kaleb's suggestion is awesome (+1) but doesn't give detail. I can't give enough detail in a comment, and didn't see a good, simple explanation of how to use it.

An undoable edit consists of 3 important parts--The constructor, the undo method and the redo method. The trick is to keep each "edit" VERY simple. Depending on how complex your game is, it could be hundreds of edits between "moves".

Let's say in a turn based simulation, you move one army--that's an edit--then the computer moves all it's armies (each one is an edit). A random weather condition--another edit, a city builds a new tank--another edit, ...

Each type of edit is a different object type. Let's say you are moving a unit from (35,150) to (35, 151). Making your move may look like this:

undoManager.addEdit( new MoveOne(map, new Point(35,150), new Point(35,151)) );

and undoing this edit would simply be:

undoManager.undo();

which automatically undos everything up to the last "significant" edit (the last one the human player made)

Here is what the "move" class would look like:

MoveOne extends AbstractUndoableEdit {
    private final Point start;
    private final Point finish;
    private final Map map;

    public MoveOne(Map pMap, Point pStart, Point pFinish) {
        start=pStart;
        finish=pFinish;
        map=pMap;
        redo();
    }

    public redo() {
        MapObject piece=map.getObjectAt(start);
        map.moveObject(piece, finish);
    }

    public undo() {
        MapObject piece=map.getObjectAt(finish);
        map.moveObject(piece, start);
    }
}

A bunch of tiny moves like this might accumulate into one "Human" move. These "human" could be tagged by the isSignificant" tag--that way you could easily undo to the last "significant" event. Everything else in your game becomes a matter of simply manipulating these trivial little objects.

I love this pattern, and props to @Kaleb for pointing out that java now supports it in the JDK!

Answer 3

Game programming has not much to do with "enterprise app" programming nor with "webapp programming".

So it depends on what kind of game you're working on but your approach and the ones gaven so fare have absolutely nothing to do with how game states are saved in "real" games. The performances are going to be abysmally bad and you'll end up using a lot of memory and disk space.

Great games like, for example, Warcraft III by Blizzard or Age of Empires by Microsoft only ever store the user inputs needed to reproduce any game state.

That's how they achieve super efficient network transmission even when players have hundreds or thousands of objects and that's how they achieve tiny save game files (that can be used to either continue the game or do a replay): want low latency? easy, simply send by UDP the keystrokes and mouseclicks of the players and the time at which these inputs happened.

How is this related to an undo/redo? Trivial...

Imagine you've had 200 user inputs since your game started and want to undo the last step: you start the game from scratch and feed the 199 first inputs. That's it. Perfect undo.

Of course you only need to replay the logic when replaying those 199 steps, without updating needing to update your view. For most games the logic is a tiny part of the total time spent (most time being spent in the view). So replaying these inputs is very fast.

Been there, done that :)

Now if you want another way to do unlimited undo/redo then something has to be say about "OO over immutable objects": I've written game tools editors (like a map editor) featuring unlimited undo/redo too. The trick is to only ever use immutable objects. Then persisting previous states is easy: simply but the object at the top of your hierarchy ('gamemap239').

Because you're only ever using immutable objects, a "new" gamemap is sharing 99.9% of its objects with the previous gamemap and hence the memory usage is ridiculously low allowing to keep huge amount of states.

I've successfully applied this "OO over immutable objects for efficient undo/redo" in commercial software that are not games and it is really an amazing technique.

Now it depends on the game you're doing: sure, for a minesweeper game you can use Swing and regular Java programming techniques. But for more advanced games, regular Java collections and APIs and regular entreprise/webapp/fatclient programming techniques simply don't cut it.