Sunday, January 24, 2010

Implementing Undo: A working approach

When I realized that the need for an extra parameter really hurts the usability, I had to rethink the way of storing moves. Additionally, moves should be executed immediately, and not simply stored and scheduled for later execution, to make the semantics feel more natural.
By the way, I changed the  name from Move to Edit, since that is the classic name for undoable stuff. Not that it would matter too much...

I didn't want to give up the tree, but needed a way to get the parent without using a parameter. Gladly, I found a solution that makes it pretty easy to create the right hierarchy. In a nutshell, the node that is currently appended to is stored in the controller, and when a node is created, it automatically finds the controller that belongs to the game.
This way, I was able to keep my tree structure and only had to do minimal changes. First, I had to change the Edit constructor to add itself to the controller. Second, the controller needed some notion of the current parent node.

Well, there were some problems on the way... I wanted to automatically execute edits at creation. the problem is the order of initialization. Imagine this:

abstract class Edit {
    public Move() {
        //add to the controller...

        //then:
        execute();
    }
    
    public abstract void execute();
    
    public abstract void rollback();
}

class MyEdit extends Edit {
    private Object importantValue;
    
    public MyEdit(Object importantValue) {
        super();
        this.importantValue = importantValue;
    }
    
    public abstract void execute() {
        //do something with importantValue
    }

    public abstract void rollback() {
        //undo something with importantValue
    }
}


execute is called in the Edit Constructor, which is called at the beginning of initialization, before importantValue is set! Although it's logical that the superclass must be initialized first - starting with Object, which reserves memory on the heap to store atributes in the first place - this leads to the requirement for some annoying workarounds. For this, it's just to move the execute out of the constructor - it is essentially done after constructing any move. I will show another workaround later - for the random number generator - until then, my new code is online; i had a hard time with subclipse, but everything's alright now. feel free to peek into laterna.magica.edit, and laterna.magica.timestamp; yet the only classes to use this new development

Saturday, January 16, 2010

Implementing Undo: Trial and Error

I'm working eagerly on undo, and have a few thoughts to share on it. first, let me say that it's really not easy. so many thing can go wrong, since undo should mean "create a state as if the last action had never occured". it's easy to forget one of the implicit things that happen when you change something. if it's an event listener, or updating some kind of cache, there are so many possibilities.

the first thing to do when you start a programming task is deciding your goals. for undo, I had two goals of great importance
  • it must be possible to divide big actions into several small ones. ideally, every action is so small that it only changes one value. in other words, an action should be simple enough that you can find almost all bugs
  • it should be easy to use the system. magic has many cards, and if the majority of card code is related to the undo system, that can't be good. coding cards should be easy, ideally fun, so that many of them get implemented.
these don't really sound very compatible. be very precise and document every action, but don't bother me with it...

the second should be looking for help and reference material, but I just skipped over to the third one: error ;)

my first thought was a tree of actions with a controller actually executing of them. the controller checks that actions are executed in proper sequence. the work would be to create and append the action, and then let the controller execute it. the parent action is passed as a parameter to the modifying method so it knows where to plug the action into the tree:
//from laterna.magica.timestamp.Timestamp

private TimestampFactory f;

private int              timestamp;


...



public void updateTimestamp(Move m) {

    //the constructor plugs the move into the tree

    //with m as its parent

    Move parent = new CompoundMove(m, true);

    //plugs in the move which creates the next timestamp

    //for the factory 
    f.nextTimestamp(parent);

    //plugs in the move which updates this Timestamp's value

    new UpdateTimestampMove(parent);

}



...



private class UpdateTimestampMove extends Move {

    private int               before;  

    public UpdateTimestampMove(Move parent) {

        //Move does the tree stuff

        super(parent);

        before = timestamp;

    }

  

    @Override

    public void make() {

        timestamp = f.getCurrentTimestamp();

    }

  

    @Override

    public void undo() {

        timestamp = before;

    }

}



//from laterna.magica.timestamp.TimestampFactory

private int currentTimestamp;



...



public int getCurrentTimestamp() {

    return currentTimestamp;

}



public void nextTimestamp(Move m) {

    new NextTimestampMove(m);

}



...



private class NextTimestampMove extends Move {

    private int               currentTimestamp;  

    public NextTimestampMove(Move parent) {

        super(parent);      

        currentTimestamp = TimestampFactory.this.currentTimestamp;

    }  

    @Override

    public void make() {

        //Set the timestamp after that of this move as current

        TimestampFactory.this.currentTimestamp = currentTimestamp + 1;

    }

  

    @Override

    public void undo() {

        //Resets to the current timestamp of this move

        TimestampFactory.this.currentTimestamp = currentTimestamp;

    }

}
You know what? a call to updateTimestamp() doesn't even really update the timestamp! and even better, it isn't correct just because of that. the line
currentTimestamp = TimestampFactory.this.currentTimestamp;
is executed when the move is constructed. so, if two such moves are constructed before any of them was executed, they bear the same value.

this is known as "lost update": you expect something to be executed in the order read-compute-write-read-compute-write, but really it's read-read-compute-compute-write-write, or something similar. both compute steps can't take into account the other computation, respectively, and the first write step is plainly overwritten.

this is exactly the problem with the code: what you expect (having the new timestamp stored after the call) ist not what the code does, and such misunderstandings are a major source of bugs. additionally, the second point is almost ignored. this layout requires an additional parameter in every method that does the slightest modification, and a manual "execute" in the controller to do the actual work.

impressing how lines fly if you really have something to talk about! i will continue with this story very soon, until then here's a quick lines-of-code count with cloc.pl:

http://cloc.sourceforge.net v 1.08  T=1.0 s (138.0 files/s, 8966.0 lines/s)
-------------------------------------------------------------------------------
Language          files     blank   comment      code    scale   3rd gen. equiv
-------------------------------------------------------------------------------
Java                138      1497      3126      4343 x   1.36 =        5906.48


Impressing, there are alone 1.5k EMPTY lines in my program ;)

Thursday, January 7, 2010

Complex systems

Previously, I said that business applications were not interesting from a programming perspective. Well, I think this is true in general, but there's probably one big exception: Enterprise Ressource Planning systems. These are pretty complex, allow plugins and customization to a big extent.
Another thing that identifies sophisticated systems is the modelling of not only data but also actions in the software. This is very important in ERP systems, so that decisions are traceable, and the output of employees or departments is visible.

This came to my mind during today's Business Information Management class. It may be a little off-topic, but it's good to see that there's interesting software around besides games.

Monday, January 4, 2010

Pros of Undo

The following is an interesting idea, and it's not one of mine. I can't find the source at the moment, but it was somewhere in the slightlymagic.net forums.

The idea is that Undo implies the recording of each action during a game, and that this information can be used for many different things: Storm counts the number of spells played during the current turn, War Elemental is sacrificed if no opponent was damaged during the turn.

But the most interesting thing is last known information. This is the concept that if a card changes zones, its state directly before it left the zone is used for effects that referenced it earlier. For example Fling: This card requires you to sacrifice a creature, and then takes its power. However, the power is not taken from the graveyard, but from the last time the creature was on the battlefield: If it was equipped, the modified power is taken, even though its power is back to normal in the graveyard.
Last known information is used more often than that: Every ability that triggers from an object leaving the battlefield may require it.

However, there's a difference to Storm and such: Storm only looks into the past, on what happened, but last known information requires you to actually go back, to see the whole game state at that time, so that you can check the card's characteristics. I'm not entirely sure if Undo is suitable for that, but I will definitely think about it.