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
Sunday, January 24, 2010
Sunday, January 17, 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
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 ;)
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.
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.
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.
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.
Saturday, December 19, 2009
Intelligence
today is nothing about programming, just philosophic thoughts about the concept of Intelligence.
It's hard define intelligence, but one thing that for sure sets us apart from computers (currently) is our extreme potential of learning. No matter if it's the complex rules, or the uncounted combos and strategies, we play magic without any problems. To get a computer to play magic, we need complex programs and have to manually teach it what is good and what bad play.
But intelligence is nothing bound only to the brain. The brain is a very complex structure of neurons that, every one on its own, only does basic tasks. however, the sum is much greater than its parts.
we're able to let computers perform basic operations, so we should also be able, in principle, to develop a really intelligent program.
A nice example is Conway's Game of Life, a cellular automaton with a very simple set of rules. For every state, the next "generation" can be calculated by applying the rules. By this, it's possible to encode programs into the pattern. In principle, this game is mighty enough to do any calculation - even intelligence!
And now, we look at that gigantic pattern as it evolves and changes. It's not able to communicate with us directly, but with the right understanding of what the movements mean, we could "read its mind"... maybe it's thinking about its creator?
It's hard define intelligence, but one thing that for sure sets us apart from computers (currently) is our extreme potential of learning. No matter if it's the complex rules, or the uncounted combos and strategies, we play magic without any problems. To get a computer to play magic, we need complex programs and have to manually teach it what is good and what bad play.
But intelligence is nothing bound only to the brain. The brain is a very complex structure of neurons that, every one on its own, only does basic tasks. however, the sum is much greater than its parts.
we're able to let computers perform basic operations, so we should also be able, in principle, to develop a really intelligent program.
A nice example is Conway's Game of Life, a cellular automaton with a very simple set of rules. For every state, the next "generation" can be calculated by applying the rules. By this, it's possible to encode programs into the pattern. In principle, this game is mighty enough to do any calculation - even intelligence!
And now, we look at that gigantic pattern as it evolves and changes. It's not able to communicate with us directly, but with the right understanding of what the movements mean, we could "read its mind"... maybe it's thinking about its creator?
Thursday, December 17, 2009
Undo
Imagine we are in such a good mood that we forget all our sorrows, make big business, and one day we notice that our earth isn't very well. We better had implemented undo so that the tropic rain forest is up and fossil oil is down again...
that's one of the hard parts with undo: the consequences of your action must be undoable. the second is not to forget anything.
What are the consequences of playing a card? you tap your lands, pay the costs, and put the spell on the stack. so to reverse that, is it enough to take the card back and untap your lands? in very certain cases, maybe, but not generally. a single triggered ability might crash your concept. there might even be abilities that triggered from untapping lands, because of the undo!
the second point is the other side of the same medal. if you view a triggered ability not as the consequence of playing a spell, but a different thing, the matter goes from "undoing all consequences" to "not overseeing other actions caused by playing the spell". while it effectively means the same - really going back to that same state - it's good to see the different aspects
in my opinion, the deeper you look into the game, the easier it is not to forget an action. if you have looked into the comprehensive rules a few times, you can notice how detailed everything is, timestamps, priority and so on. if we don't only look at huge things:
that's one of the hard parts with undo: the consequences of your action must be undoable. the second is not to forget anything.
What are the consequences of playing a card? you tap your lands, pay the costs, and put the spell on the stack. so to reverse that, is it enough to take the card back and untap your lands? in very certain cases, maybe, but not generally. a single triggered ability might crash your concept. there might even be abilities that triggered from untapping lands, because of the undo!
the second point is the other side of the same medal. if you view a triggered ability not as the consequence of playing a spell, but a different thing, the matter goes from "undoing all consequences" to "not overseeing other actions caused by playing the spell". while it effectively means the same - really going back to that same state - it's good to see the different aspects
in my opinion, the deeper you look into the game, the easier it is not to forget an action. if you have looked into the comprehensive rules a few times, you can notice how detailed everything is, timestamps, priority and so on. if we don't only look at huge things:
- play a card, triggering an ability
- tap the land for mana
- an ability triggers
- the ability is put on the stack
- you receive priority again
Saturday, December 12, 2009
Program Architecture
A program's architecture is very important. Like with a real house, it literally prevents the program from breakng down. If you don't make enough preparations (walls not solid enough), your program might not be able to have the features you want (a billard table). If you want to place a billard table in your house, you better make sure it can bear one.
A very common architecture in enterprise- and web-applications is the Multitier-Architecture. in this architecture, there are multiple tiers that communicate with each other and add abstractions. a very popular separation of tiers is the following (from bottom to top)
On the other hand, games are by definition complex. It's what makes the game fun - easy to scope, but deep in possibilities. Look at Settlers of Catan, you know what I mean.
So, this "primitive" multitier architecture is perfect for business applications, but not for a game like magic. I have, however, some architecture in mind:
All of these parts are fairly complicated:
A very common architecture in enterprise- and web-applications is the Multitier-Architecture. in this architecture, there are multiple tiers that communicate with each other and add abstractions. a very popular separation of tiers is the following (from bottom to top)
- Data tier
This tier is not much more than a database server, responsible for storing and retrieving data. - Logic tier
The logic tier communicates with the data tier and processes the information. For example, it could sum up the prices of a shopping cart. - Presentation tier
This is where the user comes into play. The presentation tier doesn't know the data tier directly, it only calls the logic tier to get structured information. It then transforms that information into something the user might like, like an HTML-Page.
On the other hand, games are by definition complex. It's what makes the game fun - easy to scope, but deep in possibilities. Look at Settlers of Catan, you know what I mean.
So, this "primitive" multitier architecture is perfect for business applications, but not for a game like magic. I have, however, some architecture in mind:
- The game state includes all of the cards with their abilities, the zones, turns and phases, the players and even a random number generator.
The random number generator should make it possible have two games being absolutely identical, which allows for duplicating a game for network play, saving, replaying and so on. The generator also has to support the "Undo" i described. - The rules engine is the classic of a complicated thing. I don't think it's possible to fully separate this from the game state. For example you control a Glorious Anthemn. Is the +1/+1 bonus part of the game state or of the rules? However, other parts can clearly be separated: A player's starting life and hand size in Vanguard, or alternate winning conditions, and the ability to play the general in Elder Dragon Highlander
- The payer abstraction in the next stage is different from the one in the game state. the state's player's purpose is to store his information, like life, cards and so on. In this stage, a player's purpose is to make decisions. The way of making a decision is of course different for the three types of players.
- You yourself want to see the game state in a nice GUI.
- The AI "only" needs to access the game state and rate its possibilities
- A network player has his own GUI at his side of the connection, but what you see is only the decision he sends to you, which is enough because the game states are identical on both sides.
Subscribe to:
Posts (Atom)