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!

Thursday, November 18, 2010

Rule-Based Programming and Magic

Although I don't have time to work on Laterna Magica right now, I have the occasional thought on it. Before the big pause, I noticed a major flaw in my implementation of characteristics. The problem is that every read-operation on the characteristics refreshes the status. This status change means that only in-game operations may read characteristics; I mentioned a couple of times that, to achieve independence of game and GUI, the GUI must not change the game state.

...and what does this mean in the context of rules-based programming? Let me first explain that term in greater detail: In the last months, we familiarized with the (unfortunately commercial) rule-based programming language "JESS", its interpreter is implemented in Java.
A rule based system operates on a fact base. Facts can be roughly compared to variables or objects. The second important part is, of course, the rules. Rules operate on facts and may be activated whenever a fact changes. An activated rule is not immediately executed! Instead, a call to run() causes the engine to process the activated rules, which may in turn change facts and activate even more rules.

And now combine the two thoughts: The reason for me to re-evaluate characteristics every time they are accessed was to make sure no out-of-date data is used. With a rule-based system keeping track of the game state, this becomes unnecessary, because the rule system would ensure that characteristics are refreshed when necessary. And without the need to do permanent refreshes, there's no problem with the GUI reading characterics.

If anyone knows some free, Java-based rules engines, this would be a great input. I haven't done any research on this, and I won't do it until I come around programming LM again, but concrete user stories and recommendations are always great to hear.

Handling Arrays in web services

I'm currently working on an assignment to implement a simple web service, and started using the following tutorial: http://www.theserverside.de/webservice-in-java/ (German). I'm not sure if that's a general problem, but the auto-generated WSDL specification, and java's wsimport code generator handle arrays... strangely. So here is my ArrayHelper class. I was searching for something along its lines, but found nothing.

The problem: The code generator generates classes like StringArrayArray instead of using java String[][] objects. A StringArrayArray object is merely a wrapper around a List<StringArray>, and so on.

The solution: Use reflection to determine what type of wrapper you have to deal with (check the generic parameter of the list) and recursively convert the wrapped lists into real arrays.

The file: is free to use and modify, comes without any kind of warranty, and is available here. It was actually tested with String[][]; I'd strongly suggest testing with primitive types before using it. please leave comments if any problems ocurr. The code is nearly 130 lines in total, 70 lines being comments (recursion, you know).

Sunday, October 31, 2010

First successes in robotics

Two months in this school year have passed, and a lot has happened. Most of our project work up to now was just research; we evaluated the JADE framework for distributed agent systems, the rule based language JESS, and the Protégé Ontology API, which all are Java based and can therefore run on the CBC controller.

On friday, Dr. David Miller arrived at Vienna, and our teacher wanted to have a robot prototype to show. On wednesday, we met at university to build something out of lego... which proved to be difficult, because the collection of Lego parts was very limited, and we hardly managed to connect a single motor to the lego gears. So we met at my place the next day and built a robot out of Fischertechnik which is, in my opinion, clearly superior to Lego. The result was this robot:


Each of the tracks is powered by two motors, although that didn't seem to bring much of a performance gain. The thing on top, in case you didn't recognize it, is a camera, and the robot's objective was to follow a blue ball.

We actually programmed the robot twice; once with C, which is natively available on the controller, and once with Java, which was installed on our controller at the university during summer. My part was the Java program, and I tried to add a few abstractions to later reuse the code.
  • As each of the tracks is powered by multiple motors, I added an abstraction for the motors, to combine multiple physical motors into one logical motor
  • Next was the drive and navigation. Our robot is tracked, so its steering uses the speed difference of the tracks. I tried to keep the theoretical possibility to use another type of steering, although some adaption is probably necessary.
  • Last but not least, the robot's construction may make it more convenient to wire it in a specific way. What actuators and sensors are on which pins can be configured, so that a new construction does not necessarily mean to change the program. Especially imagine how many times a motor may be accessed in the program, and what it would mean to change all the occurrences.
Now this is just foundation code, and the real logic, checking the camera and following the ball, was simply implemented in the main method in a loop. And that's the glorious result:


For those of you that don't understand the quiet, german comments: We have adjusted the camera for our lighting, and it already got pretty dark. For the video, we turned on the lights, and suddenly, the robot stopped recognizing the ball. So, the first thing you see in the video is me turning off the lights again, and then you can hear my teacher commenting on it^^

Saturday, October 2, 2010

Ontologies

One part of our project will be to build an ontology for our robot. An ontology is a model of the world, condensed into the relevant parts for a given problem. For example, our robot will have motors, digital and analog sensors, and so on. These would be represented in the ontology, but possibly more, like a simple model of the robot's surrounding: Hills, obstacles and so on.

At school, we're using a really easy-to use Ontology editor called Protégé; it also has some nice visualization features. The result might be an "owl" file; a standard xml file for ontologies that can easily be accessed from a program.

I'm just starting to learn this topic and not quite sure what the advantage of an ontology as opposed to e.g. an object graph is. Both model reality in some way, both are hierarchical and have properties, reference objects and so on.

One of the differences is that an ontology also models the objects, the individual instances. For example, you might model a city's subway network. In a class hierarchy, you could only model things like Subway, Station and whatever is needed for the model. Creating the objects will either mean hardcoding them or writing some code that reads the objects from a file; the former is inflexible and the second is error-prone and redundant. An ontology can (and will) contain the explicit lines and stations of the city along with the definitions, and neither of the above is needed.

The second diference is its position in context with reasoning. Reasoning is the main reason for the existence of ontologies, and therefore there are a few (hopefully good) APIs out there that make it easy to write statements like "how many stations are there on subway line 1?" or "should I go left or right around the obstacle to reach my target faster?"

And this is where we get to rule-based programming. Pulling conclusions out of the ontology is half of the work of writing a rule. See you next time!

