As so often in programming, one big question arose when I worked on my Undo/Replication framework: What is an entity, and what is a value?
I use the word entity to make clear that I mean something different from objects. An object is something identified by an address pointer, whereas for a primitive value, its bytes in memory directly represent the value instead of an address. What I mean with entity/value is best explained by an example from databases:
Suppose you have a database table storing the data of a company's employees. There is a surname, a prename, a birth date, and so on. Besides others, there's an address. The simplest approach is to handle each of these items as a table column: Surname and prename are strings, the birthdate uses a special date column type. The address can also be simply taken as a string, but there are other ways:
An address is composed of a street name, a number, probably also an appartment number, country, state etc. It could be beneficial to store all these data in a table on its own, give it an ID (the database way of saying address), and only reference this ID in the employee table.
Don't forget the third way! You could use all those columns, but put them directly into the employee table, so there would be prename, surname, birth date, street, stree no., appartment no., etc.
What's the best? Of course, it depends! Variant one is easy to use, but lacks intrinsic validity checks: When the database doesn't know that something should be an (appartment) number, how should it check it's even a number? Variant two can handle a very specific case "better": two workers have the same address. In this case, the same ID can be referenced multiple times, so that both employees not only have equal addresses but also have the same one. In this particular case, the benefit is not too big, but there are use cases where it's important that something can be referenced. About the third, it really combines the downsides of the both above... I personally see no benefit in using it. It there are, I'm sorry I didn't see them.
Now, what should have triggered your attention was the word "ID". As soon as something has an identity, it's an entity. Note how the prename is a String, which is an Object type in Java, but only a value. On the other hand, the address in case 2 has an identifier and is an entity.
And now we're back: What I do is to assign IDs to the objects I want to replicate. The objects have values which can be changed, and I transmit changes like "property XY of object 01 changed from 'ab' to 'cd'."
And now the big question: what about collections? Should it be "element 'ab' was added to list 01" (i.e. they are entities) or "element 'ab' was added to list XY of object 01?"
Showing posts with label Undo. Show all posts
Showing posts with label Undo. Show all posts
Tuesday, January 10, 2012
Saturday, January 7, 2012
Replicating Game States - JGroups
So now I've got it. My goals in implementing Replication was to keep it out of the core functionality while still making it easy to use without worrying about replication yourself. How do you do that? By providing a general interface to other software (in my case, that's a listener) and implementing a specific one for the task at hand.
So my History class, which stores all changes to the managed objects, has a listener for two possible events: A new modification is executed; and the "current" state is moved somewhere else (e.g. undoing something.) My replication listener does not support undo right now, because I haven't figured out how to best identify a state (which is where the program is going) yet, but that should be easy. The other thing, executing modifications, does work. That means, whenever a modification is executed locally, it is sent over the network so that the partner(s) can execute it too.
The only downside is that the partners also "execute it locally", so I had to use a trick to suppress resending these received modifications. And it works pretty well:
//initialization code
final History h = createHistory(createKey("test-history"));
final JChannel channel = new JGroupsReplicationListener(h) {
@Override
public void receive(Message msg) {
Modification m = (Modification) deserialize(msg.getBuffer());
if(m instanceof Creation) id = ((Creation) m).getId();
super.receive(msg);
}
}.getChannel();
//executing the actions (creating an object)
h.pushHistoryForThread();
try {
TestBean t = (TestBean) h.getObjectStore().get(Creation.create(new TestBean()));
t.setA(1);
t.setB(1);
} finally {
h.popHistoryForThread();
}
//printing the results
System.out.printf("current state: %s%n", h.getObjectStore().get(id));
I made this test a GUI application so that I can control the timing on multiple virtual machines. The public void receive(Message msg)seen above is only needed for this Test, again. It's not necessary to do something like that to get the replication. The code in the middle looks exactly the same as the example last time, except I haven't hidden some of the details in a setTest() method.
Now what's probably the most interesting is how the networking works; let me tell you, I didn't write any! As hinted by me before, and in the title of course, is that I have tried JGroups to do this. In JGroups, you create Channels and let them join into a cluster; all channels in the cluster can receive and send messages, either to only only one recipient, or to all at the same time. JGroups provides a configurable protocol stack that takes care of reliability, synchronity and such things. For my tests, I have used a UDP-based protocol stack. For wide-area connections, a TCP-based approach is probably easier.
So my History class, which stores all changes to the managed objects, has a listener for two possible events: A new modification is executed; and the "current" state is moved somewhere else (e.g. undoing something.) My replication listener does not support undo right now, because I haven't figured out how to best identify a state (which is where the program is going) yet, but that should be easy. The other thing, executing modifications, does work. That means, whenever a modification is executed locally, it is sent over the network so that the partner(s) can execute it too.
The only downside is that the partners also "execute it locally", so I had to use a trick to suppress resending these received modifications. And it works pretty well:
//initialization code
final History h = createHistory(createKey("test-history"));
final JChannel channel = new JGroupsReplicationListener(h) {
@Override
public void receive(Message msg) {
Modification m = (Modification) deserialize(msg.getBuffer());
if(m instanceof Creation) id = ((Creation) m).getId();
super.receive(msg);
}
}.getChannel();
//executing the actions (creating an object)
h.pushHistoryForThread();
try {
TestBean t = (TestBean) h.getObjectStore().get(Creation.create(new TestBean()));
t.setA(1);
t.setB(1);
} finally {
h.popHistoryForThread();
}
//printing the results
System.out.printf("current state: %s%n", h.getObjectStore().get(id));
I made this test a GUI application so that I can control the timing on multiple virtual machines. The public void receive(Message msg)seen above is only needed for this Test, again. It's not necessary to do something like that to get the replication. The code in the middle looks exactly the same as the example last time, except I haven't hidden some of the details in a setTest() method.
Now what's probably the most interesting is how the networking works; let me tell you, I didn't write any! As hinted by me before, and in the title of course, is that I have tried JGroups to do this. In JGroups, you create Channels and let them join into a cluster; all channels in the cluster can receive and send messages, either to only only one recipient, or to all at the same time. JGroups provides a configurable protocol stack that takes care of reliability, synchronity and such things. For my tests, I have used a UDP-based protocol stack. For wide-area connections, a TCP-based approach is probably easier.
Thursday, January 5, 2012
Replicating Game States - Working code!
Before you get too excited - no, there's no multiplayer yet (well, who would have guessed that...). There is, however, working code for undoing and redoing actions (even with multiple, branching histories), and even for replicating the state on multiple virtual machines.
The key to make such a library is that it looks like ordinary Java code from the outside, so that others can use your code without wondering why it looks so weird. Let's take a look:
//Test t = new Test(); is an attribute
//replaced angle with square brackets because of HTML markup
List[StateStamp] states = new ArrayList[StateStamp]();
History h = createHistory(createKey("test"));
h.pushHistoryForThread();
try {
states.add(h.getCurrentState()); // 0
print();
setTest(t);
states.add(h.getCurrentState()); // 1
print();
getTest().setA(1);
states.add(h.getCurrentState()); // 2
print();
getTest().setB(1);
states.add(h.getCurrentState()); // 3
print();
Deletion.delete(getTest());
states.add(h.getCurrentState()); // 4
print();
h.goToState(states.get(3));
print();
h.goToState(states.get(2));
print();
h.goToState(states.get(1));
print();
h.goToState(states.get(0));
print();
} finally {
h.popHistoryForThread();
}
It's probably easy to to guess that print(); prints the current state of the test object. Besides that, the only code that looks different from normal operations is marked in bold. Most of it is only necessary for this test case: storing the previous states so that you can go back. Really mandatory is only the colored code (and the actual functional code of course, but that doesn't count.)
Of course, a history for the modifications must be created. Then, the history is set for the thread: Code running in the thread (that is, everything in this method, and nothing more) can access the history without passing it as a parameter (which would make using the library awkward) or declaring it as a static variable somewhere (which is ugly from an architecture standpoint.) Everything after this is wrapped in try/finally, so that the last method is not skipped in case of an exception: this removes the association of the history with the current Thread.
Of course, implementing setTest(), setA() etc. is different from a usual simple setter. But the point here is that using the code is as simple as shown here. The result is this:
Test@732A54F9[a=0, b=0] not in store
Test@7A6D084B[a=0, b=0] in store
Test@7A6D084B[a=1, b=0] in store
Test@7A6D084B[a=1, b=1] in store
Test@7A6D084B[a=1, b=1] not in store
Test@15301ED8[a=1, b=1] in store
Test@15301ED8[a=1, b=0] in store
Test@15301ED8[a=0, b=0] in store
Test@15301ED8[a=0, b=0] not in store
You see here how the test object runs through different states up to its deletion, then goes back to its initial state. What's not shown here, but is working, is adding another branch to this history. Of course, the actual objects have only one state at a time, but the history can be switched arbitrarily between multiple histories:
This is the actual test case I ran: I went back to the state after creating the test object, changed its a value, and then switched over to the state before, and then after, deleting the test again.
I have code for replication of states going, but it's not yet as clean as for undo: a lot of handling is necessary for the network, which should be transparent to the user. I'll show it once I'm finished, but in the meantime you can look here.
The key to make such a library is that it looks like ordinary Java code from the outside, so that others can use your code without wondering why it looks so weird. Let's take a look:
//Test t = new Test(); is an attribute
//replaced angle with square brackets because of HTML markup
List[StateStamp] states = new ArrayList[StateStamp]();
History h = createHistory(createKey("test"));
h.pushHistoryForThread();
try {
states.add(h.getCurrentState()); // 0
print();
setTest(t);
states.add(h.getCurrentState()); // 1
print();
getTest().setA(1);
states.add(h.getCurrentState()); // 2
print();
getTest().setB(1);
states.add(h.getCurrentState()); // 3
print();
Deletion.delete(getTest());
states.add(h.getCurrentState()); // 4
print();
h.goToState(states.get(3));
print();
h.goToState(states.get(2));
print();
h.goToState(states.get(1));
print();
h.goToState(states.get(0));
print();
} finally {
h.popHistoryForThread();
}
It's probably easy to to guess that print(); prints the current state of the test object. Besides that, the only code that looks different from normal operations is marked in bold. Most of it is only necessary for this test case: storing the previous states so that you can go back. Really mandatory is only the colored code (and the actual functional code of course, but that doesn't count.)
Of course, a history for the modifications must be created. Then, the history is set for the thread: Code running in the thread (that is, everything in this method, and nothing more) can access the history without passing it as a parameter (which would make using the library awkward) or declaring it as a static variable somewhere (which is ugly from an architecture standpoint.) Everything after this is wrapped in try/finally, so that the last method is not skipped in case of an exception: this removes the association of the history with the current Thread.
Of course, implementing setTest(), setA() etc. is different from a usual simple setter. But the point here is that using the code is as simple as shown here. The result is this:
Test@732A54F9[a=0, b=0] not in store
Test@7A6D084B[a=0, b=0] in store
Test@7A6D084B[a=1, b=0] in store
Test@7A6D084B[a=1, b=1] in store
Test@7A6D084B[a=1, b=1] not in store
Test@15301ED8[a=1, b=1] in store
Test@15301ED8[a=1, b=0] in store
Test@15301ED8[a=0, b=0] in store
Test@15301ED8[a=0, b=0] not in store
You see here how the test object runs through different states up to its deletion, then goes back to its initial state. What's not shown here, but is working, is adding another branch to this history. Of course, the actual objects have only one state at a time, but the history can be switched arbitrarily between multiple histories:
This is the actual test case I ran: I went back to the state after creating the test object, changed its a value, and then switched over to the state before, and then after, deleting the test again.
I have code for replication of states going, but it's not yet as clean as for undo: a lot of handling is necessary for the network, which should be transparent to the user. I'll show it once I'm finished, but in the meantime you can look here.
Saturday, December 31, 2011
Replicating Game States - revised
The last time I talked about my Undo system, which should also allow multiplayer through its structure of storing actions that can be transmitted over the network, was a long time ago. I don't want to directly talk about this today; you'll see.
Especially one thought has gone through my mind in the last weeks: Replicating a state across the network properly is nothing specific to Magic - so why do I implement it in the Core of Laterna Magica? I thought about it, and there doesn't seem to be a specific reason for doing so. Another result of that thought was that there are probably complete libraries out there which do exactly what I want. Well, that's unfortunately not the case, so I'm stuck/blessed with implementing it myself.
I haven't really gotten into development yet. I have a rough skeleton, but no really fancy functionality yet. But I'm having my thoughts. I think stepping away from the application's needs and looking at the general requirements of such a library help in developing a better piece of software. I haven't done this for my current undo system, which I find kind of disappointing. Normally, I don't have problems with spotting such generalizations.
Okay, back to topic: what does a library for state replication need?
When the state replication system transmits these two modifications, the receiver does its own set operation on bar, because foo has changed. Then, the original set operation is transmitted, setting bar another time (fortunately to the same value).
Until now, I thought that this particular case is just me wanting to be clean. Now that I wrote this, I even see more problems, real ones: If we're able to detect conflicts, then this shouldn't even run through, because the last modification should be the second but really is the third. And even if we don't: this second modification in State 2 needs to be transmitted to State 1. Even if that doesn't result in errors, which is likely, it will waste network bandwidth at least.
Now for the real problem I spotted here before: Let's replace "bar = 1" with "put a token onto the battlefield". Setting a number multiple times is redundant, but creating an Object is not. There is a very definite difference between one and two tokens, you know!
Now, let's solve these problems. There are basically two ways that can lead to this problem: a complex setter, and events.
In the first case, the setter for foo includes code that calls the setter of bar. The problem here is that our replication library can't know that setting foo doesn't really do this: it actually sets foo and bar. So, refactor foo's setter so that it does only what it says, and not more. Hide this from the user by adding another method doSomething() that does what he previously did by setting foo.
Second is events. In this case, the change to foo fires an event that leads to bar being changed as well. In this case, the simple answer that is not so simple to implement is: don't fire events while replicating the state. The more complex answer that is simpler to implement is that this is similar to the first case: Don't write events that fire on state changes and perform state changes. Instead, fire a new Event in doSomething() that triggers the change. As the state replication won't call doSomething(), everything is fine.
Both solutions shown here require changes in the application, not in the library. This might seem bad, but it's actually logical: The library may sanely assume that variables change and objects are created, and that it may do that by itself as well. If the state does not fulfill the contract that it just contains values, but instead employs complex logic that the library can't predict, the task is impossible. The library needs some way to change values without triggering application logic.
Thanks for staying wiht me, and a happy new year to all of you!
Especially one thought has gone through my mind in the last weeks: Replicating a state across the network properly is nothing specific to Magic - so why do I implement it in the Core of Laterna Magica? I thought about it, and there doesn't seem to be a specific reason for doing so. Another result of that thought was that there are probably complete libraries out there which do exactly what I want. Well, that's unfortunately not the case, so I'm stuck/blessed with implementing it myself.
I haven't really gotten into development yet. I have a rough skeleton, but no really fancy functionality yet. But I'm having my thoughts. I think stepping away from the application's needs and looking at the general requirements of such a library help in developing a better piece of software. I haven't done this for my current undo system, which I find kind of disappointing. Normally, I don't have problems with spotting such generalizations.
Okay, back to topic: what does a library for state replication need?
- There needs to a notion of what has happened on a higher, application level: Transactions
- Transactions consist of atomic modifications, which are the core of the state
- Optionally, they may also consist of other sub-transactions
- Transactions and modifications must be transmittable over the network. If the whole state is represented as a tree of subtransactions under a root-transaction, then there's of course the need to transmit unfinished transactions. Otherwise, it might be enough to transmit finished transactions. I think that the first is generally more flexible. It might be a good idea to give the user a chance to mark transactions as atomic so that it's only transmitted when it is finished.
- Probably the most interesting requirement is that, of course, after transmitting the state, both/all states have to be the same!
- The system should be able to detect that there are state conflicts and that a transmitted transaction can't be carried out locally.
- When we're already speaking of it, it's probably nice (but also probably impossible, so see that as an utopic remark) to resolve/merge such conflicts.
When the state replication system transmits these two modifications, the receiver does its own set operation on bar, because foo has changed. Then, the original set operation is transmitted, setting bar another time (fortunately to the same value).
Until now, I thought that this particular case is just me wanting to be clean. Now that I wrote this, I even see more problems, real ones: If we're able to detect conflicts, then this shouldn't even run through, because the last modification should be the second but really is the third. And even if we don't: this second modification in State 2 needs to be transmitted to State 1. Even if that doesn't result in errors, which is likely, it will waste network bandwidth at least.
Now for the real problem I spotted here before: Let's replace "bar = 1" with "put a token onto the battlefield". Setting a number multiple times is redundant, but creating an Object is not. There is a very definite difference between one and two tokens, you know!
Now, let's solve these problems. There are basically two ways that can lead to this problem: a complex setter, and events.
In the first case, the setter for foo includes code that calls the setter of bar. The problem here is that our replication library can't know that setting foo doesn't really do this: it actually sets foo and bar. So, refactor foo's setter so that it does only what it says, and not more. Hide this from the user by adding another method doSomething() that does what he previously did by setting foo.
Second is events. In this case, the change to foo fires an event that leads to bar being changed as well. In this case, the simple answer that is not so simple to implement is: don't fire events while replicating the state. The more complex answer that is simpler to implement is that this is similar to the first case: Don't write events that fire on state changes and perform state changes. Instead, fire a new Event in doSomething() that triggers the change. As the state replication won't call doSomething(), everything is fine.
Both solutions shown here require changes in the application, not in the library. This might seem bad, but it's actually logical: The library may sanely assume that variables change and objects are created, and that it may do that by itself as well. If the state does not fulfill the contract that it just contains values, but instead employs complex logic that the library can't predict, the task is impossible. The library needs some way to change values without triggering application logic.
Thanks for staying wiht me, and a happy new year to all of you!
Sunday, December 26, 2010
Distributed objects, undo and proxies
I have mentioned a couple of times that the undo system should enable multiplayer games, because every action is encapsulated as an object which can be transmitted over the network and executed there.
Well, that's only half of the story. For the action to do something, it needs references to the affected objects. This means that transmitting an action also means transmitting the dependent objects; in the worst case, the whole game-state is transmitted every time, because all of the objects are interdependent.
And even so, the desired effect is not achieved: the action operates on the transmitted game state, not the one which belongs to the communication partner. The same is true for writing a game state to file, to restore it at a later time. I have been aware of this flaw for quite some time, but ignored it as a problem to the distant future. Now that I have to rewrite the characteristics system anyway, I might as well face this problem too.
One possible solution is proxy objects: A proxy object acts as the communication link between a client and a provider. Proxy objects are commonly used for distributed systems, where the proxy implements the intricacies of accessing the provider over the network.
My use would be similar; instead of passing objects directly to an action, only the proxy is passed. The proxy communicates with the actual object, but instead of transmitting it over the network, the proxy is attached to the other side's equivalent of the object.
This approach has its own downsides, of course: Java has a built-in proxy mechanism which makes it relatively easy to implement transparent proxy classes. It requires to use interfaces for everything, which isn't automatically a bad thing. Designing the interface is moreso:
RMI, Remote Method Invocation, uses proxy classes for transparent - well - remote method invocation. Because network communication can go wrong, this means that every method in those interfaces must declare RemoteException as a possible error. Declaring this exception seems very dirty, because it doesn't have anything to do with what the interface is about. Not declaring it takes me the (direct) possibility to use RMI for a central game state instead of duplicated game states. A workaround would be to use another proxy around the RMI proxy, which only throws an unchecked exception. This seems dirty again, but better than declaring protocol-specific exceptions in an application-level interface.
"Re-attaching" a proxy to the game state on another machine is the next problem: somehow, the transmitted proxies must get access to the new gamestate on the receiver's side. I think that a custom ObjectInputStream which provides this information may cover that.
The third, and probably hardest problem, is the question of object identity: How do I identify identical objects on both sides, so that the right object is attached at the receiver side? RMI's advantage in this regard is that it's not even necessary to do that, because objects are not duplicated. I have yet to find a solution for this problem, wish me luck!
Well, that's only half of the story. For the action to do something, it needs references to the affected objects. This means that transmitting an action also means transmitting the dependent objects; in the worst case, the whole game-state is transmitted every time, because all of the objects are interdependent.
And even so, the desired effect is not achieved: the action operates on the transmitted game state, not the one which belongs to the communication partner. The same is true for writing a game state to file, to restore it at a later time. I have been aware of this flaw for quite some time, but ignored it as a problem to the distant future. Now that I have to rewrite the characteristics system anyway, I might as well face this problem too.
One possible solution is proxy objects: A proxy object acts as the communication link between a client and a provider. Proxy objects are commonly used for distributed systems, where the proxy implements the intricacies of accessing the provider over the network.
My use would be similar; instead of passing objects directly to an action, only the proxy is passed. The proxy communicates with the actual object, but instead of transmitting it over the network, the proxy is attached to the other side's equivalent of the object.
This approach has its own downsides, of course: Java has a built-in proxy mechanism which makes it relatively easy to implement transparent proxy classes. It requires to use interfaces for everything, which isn't automatically a bad thing. Designing the interface is moreso:
RMI, Remote Method Invocation, uses proxy classes for transparent - well - remote method invocation. Because network communication can go wrong, this means that every method in those interfaces must declare RemoteException as a possible error. Declaring this exception seems very dirty, because it doesn't have anything to do with what the interface is about. Not declaring it takes me the (direct) possibility to use RMI for a central game state instead of duplicated game states. A workaround would be to use another proxy around the RMI proxy, which only throws an unchecked exception. This seems dirty again, but better than declaring protocol-specific exceptions in an application-level interface.
"Re-attaching" a proxy to the game state on another machine is the next problem: somehow, the transmitted proxies must get access to the new gamestate on the receiver's side. I think that a custom ObjectInputStream which provides this information may cover that.
The third, and probably hardest problem, is the question of object identity: How do I identify identical objects on both sides, so that the right object is attached at the receiver side? RMI's advantage in this regard is that it's not even necessary to do that, because objects are not duplicated. I have yet to find a solution for this problem, wish me luck!
Sunday, August 8, 2010
Last Known Information with Undo
Last Known Information is one of the hardest parts of the Magic rules to implement. It is important when handling effects that use a card that changed zones, for example Persist ("When this permanent is put into a graveyard from the battlefield, if it had no -1/-1 counters on it, return it to the battlefield under its owner's control with a -1/-1 counter on it.") or Swords to Plowshares ("Exile target creature. Its controller gains life equal to its power."). These effects happen when the card is already in the graveyard/exile, but need information of the card when it was on the battlefield. For us, this seems very natural, but from a programming point of view, we have to save the relevant values long enough so that interested effects can look it up.
The two main questions of this concept are already in the previous sentence:
Well, when we talk about time travel, of course there are problems: We have to get back to the future after looking up the needed information, but this is only possible if we didn't change history: The game will discard any actions that lie in the future if we change the past. Unfortunately, even simply looking up the power of a creature will change the past, because it results in evaluating continuous effects etc.
Well, I have another science fiction reference up my sleeve to save the day: If we must not change history, "simply" do it in a parallel universe: Create an exact copy of the game up to the point in the past we need to look up the information, then use it in our regular space-time continuum.
So much for the theory of time travel and parallel universes, the reality is a bit more complex, though. I think I can eventually work it out so that this is possible. This is also the way I expect a potential AI to work: Try out multiple variants in a parallel universe and do the best in the real universe.
But right now, only regular time travel is possible, with the limits set by changing history. The problem is that I can't transfer actions between games yet: If you tap a creature, I can't copy that action and execute it in another game, because the action stores the permanent that was tapped, which is exclusively associated with that game. The solution probably needs hashing or another type of identifier associated with each part of the game.
I hope you enjoyed the short Science-Fiction sequence. I definitely did, and I would never have guessed to talk about Time Travel and Alternate Universes as a serious metaphor for a programming problem.
The two main questions of this concept are already in the previous sentence:
- What values are "relevant"?
- What is "long enough"?
Well, when we talk about time travel, of course there are problems: We have to get back to the future after looking up the needed information, but this is only possible if we didn't change history: The game will discard any actions that lie in the future if we change the past. Unfortunately, even simply looking up the power of a creature will change the past, because it results in evaluating continuous effects etc.
Well, I have another science fiction reference up my sleeve to save the day: If we must not change history, "simply" do it in a parallel universe: Create an exact copy of the game up to the point in the past we need to look up the information, then use it in our regular space-time continuum.
So much for the theory of time travel and parallel universes, the reality is a bit more complex, though. I think I can eventually work it out so that this is possible. This is also the way I expect a potential AI to work: Try out multiple variants in a parallel universe and do the best in the real universe.
But right now, only regular time travel is possible, with the limits set by changing history. The problem is that I can't transfer actions between games yet: If you tap a creature, I can't copy that action and execute it in another game, because the action stores the permanent that was tapped, which is exclusively associated with that game. The solution probably needs hashing or another type of identifier associated with each part of the game.
I hope you enjoyed the short Science-Fiction sequence. I definitely did, and I would never have guessed to talk about Time Travel and Alternate Universes as a serious metaphor for a programming problem.
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
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 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 ;)
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.
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
Subscribe to:
Posts (Atom)