Thursday, August 1, 2013

Harmonic: Game replication and git?

So I took some time off of trying to implement game replication. Instead, I did some other stuff (like university), and gathered some experience with git. With time, I realized that git, and distributed version control in general, provides exactly those concepts needed for the model of replication I wanted. Looking back at an earlier post on that topic, I can't really say how I expected it to work out. In the end, it turned out that transmitting "unfinished transactions" was a really bad idea; in the end, the very essence of a transaction is that it executes either as a whole or not at all.

Well, anyway, now I had experience with git, and it contained exactly those concepts I needed for my replication as well:
  • a repository of files (objects) in which changes are tracked
  • a history of commits, where commits have a parent/child relation. The main attribute of that relation is what changes happened between those commits
  • branches which point at specific commits and provide a comfortable way of traversing and manipulating the history
  • definition of remote repositories for synchronization of branches
In contrast to the transaction approach I pursued earlier, where the parent/child relationship is in regard to application logic and does not really add to the synchronization capabilities of the framework, this version control approach is based around a tree of commits, where the parent/child relationship is a temporal one, and essential to the framework. The framework is less cluttered with concepts that are not important to it.

Of course, a few things are different: a git repository manages files, essentially byte sequences, while a replication framework manages objects. While these could be interpreted as byte sequences, it doesn't really add to the usability, because objects are usually manipulated on the level of fields and methods. Furthermore, files are organized in a file system with human-chosen names for every single file. Objects simply reside at some location in memory not even the program can control; some other sort of identification is needed. And finally, for file versioning, a human user can try to resolve conflicts. For replication, this is not possible. Conflicts can't be resolved automatically, and as different object store different data, even manual merging could result in inconsistent state.

Luckily, besides the last problem, these can be solved. And for the last problem, usually it shouldn't be a problem in the first place, at least when talking about Magic. Magic is not a game of reaction time, where all players try to do something at the same time, and in the end someone was the earliest. Magic's system of priority defines very clearly which player may take an action at what point, so the game logic can ensure that conflicts do not arise, simply by obeying the rules.

You can take a look at Harmonic if you want. I'm not happy with the name, but I couldn't come up with anything better. I wanted it to sound like multiple independent systems are in sync, like vibrating at the same frequency, or looking the same; I don't think I succeeded, but that's okay as long as it works.

An Entity compares to a file. Entities are objects managed by Harmonic and are identified by a numeric ID. IDs are created by simply incrementing a counter, so creating IDs in different instances of Harmonic is consistent.

An Engine compares to a repository; it is a store of entities. An Engine also manages the different states (analogous to commits), and its current state: in a repository, the files always reflect one specific commit. In the engine, the entities always reflect one state, and the engine knows how to move between the states. Engines are identified with random IDs; as engines are generated on different machines, there is no way to ensure that engine IDs are always different. So, random IDs are used.

States, as mentioned above, compare to commits. Git uses random commit IDs - at least they look random. In Harmonic, the engine ID is part of the state ID. Assuming the engine IDs are different, it's enough to simply increase the ID for each subsequently created state.

Last but not least, Actions and Modifications correspond to the changes that make up a commit. A modification is a single change that is easily reverted, like setting a variable (or creating a new entity ID). An action is a sequence of modifications, so the action can be reverted by reverting the modifications making it up.

In this model, states, containing actions, are transmitted between engines, but modifications are not. Actions are defined by the application, so they may be as small as needed and as big as possible. The modifications making up the action are only created during execution, so they don't need to be transmitted, making large actions more efficient. For example, instead of transmitting that a card is tapped and mana is added to a mana pool, it's now enough to transmit that a mana ability of a land was played.

I like the direction where this is going. I think distributed source control is an elegant concept, and I don't think I did a bad job at catching its essence, so this should turn out to be pretty usable. In fact, while developing Harmonic, I also wrote a game of Tic Tac Toe that uses it, so I have a proof of concept that Harmonic really works as intended in a turn based game.

1 comment:

Anonymous said...

That's an interesting approach.Never thought of a Magic state that way.