Monday, September 20, 2010

Delaying Laterna Magica: Graduation Project

School has totally got me now. We spent last week in Carinthia and focused completely on the project. It was a great experience and we laid much of the foundation work. Today, we got even more long-term assignments, and my impression is that the difference to our graduation project is not the amount of work, but that the teachers don't give us as much time...

Okay, enough of that. What I really want to tell today is two things. Bad news are always first, so let's get it out of the way: I won't have much (if any) time to work on Laterna Magica in the near future.
And the reason is already the good news: I have a veeery interesting graduation project together with 3 colleagues: We're building and programming a robot to attend a robot competition in the USA.

Okay, to make my excitement clear, let's break this down:
We're building a robot
I think this is pretty clear. The competition consists of a few challenges, and the robot has to reflect these hardware-wise to show optimal performance. The challenges are presented at the end of October; an employee of the competiton's organization visits us personally, because we'd be the first team from Europe to attend.
We're programming a robot
This is probably the most interesting part of it. Our project is sponsored by TU Wien, Vienna's technical university, and our job is not just to program the robot, but to do so using a rule- and agent-based artificial intelligence.
  • Rule-based is basically a programming approach such as imperative or functional. It means to define a program in terms of condition-reaction pairs. It is supported by a framework which checks the conditions and execites the appropriate actions. While this might not seem spectacular, think about it: have you ever written or seen a program using this approach? Note that this is not another name for an event system; events also result in a reaction, but they only allow for reactions on one-time events (if some event happens), not to states (if some condition holds).
    Rule-based systems are good for modelling intelligent behavior. A human reacts to events because of the state-changes they cause, not the events themselves: If a window falls open, you close it because it's cold or loud outside, not because the window has opened.
  • Agent is just another word for actor. Remember how I wrote about the downloader; it's essentially the same. The only difference is that all this is now integrated into a rule system, which also changes the way how the agents exchange messages. Besides that, the concept of parallel processing stays. In our case, the focus lies on the independence of the actors to cooperatively reach a solution for a problem, and not on simpler multithreading by getting away from traditional synchronization.
  • Artificial intelligence always sounds good, but what does it really mean? Our parent project at TU Wien has a very specific goal: To build cooperative robots capable of disassembling Lego models. We won't get anywhere near disassembly, but the cooperation is still there, just in the software though. In the end, an artificial intelligence is always task-oriented, and the border where intelligence begins is not well-defined. The question is very interesting, but more philosiphical than technical, so maybe in a later post.
...to attend a robot competition in the USA
This is a goal we all really want to reach, but if we do will depend on how we perform. Our project is definitely complex, so if it doesn't work out too well, we won't go. I'm positive about it, though.
The competition we would attend is BotBall, organized by the KISS Institute of Practical Robotics, and we have the honor to be invited directly to the final "Global Conference of Educational Robotics", without attending any of the qualification tournaments. (I hope you can read from all this how proud I am^^)

So the last point to check for today is: This is definitely good news for me, but how is it for you? Well, I'll write about it, of course. Some things might be off-topic in terms of Magic, but artificial intelligence is definitely in, right? Be sure to check back in a few weeks, there are definitely interesting things to come!

Wednesday, September 8, 2010

Static and triggered abilities

Laterna Magica already supports some core functionalities of Magic, but there's still much left. I don't talk about discard and such things; these are effects that just need to be coded, and then they will be there; just a new flavor of an existing thing. I also don't talk about very complicated effects. All cards currently supported in Laterna Magica use the original oracle wording (with the exception that "draw three cards" must be changed into "draw 3 cards"), which won't be possible for all abilities, but such abilities are still not what I'm talking about.

I'm thinking about really new features, like static and triggered abilities, the ability to target, or text changing effects.
Text changing effects are just very hard; they kind of break my concept of "one template, many instances" for abilities: The printed wording can be shared between cards, just its interpretation, the rules meaning, is card-specific.
Targets are currently not my goal; I don't really want to do much UI at the moment, and this in inevitable with giving the player yet another possibility to make a choice.

That neatly leaves behind the two thing I already stated in the title, and they have one thing in common which currently gives me a headache: Scope of influence.

The scope of an ability means in what places and at what times it works. For spells and activated abilities it's comparable to legality, but the big difference is that the user initiates those abilities; static and triggered abilities are around at all times.

There are two ways to handle the situation:
  • keep all abilities at all times and ask them if they should apply on every single occasion
  • let the abilities themselves handle it; registering and unregistering using some events
I don't know why, but my initial though was to use the second. Both have good and bad points of course: The first can result in a performance problem, the second might break in strange corner cases.
A more obvious, but still realistic example is controller changes: Imagine you get control of a Glorious Anthem, but it still pumps your opponent's creatures.
But even the first approach has similar issues, namely abilities that didn't exist at the beginning of the game, for example on tokens or from Auras. If you register all abilities at the beginning of the game, those would be ignored.

If you expected a definitive solution here, I'm sorry. I don't have one. There's no right way to do anything, just several ways with different consequences.

Monday, September 6, 2010

Update

I was kindly brought to a windows incompatibility in my program, so I fixed this. Along with it came an update of the installation, which should make it much easier to update to future versions.

You can see the result here.

Saturday, September 4, 2010

First release!

This is only a short post, but one that makes me proud nonetheless.

This is the day where I put the first release version online. Don't expect too much; the basic rules including combat works, but there are currently nearly only vanilla creatures. Anyway, if you want to try it, or at least see what's there exactly, go to the forums and download it.

Tuesday, August 31, 2010

When you feel plainly dumb...

There are time when you work on a problem and nothing seems to help. You have checked everything, yet nothing works. And then you see the obvious answer. I had such a problem today. Until now, Laterna Magica only allowed you to pay costs in advance, first adding all the mana to the pool, then activating an ability or (more likely in LM) casting a spell.

The rules allow it, however, to play mana abilities while playing spells/abilities. So I wrote the code: A piece in the cost to ask the player for input, a piece in the player to handle the GUI. and it didn't work. Clicking on a card was just not recognized.

I first thought it could be that my legality checking code was not working while a spell is being cast, but I couldn't find any line in the code that even bothered about that. Next, I suspected that the asynchronous communication between game and GUI didn't work, and enabled a few debug statements, which in turn made clear that everything went like desired. So I thought to myself: where could I easily check if the action was successfully processed? Well, in the cost, where the player was asked in the first place.

But I never got to writing a debug statement; the bug was clear and simple: While I retrieved the activate action, I didn't execute it. These are the times when you feel plainly dumb...

Saturday, August 28, 2010

New Downloader

Besides working on combat, I played a little more with Jetlang and created a downloader, which works asynchronously and can inform interested listeners over PropertyChangeEvents.
Jetlang's concurrency approach is centered around the actors (who performs a task/where is it performed) and the tasks instead of around the data. Normal multithreading requires you to synchronize on the data you share, while an Actor framework doesn't share data but pass it around, so that only one thread "has" it at a time.
This makes it easier to code, because it is how humans think: You don't worry that two people will write on the same piece of paper at the same time; you wait until the piece of paper is passed to you. That said, it still needs a lot of thinking: Who are the people in your program, what's the piece of paper, and when should you pass it around?

Btw, I made a little comparison between the new downloader and the one used by forge (admittedly, in which I also had a great part).

Program           After 2 minutes  For 1500 images
Laterna Magica    1500 images       2:00 minutes
Forge              200 images      10:00 minutes

I looked at the code for Forge and checked if it is roughly comparable to mine, and it was; otherwise I wouldn't have posted this. I changed two things, however: I increased the buffer size to 8 kB to match Laterna Magica, and I removed a print statement. These are pretty slow and shouldn't be there when measuring time.

Laterna Magica's downloader uses 10 threads, which means that 10 pictures are downloaded at the same time. Even though it might seem at first that it shouldn't make much of a difference, because the total bandwidth stays the same, the numbers clearly say that download speed is five times better. The reason for that is the reduced overhead. Every picture needs the following steps to be done:
  1. Connect to the server
  2. Request the image
  3. Receive the data, store it into a file
The time is lost between step 2 and 3. The first two steps has you upload data (the request), the third has you download data. Between that is only waiting. When using only a single thread, this waiting directly influences the download speed, because nothing else happens in that time. Using multiple threads, waiting only blocks one of the threads, leaving 9 downloads running in the meantime.

Besides downloading card pictures, I adapted Laterna Editor to use the new downloader, which also shown its flexibility: Laterna Editor downloads HTML pages from Gatherer, but doesn't save them to files. Instead, it further processes them to compact card descriptions for Laterna Magica. While it took a little work, the downloader is not limited to Files but can download to any location, such as a string buffer in memory.

The card downloader from Laterna Editor also shows how the task-centric approach helps with programming. This picture pretty much describes how the download process works:


Both Source and Destination are classes implemented by CardDownloader, but implement interfaces specified by Downloader. The source checks if the URL is a search or a single card, and also handles the automatic redirect if Gatherer only finds a single card for a search. The destination saves the HTML page to a string and waits for the download to finish, by registering a property change listener to the download job. If the download was successful, it sends the page to the search- or card processor, depending on the source. If it wasn't, it just discards the downloaded page.
The search processor finds additional result pages (every page has at most 100 cards in the compact view, which is used by the downloader) and of course the individual cards. The download of those is again done by the same process. The search processor simply posts the DownloadJob to the downloader and that's it.
The card processor finds the individual fields like name and mana cost, and stores them into a card. Once that's done, it posts the card to a Channel where the Gui can find it and in turn show the editor.

Monday, August 23, 2010

Combat and concurrency

It was on July 15th when I titled a blog post "Combat in sight?", but now it really is. Today, I committed a version to my project where players can attack and thus deal damage. Blocking is not possible yet, but that's more a matter of work and not of thinking. Players still can't loose the game, but that's another story...

Now, for those of you not familiar with "concurrency" in programming, it means when multiple parts of a program run at the same time, "competing for the computer's resources" like CPU or RAM. Concurrency is hard for three reasons:
  • you have to control what happens when, because the classical "everything happens in a fixed sequence" is not true
  • speaking of "competing for resources", when two concurrent threads of execution access the same data, they can overwrite each other, messing things up
  • for this reason, locks and synchronizing have come up, which grant exclusive access to a resource to a single thread. This also means that threads have to wait for resources until they aren't locked any more. In the worst case, two threads can wait for each other.
Laterna Magica uses an approach that has two main threads; one for the game, and one for the user interface. While the UI thread is mandated by Java, I could have implemented LM to run on the same thread. The main reason I did not was to make LM independent of the GUI, meaning that the program can use different UIs and even run without a User Interface, say in a Computer-vs-Computer simulation or on a server (while the latter needs more preparation, I believe it will be possible someday).

So there are two threads, which means every GUI interaction means synchronization. The first GUI interaction implemented was playing cards and activating abilities. The code to enable that was pretty wordy and hardly extensible:


private boolean    ready;
private PlayAction a;

public GuiActor(Player player) {
    super(player);
} 
 
public synchronized void putAction(PlayAction a) {
    ready = true;
    this.a = a;
    notifyAll();
}

public synchronized PlayAction getAction() {
    ready = false;
    while(!ready)
        try {
            wait();
        } catch(InterruptedException ex) {
            ex.printStackTrace();
        }
    return a;
}

On the surface, it doesn't look that bad, but it has several issues:
  • It is low-level: It handles all the synchronization stuff itself, as seen by boolean ready, notifyAll(), synchronized, while(!ready) ... This is all stuff that has to be repeated for every sort of user input: declare attacker, blocker, ...
  • It moves control away from the actor: putAction takes a PlayAction, which is the result of e.g. clicking on a card. How that click is associated to the PlayAction is not controlled by the actor which violates atomicity
    • Translating click to PlayAction is specific to playing spells and not compatible with e.g. declaring attackers. This means that the translation, which is not atomic, has to be performed for every type of input
  • Missing Encapsulation: The interpretation as a PlayAction is only valid when the player has priority, and this fact is not represented here: There is no representation of the fact whether the Actor is waiting for a PlayAction or for declaring an attacker
On the opposite, here is the new variant:

public class GuiMagicActor extends AbstractMagicActor {
    public final GuiChannels    channels = new GuiChannels();
   

    private static T getValue(Fiber f, Channel ch, GuiActor a) {
        a.start();
        log.debug("Waiting for result...");
        T result = Parallel.getValue(f, ch);
        log.debug("received!");
        a.dispose();
        return result;
    }
   
    public PlayAction getAction() {
        return getValue(channels.fiber, channels.actions, new ActionActor(this));
    }

    
    ...
}

This new version is based on the Jetlang concurrency framework, which works using channels and callbacks: Messages published to a channel are - asynchronously - forwarded to registered callbacks, which may then in turn publish new messages. The Parallel.getValue() method is used to get a value back from the channel synchonously, and the ActionActor encapsulates the state, in this case choosing a PlayAction to perform:

public class GuiChannels {
    /**
     * Channel for receiving {@link PlayAction}s to execute when the player has priority
     */
    public final Channel  actions      = new MemoryChannel();
   
    /**
     * Channel for publishing {@link MagicObject}s when the user clicks on them
     */
    public final Channel objects      = new MemoryChannel();
   
    /**
     * Channel for publishing {@link Player}s when the user clicks on them
     */
    public final Channel      players      = new MemoryChannel();
   
    /**
     * Channel for publishing when the user clicks "pass priority"
     */
    public final Channel        passPriority = new MemoryChannel();
   
    public final Fiber                fiber;
   
    public GuiChannels() {
        PoolFiberFactory f = new PoolFiberFactory(Executors.newCachedThreadPool());
        fiber = start(f.create());
    }
   
    private Fiber start(Fiber f) {
        f.start();
        return f;
    }
}


public class ActionActor extends GuiActor {
    public ActionActor(GuiMagicActor actor) {
        super(actor);
    }
   
    @Override
    public void start() {
        disposables.add(actor.channels.objects.subscribe(actor.channels.fiber, new CardCallback()));
        disposables.add(actor.channels.passPriority.subscribe(actor.channels.fiber, new PassPriorityCallback()));
    }
   
    private class CardCallback implements Callback {
        @Override
        public void onMessage(MagicObject c) {
            log.debug("Received: " + c);
            PlayAction a = GuiUtil.getActionOptional(actor.getPlayer(), c);
            if(a != null) actor.channels.actions.publish(a);
        }
    }
   
    private class PassPriorityCallback implements Callback {
        @Override
        public void onMessage(Void v) {
            log.debug("Received pass priority");
            actor.channels.actions.publish(null);
        }
    }
}
 

The ActionActor receives Messages through the objects and passPriority channels and reacts specific to its task.

Hope you liked it!

    Saturday, August 21, 2010

    Scala: Functional programming & DSL

    I first learned about Scala in forge's comment to this post, and the tutorial he mentioned is really great. Just for experimenting, I extended the Calculator example for Variables, Functions and exponentiation. The result is really extensible and took me just 140 lines of code, which really impressed me. So I'm showing you the result:

    AST.scala (Scala doesn't require Files to represent the class names, and AST (abstract syntax tree) fits the classes in this file)
    package net.slightlymagic.calc {
      abstract class Expr
      case class Variable(name: String) extends Expr {
        override def toString = name
      }
      case class Number(value: Double) extends Expr {
        override def toString = "" + value
      }
      case class UnaryOp(name: String, arg: Expr) extends Expr {
        override def toString = name + arg
      }
      case class BinaryOp(name: String, left: Expr, right: Expr) extends Expr {
        override def toString = "(" + left + name + right + ")"
      }
      case class Function(name: String, args: List[Expr]) extends Expr {
        override def toString = name + args.mkString("(", ", ", ")")
      }
    }


    Calc.scala

    package net.slightlymagic.calc {
      object Calc {
        def simplify(e: Expr): Expr = {
          def simpArgs(e: Expr) = e match {
            case BinaryOp(op, left, right) => BinaryOp(op, simplify(left), simplify(right))
            case UnaryOp(op, operand) => UnaryOp(op, simplify(operand))
            case Function(op, operands) => Function(op, operands.map((x) => simplify(x)))
            case x => x
          }
         
          def simpTop(e: Expr) = e match {
            case UnaryOp("-", UnaryOp("-", x)) => x
            case BinaryOp("-", x, Number(0)) => x
            case BinaryOp("-", Number(0), x) => UnaryOp("-", x)
            case BinaryOp("-", x1, x2) if x1 == x2 => Number(0)
           
            case UnaryOp("+", x) => x
            case BinaryOp("+", x, Number(0)) => x
            case BinaryOp("+", Number(0), x) => x
           
            case BinaryOp("*", x, Number(1)) => x
            case BinaryOp("*", Number(1), x) => x
           
            case BinaryOp("*", x, Number(0)) => Number(0)
            case BinaryOp("*", Number(0), x) => Number(0)
           
            case BinaryOp("/", x, Number(1)) => x
            case BinaryOp("/", x1, x2) if x1 == x2 => Number(1)
           
            case BinaryOp("^", x, Number(1)) => x
            case BinaryOp("^", x, Number(0)) if x != Number(0) => Number(1)
            case BinaryOp("^", x1, UnaryOp("-", x2)) => BinaryOp("/", Number(1), BinaryOp("^", x1, x2))
            case e => e
          }
         
          simpTop(simpArgs(e))
        }
       
        def evaluate(expr: Expr, variables: Map[String, Double], functions: Map[String, (List[Double]) => Double]): Double = {
          expr match {
            case Number(x) => x
            case UnaryOp("-", x) => -evaluate(x, variables, functions)
            case BinaryOp("+", x1, x2) => evaluate(x1, variables, functions) + evaluate(x2, variables, functions)
            case BinaryOp("-", x1, x2) => evaluate(x1, variables, functions) - evaluate(x2, variables, functions)
            case BinaryOp("*", x1, x2) => evaluate(x1, variables, functions) * evaluate(x2, variables, functions)
            case BinaryOp("/", x1, x2) => evaluate(x1, variables, functions) / evaluate(x2, variables, functions)
            case BinaryOp("^", x1, x2) => Math.pow(evaluate(x1, variables, functions), evaluate(x2, variables, functions))
            case Variable(x) => variables(x)
            case Function(x, args) => functions(x)(args.map((x) => evaluate(x, variables, functions)))
          }
        }
       
        def parse(text : String) = CalcParser.parse(text).get
       
        val standardVars =
          Map(
            "E"  -> Math.E,
            "Pi" -> Math.Pi
          )
       
        val standardFuns =
          Map(
            "sin"  -> {x:List[Double] => Math.sin(x(0))},
            "cos"  -> {x:List[Double] => Math.cos(x(0))},
            "tan"  -> {x:List[Double] => Math.tan(x(0))},
            "cot"  -> {x:List[Double] => 1/Math.tan(x(0))},
            "asin" -> {x:List[Double] => Math.asin(x(0))},
            "acos" -> {x:List[Double] => Math.acos(x(0))},
            "atan" -> {x:List[Double] => Math.atan(x(0))},
            "acot" -> {x:List[Double] => Math.atan(1/x(0))},
            "exp"  -> {x:List[Double] => Math.exp(x(0))},
            "log"  -> {x:List[Double] => Math.log(x(0))},
            "min"  -> {x:List[Double] => Math.min(x(0), x(1))},
            "max"  -> {x:List[Double] => Math.max(x(0), x(1))}
          )
       
        def evaluate(expr: String, variables: Map[String, Double], functions: Map[String, (List[Double]) => Double]): Double = {
          evaluate(
            simplify(parse(expr)),
            if(variables == null) standardVars else standardVars ++ variables,
            if(functions == null) standardFuns else standardFuns ++ functions
          )
        }
       
       
        import scala.util.parsing.combinator._
       
        object CalcParser extends JavaTokenParsers {
         
          def expr: Parser[Expr] =
            (term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |
            (term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |
            term
     
          def term: Parser[Expr] =
            (factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) } |
            (factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) } |
            factor
     
          def factor : Parser[Expr] =
            (exp ~ "^" ~ exp) ^^ { case lhs~exp~rhs => BinaryOp("^", lhs, rhs) } |
            exp
     
          def exp : Parser[Expr] =
            ("+" ~ expr) ^^ { case plus~rhs => UnaryOp("+", rhs) } |
            ("-" ~ expr) ^^ { case minus~rhs => UnaryOp("-", rhs) } |
            "(" ~> expr <~ ")" |
            ident ~ params ^^ {case name~params => Function(name, params)} |
            ident ^^ {case name => Variable(name)} |
            floatingPointNumber ^^ {x => Number(x.toFloat) }
         
          def params : Parser[List[Expr]] =
            "(" ~> repsep(expr, ",") <~ ")"
         
          def parse(text : String) = parseAll(expr, text)
        }
      }
    }


    Wow! I don't want to repeat the tutorial, which is really great, but I want to mention a few features that really improved the way this code is written.

    First of all, Scala is a mixture of functional and object oriented: Map[String, (List[Double]) => Double] (Scala uses square brackets for generic types) means a Map of Strings and Functions, which take a list of Doubles as a parameter and yields a Double as the result. To get the same result as standardFuns in the Calc object... Yes, object. This basically means that all members are static. On the opposite, normal classes can't have static members, which doesn't really matter because you can have class and object of the same name. To get the same result as standardFuns using Java, you'd have to define a common interface and several anonymous classes, which means a lot of duplication. Using anonymous functions and the fact that a function can be passed as a parameter, something you don't get from nonfuntional languages, you avoid most of the redundant code. No interface definition, just a single line per anonymous function.

    The second thing that you can write method calls in an "unusual way": a.plus(b) is the same as a plus b. Together with the fact that you can name methods, e.g. "+", you basically have overriding operators. This means not much more than you can write short, concise code. But that is very important; just look at the preceding paragraph. The parser package of Scala uses such "Operators" to write short, expressive text parsing code.

    Lastly, pattern matching. This is a great feature that is really hard to imitate using Java. It uses case classes, as seen in AST.scala, and the match/case construct. For example:

    expr match {
      case BinaryOp(x1, op, x2) => doSomething()
      case BinaryOp(Number(x1), "+", Number(x2) => doSomethingElse()
    }

    doSomething() is only executed if the case matches, and at the same time assigns the three variables x1, op, x2. You can build more complex constructs, as the second example shows, including nesting Objects and using constant expressions to narrow down matching cases. This works as long as you use case classes.

    And now comes another important part: Scala compiles to Java byte code, which means that you can code a part in scala. For example, the simple Calculator DSL was way easier to write in Scala than it would be in Java. Once it's packed as a jar, you don't even notice that the code was not written in traditional Java, and integrates nicely into the other parts. (Except you'd have a hard time to call "operator methods" or use API that uses Functions as parameters. Consider that for your public, plain-old-java accessible API)
    The only downside is that Eclipse integration is not great so far. Maven does a good task in still compiling your Scala code, but the Scala plugin is not very stable, so I use the plain text editor. It works for small things like the Calculator, but I miss obvious features like import organizing, content assist, automatic building on every change, syntax & error highlighting, parentheses matching, folding...

    Thursday, August 19, 2010

    Performance of Software

    I was reading a little about scala these days and think that it's a cool language that would probably make my life a lot easier. For example, the CardCompiler is hard to use; you have to go through a few hoops to implement new effect parsers. I think that I am on the right way, but there is much room for improvement in terms of usability.

    But today I don't want to talk about Scala, but software performance. One point with Scala is that it largely uses immutable objects, putting copying over mutating existing objects. The first thought when you hear this is probably how much memory this would waste and that it will also need more processing power all the data has to be copied.

    However, performance doesn't mean to use as little resources as possible. It means to use the resources you have the best possible. And nowadays, the resource we have but use the least are multiple processors.

    Modern processors work on the edge of physical possibilities. Circuits are not thicker than a few atoms, and currencies are so small that you can almost measure the number of electrons flowing. At this scale, quantum effects matter, and this means randomness. That's about the reason why (semiconductor) processors don't get faster any more and increasing speed does only occur by parralelism.

    Writing software that works parallel, however, is hard, because multiple threads can access the same resource at the same time and thus wreak havoc. Which leads back to immutable objects: Data corruption can only occur when writing. when every access is read-only or creates a copy, nothing bad can happen.

    This leaves one question: How bad is copying really? Well, every copy you don't need any more can be garbage collected, so memory should not really be a concern. Memory size is also not as restricted as processor speed, so there should be enough potential to support memory-heavy rather than processor-heavy software.
    Garbage collection itself, however, uses the processor. It finds objects that are no longer accessed by any thread; that means that it is not constrained to work in the program's normal flow and can work in its own thread. As the garbage collector is not really interested in the objects, it can even be spread to multiple threads if necessary.

    Copying itself uses processing power, and can take some time for large objects. Usually, the only type of large objects are arrays. There are really not many possibilities: boolean, byte, short, char, int, float, long, double, Object. All these take up to 8 bytes to store. All that stays are the indexes of arrays, which can go into several millions. If we stay with immutable objects, this is really the only bottleneck we have to deal with, because you don't need to copy the array's content objects, as they can't change.

    I guess this wasn't all that interesting to read, but I really wanted to speak this out: parallelism is the future of software, parallelism is hard, so any attempt to make it easier, for example by using immutable objects, is a step into the right direction

    Monday, August 16, 2010

    To URI or not to URI

    I'm not an English native speaker, so don't blame me if this Shakespeare reference is not recognizable. Maybe "URI or not URI" would fit better for pronunciation...

    Anyway, I'll brighten up the situation for anyone who doesn't know URIs: "URI" stands for Uniform Resource Identifier, and the "not to URI" part of the title refers to "URL", Uniform Resource Locator. Seriously, I don't know what the difference between them is supposed to be, just that they behave pretty differently in Java.
    (And for anyone who thinks, "Well, so you do know the difference?" No, the Java classes are an implementation of a specification that I don't understand, and not even really know. I know, however, how the implementation behaves. If this behavior follows the original specification, which was not made for the Java language but presumably for the internet, I don't know.)

    So, from my point of view, both URIs and URLs are meant to identify some sort of resource, like a network drive of some web site.
    • In Java, you can directly connect to a URL and read from and write to it. You can't do that for a URI, but you can convert between both forms (if the resource is legal in both representations).
    • The equals() and hashCode() methods of URL perform a name space lookup, making them very slow. URLs are therefore poor choices for map keys, for example for caching downloaded files.
    So, it seems like a tied match. The first one is "obvious", you can see it in the API that URI can't directly open connections. equals() and hashCode() being slow is so subtle that there is an entry in FindBugs, an Eclipse plugin that helps to find common programming mistakes, which is how I learned about it.

    The third difference I've experienced so far is very subtle and unexpected, and it is the real reason for this post. wow, about time to get to the point...

    You can represent a file inside a Jar (or Zip) archive using a URL or URI; both work. You can also "resolve" a relative URL/URI against another one to get an absolute one. But the combination of both only works with URL!

    jar:file:/path/to/archive.jar!/path/inside/archive/
    jar:file:/path/to/archive.jar!/path/inside/archive.txt

    are both legitimate URIs/URLs. Say, you want to resolve "hello.txt" against these, you expect:

    jar:file:/path/to/archive.jar!/path/inside/archive/hello.txt
    jar:file:/path/to/archive.jar!/path/inside/hello.txt

    however, this works only with URLs. A URI won't be able to resolve and will just return "hello.txt"

    I said that I recently reimplemented TreeProperties, and I did it based on URIs. As you might guess, resolving paths relative to some context is pretty important for a tree structure. Finding the bug was very annoying, because reading from a Jar file, or even multiple Jar files, is not something I have years of experience with. Fixing the bug was way easier once I sorted out its origin.

    I'd like to end this post with another Shakespeare quote:

    "But none come to mind. I hope I have at least fooled you with the quotation marks. Just be aware or the differences between Uniform Resource Locators and Identifiers"

    Friday, August 13, 2010

    Migrating to Maven

    This week, I've finally done what I wanted to do for a very long time: I migrated my project to Maven. Warning: Non-programmers will probably be hopelessly bored.

    Maven is a build system with many capabilities that are probably beyond my current recognition. For me, it means essentially these things:
    • Managing dependencies to external libraries, such as Dom4J, an XML API, and also to the different projects that belong to LaternaMagica, like TreeProperties.
      • For an Open Source project, this also means that I don't have to care that others have all the required libraries, because they can find and download them on-demand. Having the right configurations in the development environment is not that important this way. As a downside, it makes Maven pretty much a requirement for working with my code, but that's just like English is required to read my blog: it's good to know English, no matter what.
    • Automatic testing and generation of source, binary and documentation archives, or "snapshots"
    I said I wanted to do this for a long time. If you're asking why I haven't done it earlier... well, I was dumb. I couldn't get my Eclipse installation working with the Maven plugin. The problem was... that my eclipse installation was owned by root (the administrator, for all the poor Windows users out there^^) and installing the plugin simply didn't do anything as I didn't have the rights.

    So finally, everything is alright. I have totally rewritten TreeProperties and Utils, and also greatly reworked LaternaDoc, which finally does what it should. More on those another time ;)

    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:
    • What values are "relevant"?
    • What is "long enough"?
    An this is where Undo steps in! Why store the values separately when we can travel back in time and look at the original ones? with that approach, there is no chance that we need a value that was not saved - because we look at the original.
    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.

    Tuesday, August 3, 2010

    Simultaneity: Warp World

    The first time I mentioned simultaneity is with combat. It was just a coincidence that this was the first time, but it is very reasonable, because simultaneity happens very often during combat: Technically, creatures become attacking creatures simultaneously, then the same happens with blockers, damage etc.

    Simultaneity means multiple things, and I'm not sure if I have a full understanding of these. I'll take the example of Warp World, which is a classic example for discussing timing:

    Each player shuffles all permanents he or she owns into his or her library, then reveals that many cards from the top of his or her library. Each player puts all artifact, creature, and land cards revealed this way onto the battlefield, then does the same for enchantment cards, then puts all cards revealed this way that weren't put onto the battlefield on the bottom of his or her library.

    First, all permanents are shuffled into their respective owner's library, triggering from leaving play. All these abilities see all the cards leaving play, meaning that an ability like "leaves the battlefield" sees all the permanents. There is no variant where that ability leaves early and isn't active when the permanents leave play.

    The "then"s in the card's text neatly separate the parts that happen simultaneously. All "enters the battlefield" abilities of cards trigger for cards that enter the battlefield at the same time as them; it seems like the abilities are active just a little earlier than they are in play... it's a little awkward in my opinion.

    now hold on - Auras with "Enchant Enchantment" won't make it on the battlefield, because Enchant is not a triggered ability. The Comprehensive rules don't specify a wording for Enchant but rather give it extra rules. It feels, however, like a replacement effect, just like "As ... enters the battlefield" (which don't use the stack at all - they are effects generated by static abilities).

    Lands with additional costs, like the painlands, are worded like this, because if it was a triggered ability, you could play the mana ability in response to the cost. So, just like "Enchant Enchantment" enchantments (^^) don't make it, lands like "As ... comes into play, return a land you control to your hand. If you don't, put ... into your graveyard instead." won't, too. Champion, however, is a triggered ability, so your champions can survive. you can even enchant the creatures you wish to exile, because the triggered abilities won't resolve or even be put onto the stack until Warp World finished resolving.


    One last thing: after resolving the spells, all the abilities are put onto the stack, in an order depending on player seating and player choice. you can put abilities from entering the battlefield on the stack earlier that those from leaving the battlefield, even though these happened in another sequence...

    Friday, July 30, 2010

    Damage

    I just re-read my post about destruction and realised I should show what it took me to implement damage. This might not be my most interesting post, as it is just code, but maybe some of you are interested. Get ready... there are about 200 lines of code coming for you!


    public abstract class DamageEvent extends ReplaceableEvent {
        private MagicObject source;
        private int         ammount;
        private boolean     combat, preventable;
        
        public DamageEvent(MagicObject affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
            this(you(ofInstance(affected)), source, ammount, combat, preventable);
        }
        
        public DamageEvent(Player affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
            this(ofInstance(affected), source, ammount, combat, preventable);
        }
        
        public DamageEvent(Supplier affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
            super(affected);
            this.source = source;
            this.ammount = ammount;
            this.combat = combat;
            this.preventable = preventable;
        }
        
        public MagicObject getSource() {
            return source;
        }
        
        /**
         * This method can be used by replacement effects that prevent or increase damage.
         */
        public void setAmmount(int ammount) {
            this.ammount = ammount;
        }
        
        public int getAmmount() {
            return ammount;
        }
        
        public boolean isCombatDamage() {
            return combat;
        }
        
        public boolean isPreventable() {
            return preventable;
        }
    }



    public class DamagePlayerEvent extends DamageEvent {
        private Player p;
        
        public DamagePlayerEvent(Player p, MagicObject source, int ammount, boolean combat, boolean preventable) {
            super(p, source, ammount, combat, preventable);
            this.p = p;
        }
        
        public Player getPlayer() {
            return p;
        }
        
        @Override
        protected boolean execute0() {
            CompoundEdit ed = new CompoundEdit(getGame(), true, "Deal damage");
            
            //118.3a. Damage dealt to a player causes that player to lose that much life.
            getPlayer().getLifeTotal().loseLife(getAmmount());
            
            ed.end();
            
            return true;
        }
    }



    public class DamagePermanentEvent extends DamageEvent {
        private static final Predicate legalAffected  = and(isIn(ofInstance(BATTLEFIELD)),
                                                                           card(or(CREATURE, PLANESWALKER)));
        
        private static final Predicate isPlaneswalker = card(has(PLANESWALKER));
        //TODO implement wither and lifelink
        private static final Predicate hasWither      = alwaysFalse();
        private static final Predicate hasLifelink    = alwaysFalse();
        
        private CardObject                          permanent;
        
        public DamagePermanentEvent(CardObject affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
            super(affected, source, ammount, combat, preventable);
            if(!legalAffected.apply(affected)) throw new IllegalArgumentException(
                    "affected must be a creature or planeswalker permanent: " + affected);
            permanent = affected;
        }
        
        public CardObject getPermanent() {
            return permanent;
        }
        
        @Override
        protected boolean execute0() {
            CompoundEdit ed = new CompoundEdit(getGame(), true, "Deal damage");
            
            //118.3b. Damage dealt to a planeswalker causes that many loyalty counters to be removed from that
            // planeswalker.
            if(isPlaneswalker.apply(getPermanent())) {
                //TODO remove counters
            }
            //118.3c. Damage dealt to a creature by a source with wither causes that many -1/-1 counters to be put on
            // that creature.
            else if(hasWither.apply(getSource())) {
                //TODO add counters
            }
            //118.3d. Damage dealt to a creature by a source without wither causes that much damage to be marked on
            // that creature.
            else {
                getPermanent().setMarkedDamage(getPermanent().getMarkedDamage() + getAmmount());
            }
            //118.3e. Damage dealt to an object or player by a source with lifelink causes that source's controller to
            // gain that much life, in addition to the damage's other results.
            if(hasLifelink.apply(getSource())) {
                getSource().getController().getLifeTotal().gainLife(getAmmount());
            }
            
            ed.end();
            
            return true;
        }
    }


    I don't really like this code, because it has the effects of damage hard coded, but I think it's fine for now. extracting these effects later if it's necessary shouldn't be too hard, as the different effects of damage will only be mentioned here, so I can safely delay this task.

    Friday, July 23, 2010

    Trying out the card editor

    I just tried out my card editor to download "a few" cards; all the vanilla creatures and old (non-pain) dual lands. If I haven't done anything wrong in my gatherer search, there are 177 vanilla creatures. it's in fact not so easy to search for textless cards; I had to use the regular expressing "m/^$/" ("m/.../" is the gatherer identifier for regexes, "^$" essentially means "the beginning of the text immediately followed by the end")

    by the way, I haven't done a full fledged form for gatherer searches; I did the search on the web site and pasted the search URL into my program. takes me much less time^^


    there were two problems: first, my download just discontinued after 89 cards. Looking at what card that was, it was Little Girl from Unhinged with a half mana symbol. Second, even after refining my search to exclude Un-cards, my program only wound up downloading 100 cards. my workaround for that problem was simply to download the other cards by reverting the sort order^^



    so, putting things short, I now have over 200 cards implemented, including 177 vanilla creatures, 10 classic dual lands, 10 SHM/EVE dual lands, 5 basic lands, Wrath of God, Damnation and Llanowar Elves. It's really time for combat^^

    Thursday, July 22, 2010

    Event Handling

    If you recall what I wrote a long time ago about challenges in programming, event handling would be one of the easy, boring parts. The point of event handling is to inform parts of your program when something happens in another part. This is espacially important for the user interface, as you always want to see what's currently going on, but in the context of Magic, there is another very important reason for event handling: Triggered abilities.

    If you now think that the User Interface and Triggered abilities can share the event handling system, therefore effectively reducing the ammount of programming needed for each of them, I fear you'll be disappointed. The reason for this is the undo system. While it enables things like handling illegal actions, the most direct interpretation of what it does prevents me from sharing one event system: Undo means that every action and event can happen in two directions in time.
    When you attack with a creature, it becomes tapped. An ability could trigger from that tapping. If you now determine that the creature isn't allowed to attack, everything's undone and the creature is untapped again. You want to see the creature untapped in the user interface, but you don't want abilities trigger from it untapping.

    Of course the event handling functions after the same principle, but the events are duplicated - in some sense. There's no real 1:1 mapping between GUI and game events, because the GUI is satisfied by state-changes, while the game needs more high level events: The gui doesn't care if you've drawn a card or just put it into your hand. It just needs to know that your library has become smaller and your hand grew larger.

    Fortunately, Java has some built in functionality for handling these low-level events, namely PropertyChangeSupport. It allows you to keep track of properties and notify the listeners whenever a change occurs. Well, you still have to call the listeners on a change, but the major work, managing all the listeners and what properties they are interested in, is done for you.
    Along with adding PropertyChangeSupport to Laterna Magica, I have restructured a lot of code. Previously, every class implemented undo support for its properties itself. This is now separated into an extra class, which also allows to use PropertyChangeSupport more easily:

    public class EditableProperty extends AbstractGameContent {
        private EditablePropertyChangeSupport s;
        private String                        name;
        private T                             value;
       
        public EditableProperty(Game game, EditablePropertyChangeSupport s, String name) {
            this(game, s, name, null);
        }
       
        public EditableProperty(Game game, EditablePropertyChangeSupport s, String name, T initialValue) {
            super(game);
            this.s = s;
            this.name = name;
            value = initialValue;
        }
       
        public void setValue(T value) {
            new SetValueEdit(value).execute();
        }
       
        public T getValue() {
            return value;
        }
       
        @Override
        public String toString() {
            return valueOf(getValue());
        }
       
        private class SetValueEdit extends Edit {
            private static final long serialVersionUID = 93955529563844615L;
           
            private T                 oldValue, newValue;
           
            public SetValueEdit(T newValue) {
                super(EditableProperty.this.getGame());
                this.newValue = newValue;
            }
           
            @Override
            protected void execute() {
                oldValue = value;
                value = newValue;
                if(s != null) s.firePropertyChange(name, oldValue, newValue);
            }
           
            @Override
            protected void rollback() {
                value = oldValue;
                if(s != null) s.firePropertyChange(name, newValue, oldValue);
            }
           
            @Override
            public String toString() {
                return "Set " + s.getSourceBean() + "'s " + name + " to " + newValue;
            }
        }
    }